UVa 10050 - Hartals
1 题目
===================
Problem D: Hartals
| Problem D: Hartals |
A social research organization has determined a simple set of parameters to simulate the behavior of the political parties of our country. One of the parameters is a positive integer h (called
the hartal parameter) that denotes the average number of days between two successivehartals (strikes)
called by the corresponding party. Though the parameter is far too simple to be flawless, it can still be used to forecast the damages caused by hartals.
The following example will give you a clear idea:
Consider three political parties. Assume h1 = 3, h2 = 4 and h3 = 8 where hi is the hartal parameter for party i ( i = 1, 2, 3). Now, we will
simulate the behavior of these three parties for N = 14 days. One must always start the simulation on a Sunday and assume that there will be no hartals on weekly holidays (on Fridays and Saturdays).
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | |
| Days | ||||||||||||||
| Su | Mo | Tu | We | Th | Fr | Sa | Su | Mo | Tu | We | Th | Fr | Sa | |
| Party 1 | x | x | x | x | ||||||||||
| Party 2 | x | x | x | |||||||||||
| Party 3 | x | |||||||||||||
| Hartals | 1 | 2 | 3 | 4 | 5 |
The simulation above shows that there will be exactly 5 hartals (on days 3, 4, 8, 9 and 12) in 14 days. There will be no hartal on day 6 since it is a Friday. Hence we lose 5 working days in 2 weeks.
In this problem, given the hartal parameters for several political parties and the value of N, your job is to determine the number of working days we lose in those N days.
Input
The first line of the input consists of a single integer T giving the number of test cases to follow.
The first line of each test case contains an integer N ( 
)
giving the number of days over which the simulation must be run. The next line contains another integer P ( 
)
representing the number of political parties in this case. The ith of the next Plines contains a positive integer hi (which will never be a multiple of 7) giving the hartal parameter for party i ( 
).
Output
For each test case in the input output the number of working days we lose. Each output must be on a separate line.
Sample Input
2 14 3 3 4 8 100 4 12 15 25 40
Sample Output
5 15
Miguel Revilla
2000-12-26
===================
2 思路
这是一个模拟题，相当于给了n天，把天的序号为a1倍数，a2倍数，…,an倍数的那些 天选出来，排除周五周六，看看选中的一共多少天。奇怪的是这个题为什么会划分在 Data Structure的List分类里，而且我的用时怎么也到不了最好的0.000s，在网上搜 了其它人的答案，基本和我用时差不多。我怀疑有简便的算法，通过计算而非模拟来 解决问题，但是一直找不到答案。先记下模拟的代码吧。
3 代码
/*
* Problem: UVa 10050 Hartals
* Lang: ANSI C
* Time: 0.012s
* Author: minix
*/
#include <stdio.h>
#include <string.h>
#define N 3650
#define P 100
int s[N];
int main() {
int n, m, d, i, j, k, t, r, h;
scanf ("%d", &n);
for (i=0; i<n; i++) {
memset (s, 0, sizeof(s[0])*N);
scanf ("%d", &d);
scanf ("%d", &m);
for (j=0; j<m; j++) {
scanf ("%d", &h);
t = h;
while (t <= d) {
s[t] = 1;
t += h;
}
}
t = 7; r = 0;
for (j=1; j<=d; j++) {
if (t!=5&&t!=6&&s[j]) r ++;
t ++; if (t>7) t-= 7;
}
printf ("%d\n", r);
}
return 0;
}