Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VIVO - Vivo ou Morto

Toda criança certamente já brincou de “vivo ou morto”. A brincadeira é dirigida por um “chefe” (um adulto), que comanda dois ou mais participantes (crianças). A brincadeira é composta de rodadas. No início, os participantes são organizados pelo chefe em fila única. A cada rodada o chefe grita “vivo” ou “morto” e todos os participantes tentam seguir sua ordem, levantando-se ao ouvir a palavra “vivo” ou abaixando-se ao ouvir a palavra “morto”. Um participante que não segue a ordem do chefe é eliminado, deixando o seu lugar na fila. Os participantes remanescentes agrupam-se novamente em fila única, preenchendo as posições dos participantes eliminados, mas mantendo suas posições relativas. O jogo continua até que uma rodada seja composta por exatamente um participante. Tal participante é dito o vencedor do jogo.

Por exemplo, considere que a brincadeira inicie com cinco participantes, identificados por números inteiros de 1 a 5, e que o chefe organize a fila na ordem 3 -> 2 -> 1 -> 4 -> 5. Se na primeira rodada forem eliminados os participantes 2 e 4, a fila da segunda rodada será formada por 3 -> 1 -> 5; se na segunda rodada for eliminado o participante 1, a fila da terceira rodada será formada por 3 -> 5. Se na terceira rodada o participante 3 for eliminado, o vencedor da brincadeira será o participante 5.

Tarefa

Sua tarefa é escrever um programa que determine o vencedor de uma partida de “vivo ou morto”, a partir da informação das ordens dadas pelo chefe e das ações executadas pelos participantes em cada rodada.

Entrada

A entrada é constituída de vários casos de teste, cada um representando uma partida. A primeira linha de um caso de teste contém dois números inteiros P e R indicando respectivamente a quantidade inicial de participantes (2 <= P <= 100) e quantidade de rodadas da partida (1 <= R <= 100). Os participantes são identificados por números de 1 a P. A segunda linha de um caso de teste descreve a fila organizada pelo chefe, contendo P números inteiros distintos x1, x2, . . . xP , onde x1 representa o identificador do participante no primeiro lugar na fila, x2 representa o identificador do participante no segundo lugar na fila, e assim por diante (1 <= xi <= P). Cada uma das R linhas seguintes representa uma rodada, contendo um número inteiro inteiro N indicando o número de participantes da rodada (2 <= N <= P), um número inteiro inteiro J representando a ordem dada pelo chefe (0 <= J <= 1) e N números inteiros Ai representando a ação do participante colocado na i-ésima posição na fila (0 <= Ai <= 1). Ordens e ações “vivo” são representadas pelo valor 1, ordens e ações “morto” pelo valor zero. Cada partida tem exatamente um vencedor, determinado somente na última rodada fornecida no caso de teste correspondente. O final da entrada é indicado por P = R = 0.

Saída

Para cada caso de teste seu programa deve produzir três linhas. A primeira identifica o conjunto de teste no formato “Teste n”, onde n é numerado a partir de 1. A segunda linha deve conter o identificador do vencedor. A terceira linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

Exemplo

Entrada:
2 2
2 1
2 1 1 1
2 1 1 0
5 4
3 2 1 4 5
5 1 1 1 1 1 1
5 0 0 1 0 1 0
3 0 0 1 0
2 1 0 1
0 0

Saída:
Teste 1
2
Teste 2
5

Restrições

2 <= P <= 100 (P = 0 apenas para indicar o fim da entrada)
1 <= R <= 100 (R = 0 apenas para indicar o fim da entrada)
1 <= xi <= P, para 1 <= i <= P
2 <= N <= P
0 <= J <= 1
0 <= Ai <= 1, para 1 <= i <= N

Adicionado por:Wanderley Guimarăes
Data:2007-03-09
Tempo limite:0.124s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO PERL6 PY_NBC SCALA TCL
Origem:Olimpiada Brasileira de Informatica 2005 Programacao Nivel 2

hide comments
2016-05-08 01:28:12
Davi Ozolin [UFABC] Muito obrigado, salvou meu dia...
2016-04-17 18:44:29 Elsio [UFABC]
Parecido com http://br.spoj.com/problems/VIRA11/
2015-06-18 16:59:24 Elsio [UFABC]
Poha! queria dar um like na edulira :/
2015-06-10 03:53:33 Davi Ozolin [UFABC]
Dica, caso esteja dando Tempo Limite Excedido, veja se você está utilizando cin em vez de scanf.
2012-09-06 17:55:59 Cristhian Bonilha
A saída está correta Diego, acontece que a fila é refeita sempre após eliminaçőes.
2012-03-29 03:23:47 Filipe Bittencourt [UNIFEI]
\n ae

Last edit: 2012-03-29 03:24:24
2012-03-15 06:37:38 Diego H. [IFTM Uberlândia]
Esse caso de teste esta incorreto
pois no final sobra posicao 1 e 5.
5 4
3 2 1 4 5
5 1 1 1 1 1 1
5 0 0 1 0 1 0
3 0 0 1 0
2 1 0 1
0 0

5 4
3 2 1 4 5
5 1 1 1 1 1 1
5 0 0 x 0 x 0
3 0 0 x 0 x 0
2 1 x x 1 x 0
0 0

Resposta posicao 1 e 5

Last edit: 2012-03-15 06:40:57
2009-12-10 22:29:37 Davi Alves Magalhães [UERN]
A saída do exemplo está incorreta.
2009-09-09 15:40:21 edulira
"A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente."
Não siga a grafia, siga o enunciado.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.