Game

InternationalOlympiadinInformatics2014
13-20thJuly2014
Taipei,Taiwan
game
Day-1tasks
Language:en-PRT
Game
Jian-Jiaéumjovemquegostadejogos.Quandolhefazemumapergunta,elepreferebrincaraoinvés
deresponderdiretamente.Jian-JiaencontrousuaamigaMei-Yuefalou-lhesobrearedeaéreaem
Taiwan.Há cidadesemTaiwan(numeradas0,...,
),algumasdasquaissãoconectadaspor
voos.Cadavooconectaduascidadesepodeserusadoemambasasdireções.
Mei-YuperguntouaJian-Jiaseépossívelviajardeaviãoentrequaisquerduascidades(diretaou
indiretamente).Jian-Jianãoquisdararesposta,aoinvésdissosugeriuumjogo.Mei-Yupodefazer
perguntasdaforma"Ascidades e sãoconectadasdiretamenteporalgumvoo?",eJian-Jia
responderáessasperguntasdeimediato.Mei-Yufaráaperguntaparacadapardecidades
exatamenteumavez,numtotalde
perguntas.Mei-Yuganhaojogose,depoisde
obterrespostasparaasprimeiras perguntasparaalgum
,elapodeinferirsearedeéounão
conexa,ouseja,seépossívelviajardeaviãoentrequalquerpardecidades(diretaouindiretamente).
Casocontrário,istoé,seelaprecisardetodasas perguntas,entãoovencedorseráJian-Jia.
ParadeixarojogomaisdivertidoparaJian-Jia,osamigosconcordaramqueelenãoprecisalevarem
contaaredeaérearealdeTaiwan,epodeinventarasuaredeàmedidaqueojogoprogride,
escolhendosuasrespostascombasenasperguntasjáfeitasporMei-Yu.SuatarefaéajudarJian-Jiaa
ganharojogo,decidindocomoeledeveresponderàsperguntas.
Exemplos
Vamosexplicarasregrasdojogoatravésdetrêsexemplos.Cadaexemplotem
rodadasdeperguntaserespostas.
cidadese
Noprimeiroexemplo(tabelaabaixo),Jian-Jiaperdeporquedepoisdarodada4,Mei-Yutemcerteza
quesepodeviajardeaviãoentrequaisquerduascidades,quaisquerquesejamasrespostasdeJian-Jia
paraasperguntas5e6.
rodada
1
2
3
4
----5
6
pergunta
0,1
3,0
1,2
0,2
-------3,1
2,3
resposta
sim
sim
não
sim
-----não
não
NopróximoexemploMei-Yupodeprovar,depoisdarodada3,quenãoimportaquaisasrespostasde
Jian-Jiaparaasperguntas4,5e6,nãosepodeviajardeaviãoentreascidades0e1,deformaque
Jian-Jiaperdetambém.
1/3
rodada
1
2
3
----4
5
6
pergunta
0,3
2,0
0,1
-------1,2
1,3
2,3
resposta
não
não
não
-----sim
sim
sim
NoúltimoexemploMei-Yunãopodedeterminarseépossívelviajardeaviãoentrequaisquerduas
cidadeantesquetodasasseisperguntassejamrespondidas,deformaqueJian-Jiaganhaojogo.
Especificamente,dadoqueJian-Jiarespondeusimnaúltimapergunta(vejaatabelaabaixo),entãoé
possívelviajarentrequalquerpardecidades.Contudo,seJian-Jiativesserespondidonãoparaa
últimaquestão,entãoseriaimpossível.
rodada
1
2
3
4
5
6
pergunta
0,3
1,0
0,2
3,1
1,2
2,3
resposta
não
sim
não
sim
não
sim
Tarefa
FavorescreverumprogramaqueajudeJian-Jiaaganharojogo.NotequenemMei-YunemJian-Jia
conhecemaestratégiadooutro.Mei-Yupodefazerperguntassobreparesdecidadesemqualquer
ordem,eJian-Jiaprecisarespondê-lasimediatamente,semsabernadasobreasperguntasseguintes.
Vocêprecisaimplementarasseguintesduasfunções.
initialize(n)--Vamoschamarinitializeprimeiro.Oparâmetro éonúmerode
cidades.
hasEdge(u,v)--DepoisvamoschamarhasEdge
vezes.Essaschamadas
representamasperguntasdeMei-Yu,naordememqueelaasfaz.Vocêprecisaresponderse
existeumvoodiretoentreascidades e .Maisprecisamente,ovalorretornadodeveser1se
existeumvoodireto,e0casocontrário.
Subtarefas
Cadasubtarefaconsistedeváriosjogos.Vocêsomenteganharápontosparaumsubtarefaseseu
programaganhatodososjogosparaJian-Jia.
2/3
subtarefa pontos
1
15
2
27
3
58
Detalhesdeimplementação
Vocêtemquesubmeterexatamenteumarquivo,chamadogame.c,game.cppougame.pas.Esse
arquivoimplementaossubprogramasdescritosacima,usandoasseguintesassinaturas.
ProgramasemC/C++
voidinitialize(intn);
inthasEdge(intu,intv);
ProgramasemPascal
procedureinitialize(n:longint);
functionhasEdge(u,v:longint):longint;
Avaliadorexemplo
Oavaliadorexemplolêaentradanoseguinteformato:
linha1:n
as linhasseguintes:cadalinhacontémdoisinteirosuandvquedescrevemaperguntarelativa
àscidades e .
3/3