루미 알고리즘

#1332플래티넘Fiskspelet

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

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

Problem

Du spelar fiskspelet. Du är en fisk som ska äta mindre fiskar men aldrig får bli uppäten av större fiskar. Fiskarna ändrar aldrig storlek. Du får poäng för varje fisk du äter och självklart vill du ha så mycket poäng som möjligt.

Spelplanen kan ses som ett rutnät med H rader (numrerade från 1 till H) men obegränsat antal kolumner. Du befinner dig i kolumnen x=0 och kan bara röra dig vertikalt (uppåt och nedåt). De andra fiskarna rör sig däremot aldrig vertikalt utan börjar i en viss kolumn x>0 och flyter med konstant fart åt vänster (mot din kolumn).

Alla fiskar (även du) har bredden 1 ruta. Din höjd är 7. Det finns tre andra sorters fiskar: ”liten” med höjd 3, ”mellan” med höjd 5 och ”stor” med höjd 9. Fiskarna har olika hastigheter. Varje sekund kan du röra dig en ruta uppåt eller nedåt (eller stå stilla). På samma tid rör sig en liten fisk 1 ruta, en mellanfisk 2 rutor och en stor fisk 3 rutor åt vänster. Du väljer själv på vilken höjd-nivå din fisk ska börja, men observera att hela fisken alltid måste vara inom spelplanen.

En fisk kan äta fiskar som är mindre än den själv. Du kan alltså äta fiskar av storlek 3 och 5, och får då 10 respektive 20 poäng. Men fiskar av höjd 9 kommer att äta upp dig, och du måste akta dig för dem. Skulle du bli uppäten förlorar du. För att det inte ska bli orättvist vem som äter vem så har sjöjungfrun Arashiel bestämt att följande sker i varje diskret sekundsteg:

  1. Du gör ditt drag (flyttar upp, ner, eller stannar kvar).
  2. Stora fiskar avancerar tre steg, mellan-fiskar avancerar två steg och små fiskar avancerar ett steg.
  3. Stora fiskar äter mellan- och småfiskar (eller dig) om de är i samma kolumn och överlappar vertikalt (minst en ruta gemensam).
  4. Mellanfiskar som överlevt äter småfiskar om de är i samma kolumn och överlappar vertikalt.
  5. Du äter små- och mellanfiskar om de är i din kolumn (x=0) och överlappar vertikalt.

Indata

På första raden står två heltal, N (1 ≤ N ≤ 50000), antalet fiskar, och H (20 ≤ H ≤ 1000), höjden på banan.

Sedan följer N rader, en för varje fisk. På varje rad står först en bokstav, L/M/S, alltså om fisken är liten, mellan eller stor. Därefter följer kolumnen x som fisken startar på (2 ≤ x ≤ 10^16), samt vilken rad y som utgör fiskens mellersta ruta (alltid vald så att hela fisken får plats inom intervallet [1, h]). De tre värdena åtskiljs med blanksteg.

Dessutom gäller att:

  • Inga fiskar i indata kommer överlappa varken helt eller delvis (initialt).
  • x-koordinaten för varje fisk kommer alltid att vara jämn. För den större fiskstorleken kommer den även alltid att vara delbar med 3. Detta eftersom vi vill att alla krockar ska ske på heltalskoordinater.
  • Du kommer alltid kunna klara dig från att bli uppäten, dvs spelet har alltid en lösning.

Utdata

Skriv ut en rad med ett enda heltal, antalet poäng du får om du spelar spelet optimalt.

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ängGränser
120N ≤ 1000, H ≤ 50, x ≤ 10000
220H ≤ 50, inga fiskar äter upp varandra
320H ≤ 50, mellanfiskar äter aldrig småfiskar
420H ≤ 50
520Inga ytterligare begränsningar.

Förklaring av exempelfall

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

Figur 1: Situationen i exempelfall 1

En möjlig lösning till det första exemplet visas i figur 1. De heldragna färgade rektanglarna visar fiskarnas utgångspositioner och de streckade rektanglarna visar deras positioner efter 4 respektive 8 sekunder. Den svarta rektangeln visar en av flera optimala utgångspositioner för dig. I detta fall kan du helt enkelt stå stilla och invänta den gröna mellanfisken.

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

Figur 2: Situationen i exempelfall 2

En möjlig lösning till det andra exemplet visas i figur 2. Den svarta rektangeln visar var du måste befinna dig vid tiden t=4 sekunder när du äter den blå lilla fisken (det går bra att även ha detta som utgångsposition). Den delade rutan markerar att fiskarna överlappar på denna ruta. Sedan måste du röra dig i full fart uppåt för att kunna äta den gröna mellanfisken vid t=11 (din position visas då av den grå streckade rektangeln). Slutligen måste du fortsätta uppåt för att undkomma den röda stora fisken som når din kolumn vid t=14 (detta skulle bli för kladdigt att visa i figuren).

예제

예제 1

입력
3 20
L 4 2
S 30 8
M 20 18
출력
20

예제 2

입력
3 20
L 4 2
S 42 8
M 22 18
출력
30

예제 3

입력
2 20
L 6 3
L 6 12
출력
10

예제 4

입력
4 20
L 10 6
L 20 5
L 30 7
M 40 6
출력
30

예제 5

입력
3 20
L 18 3
L 16 9
M 20 6
출력
20

예제 6

입력
3 20
L 12345678901234 3
L 12345678901234 9
M 12345678901232 6
출력
40

예제 7

입력
3 20
L 12345678901234 3
L 12345678901234 9
M 12345678901236 6
출력
20

출처 표기

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