InternationalOlympiadinInformatics2015
26thJuly-2ndAugust2015
Almaty,Kazakhstan
Day1
scales
Language:pt-BR
Scales
Aminatemseismoedas,numeradasde a esabequeasmoedastêmtodaspesosdiferentes.Ela
gostariadeordená-lasdeacordocomosseuspesos.Paratanto,Aminadesenvolveuumnovotipode
balança.
Umabalançatradicionaltemdoispratos.Parausarumadessasbalanças,vocêcolocaumamoedaem
cadapratoedeterminaqualdasmoedaséamaispesada.
AnovabalançadaAminaémaiscomplexa.Temquatropratos,rotulados , , e .Abalança
temquatroconfiguraçõesdiferentes,cadaumadasquaisrespondeaumaperguntadiferenteem
relaçãoàsmoedas.Parausarabalança,énecessáriocolocarexatamenteumamoedaemcadaum
dospratos , e .Alémdisso,naquartaconfiguração,énecessáriotambémcolocarexatamente
umamoedanoprato .
Asquatroconfiguraçõesfazemabalançaresponderàsquatroperguntasabaixo:
1. Qualdasmoedasnospratos , e éamaispesada?
2. Qualdasmoedasnospratos , e éamaisleve?
3. Qualdasmoedasnospratos , e éamediana?(Estaéamoedaquenãoénemamais
pesadanemamaislevedastrês.)
4. Dasmoedasnospratos , e ,considereapenasasmoedasquesãomaispesadasdoquea
moedanoprato .Seexistemmoedasassim,qualéamaisleve?Poroutrolado,senão
existemmoedasassim,qualdasmoedasnospratos , e éamaisleve?
Tarefa
EscrevaumprogramaqueordenaasseismoedasdeAminadeacordocomoseupeso.Oprograma
podeconsultarabalançaparacompararospesosdasmoedas.Seuprogramareceberávárioscasos
detestepararesolver,cadaumcorrespondendoaumnovoconjuntodeseismoedas.
SeuprogramadeveimplementarasfunçõesiniteorderCoins.Acadaexecuçãodoseu
programa,oavaliadorchamaráinitprecisamenteumavez.Istoforneceráonúmerodecasosde
testeelhepermitiráinicializarquaisquervariáveis.OavaliadorentãochamaráorderCoins()uma
vezparacadacasodeteste.
init(T)
T:Onúmerodecasosdetestequeseuprogramateráqueresolvernestaexecução.Té
uminteironointervalo
.
Estafunçãonãoretornanenhumvalor.
orderCoins()
1/4
Estafunçãoéchamadaexatamenteumavezparacadacasodeteste.
AfunçãodevedeterminaraordemcorretadasmoedasdaAmina,chamandoasfunções
getHeaviest(),getLightest(),getMedian(),e/ougetNextLightest()do
avaliador.
Umavezqueafunçãodeterminaaordemcorreta,devereportá-la,chamandoafunção
answer()doavaliador.
Depoisdechamaranswer(),afunçãoorderCoins()deveretornar,semdevolver
nenhumvalor.
Noseuprograma,vocêpodeusarasseguintesfunçõesdoavaliador:
answer(W)—seuprogramadeveusarestafunçãoparaindicararespostaquedeterminou.
W:Umvetordecomprimento6quecontémaordemcorretadasmoedas.W[0]aW[5]
devemserosnúmerosdasmoedas(i.e.,númerosde a )naordem,damaisleveparaa
maispesada.
SeuprogramadevesomentechamarestafunçãoapartirdeorderCoins(),umavez
paracadacasodeteste.
Estafunçãonãoretornanenhumvalor.
getHeaviest(A,B,C),getLightest(A,B,C),getMedian(A,B,C) —estas
funçõescorrespondem,respectivamente,àsconfigurações1,2e3dabalançadaAmina.
A,B,C:Asmoedassãocolocadasnospratos , e ,respectivamente.A,BeCdevem
sertrêsinteirosdistintos,todosnointerrvaloentre e inclusive.
CadafunçãoretornaumdosnúmberosA,B,eC:onúmerodamoedaapropriada.Por
exemplo,getHeaviest(A,B,C)retornaonúmerodamoedamaispesadadastrês.
getNextLightest(A,B,C,D) —estacorrespondeàconfiguração4dabalançade
Amina.
A,B,C,D:Asmoedasquesãocolocadasnospratos , , e ,respectivamente.A,B,
CeDdevemserquatrointeirosdistintos,todosnointervalode a ,inclusive.
AfunçãoretornaumdosnúmerosA,BeC:onúmerodamoedaselecionadapelabalança,
comodescritoacima,naconfiguração4.Assim,amoedaretornadaéamaislevedentre
asmoedasnospratos , e quesãomaispesadasqueamoedanoprato ,ou,se
nenhumadelasformaispesadadoqueamoedanoprato ,amoedaretornadaé
simplesmenteamaislevedastrêsmoedasnospratos , e .
Pontuação
Nãohásubtarefasnesteproblema.Apontuaçãoserábaseadaemquantaspesagensoseuprograma
executa(númerototaldechamadasparaasfunçõesgetLightest(),getHeaviest(),
getMedian()e/ougetNextLightest()).
Seuprogramaseráexecutadováriasvezes,cadavezcommúltiploscasosdeteste.Seja onúmero
deexecuçõesdoseuprograma.Estenúmeroestáfixadopelosdadosdeteste.Seseuprogramanão
ordenarasmoedascorretamenteemqualquercasodetestedequalquerexecução,receberá0pontos.
2/4
Casocontrário,asexecuçõesserãopontuadosindividualmente,comosegueabaixo.
Seja omenornúmerodepesagensparaordenarqualquersequênciadeseismoedasusandoa
balançadeAmina.Paratornaratarefamaisdesafiadora,nãovamosrevelarovalorde agora.
Suponhaqueomaiornúmerodepesagensentretodososcasosdetestedetodasasexecuçõesseja
,paraalguminteiro .Então,considereumaexecuçãoemparticulardoseuprograma.Seja
omaiornúmerodepesagensdestaexecução,considerandotodosostestesdecaso,onde é
umnúmeronãonegativo.(Sevocêusarmenosdoque pesagensparatodososcasosdetestedesta
execução,então
.)Então,apontuaçãodestaexecuçãoserá
,arrendondadopara
baixocomprecisãodedoisalgarismosdepoisdavírgula.
Emparticular,seseuprogramafizernomáximo pesagensparacadacasotestedecadaexecução,
vocêreceberá100pontos.
Exemplo
Suponhaqueaordemdasmoedasseja
Funçãochamada
getMedian(4,5,6)
getHeaviest(3,1,
2)
getNextLightest(2,
3,4,5)
getNextLightest(1,
6,3,4)
getHeaviest(3,5,
6)
getMedian(1,5,6)
getMedian(2,4,6)
answer([3,4,6,2,
1,5])
,damaisleveparaamaispesada.
Retorna
Explicação
6
Amoeda éamedianaentreasmoedas , e .
1
3
6
Amoeda éamaispesadaentreasmoedas , e .
Asmoedas , e sãotodasmaislevesdoqueamoeda ,entãoa
maisleveentreelas( )éretornada.
Asmoedas e sãoambasmaispesadasdoqueamoeda .Entre
asmoedas e ,amoeda éamaisleve.
5
Amoeda éamaispesadaentreasmoedas , e .
1
6
Amoeda éamedianaentreasmoedas , e .
Amoeda éamedianaentreasmoedas , e .
Oprogramadeterminouarespostacorretaparaestecasodeteste.
Avaliadorexemplo
Oavaliadorexemplolêdadosnoseguinteformato:
linha : —-onúmerodecasosdeteste
cadaumadaslinhasde a
:umasequênciade númerosdistintosde a :aordemdas
moedas,damaisleveàmaispesada.
Porexemplo,setivermosdoiscasosdeteste,emqueasmoedassãoordenadasrespectivamente
e
,aentradaseráaseguinte:
2
123456
346215
3/4
Oavaliadorexemploimprimeovetorquefoipassadocomoparâmetroparaafunçãoanswer().
4/4