Download Balanzas

InternationalOlympiadinInformatics2015
26thJuly-2ndAugust2015
Almaty,Kazakhstan
Day1
scales
Language:en-BOL
Balanzas
Aminatieneseismonedas,numeradasde a .Ellasabequecadamonedatieneunpesodiferente.A
ellalegustaríaordenarlasmonedasdeacuerdoasupeso.Paraestoellahadesarrolladounnuevotipo
debalanza.
Unabalanzatradicionaltienedosplatos.Parausarestetipodebalanza,debesponerunamonedaen
cadaplatoylabalanzadeterminarácuálmonedaeslamáspesada.
LanuevabalanzadeAminaesmáscompleja.Estaposeecuatroplatos,etiquetados , , y .La
balanzatienecuatroconfiguracionesdiferentes,cadaunapararesponderunapreguntadiferente.Para
usarestabalanza,Aminadebeponerexactamenteunamonedaencadaunodelosplatos , ,y .
Adicionalmente,sóloenlacuartaconfiguración,elladebeponerunamonedaenelplato .
Cadaunadelascuatroconfiguracionesresponderáunadelassiguientescuatropreguntas:
1. ¿Cuáldelasmonedasenlosplatos , ,y eslamáspesada?
2. ¿Cuáldelasmonedasenlosplatos , ,y eslamásliviana?
3. ¿Cuáldelasmonedasenlosplatos , ,y eslamediana?(Estaeslamonedaquenoesni
lamáspesadanilamásliviana.)
4. Entrelasmonedasenlosplatos , ,y ,consideralasmonedasquesonmáspesadasquela
monedaenelplato .Sihaymonedasquecumplenesto,¿cuáldeestaseslamásliviana?En
casocontrario,siningunadelasmonedasen , ,y esmáspesadaquelamonedaen ,
responde¿cuáldelasmonedasenlosplatos , ,y eslamásliviana?
Tarea
EscribeunprogramaqueordenelasseismonedasdeAminadeacuerdoasupeso.Elprogramapuede
hacerpreguntasalabalanzadeAminaparacompararelpesodelasmonedas.Tuprogramaserá
probadoconvarioscasosdeprueba,cadaunocorrespondienteaunnuevoconjuntodeseismonedas.
TuprogramadebeimplementarlasfuncionesinityorderCoins.Durantecadaejecucióndetu
programa,elevaluador(grader)llamaráprimeroainit;exactamenteunavez.Estotedaráel
númerodecasosdepruebasytepermitiráinicializarlasvariables.Elevaluadorllamará
posteriormenteaorderCoins();unavezporcasodeprueba.
init(T)
T:Elnúmerodecasosdepruebaquetuprogramadeberáresolverduranteestaejecución.
Tesunenteroenelrango
.
Estafunciónnotienevalorderetorno.
orderCoins()
1/4
Estafunciónesllamadaexactamenteunavezporcadacasodeprueba.
LafuncióndebedeterminarelordencorrectoparalasmonedasdeAminallamandoalas
funcionesgetHeaviest(),getLightest(),getMedian(),y/o
getNextLightest().
Unavezquelafuncióndeterminaelordencorrectodebereportarlo,llamandoalafunción
answer().
Despuésdellamaraanswer(),lafunciónorderCoins()deberetornar.
orderCoins()notieneningúnvalorderetorno.
Puedesusarlassiguientesfuncionesentuprograma:
answer(W)—tuprogramadebeusarestafunciónparareportarlarespuestaqueencuentre.
W:Unarreglodetamaño6quecontieneelordencorrectodelasmonedas.W[0]hasta
W[5]debeserelnúmerodecadamoneda(esdecir,númerosde a )enelordendela
máslivianaalamáspesada.
TuprogramadebellamarestafuncióndesdeorderCoins()solounavezporcasode
prueba.
Estafunciónnotienevalorderetorno.
getHeaviest(A,B,C),getLightest(A,B,C),getMedian(A,B,C) —estas
correspondenrespectivamentealasconfiguraciones1,2y3enlabalanzadeAmina’s.
A,B,C:Lasmonedasparaponerenlosplatos , ,y ,respectivamente.A,B,yC
debensertresenterosdistintosentre y .
CadafunciónretornaunodelosnúmerosA,B,yC:elnúmerodelamonedaapropiada.
Porejemplo,getHeaviest(A,B,C)retornaelnúmerodelamonedamáspesada
entrelastresdadascomoparámetro.
getNextLightest(A,B,C,D) —estacorrespondealaconfiguración4enlabalanzade
Amina.
A,B,C,D:Lasmonedasparaponerenlosplatos , , ,y ,respectivamente.A,B,C,
yDdebensercuatroenterosdistintosentre y .
LafunciónretornaunodelosnúmerosA,B,yC:elnúmerodelamonedaseleccionadapor
labalanzadelaformadescritaparalaconfiguración4.Estoes,lamonedaretornadaesla
máslivianaentreaquellasmonedasenlosplatos , , quesonmáspesadasquela
monedaenelplato ;o,siningúnaesmáspesadaquelamonedaenelplato ,la
monedaretornadaessimplementelamáslivianaentrelasmonedasenlosplatos , , .
Puntaje
Nohaysubtareasenesteproblema.Envezdeesto,tupuntajesebasaráencuántasvecestu
programausalabalanza(elnúmerototaldellamadasalasfuncionesgetLightest(),
getHeaviest(),getMedian()y/ogetNextLightest()).
Tuprogramaseejecutarávariasvecesconmultiplescasosdepruebaencadaejecución.Definamos
2/4
como elnúmerodeejecucionesdetuprograma.Estenúmeroestáfijadoporloscasosdeprueba.Si
tuprogramanoordenalasmonedasdeformacorrectaenalgunodeloscasosdepruebadealguna
ejecución,obtendrá0puntos.Deotraforma,cadaejecuciónseráevaluadaindividualmentecomose
describeacontinuación.
Sea elmenornúmeroconelcuálesposibleordenarlasecuenciadeseismonedasusando veces
labalanza.Parahacerlatareamásdesafiante,norevelaremoselvalorde aquí.
Supónqueelnúmeromáximodeusosdelabalanzaentretodosloscasosdepruebadetodaslas
ejecucioneses
paraalgúnentero .Consideraahoraunasolaejecucióndetuprograma.Sea
elnúmeromásgrandedeusosdelabalanzaentretodoslos casosdepruebaenunasóla
ejecuciónparaalgúnenterononegativo .(Siusasmenosde usosdelabalanzaparacadacasode
prueba,entonces
.)Entonces,elpuntajeparaesaejecuciónserá
,redondeado
haciaabajohastadosdígitosdespuésdelpuntodecimal.
Enparticular,situprogramarealizaalomás usosdelabalanzaencadacasodepruebaparacada
ejecución,obtendrás100puntos.
Ejemplo
Supónquelasmonedasestánordenadas
Llamadaa
función
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])
desdelamáslivianaalamáspesada.
Valorde
Explicación
retorno
6
Lamoneda eslamediaentrelasmonedas , ,y .
1
3
6
Lamoneda eslamáspesadaentrelasmonedas , ,y .
Lasmonedas , ,y sonmáslivianasquelamoneda ,luegola
máslivianaentreellas( )esretornada.
Lasmonedas y sonambasmáspesadasquelamoneda .Entre
lasmonedas y ,lamoneda eslamásliviana.
5
Lamoneda eslamáspesadaentrelasmonedas , y .
1
6
Lamoneda eslamedianaentrelasmonedas , y .
Lamoneda eslamedianaentrelasmonedas , y .
Elprogramaencontrólarespuestacorrectaparaestecasode
prueba.
Evaluadordeejemplo
Elevaluadordeejemploleeelinputenelsiguienteformato:
línea : —-Elnúmerodecasosdeprueba
cadaunadelaslíneasdela ala
:unasecuenciade númerosdistintosentre y :el
ordendelasmonedasdesdelasmáslivianahastalamáspesada.
Porejemplo,uninputqueconsisteendoscasosdepruebadondeelordendelasmonedases
y
sevedelasiguienteforma:
3/4
2
123456
346215
Elevaluadordeejemploimprimeelarregloqueespasadocomoparametroalafunciónanswer().
4/4