Problem U
Gullpeningastaflar

Mynd fengin af flickr.com

Fyrir framan þig eru $n$ staflar af gullpeningum, hver þeirra með $n$ gullpeninga. Aðeins einn þessarra stafla er með alvöru gullpeninga, hinir staflarnir eru með eftirlíkingar. Þessar eftirlíkingar eru mjög vel gerðar, það er nánast ómögulegt að gera greinarmun á alvöru gullpening og eftirlíkingu. Eini munurinn á þeim er þyngdin þeirra, en meira segja sá munur er smávægilegur. Eftirlíkingarnar eru $n$ einingar að þyngd hver og alvöru gullpeningar $n+1$ einingar að þyngd hver.

Markmið þitt er að finna staflann með alvöru gullpeningunum svo þú getir tekið hann og skilið virðislausu eftirlíkingarnar eftir. Þar sem erfitt er að gera greinarmun á peningunum út frá þyngd hefurðu tekið vigt með þér. Þú getur tekið eins marga peninga úr hverjum stafla og þú vilt, og sett á vigtina. Þá sýnir vigtin þér heildarþyngd peninganna. Peningarnir fara svo aftur hver í sinn stafla eftir vigtunina.

Geturðu fundið staflann með alvöru gullpeningunum í sem fæstum vigtunum?

Gagnvirkni

Þetta er gagnvirkt verkefni. Lausnin þín verður keyrð á móti gagnvirkum dómara sem les úttakið frá lausninni þinni og skrifar í inntakið á lausninni þinni. Þessi gagnvirkni fylgir ákveðnum reglum:

Lausnin þín skal fyrst lesa inn eina línu með einni heiltölu $n$. Í földu prufutilvikunum mun $n$ alltaf vera $1\, 024$, en í sýnidæmunum er $n$ lægra.

Því næst má lausnin þín annað hvort gefa lokasvar eða spyrja spurninga til að öðlast upplýsingar.

Til að spyrja spurningu skal lausnin þín skrifa út línu sem hefst á tákninu ? og svo $n$ heiltölur aðskildar með bilum, sem tákna hversu marga gullpeninga úr hverjum stafla þú setur á vigtina. Lausnin þín skal svo lesa inn eina línu með einni heiltölu, þyngd gullpeninganna sem voru settir á vigtina.

Þegar lausnin þín hefur ákvarðað hvaða stafli er með alvöru gullpeninga, skal hún skrifa út táknið !, eitt bil og svo eina heiltölu sem táknar númerið á staflanum. Staflarnir eru númeraðir frá $1$ upp í $n$. Ef svarið er rangt verður lausnin dæmd röng, annars getur hún fengið stig eins og er lýst hér að neðan.

Með verkefninu fylgir tól sem viðhengi til þess að hjálpa við að prófa lausnina þína.

Stigagjöf

Lausnin þín verður keyrð á mörgum prufutilvikum og versta niðurstaða yfir öll prufutilvik mun gilda til stigagjafar. Lausnin þín fær stig út frá fjölda spurninga sem hún spyr. Ef lausnin spyr minna en $2n$ spurningar fær hún stig. Færri fyrirspurnir gefa fleiri stig og mest er hægt að fá $100$ stig. Ef lausnin þín spyr $2n$ eða fleiri spurningar verður hún dæmd röng.

10

? 10 10 10 10 10 10 10 10 10 10

1010

? 0 0 0 0 0 5 0 0 0 0

50

? 0 0 0 10 0 0 0 0 0 0

110

! 4