Sequências complementares
Problema A - Sequências Complementares
O Samuel acabou de ler um artigo sobre a sequência de Thue-Morse, e ficou fascinado com a sua beleza. É uma sequência binária inifinita com propriedades tão interessantes como nunca apresentar três blocos (subsequências contíguas de bits) consecutivos iguais entre si. Os primeiros bits da sequência de Thue-Morse são 01101001100101101001011001101001...
Para obter esta sequência faz-se o seguinte:
Começa-se com o um único bit, o 0.
Em cada passo pega-se no complemento binário (ou seja, a negação, ou inversão) dessa sequência e adiciona-se (concatena-se) ao final, repetindo sempre este passo.
Exemplificando com os primeiros passos:
O complemento de 0 é 1. Adicionando ao que já existia ficamos com: 01
O complemento de 01 é 10. Adicionando ao que já existia ficamos com: 0110
O complemento de 0110 é 1001. Adicionando ao que já existia ficamos com: 01101001
O complemento de 01101001 é 10010110. Adicionando ao que já existia ficamos com: 0110100110010110
O Samuel resolveu começar a contar os bits ligados (marcados a 1) para conhecer melhor a sequência, mas rapidamente ficou cansado e resolveu pedir a tua ajuda. O que ele quer mesmo saber é quantos 1's existem num dado intervalo de posições [a,b] (o primeiro elemento da sequência está na posição 1). Por exemplo, se o intervalo em que ele está interessado for [1,10] (indicado a vermelho), existem 5 bits ligados (indicados a negrito):
Se o intervalo fosse [5,8], existiam apenas dois bits ligados:
O Samuel ficou empolgado e achou que podia até generalizar a sequência, modificando os bits iniciais que dão início ao processo de geração. Por exemplo, se os bits iniciais forem 1101, a sequência fica:
O complemento de 1101 é 0010. Adicionando ao que já existia ficamos com: 11010010
O complemento de 11010010 é 00101101. Adicionando ao que já existia ficamos com: 1101001000101101
Claro que o Samuel quer também poder contar os bits ligados para uma sequência geral como esta. Será que podes ajudá-lo?
Dada um conjunto de N bits iniciais, e P perguntas, cada uma indicando um intervalo [ai, bi], a tua tarefa é, para cada pergunta, indicar quantos bits estão ligados no intervalo correspondente, supondo que a sequência foi gerada como atrás descrito (ir sucessivamente concatenando o complemento da sequência actual).
Na primeira linha vem um número inteiro N indicando o número de bits iniciais.
Na segunda linha vêm os N bits (0's ou 1's) da sequência.
Na terceira linha vem um único inteiro P indicando o número de perguntas. Seguem-se P linhas, cada uma com dois inteiros ai e bi indicando o intervalo a considerar para essa pergunta.
O output deve conter P linhas, uma para cada pergunta, indicando o número de ligados entre as posições ai e bi (inclusive) na sequência criada como atrás descrito e que começa com os bits iniciais indicados
1 ≤ N ≤ 10 Número de bits iniciais
1 ≤ ai ≤ bi ≤ 1015 Posições dos intervalos a considerar
Nota que para ler um número da ordem de 1015 são necessários 64 bits, ou seja, deves usar o long long de C/C++ ou o long de Java.