루미 알고리즘

#1490플래티넘Tågresan

PO 2020 훈련 캠프코딩출제 Björn Magnusson스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

En grupp personer ska åka tåg och funderar hur de ska sitta. M par av personerna är vänner och vill sitta så nära varandra som möjligt. Tågvagnen de ska sitta i har N rader och är utformad som ett N × 4 rutnät, med 4 platser på varje rad. Det finns 4N personer i gruppen. Personerna är numrerade 1 till 4N.

Varje par av vänner som sitter på platser med euklidiskt avstånd L = √(dx^2 + dy^2) bidrar med 1/L^2 till gruppens totala lycka. Din uppgift är att placera ut personerna så att gruppens lycka blir så stor som möjligt.

Indata

Indatan består av 10 testfall.

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 och M (1 ≤ N ≤ 25000, 1 ≤ M ≤ 100000), antalet rader i tågvagnen samt antalet par av vänner. De följande M raderna innehåller två heltal a och b (1 ≤ a,b ≤ 4N, a ≠ b), nummer för två vänner.

Utdata

Skriv ut N rader med 4 heltal på varje. Varje rad ska innehålla nummer för de fyra personer som sitter på den raden. Alla personer ska placeras ut någonstans.

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 8 personer i ett 2 × 4 rutnät. Exempellösningen optimerar avståndet för alla vänskapsrelationer utom 1 och 4 som sitter på avstånd √3 från varandra. Summan av lycka blir 4 · 1/1 + 1/3 ≈ 4.33.

En bättre lösning kan fås till så att alla par av vänner sitter på avstånd 1. Om det testfallet have varit ett riktigt testfall och en annan deltagare hade genererat denna lösning (total lycka 5) så hade testfallet getts 10 · (4.33 / 5)^2 ≈ 7.51 poäng.

Testfall

Här är beskrivningar av de 10 testfallen som förekommer:

TestfallGränserBeskrivning av testfall
1N = 10, M = 100Alla kanter är genererade slumpmässigt.
2N = 100, M = 500Alla kanter är genererade slumpmässigt.
3N = 100, M = 8000Alla kanter är genererade slumpmässigt.
4N = 8000, M ≤ 45000G är uppbyggd av grupper av vänner i storlek 1-5 där alla känner alla.
5N = 2500, M = 8000G innehåller inga cykler. Det maximala avståndet i G är 2.
6N = 2500, M = 9800G innehåller inga cykler. Det maximala avståndet i G är 2.
7N = 2500, M = 9999G innehåller inga cykler.
8N = 25000, M = 99999G innehåller inga cykler.
9N = 10000, M = 100000Alla kanter är genererade slumpmässigt.
10N = 25000, M = 100000Alla kanter är genererade slumpmässigt.

Med slumpmässig menas här likformigt slumpmässig (https://sv.wikipedia.org/wiki/Likformig_sannolikhetsf%C3%B6rdelning). Grafen av vänskapsrelationer kallas G i vissa av beskrivningarna.

예제

예제 1

입력
0
2 5
5 7
8 7
1 2
2 3
1 4
출력
6 5 7 8
1 2 3 4

출처 표기

출처: Programmeringsolympiaden 2020년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.