Last Updated: February 25, 2016
·
1.919K
· saurabhksingh

# Algorithm : Hartals PC/UVa IDs: 110203/10050

Problem Statement :

Political parties in Bangladesh show their muscle by calling for regular hartals
(strikes), which cause considerable economic damage. For our purposes, each party
may be characterized by a positive integer h called the hartal parameter that denotes
the average number of days between two successive strikes called by the given party.
Consider three political parties. Assume h1 = 3, h2 = 4, and h3 = 8, where hi is
the hartal parameter for party i. We can simulate the behavior of these three parties
for N = 14 days. We always start the simulation on a Sunday. There are no hartals on
either Fridays or Saturdays.
Given the hartal parameters for several political parties and the value of N , determine
the number of working days lost in those N days.
Input
The ﬁrst line of the input consists of a single integer T giving the number of test cases
to follow. The ﬁrst line of each test case contains an integer N (7 ≤ N ≤ 3, 650), giving
the number of days over which the simulation must be run. The next line contains
another integer P (1 ≤ P ≤ 100) representing the number of political parties. The ith
of the next P lines contains a positive integer hi (which will never be a multiple of 7)
giving the hartal parameter for party i (1 ≤ i ≤ P ).

Output
For each test case, output the number of working days lost on a separate line.
Sample Input
2
14
3
3
4
8
100
4
12
15
25
40
Sample Output
5
15

Solution :

We will be using bit-vector here of size equal to number of days we are going to monitor the hartal event. We will maintain a counter for recording the total number of hartal days which will incremented only when the bit is going to be set. If a bit position is already set then the counter will not be incremented.

Below is the code

import java.io.IOException;
import java.util.BitSet;

public class Hartals {

``````/**
* @param args
*/``````

public static void main(String[] args) throws IOException {

``````BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int totalNumberOfInputs = Integer.parseInt(input);
int [] output = new int[totalNumberOfInputs];
for (int i = 0 ; i < totalNumberOfInputs; i++)
{
BitSet bitSet = new BitSet();
int [] hartalFreq = new int [numberOfPoliticalParties];
for(int j = 0; j < numberOfPoliticalParties; j++)
{
}
for (int freq : hartalFreq)
{
int currentDay = freq;
int count = 1;
while (currentDay <= numberOfDaysToMonitor)
{
count ++;
if(!bitSet.get(currentDay) && !(currentDay%7 ==6 || currentDay%7 == 0))
{
output[i] ++;
bitSet.set(currentDay);
}
currentDay = freq * count;
}
}

}
System.out.println("Output");
for(int out : output)
{
System.out.println(out);
}
}``````

}

21.87K
2

11.72K
0

8.761K
0

Best #N Authors
turtlebender
21.86K
saurabhksingh
19.23K
ajithhub
11.71K
leesmith
8.747K
shanselman
7.629K
Related Tags
#n
Awesome Job