루미 알고리즘

#1337골드Trevliga tal

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

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

Problem

Det svenska juniorlandslaget i programmering älskar att ha det trevligt när de är ute och reser. En som uppskattade trevlighet mer än någon annan var Mårten. Han hade dock inte samma bild av trevlighet som alla andra. För Mårten hade trevlighet en rent matematisk definition: ett visst tal är trevligt om och endast om det är delbart med 3.

Eftersom inte alla tal är trevliga så måste man förstås hitta sätt att göra dem trevliga på. Du kommer att få ett heltal, och ditt uppdrag är att hjälpa Mårten räkna ut på hur många sätt han kan göra talet trevligt genom att stryka vissa av siffrorna i talet. Han får dock inte stryka alla siffrorna och det resulterande talet får inte ha inledande nollor (dock anses talet 0 vara trevligt, så en ensam nolla är okej). Kom ihåg att ett tal är delbart med tre om och endast om dess siffersumma är delbar med tre.

Indata

På den första och enda raden i indata står ett heltal (med upp till 100000 siffror). Talet innehåller endast siffror 0-9. Talet börjar inte med en nolla.

Utdata

Ditt program ska skriva ut ett enda tal på en rad: antalet olika sätt på vilket Mårten kan ta bort siffror ur talet så att det blir delbart med 3. Två sätt anses vara olika om indexen där siffror tagits bort skiljer sig. Eftersom svaret kan bli jättestort så ska du ska du skriva ut resten som uppstår då svaret divideras med en miljard.

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
120N ≤ 6 och svaret är mindre än en miljard
220N ≤ 20 och svaret är mindre än en miljard
320N ≤ 1000
440Inga ytterligare begränsningar

Förklaring av exempelfall

Förklaring av exempelfall 1: Mårten kan åstadkomma delbarhet på ett sätt, genom att stryka ettan i talet. Kvar blir då bara talet 3, som förstås är delbart med tre.

Förklaring av exempelfall 2: Mårten åstadkommer delbarhet genom att inte stryka någon siffra alls.

Förklaring av exempelfall 3: det går inte att skapa ett trevligt tal oavsett vad Mårten gör.

Förklaring av exempelfall 4: det går att skapa de trevliga talen 9, 192, 912 och 12, men det sistnämnda kan åstadkommas på två sätt: genom att stryka de två första siffrorna eller genom att stryka de två mittersta siffrorna.

Förklaring av exempelfall 5: det går att skapa de trevliga talen 0, 3, 12, 102, 123 och 1023.

예제

예제 1

입력
13
출력
1

예제 2

입력
9
출력
1

예제 3

입력
1
출력
0

예제 4

입력
1912
출력
5

예제 5

입력
1023
출력
6

예제 6

입력
8702004673
출력
294

출처 표기

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