URI PROBLEMA 1202 - Festival das Noites Brancas SOLUÇÃO EM C++

URI Online Judge | 1202

Festival das Noites Brancas

Por Marcel K. de C. Silva  Brasil

Timelimit: 1

Todos os anos, na época das chamadas “noites brancas” em que o sol não se põe sobre a cidade de São Petersburgo ocorre o “festival de artes das noites brancas”, que consiste de uma série de apresentações musicais, concertos, balés, e muito mais que atraem artistas de todo o mundo.

É considerado uma das maiores manifestações populares de toda a Russia, uma vez que no auge das noites brancas, o festival costuma ter até um milhão de participantes circulando pelas ruas da cidade. O Teatro Mariinski recebe alguns dos melhores espetáculos e, uma vez que não tem ingressos suficientes para todos os que desejam assistir `as performances, costuma utilizar um sistema curioso e divertido para sortear os que poderão entrar no teatro.

Cada pessoa que entra no teatro, interessado em assistir a uma apresentação escolhe uma fileira na qual gostaria de sentar e recebe um cartão com um número de 000 a 999 escrito nele. Este número é o código do sorteio daquela pessoa. Ao chegar `a entrada o atendente verifica a situação da fila na qual a pessoa sentará. A fila é descrita por uma sequência de ’1’s e ’0’s, onde 1 indica cadeira livre e 0 indica cadeira ocupada. Essa sequência é então interpretada como a representação binária do número n. A pessoa entrará com seus acompanhantes se o n-ésimo número da sequência de Fibonacci terminar exatamente com o número escrito no seu cartão. Assim, por exemplo, se a descrição da fileira é 100 a pessoa só entrará se possuir o cartão com o número 003.

Entrada

A entrada é composta por diversas instâncias. A primeira linha da entrada contém um inteiro T indicando o número de instâncias.
Cada instância consiste em uma linha contendo uma descrição de fileira com até 10000 dígitos. A descrição de uma fileira é uma sequência de ’1’s e ’0’s, nunca começando com ’0’ (a primeira cadeira de todas as fileiras estão reservadas).

Saída

Para cada instância imprima os 3 dígitos que devem estar escrito no cartão para a pessoa entrar no teatro.

#include <iostream>

#include <string>

#define MAXN 2

#define MODULO 1000

using namespace std;

struct Matrix{

int mat[MAXN][MAXN];

};

Matrix base;

inline Matrix multiplication(Matrix A,Matrix B){

Matrix C;

for(int i=0;i<MAXN;i++){

for(int j=0;j<MAXN;j++){

C.mat[i][j] = 0;

for(int k=0;k<MAXN;k++){

C.mat[i][j] += (A.mat[i][k] * B.mat[k][j]) % MODULO;

C.mat[i][j] %= MODULO;

}

}

}

return C;

}

Matrix exponentiation(string expo){

Matrix resp;

for(int i=0;i<MAXN;i++){

for(int j=0;j<MAXN;j++){

resp.mat[i][j] = int(i==j);

}

}

while(true){

if(expo.empty()) break;

if(expo.back() == '1') resp = multiplication(resp,base);

base = multiplication(base,base);

expo.pop_back();

}

return resp;

}

int main(){

ios_base::sync_with_stdio(0);

cin.tie(0);

int TC;

cin >> TC;

while(TC--){

for(int i=0;i<MAXN;i++){

for(int j=0;j<MAXN;j++){

base.mat[i][j] = 1;

}

}

base.mat[1][1] = 0;

string num;

cin >> num;

Matrix resposta = exponentiation(num);

int exibir = resposta.mat[0][1];

if(exibir < 10) cout << "00";

else if(exibir < 100) cout << "0";

cout << exibir << endl;

}

return 0;

}