Algoritmo: Hartals PC / UVa IDs: 110203/10050

Declaração do problema:

Os partidos políticos em Bangladesh mostram sua força convocando hartals
(greves) regulares , que causam consideráveis ​​danos econômicos. Para nossos propósitos, cada parte
pode ser caracterizada por um número inteiro positivo h chamado de parâmetro hartal que denota
o número médio de dias entre dois ataques sucessivos chamados por uma parte dada.
Considere três partidos políticos. Assuma h1 = 3, h2 = 4 e h3 = 8, onde hi é
o parâmetro hartal para o partido i. Podemos simular o comportamento dessas três partes
para N = 14 dias. Sempre iniciamos a simulação no domingo. Não há hartals nas
sextas-feiras ou sábados.
Dados os parâmetros hartal para vários partidos políticos e o valor de N, determine
o número de dias de trabalho perdidos nesses N dias.
Entrada
A primeira linha da entrada consiste em um único inteiro T dando o número de casos de teste
a seguir. A primeira linha de cada caso de teste contém um inteiro N (7 ≤ N ≤ 3, 650), fornecendo
o número de dias durante os quais a simulação deve ser executada. A próxima linha contém
outro inteiro P (1 ≤ P ≤ 100) representando o número de partidos políticos. O i-ésimo
das próximas P linhas contém um inteiro positivo hi (que nunca será um múltiplo de 7)
fornecendo o parâmetro hartal para a parte i (1 ≤ i ≤ P).

Saída
Para cada caso de teste, imprima o número de dias úteis perdidos em uma linha separada.
Amostra de entrada
2
14
3
3
4
8
100
4
12
15
25
40
Amostra de saída
5
15

Solução:

Estaremos usando vetor de bits aqui de tamanho igual ao número de dias em que vamos monitorar o evento hartal. Manteremos um contador para registrar o número total de dias hartal que será incrementado somente quando o bit for definido. Se uma posição de bit já estiver definida, o contador não será incrementado.

Abaixo está o código

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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));
String input = br.readLine();

int totalNumberOfInputs = Integer.parseInt(input);
int [] output = new int[totalNumberOfInputs];
for (int i = 0 ; i < totalNumberOfInputs; i++)
{
    int numberOfDaysToMonitor = Integer.parseInt(br.readLine());
    BitSet bitSet = new BitSet();
    int numberOfPoliticalParties = Integer.parseInt(br.readLine());
    int [] hartalFreq = new int [numberOfPoliticalParties];
    for(int j = 0; j < numberOfPoliticalParties; j++)
    {
        hartalFreq [j] = Integer.parseInt(br.readLine());
    }           
    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);
}
}

}