Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2316
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2316
Autorama
Por OBI - Olimpíada Brasileira de Informática 2006 
Brazil
Timelimit: 1
Seu Diniz possui uma pista de autorama profissional. Nessa pista a marcação de tempo é feita com sensores que fazem leitura da passagem de cada cada carrinho pelo ponto onde o sensor está instalado. K sensores são distribuídos ao longo da pista nos chamados postos de checagem.
Durante uma corrida, os carrinhos devem passar pelos postos de checagem na ordem pré-estabelecida, ou seja, primeiro no posto de checagem 1, depois no 2, até o posto de checagem K, quando ele deve retornar ao posto de checagem 1 para completar uma volta. Entretanto, às vezes, quando os carrinhos saem da pista os competidores os recolocam mais à frente na pista, pulando alguns postos de checagem. Nesse caso, todas as passagens daquele carrinho por postos de checagem devem ser ignoradas até que ele passe pelo posto de checagem correto.
A posição de um carrinho na corrida é determinada pelo número de postos de checagem que ele passou na ordem correta. Caso dois carrinhos tenham passado pelo mesmo número de postos de checagem, a ordem utilizada é a ordem cronológica, ou seja, está mais à frente o carrinho que passou pelo último posto de checagem primeiro.
A pista de autorama do Seu Diniz possui um computador central que recebe os sinais lidos pelos sensores, mas ainda não possui um programa que permita determinar a posição dos carrinhos ao final da corrida.
Escreva um programa que, dado uma lista de leituras feitas pelos sensores, determine a classificação dos carrinhos na corrida.
Entrada
A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha da entrada contêm três inteiros, K, N e M. K representa o número de postos de checagem (1 ≤ K ≤ 100), N o número de carrinhos (1 ≤ N ≤ 100) e M o número de leituras feitas pelos sensores (1 ≤ M ≤ 10000). Os carrinhos são identificados por inteiros de 1 a N e os postos de checagem por inteiros de 1 a K. As M linhas seguintes contêm cada uma dois inteiros X e Y, separados por espaço. Eles indicam que o carrinho número X (1 ≤ X ≤ N) passou pelo posto de checagem Y (1 ≤ Y ≤ K). Os eventos são apresentados na ordem cronológica. Sempre é possível determinar a classificação de todos os pilotos com os dados fornecidos.
Saída
Seu programa deve imprimir, na saída padrão, uma linha contendo N inteiros, sendo que o i-ésimo inteiro representa o carrinho que ocupa a posição i na corrida. Ou seja, o primeiro inteiro é o que ocupa o primeiro lugar, o segundo inteiro é o carrinho que ocupa o segundo lugar, e assim por diante.
Cada inteiro I contendo o número do carrinho que ocupa a posição de número I na corrida: o primeiro colocado ocupa a posição de número 1, o segundo colocado a posição de número 2, etc.
| Exemplos de Entrada | Exemplos de Saída |
|
3 3 6 |
3 2 1 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <cstdio>
#define MAXN 110
using namespace std;
int k, n, m;
int ultimo[MAXN], voltas[MAXN], competidores[MAXN], momentoconclusao[MAXN];
bool compara(int x, int y) {
if (voltas[x] == voltas[y]) {
if (ultimo[x] == ultimo[y]) {
if (momentoconclusao[x] == momentoconclusao[y]) return x < y;
return momentoconclusao[x] < momentoconclusao[y];
}
return ultimo[x] > ultimo[y];
}
return voltas[x] > voltas[y];
}
int main() {
scanf("%d %d %d", &k, &n, &m);
for (int i = 1; i < = n; i++) competidores[i] = i;
for (int i = 1; i < = m; i++) {
int a, b;
scanf("%d %d", &a, &b);
if (b - ultimo[a] == 1) {
momentoconclusao[a] = i;
if (b == k) {
voltas[a] += 1;
ultimo[a] = 0;
} else {
ultimo[a]++;
}
}
}
sort(competidores + 1, competidores + n + 1, compara);
printf("%d", competidores[1]);
for (int i = 2; i < = n; i++) printf(" %d", competidores[i]);
printf("\n");
return 0;
}
Input
3 1
1 1
2 1
3 2
3 3
2 2
Output