Role-Playing Game, ou RPG, é um formato de jogo onde um jogador, o mestre, cria, coordena e planeja os eventos de um universo fictício, enquanto os demais jogadores interpretam personagens dentro desse universo, enfrentando muitos desafios e realizando tarefas através de sua criatividade. Em cada rodada, as habilidades de cada um dos personagem são testadas usando uma combinação de um número sorteado por um dado e dos vários atributos que compõem a personalidade do personagem.

No Prison Explorer, o universo é um enorme calabouço com várias celas interligadas, cada uma com guardas diferentes e com as mais diversas particularidades. O jogo começa depois de um mercenário ter prendido cada personagem em uma cela distinta. O objetivo é que todos se reencontrem em uma mesma cela depois de um certo número de rodadas. Assim, em conjunto, podem finalmente derrotar o inimigo e se libertar.

Em uma rodada, o mestre desafia cada jogador a mover-se a alguma outra cela descrita no livro. Se vencer, o jogador é libertado de sua cela atual e recebe a chave da nova cela. Nesse momento, são testados os níveis atuais de habilidade nos seis atributos de um personagem: Força, Destreza, Constituição, Inteligência, Sabedoria e Carisma. Os níveis de um personagem no início da rodada correspondem aos níveis mínimos da cela em que ele está atualmente, independentemente do percurso e das rodadas anteriores.

Quando um jogador recebe um desafio, ele lança um dado e pode aumentar algum atributo de seu personagem em até uma unidade. Qual atributo será aumentado vai depender do número sorteado pelo dado. Para vencer o desafio e acessar uma nova cela, o jogador precisa que as habilidades do personagem, depois de aumentado um atributo, tenham pelo menos os níveis mínimos da nova cela — além de interpretar bem o personagem e contar com a sorte, é claro!

Entre as responsabilidades do mestre, está montar o layout do calabouço, selecionando quais celas do livro farão parte do jogo. Cada rodada pode levar desde minutos até horas, então a maior dificuldade é garantir que o jogo não seja impossível de terminar. Por resolver esse problema, como mestre de RPG experiente que é, você gostaria de descobrir em quais celas o jogo pode terminar, de forma que possa ser completado em até duas rodadas.

Entrada

A primeira linha contém o número de celas descritas no livro. Cada uma é representada por uma linha contendo o nome e os níveis mínimos dos atributos associados, em ordem de Força, Destreza, Constituição, Inteligência, Sabedoria e Carisma, conforme exemplo. Em seguida, é dado o número de personagens, cada um representado pelo nome e pelos atributos de sua cela inicial escolhida pelo jogador. Você pode supor que os nomes já estão ordenados.

Exemplo de entrada

6
corredor            3 4 5 3 5 1
galpao-misterioso   3 4 5 4 5 2
quarto-dos-brutos   3 4 4 3 5 2
saguao-dos-tolos    3 3 5 3 5 2
sala-do-chefe       4 4 5 5 5 1
salto-rapido        3 4 5 3 5 2

3
jon                 3 4 5 3 5 1
olaf                3 4 4 3 5 2
rufus               3 3 5 3 5 2

Saída

Contém os nomes de todas as celas, em ordem, onde o grupo todo poderá se encontrar após duas rodadas. Se não for possível, então deve conter uma linha Impossivel terminar em duas rodadas..

Exemplo de saída

corredor
galpao-misterioso
quarto-dos-brutos
saguao-dos-tolos
salto-rapido

Critérios

Você deve abstrair e representar os dados do problema como um grafo. Antes de escrever seu algoritmo, crie um arquivo grafo.md com um parágrafo descrevendo muito sucintamente quem são os vértices do grafo e quando há aresta entre dois vértices. Também, tente descrever a saída do problema em termos do grafo que você definiu. Não tente resolver o problema antes de ter certeza de que modelou o problema como um grafo e o descreveu adequadamente. Depois de escrever o algoritmo, implemente um programa em um arquivo rpg.c.

Correção

Esta tarefa será corrigida automaticamente sempre que você realizar um git push. Depois de terminada a tarefa, deve-se utilizar o botão na interface de notas para solicitar a correção de um monitor.

Turma AB: O peso desta tarefa será 5.

← Anterior Voltar Próximo →