Agora que
as ONI estão quase a terminar, está na hora do grande jantar de
despedida. Toda a gente vai estar presente, o Gabriel, a Joana, o
João, o Duarte, o Marco, ... no total vão estar N pessoas
presentes, entre concorrentes, ex-concorrentes e público
interessado.
O jantar será servido numa grande mesa de N lugares, com os lugares distribuidos sequencialmente, como mostra a imagem seguinte:
Antes de começar o jantar, cada pessoa irá sentar-se no seu lugar e esperar que o seu prato chegue. Visto que há N pessoas, os pratos vão saindo um a um, a cada minuto que passa. Como é sabido, é boa educação esperar que toda a gente na mesa tenha o seu prato antes de se começar a comer. Visto que a mesa é comprida e há tanta gente, nem toda a gente consegue ver toda a gente e por isso a pessoa i só espera pelas pessoas num raio de Ri lugares (ou seja, as pessoas à sua direita e esquerda a menos de Ri lugares de distância). A imagem seguinte representa os raios de espera de cada pessoa:
No exemplo anterior, temos:
Visto que a ordem de chegada dos pratos pode ser qualquer uma, cada pessoa pode demorar um tempo diferente até começar a comer. Por exemplo, considera a ordem de chegada dos pratos seguinte: 1, 3, 2, 5, 4, 6, ou seja, no minuto 1 chega o prato para o lugar 2, no minuto 2 chega o prato para o lugar 3 e por ai fora. Neste caso, temos:
A equipa de catering precisa de saber o tempo de espera em diferentes momentos (exatamente Q momentos), para perceber se a ordem que escolheram para servir os pratos foi boa ou não. Como algumas pessoas ainda podem estar à espera para comer, a equipa a qualquer momento apenas quer saber a soma dos tempos de espera das pessoas que já estão a comer. Consegues ajudá-los?
Dado o número de pessoas a participar no jantar N, a ordem de chegada dos pratos, responder a um conjunto de Q perguntas sobre a soma dos tempos de espera em diferentes momentos.
Podes começar por descarregar os ficheiros correspondentes à tua linguagem (ou um arquivo zip contendo tudo):
| Linguagem | Ficheiro a implementar | Ficheiro com avaliador exemplo | Ficheiros auxiliares | Input para avaliador exemplo |
| C | resolver.c | avaliador.c | avaliador.h | input.txt |
| C++ | resolver.cpp | avaliador.cpp | ||
| Java | resolver.java | avaliador.java | ------ |
Nota que a implementação do avaliador a usar nos testes oficiais será diferente, mas podes esperar o mesmo comportamento.
Deves submeter um único ficheiro que implementa três funções:
iniciar(N, Q, R), que recebe um
inteiro N, que representa o número de pessoas, um
inteiro Q, que representa o número de perguntas e uma
lista de N inteiros R, cujo i-ésimo elemento
representa o raio de espera da i-ésima pessoa. Esta função é
chamada apenas uma vez no início da execução do programa (ou
seja, antes de qualquer uma das outras funções). A função não
deve retornar nada.chegada(i), que recebe um inteiro i, que
representa a chegada do prato da pessoa i. Esta função
será chamada exatamente N vezes pela ordem de chegada
dos pratos. A função não deve retornar nada.pergunta(), que não recebe qualquer
argumento. Esta função será chamada exatamente Q
vezes. A função deve retornar um inteiro que representa a soma
dos tempos de espera das pessoas que já estão a comer no
momento da pergunta, considerando apenas os pratos que já
chegaram (ou seja, que foram indicados pelas chamadas da
função chegada(i) já feitas).
O avaliador começará por chamar a função iniciar(N,
R) e depois chamará as funções chegada(i)
e pergunta() alternadamente.
Para isso deves usar o ficheiro resolver.{c,cpp,java,pas} que descarregaste, colocando no interior das funções o teu código. Podes acrescentar outras funções, mas devem ficar todas neste ficheiro que é o único que deves submeter.
Funções a implementar:
| C/C++: | void iniciar(int N, int Q, int R[MAXN]); |
| Java: | void iniciar(int N, int Q, int[] R); |
| C/C++/Java: | void chegada(int i); |
| C/C++: | long long int pergunta(); |
| Java: | long pergunta(); |
Notem ainda que o tipo de inteiro para a
função pergunta() é long long int no caso
de C/C++ e long no caso de Java.
A vossa função não deve ler nem escrever para os canais de entrada/saída padrão.
Imagina que N = 6 pessoas com raios de espera 2, 1, 2, 4,
1, 1, respetivamente (como no exemplo a cima), serão
feitas Q = 3 perguntas. A função iniciar que
deves implementar será chamada como resolver(6,
3, {2, 1, 2, 4, 1, 1}).
Uma possível execução seria a seguinte (com a ordem das chamadas a ser de cima para baixo):
| Invocação | Resultado | Descrição |
| chegada(1) | - | - |
| chegada(3) | - | - |
| chegada(2) | - | - |
| pergunta() | 2 | As pessoas 1 (espera 2 minutos) e 2 (espera 0 minutos) já começaram a comer. |
| chegada(5) | - | - |
| chegada(4) | - | - |
| pergunta() | 5 | As pessoas 1 (espera 2 minutos), 2 (espera 0 minutos) e 3 (espera 3 minutos) já começaram a comer. |
| chegada(6) | - | - |
| pergunta() | 8 | Todos já estão a comer, para um tempo de espera total de 8. |
Reparem que a ordem de chegada dos pratos é igual à do exemplo a cima.
| 1 ≤ N ≤ 100 000 | Número de pessoas. | |
| 1 ≤ Q ≤ 100 000 | Número de perguntas. | |
| 0 ≤ Ri ≤ N | Raios de espera. |
Cada grupo tem um número de pontos associado e um conjunto de restrições adicionais. Os grupos são os seguintes:
| Grupo | Número de Pontos | Restrições adicionais |
|---|---|---|
| 1 | 25 | N ≤ 1 000, Q ≤ 1 000 |
| 2 | 20 | Q = 1 |
| 3 | 10 | Q ≤ 10 |
| 4 | 20 | Todos os Ri são iguais |
| 5 | 25 | - |
É disponibilizado um avaliador exemplo em cada linguagem (avaliador.{c,cpp,java,pas}) que pode ser utilizado para testar a vossa submissão. Para C/C++ está ainda disponível um ficheiro auxiliar (para C/C++ o avaliador.h). Este avaliador não corresponde ao utilizado pelo sistema de avaliação.
Este avaliador começa por receber como input um inteiro N e um inteiro Q correspondendo, respetivamente, ao número de pessoas e perguntas. Segue-se uma linha com N inteiros entre 1 e N, separados por espaços, que representam os raios de espera de cada pessoas (por ordem de lugar).
Seguem-se N + Q linhas, cada uma contendo ou: C i, indicando que chegou o prato para o lugar i; P, indicando que foi feita uma pergunta. Devem garantir que o número de chegadas é exatamente N e de perguntas Q.
O avaliador irá automaticamente invocar a
função iniciar(N,Q,R) por vocês implementada e
chamará de seguida as funções chegada(i)
e pergunta() alternadamente, de acordo com o dado
no input. O avaliador irá imprimir o resultado de cada
pergunta para uma linha diferente, pela ordem do input
(devem comparar com o resultado esperado para o input
dado).
Disponibilizamos um ficheiro input.txt que contém o caso de exemplo referido a cima, cujo output correto deve ser:
2 5 8
Um exemplo de teste na tua máquina (supondo que tens os compiladores oficiais instalados) seria o seguinte:
| Linguagem | Compilar | Executar com o exemplo |
| C | gcc -Wall avaliador.c resolver.c | ./a.out < input.txt |
| C++ | g++ -Wall avaliador.cpp resolver.cpp | ./a.out < input.txt |
| Java | javac avaliador.java resolver.java | java avaliador < input.txt |