루미 알고리즘

#1317플래티넘Räkneord

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

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

Problem

Monika skriver ner alla räkneord mellan 1 och N. Sedan sorterar hon orden alfabetiskt och konkatenerar dem till en enda lång sträng. Skriv ett program som hittar bokstav nummer K, K+1 och K+2 i Monikas sträng.

För att undvika problem med teckenkodning byter vi ut å och ä mot a. Vidare använder vi formerna etthundra, ettusen (observera stavningen), enmiljon och enmiljard, men bara när siffran 1 står ensam före mängdordet (ej inräknat tidigare mängdord). När siffran 1 däremot står sist i ett förled som betecknar flera tusen, miljoner eller miljarder så skriver vi för enkelhets skull alltid “en”: tjugoentusen, etthundraenmiljoner, tvahundraattioenmiljarder etc. Allra sist i ett räkneord skriver vi dock alltid siffran 1 som “ett”.

En tabell med de grundläggande räkneorden och några exempel på längre ord bringar förhoppningsvis klarhet i reglerna:

TalRäkneordTalRäkneord
1ett10tio
2tva20tjugo
3tre30trettio
4fyra40fyrtio
5fem50femtio
6sex60sextio
7sju70sjuttio
8atta80attio
9nio90nittio
11elva100etthundra
12tolv198etthundranittioatta
13tretton201tvahundraett
14fjorton1121ettusenetthundratjugoett
15femton581743femhundraattioentusensjuhundrafyrtiotre
16sexton51101001femtioenmiljoneretthundraentusenett
17sjutton162500020etthundrasextiotvamiljonerfemhundratusentjugo
18arton1002001004enmiljardtvamiljonerettusenfyra
19nitton91011091000nittioenmiljarderelvamiljonernittioentusen

Och som en ytterligare kontrollmöjlighet ger vi längden på Monikas sträng för några olika N:

NSträngens längd
99916260
9999235600
999992908000
99999937425000
9999999472250000
999999995319500000
99999999961585000000
9999999999722850000000
999999999997834500000000
99999999999986744000000000

Indata

En rad med två heltal N och K, där 1 ≤ N < 10^12 och 1 ≤ K ≤ L-2, där L är längden på den bildade strängen.

Utdata

En rad med tre bokstäver utan åtskiljande blanksteg: bokstav nummer K, K+1 och K+2 i strängen.

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
115N ≤ 2000
220N ≤ 5*10^5
330N = 999999999999
435Inga ytterligare begränsningar.

Förklaring till första exemplet

Monikas sträng, skriven med 40 bokstäver per rad, är

artonattaelvaettfemfemtonfjortonfyranion
ittonsexsextonsjusjuttontiotjugotjugoett
tjugofemtjugofyratjugosextjugotretjugotv
atolvtretrettontva

예제

예제 1

입력
26 120
출력
vat

예제 2

입력
105 508
출력
ase

예제 3

입력
426760 11111111
출력
atr

출처 표기

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