Procurando pseudo-aleatórios modulados

Preâmbulo

A pacata cidade de South Park nada de pacata tem. Butters, digo, Professor Chaos está aterrorizando mais uma vez! Ele busca o que ninguém jamais procurou, as ocorrências de alguns números pseudo-aleatórios modulares!

Professor Chaos

O desejo de professor Chaos é muito simples. Ele possui duas sementes para geração de números pseudo-aleatórios e precisa saber quantas ocorrências de alguns números ocorrem a cada 100000100000 (isso mesmo cem mil) gerações de números pseudo-aleatórios para as duas sementes que ele possui.

Entrada

A entrada possui um único caso de teste contendo um número indeterminado de linhas.

A primeira possui dois números inteiros sem sinal, S1S1 e S2S2, representanto, respectivamente, a primeira semente e a segunda semente.

Depois da primeira linha existirão diversas linhas contendo dois inteiros MiM_i e BiB_i, representando, respectivamente, MÓDULO (em C representado pelo sinal %) e o número que seja se procurar.

Saída

Para cada linha contendo MiM_i e BiB_i você deve responder quantas ocorrências de BiB_i aconteceram para cada um dos 200000200000 números (100000100000 de cada semente) pseudo-aleatórios módulo MiM_i.

TAREFA

Você já deve ter percebido que esse problema talvez funcione mais rapidamente se for utilizado o conceito de threads e semáforos.

Exemplo ilustrativo

Para simplificar o entendimento, vou explicar nesta seção um exemplo reduzido, que ao invés de gerar 100000100000 valores, geraremos somente 55.

Caso a entrada fosse:

300 801 (ref:sementes)
8 6
512 100

Na linha (sementes), recebemos duas sementes, 300300 e 801801. Gerando 55 números pseudo-aleatórios com essas sementes, teríamos:

1179231837 1613409366 312769636 1637092777 840974024
1471841391 193279630 141119683 166125014 238450767

A primeira linha os números gerados da semente 300300 e a segunda dos números de 801801. Nunca modifique esses números, pois eles serão utilizados para toda as outras consultas.

Agora precisaríamos processar as próximas linhas, o primeiro MiM_i é 88 que busca a quantidade de ocorrências de 66, calculando o MOD 88 para cada pseudo-aleatório (gerados e armazenaods anteriormente) teríamos:

5 6 4 1 0
7 6 3 6 7

Já que queremos saber a quantidade de ocorrências de 66, obtemos 3 ocorrências. Portanto, imprime 33.

Já para a segunda linha com MiM_i 512512 buscando ocorrências de 100100. Teríamos os seguintes números em módulo 512512, calculados dos números pseudo-aleatórios do primeiro passo:

93 86 100 425 200
184 259 385 368 13

Neste caso temos somente uma ocorrência de 100100, portanto imprimiria 11.

Tentativa de Professor Chaos

Nosso amigo Chaos possui uma quase implementação, pena que muitos passos estão faltando.

void calcula_perguntas(unsigned int s)
{
    int v[MAXRANDOM];
    for(int i=0;i<MAXRANDOM;i++)
        v[i]=rand_r(&s);
    int mi,bi;

    while(ESPERA(mi,bi))
    {
        conta=0;
        for(int i=0;i<MAXRANDOM;i++)
            if(v[i]%mi==bi)
                conta++;
        somaglobal+=conta;
        CALCULOFEITO
    }
}

int main(void)
{
    leia(s1,s2);
    cria_thread(calcula_perguntas,s1);
    cria_thread(calcula_perguntas,s2);
    while(leia(mi,bi))
    {
        LIBERATHREADS;
        AGUARDECALCULOTHREADS;
        printf("%d\n",somaglobal);
    }
}

LTT

A abordagem feita por Chaos é muito ingênua e deve demorar bastante em entradas maiores. Uma abordagem parecida com produtor-consumidor é mais adequada, algo como feito no exercício do get_ticket.

Limites

Exemplos

Exemplo de entrada

100 200
8 7
256 7
1000000 533

Saída para o exemplo acima

24961
734
0

Exemplo de entrada

5270 22136
705 416
604 478
318 316
583 163
344 137
353 129
762 703
550 124
249 49
351 237

Saída para o exemplo acima

293
350
600
319
575
558
254
359
831
563

Exemplo de entrada

27809 12061
365 19
975 42
525 154
18 0
384 236
291 27
950 785
290 141
183 20
904 268

Saída para o exemplo acima

544
190
399
11109
525
657
202
698
1061
252

Exemplo de entrada

3732 28201
15 4
334 311
715 341
147 43
403 66
307 186
384 236
309 56
185 145
394 218

Saída para o exemplo acima

13355
613
276
1289
511
644
507
650
1081
504

Author: Bruno Ribas