스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
Ett antal excentriker från centrala New York har bestämt sig för att de har fått nog av det moderna samhället, och vill flytta därifrån. Tillsammans har de köpt en rektangulär bit mark långt borta, och ska nu bosätta sig där.
Marken består av N × M rutor, och det går att bygga högst ett hus på en given ruta. Varje ruta har ett värde a_{x,y} som beskriver hur trevlig den är, på en skala mellan 0 och 100. Excentrikernas mål är att komma så långt bort som möjligt från alla andra, inklusive varandra. Lyckan en excentriker upplever av att bygga sitt hus på ruta (x,y) är därmed a_{x,y} · d, där d är det minsta avstånd till någon annan person. Av vana använder sig excentrikerna av manhattanavstånd (https://sv.wikipedia.org/wiki/Manhattangeometri) för att mäta detta; d definieras alltså som min |x - x_2| + |y - y_2| över alla andra personers rutor (x_2, y_2).
Excentrikerna vill nu ha din hjälp med att placera sina hus optimalt, så att summan av lyckan de upplever är så hög som möjligt. Kan du hjälpa dem?
Indata
Indatan består av 10 testfall, som beskrivs längre ner.
Den första raden innehåller talet T (0 ≤ T ≤ 10), som beskriver numret på testfallet (0 för sample). Den andra raden innehåller talen N, M och K (1 ≤ N, M ≤ 1000, 2 ≤ K ≤ N · M) – höjden och bredden på markrutnätet, och antalet personer. De följande N raderna innehåller M heltal vardera – värdena a_{x,y} (0 ≤ a_{x,y} ≤ 100).
Utdata
Skriv ut K rader med husens positioner. Varje rad ska innehålla två tal: först raden för huset (mellan 1 och N), därefter kolumnen (mellan 1 och M). Två hus får inte placeras på samma position.
Poängsättning
Ditt program kommer att testas på 10 testfall, och poängsättas baserat på hur det står sig relativt alla andra deltagare. Om din inskickning på ett givet testfall får en summa av lycka som är X, och den bästa summan någon har uppnått på det testfallet är Y, så blir din poäng på det testfallet 10 · (X / Y)^2, avrundat till två decimaler.
Din poäng för en inskickning är summan av poängen för testfallen, och din totala poäng är poängen för den bästa inskickningen. Det går alltså inte att kombinera testfall mellan olika inskickningar, utan du måste skicka in ett enda program som maximerar din poäng på alla testfall samtidigt.
Under själva tävlingen kommer din poäng sättas relativt en domarlösning; efter att den slutat kommer alla lösningar att rättas om mot de bästa deltagarlösningarna. Om din lösning är bättre än den domarna slängt ihop är det därmed möjligt att du tillfälligt får mer än 10 poäng på ett testfall. Din (temporära) totalpoäng kommer dock att begränsas till 100.
Sampletestfallet kommer alltid att ge 0 poäng.
Förklaring av exampelfall
I exempelfallet vill vi placera ut två hus på ett 2 × 3 rutnät. Exempellösningen placerar ett av husen i det nedre vänstra hörnet och ett i det övre högra hörnet. Båda husens kortaste avstånd till något annat hus kommer då bli 2 + 1 = 3, och summan av lycka därmed 3 · 30 + 3 · 50 = 240.
Om det testfallet hade varit ett riktigt testfall och en annan deltagare placerat sina hus i det övre vänstra och nedre högra hörnet (vilket hade uppnått den högre lyckan 270) så hade testfallet getts 10 · (240 / 270)^2 ≈ 7.90 poäng.
Testfall
För att undvika att problemet blir en gissningslek kommer här beskrivningar av de 10 testfallen som förekommer:
| Testfall | Gränser | Rutnät |
| 1 | N = M = 100, K = 1000 | Alla värden a_{i,j} är samma. |
| 2 | N = M = 100, K = 500 | a_{i,j} är slumpmässig mellan 0 och 100. |
| 3 | N = 200, M = 1, K = 30 | a_{i,j} är slumpmässig mellan 0 och 100. |
| 4 | N = M = 1000, K = 40000 | a_{i,j} är slumpmässig mellan 0 och 100. |
| 5 | N = M = 100, K = 20 | a_{i,j} = min(100, max(0, i + r)), där r är slumpmässig mellan -5 och 5, och i är radnumret, nollindexerat. |
| 6 | N = M = 1000, K = 10000 | a_{i,j} = min(100, max(0, ⌊ 0.101 · i ⌋ + r)), där r är slumpmässig mellan -5 och 5. |
| 7 | N = M = 100, K = 500 | a_{i,j} = ⌊ 100 / r ⌉, där r är ett slumpmässigt flyttal mellan 1 och 200. |
| 8 | N = M = 100, K = 500 | a_{i,j} = ⌊ 100 / r^2 ⌉, där r är ett slumpmässigt flyttal mellan 1 och 200. |
| 9 | N = M = 1000, K = 40000 | a_{i,j} = ⌊ 100 / r^2 ⌉, där r är ett slumpmässigt flyttal mellan 1 och 200. |
| 10 | N = M = 100, K = 9 | Rutnätet består av enbart 1:or med 50 block av 0:or slumpmässiga utplacerade (överlappande; de flesta med storlek 10 × 10, några större). |
Med slumpmässig menas här likformigt slumpmässig (https://sv.wikipedia.org/wiki/Likformig_sannolikhetsf%C3%B6rdelning). ⌊ x ⌋ betecknar x avrundat nedåt, och ⌊ x ⌉ är x avrundat till närmsta heltal.
예제
예제 1
0 2 3 2 50 60 50 30 50 40
1 3 2 1