루미 알고리즘

#1275골드Tåget

PO 2004 결선코딩출제 Jimmy Mårdell, Håkan Strömberg, Pär Söderhjelm스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

Tåg kan genom olika vagnar komponeras på olika sätt. Här ska d u skriva ett program som tar reda på hur många. Våra tåg kan innehålla fyra olika typer av vagnar: postvagn (M), personvagn (P), restaurangvagn (R) och godsvagn (G). Loket räknas inte till vagnarna och ingår därför inte i våra kompositioner.

Följande regler gäller för sammansättningen:

  • Postvagn kan bara inleda tåget, kopplas direkt efter loket eller efter en annan postvagn. Det kan högst finnas två postvagnar, men behöver inte finnas någon.
  • Restaurangvagn måste alltid befinna sig mellan två personvagnar. Det kan finnas hur många som helst men behöver inte finnas någon.
  • Det måste finnas minst en personvagn och kan finnas hur många som helst.
  • Godsvagn kopplas alltid sist i tåget. En godsvagn kan endast ha en annan godsvagn efter sig. Det får finnas högst tre godsvagnar, men behöver inte finnas någon. Programmet ska fråga efter hur många vagnar tåget innehåller och därefter beräkna och skriva ut antalet olika tåg som kan komponeras.

Indata

Indata består av ett heltal 1 ≤ n ≤ 30 - antalet vagnar i tåget.

Utdata

Ditt program ska skriva ut antalet tåg som kan skapas.

예제

예제 1

입력
13
출력
1042

예제 2

입력
4
출력
13

출처 표기

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