Este é um problema interativo.
Contexto
Passado meio ano, a loja de I 君 acabou por se tornar inviável. Decidiu trespassá-la e tornar-se explorador, para descobrir o vasto mundo desconhecido.
Seguindo as descrições de um livro antigo, encontrou, no interior de um grande deserto, um palácio subterrâneo construído por uma civilização desconhecida. O palácio tem $N$ grandes cavernas e $M$ passagens de dois sentidos que as ligam. Com a ajuda do livro, I 君 consegue identificar a caverna onde está, mas o livro não regista a estrutura das $M$ passagens. Por isso, é difícil procurar o tesouro inesgotável que, segundo a lenda, está escondido no palácio.
Agora, porém, I 君 descobriu um mecanismo misterioso que revela informações sobre o palácio. Decidiu usá-lo para determinar a estrutura das ligações. Ajuda-o.
Descrição do problema
O palácio subterrâneo pode ser representado por um grafo simples não orientado com $N$ vértices e $M$ arestas. Num grafo simples, existe no máximo uma aresta diretamente entre quaisquer dois vértices. As cavernas são numeradas de $0$ a $n-1$. Neste momento, não sabes quais são as arestas.
Cada caverna tem uma fonte de luz, que pode estar ligada ou desligada. A caverna só fica iluminada quando a sua fonte de luz está ligada. Inicialmente, todas as fontes estão desligadas, e os seus estados só podem ser alterados pelo mecanismo descoberto por I 君. Mais precisamente, o mecanismo permite quatro operações:
- Fornecer um número $x$: o mecanismo inverte o estado da fonte de luz da caverna $x$ e das cavernas diretamente ligadas a $x$ por uma passagem. As fontes ligadas desligam-se e as desligadas ligam-se.
- Fornecer um número $x$: o mecanismo mostra o estado atual da fonte de luz da caverna $x$.
- Fornecer dois números $x,y$, declarando que tens a certeza de que existe uma passagem entre essas cavernas, e pedir ao mecanismo que a registe.
- Fornecer um número $x$: o mecanismo verifica se todas as passagens ligadas à caverna $x$ já foram registadas.
Uma operação só pode começar depois de a anterior terminar. O mecanismo não pode ser usado livremente: os limites de utilização das quatro operações são, respetivamente, $L_m,L_q,M,L_c$. A tua tarefa é escrever um programa que ajude I 君 a utilizar o mecanismo de forma adequada para encontrar corretamente as $M$ passagens.
Detalhes de implementação
Não precisas de implementar a função principal, e não a deves implementar. Só tens de implementar explore(N, M), em que $N,M$ são o número de cavernas e de passagens. Podes interagir com a biblioteca através das quatro funções seguintes:
modify(x)- Executa a operação 1 com o número $x$.
- Tens de garantir que $0\le x<N$. A função não devolve nenhum valor.
query(x)- Executa a operação 2 com o número $x$.
- Tens de garantir que $0\le x<N$. Devolve $0$ ou $1$, indicando que a fonte da caverna $x$ está atualmente desligada ou ligada, respetivamente.
report(x, y)- Executa a operação 3 com os números $x,y$.
- Tens de garantir que $0\le x,y<N$ e $x\ne y$. A função não devolve nenhum valor.
check(x)- Executa a operação 4 com o número $x$.
- Tens de garantir que $0\le x<N$. Devolve $0$ ou $1$, sendo $1$ se e somente se todas as passagens ligadas à caverna $x$ já tiverem sido registadas pela operação 3.
Na avaliação, a biblioteca chama explore exatamente uma vez.
Garante-se que o grafo está completamente definido antes do início da interação e que não é construído dinamicamente em função da interação com o teu programa. Portanto, todas as operações são determinísticas e não precisas de te preocupar com a sua implementação específica na biblioteca.
Garante-se que, respeitando os limites de chamadas, a biblioteca demora no máximo 1 segundo a executar. A memória utilizada pela biblioteca é fixa e não excede 128 MB.
Como implementar
O ficheiro template_explore.cpp/c/pas já está no diretório de trabalho. Copia-o, muda-lhe o nome para explore.cpp/c/pas e desenvolve a tua solução a partir dele.
Para programadores de C++/C
- Garante que o teu programa começa com
#include "explore.h". - A interface da função que deves implementar é:
void explore(int N, int M);- As interfaces das funções de interação que podes chamar são:
void modify(int x);
int query(int x);
void report(int x, int y);
int check(int x);Para programadores de Pascal
- Atenção: a sintaxe de implementação da interface em Pascal é mais complexa. Desenvolve a solução diretamente a partir do ficheiro fornecido
template_explore.pas, em vez de escreveres tudo de raiz. - A interface da função que deves implementar é:
procedure _explore(N, M : longint);- Atenção: o nome é
_explore, e nãoexplore. Usarexploreprovoca um erro de compilação. - As interfaces das funções de interação que podes chamar são:
procedure modify(x : longint);
function query(x : longint) : longint;
procedure report(x : longint; y : longint);
function check(x : longint) : longint;Como testar o programa
Os ficheiros grader.cpp/c e graderhelperlib.pas no diretório do problema são uma implementação de referência da biblioteca. A implementação utilizada na avaliação final é diferente; por isso, a tua solução não deve depender da implementação da biblioteca.
Para programadores de C/C++
Compila o executável no diretório do problema com os comandos seguintes.
Para C:
gcc grader.c explore.c -o explore -O2 -lmPara C++:
g++ grader.cpp explore.cpp -o explore -O2 -lmPara programadores de Pascal
Compila o executável no diretório do problema com o comando:
fpc grader.pas -o"explore" -O2Para o executável compilado
O executável lê da entrada padrão os dados no formato seguinte:
A primeira linha contém três inteiros $L_m,L_q,L_c$, e a segunda contém dois inteiros $N,M$, com os significados indicados no enunciado. Seguem-se $M$ linhas, cada uma com dois inteiros $x,y$ que descrevem uma passagem entre as cavernas $x$ e $y$.
Depois da leitura, a biblioteca chama explore exatamente uma vez e testa a tua função com os dados lidos. Depois de a função devolver normalmente, a biblioteca verifica se o cálculo está correto. Se estiver, escreve Correct e informações sobre as quantidades de chamadas às funções de interação; caso contrário, apresenta a mensagem de erro correspondente.
Exemplo de interação
Suponhamos que o executável lê os dados seguintes:
100 200 300 3 2 0 1 1 2
Os três inteiros da primeira linha são os limites de chamadas de três operações: modify(x) não pode ser chamada mais de $100$ vezes, query(x) mais de $200$ vezes e check(x) mais de $300$ vezes.
Os dois inteiros da segunda linha são o número de cavernas e o número de passagens: $N=3$, $M=2$.
report(x, y) não pode ser chamada mais de $M$ vezes; neste exemplo, no máximo 2 vezes.
Uma interação correta é:
| Programa do concorrente | Biblioteca de interação | Explicação |
|---|---|---|
Chama explore(3, 2) |
Inicia o teste | |
Chama modify(0) |
Executa a operação 1 na caverna 0 | |
Chama query(2) |
Devolve $0$ | A fonte de luz da caverna 2 está atualmente desligada |
Chama report(0, 1) |
Descobre e regista a passagem $(0,1)$ | |
Chama check(0) |
Devolve $1$ | Todas as passagens ligadas à caverna 0 já foram registadas |
Chama report(2, 1) |
Descobre e regista a passagem $(2,1)$ | |
| Termina a execução e devolve | Escreve Correct no ecrã |
A interação termina com resultado correto |
Ficheiros fornecidos
No diretório do problema:
grader.cpp/cegraderhelperlib.passão a implementação de referência fornecida para a biblioteca de interação.explore.hegrader.passão ficheiros de cabeçalho; não precisas de conhecer o seu conteúdo.template_explore.cpp/c/passão os ficheiros de código-fonte de exemplo fornecidos.explore1.in,explore2.in,explore3.insão entradas de exemplo para testes.
Faz cópias de segurança de todos os ficheiros fornecidos. A avaliação recolhe apenas explore.c/cpp/pas no diretório do problema, e alterar outros ficheiros não tem efeito.
Avaliação
A avaliação final recolhe apenas explore.cpp/c/pas. Alterar outros ficheiros do diretório não tem efeito na avaliação.
Este problema está sujeito, em primeiro lugar, aos mesmos limites dos problemas tradicionais. Por exemplo, um erro de compilação resulta em zero pontos no problema inteiro; erros de execução ou excesso dos limites de tempo ou memória resultam em zero pontos nos testes correspondentes. Só podes aceder às variáveis que defines e às fornecidas pela biblioteca, bem como à memória que lhes corresponde. Tentar aceder a outras zonas de memória pode provocar erros de compilação ou de execução.
Respeitando estas condições, obténs a pontuação total de um teste se e somente se:
- Todas as chamadas forem válidas, e as quantidades de chamadas a
modify,queryechecknão excederem, respetivamente, $L_m,L_q,L_c$. - Como
reportsó pode ser chamada $M$ vezes, cada chamada tem de registar uma aresta nova e existente. Ao chamarreport(x, y), tem de existir uma passagem entre $x$ e $y$, e não pode ter sido chamada anteriormente nemreport(x, y)nemreport(y, x). - A função
exploreque implementas devolve normalmente. - Quando
exploredevolve, já registaste todas as $M$ passagens através de chamadas areport.
Restrições e dicas
Este problema tem 25 testes, cada um valendo 4 pontos. Os tamanhos dos dados e os limites de cada teste estão na tabela seguinte.
| Teste | $N=$ | $M=$ | $L_m=$ | $L_q=$ | $L_c=$ | Propriedade especial |
|---|---|---|---|---|---|---|
| 1 | $3$ | $2$ | $100$ | $100$ | $100$ | Nenhuma |
| 2 | $100$ | $10N$ | $200$ | $10^4$ | $2M$ | Nenhuma |
| 3 | $200$ | $10N$ | $200$ | $4\times10^4$ | $2M$ | Nenhuma |
| 4 | $300$ | $10N$ | $299$ | $9\times10^4$ | $2M$ | Nenhuma |
| 5 | $500$ | $10N$ | $499$ | $1.5\times10^5$ | $2M$ | Nenhuma |
| 6 | $59998$ | $\frac N2$ | $17N$ | $17N$ | $0$ | A |
| 7 | $99998$ | $\frac N2$ | $18N$ | $18N$ | $0$ | A |
| 8 | $199998$ | $\frac N2$ | $19N$ | $19N$ | $0$ | A |
| 9 | $199998$ | $\frac N2$ | $19N$ | $19N$ | $0$ | A |
| 10 | $99997$ | $N-1$ | $18N$ | $18N$ | $0$ | B |
| 11 | $199997$ | $N-1$ | $19N$ | $19N$ | $0$ | B |
| 12 | $99996$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | C |
| 13 | $199996$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | C |
| 14 | $199996$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | C |
| 15 | $99995$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | D |
| 16 | $99995$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | D |
| 17 | $199995$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | D |
| 18 | $1004$ | $2000$ | $10^7$ | $5\times10^4$ | $2M$ | Nenhuma |
| 19 | $1004$ | $3000$ | $10^7$ | $5\times10^4$ | $2M$ | Nenhuma |
| 20 | $1004$ | $3000$ | $10^7$ | $5\times10^4$ | $2M$ | Nenhuma |
| 21 | $50000$ | $2N$ | $10^7$ | $10^7$ | $2M$ | Nenhuma |
| 22 | $100000$ | $2N$ | $10^7$ | $10^7$ | $2M$ | Nenhuma |
| 23 | $150000$ | $200000$ | $10^7$ | $10^7$ | $2M$ | Nenhuma |
| 24 | $200000$ | $250000$ | $10^7$ | $10^7$ | $2M$ | Nenhuma |
| 25 | $200000$ | $300000$ | $10^7$ | $10^7$ | $2M$ | Nenhuma |
Relembramos que o grafo utilizado na avaliação está completamente definido antes do início da interação e não é construído dinamicamente em função da interação com o teu programa.
As propriedades especiais da tabela têm os significados seguintes:
A: o grau de cada vértice é exatamente $1$.
B: para cada $x>0$, existe exatamente um $y<x$ tal que as cavernas $x$ e $y$ estão diretamente ligadas por uma passagem.
C: existe uma permutação $p_0,p_1,\ldots,p_{N-1}$ de $0$ a $N-1$ tal que, para todo o $1\le i<N$, existe uma passagem entre as cavernas de números $p_{i-1}$ e $p_i$.
D: garante-se que o grafo é conexo.
- Dica: o teu programa pode distinguir os tipos de dados acima através do algarismo das unidades do valor $N$ recebido.