루미 알고리즘

#1417플래티넘Kubiska boxar

PO 2017 결선코딩출제 Arash Rouhani스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

Din syssling Paulo R älskar boxar. Just nu är du på väg att fira jul hos Paulo (traditionsenligt firar du jul en gång med varje del av din släkt, som just nu består av 72 olika familjer). Tyvärr har du precis insett att du glömt att köpa julklappar!

Eftersom Paulo älskar boxar, är detta precis vad du tänker köpa till honom. En box är kubisk med en viss sidlängd, och har en av tre färger – röd (R), grön (G) eller blå (B). Du har skrivit ner en inköpslista med alla boxar du tänker köpa. Tyvärr säljs boxarna i tre olika butiker, där varje butik säljer boxar av en viss färg.

Din plan är nu att åka till alla tre butiker för att köpa de nödvändiga boxarna. För att spara plats i baggageutrymmet tänker du placera vissa av boxarna i varandra. Om du besöker butikerna i ordningen f_1, f_2, f_3, (t.ex. R, G, B) så får du placera boxar av färgen f_3 i boxar av färgen f_2, och boxar av färgen f_2 i boxar av färgen f_1. Ordningen R, G, B innebär alltså att Paulo kan placera blåa boxar i gröna boxar, och gröna boxar i röda boxar. Du får inte placera boxar av färgen f_3 i boxar av färgen f_1 – det hade ju varit helt absurt. Dessutom kan en box bara placeras i en box som har en strikt större sidlängd.

(그림은 원문 저장소에서 볼 수 있습니다)

Figur 1: En möjlig lösning till exempel 3. Till vänster en grön box är placerad i en röd box som är placerad i en blå box. Till höger en grön box placerad i en röd box.

Kan du avgöra i vilken ordning du ska besöka butikerna, för att minimera antalet ytterboxar (d.v.s. boxar som inte ligger inuti en annan box), om du placerar boxarna optimalt?

Indata

Indatan börjar med talet N, antalet boxar, där 1 ≤ N ≤ 1000. Därefter följer N rader med sidlängd l_i (1 ≤ l_i ≤ 10000000) och färg f_i (R, G, eller B) för varje box.

Utdata

Du ska skriva ut två rader. Den första raden ska innehålla den ordning du besöker butikerna i, på formen f_1 f_2 f_3. Den andra raden ska bestå av ett heltal – det minsta antalet ytterboxar du kan åstadkomma efter att du stoppat in boxarna i varandra.

Om flera ordningar ger samma minimala antal ytterboxar, kan du skriva ut vilken av dessa ordningar som helst.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

GruppPoängvärdeGränser
150Du kommer alltid besöka butikerna i ordningen B G R
250Inga begränsningar.

Förklaring av exempel 3

En möjlig lösning är illustrerad i Figur 1. Den optimala ordningen är att besöka butikerna i ordningen blå, röd, grön.

Vi kan då lägga de två G-boxarna (storlek 1) i varsin R-box (storlek 10). Därefter kan den ena R-boxen läggas i en B-box. Kvar återstår då en R-box och en B-box som ytterboxar.

예제

예제 1

입력
3
15 B
10 G
5 R
출력
BGR
1

예제 2

입력
4
100 B
10 R
10 R
5 G
출력
BRG
2

예제 3

입력
5
100 B
10 R
10 R
1 G
1 G
출력
BRG
2

예제 4

입력
9
1 R
1 G
1 B
4 R
5 G
6 B
4 R
5 G
6 B
출력
BGR
5

출처 표기

출처: Programmeringsolympiaden 2017년 결선 · 원문 페이지 · 이용 조건 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.