Utskriftsvennlig versjon Hele brosjyren
Merk: Det er ikke nødvendig å løse alle oppgavene for å delta.
Sudokuoppgavene har nå herjet landet over lengre tid. Mange personer har kastet bort utallige timer på å finne de små tallenes riktige posisjoner. Det verste er når man nesten er ferdig, og så viser det seg at man har gjort en bitteliten feil slik at man nesten må starte på nytt igjen.
Du har bestemt deg for å gjøre slutt på denne frustrasjonen en gang for alle, ved å skrive et dataprogram som kan løse alle Sudokuer.
Skriv et program som tar et uferdig sudokubrett som input og skriver ut det ferdig løste brettet. Om det finnes flere mulige løsninger, er det nok å skrive ut én av dem.
Input- og output- spesifikasjoner
Input vil bestå av 9 linjer med 9 tall fra 0 til 9. (0 betyr tom rute.)
Output skal bestå av 9 linjer med 9 tall fra 1 til 9. Det skal være et gyldig utfylt sudokubrett hvor tallene fra input er på de samme plassene.
Eksempel
|
|
Sudokureglene
Kvadrater er et spill for to spillere som spilles på et rektangulært brett, som ligner på et meget stort sjakkbrett. Feltene er nummerert fra (1,1) i det nedre venstre hjørnet, til (1,w) i det nedre høyre hjørnet, og (h,w) på det øverste høyre hjørnet. h og w er henholdsvis høyden og bredden på brettet.
Et trekk består i å velge et fritt felt. Feltet utvides til høyre og oppover slik at det former et størst mulig kvadrat uten at det inneholder noen felter som allerede er opptatt. Feltene i dette kvadratet tilhører nå spilleren som gjorde trekket, og er ikke lenger fritt.
For nybegynnere er det ofte en god strategi å velge ruten som gir det størst mulige kvadratet. Din oppgave er å skrive et program som finner dette feltet, gitt dimensjonene på et brett, og en sekvens med trekk som allerede er gjort.
Input-spesifikasjoner
Først tre heltall: 1 <= H <= 1000 høyde, 1 <= W <= 1000 bredde på brettet og 0 <= M <= 100 antall trekk som allerede er gjort. Deretter følger M linjer med to heltall rad (1 <= R <= H) og kolonne (1 <= C <= W) på hver linje, som beskriver trekkene som allerede er gjort.
Output-spesifikasjoner
Dersom ikke noe gyldig trekk er mulig, skriv ut "game over". Dersom det er mulig å gjøre et trekk, skriv ut tre heltall r, c og s. Der r er rad, c er kolonne, og s er sidelengden i det største mulige kvadratet. Hvis mer enn en løsning har samme sidelengde s, skriv ut den med minste r. Hvis det fortsatt er flere muligheter, skriv ut den med minst c.
Eksempel
| Input | Output | Kommentar |
|---|---|---|
8 8 4 8 1 3 6 1 4 2 1 |
5 2 4 |
Etter at de oppgitte trekkene er gjort, ser brettet slik ut: x....... ........ ........ .....xxx xxx..xxx xxx..xxx xxxxx... ...xx... |
500 1000 2 1 1 1 501 |
game over |
Alle feltene er allerede tatt. |
En av demningene i Opperland har sprunget lekk, og dalen nedenfor fylles med vann. Terrenget består mystisk nok av kvadratiske ruter som hver har en bestemt høyde over havet (mellom 0 og 9). Du vil få oppgitt et kart som viser høyden til hver rute i rutenettet. Demningen ligger på en av kantene til kartet, på koordinatene (ud, vd). Kartet er 0-indeksert, og (0, 0) ligger øverst til venstre slik at punkt (u, v) ligger på rad u + 1, kolonne v + 1; raden angis altså først. Vannhøyden over havet i reservoaret er w. Reservoaret er digert (vi antar at det inneholder en ubegrenset vannmengde), så vannet vil spre seg utover fra dette punktet så langt det kommer. Det sprer seg alltid fra ett punkt til alle nabopunkter (opp, ned, venstre og høyre - ikke på skrått - se eksempelet) som har høyde mindre enn w. Hvor mye volum vil fylles opp? Vannvolumet i en rute med høyde h er lik w–h. Merk at punktet der demningen stod, også blir dekket av vann.
NB: Teksten her er blitt endret pga. feil. Originalteksten var "punkt (u, v) ligger på rad v – 1, kolonne u – 1". Eksempelet er uendret (det var feil i forhold til den gamle teksten, men er riktig nå). Har du løst oppgaven i henhold til den gamle teksten, trenger du ikke å endre noe - vi vil ta hensyn til dette ved rettingen.
Det korrekte koordinatsystemet ser slik ut:
v ---------
0 1 2 3 4 5
u 0
| 1
| 2
| 3
| 4
Input-spesifikasjoner
Første linje: Høyden h og bredden b, 3 <= b,h <= 10000; Andre linje: ud vd; Tredje linje: w, 1 <= w <= 9. Så følger h linjer med b tegn, hvor hvert tegn er mellom 0 og 9 (inkludert) og angir terrengets høyde over havet. Terrenghøyden på (ud, vd) vil være mindre enn w, og alle punkter som ligger i ytterkanten av kartet (unntatt (ud, vd)) vil ha en høyde på minst w.
Output-spesifikasjoner
Eneste linje: Det resulterende vannvolumet på kartet.
Eksempel
| Input | Output | Kommentar |
|---|---|---|
5 6 0 3 3 443134 432234 322123 404124 344443 |
15 |
Vannet vil i eksempelet spre seg utover slik: ###.## ##..## #....# #.#..# ###### |
Du og mange av vennene dine står på forskjellige steder i en stor by. Gatenettet i byen ser ut som et stort rutenett, der alle kvartaler er kvadratiske og like store. Dere ønsker å møtes i et hvilket som helst av byens gatekryss, men dere vil gå minst mulig til sammen.
Alle gatekryssene har en koordinat (x, y) som er oppgitt i forhold til et "origo"-kryss (0, 0). x og y er alltid heltall. Man kan kun benytte gatene, det vil si at det er umulig å gå på skrå gjennom bygningene.
Input-spesifikasjoner
Første linje: N (antall personer), 1 <= N <= 100000
De neste N linjene: x y, koordinatene til en person, -10000 <= x,y <= 10000.
Output-spesifikasjoner
Én linje: x0 y0 (koordinatene til det gatekrysset der alle skal møtes slik at den totale lengden folk må gå, er minst mulig).
Hvis det finnes flere koordinater som gir minimal distanse, skal du velge den med lavest x. Hvis det fremdeles er flere mulige, velger du den med lavest y.
Eksempel
| Input | Output | Kommentar |
|---|---|---|
3 -2 -3 2 2 3 -2 |
2 -2 |
Den totale avstanden for person 1, 2 og 3 blir 5, 4 og 1, og 5 + 4 + 1 = 10 er den korteste avstanden. Bildet viser rutene til de tre vennene. |
NIO trenger en ny logo. En logo som vi alle kan like, en logo som er norsk, algoritmisk og morsom. Send inn ditt forslag, enten separat eller sammen med de andre løsningene, på e-post til nio *at* nio.ntnu.no. Alle deltagerne og dommerne i NIO-finalen stemmer over forslagene og velger den nye logoen. Vinneren mottar en spennende bokpremie!
Merk at dette ikke er en del av selve den innledende runden, så man får ikke poeng for å sende inn logo. Det er ikke nødvendig å sende inn en logo sammen med besvarelsen, og vi mottar også forslag fra personer som ikke deltar ellers.