루미 알고리즘

#1323다이아Udda mullvadar

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

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

Problem

Axel har en oändlig endimensionell trädgård som löper över tallinjen. Eftersom han inte orkar lägga för mycket tid på att sköta om den (en oändlig trädgård kräver en hel del tid) så är den dock full med mullvadar. Närmare bestämt så bor det en mullvad på varje position x, där x är ett heltal (även negativa heltal). Vi kallar mullvaden på position x för m_x.

Detta stör inte Axel så länge mullvadarna är lugna och håller sig i sina bon, men då och då så får mullvadarna för sig att börja festa och allting spårar ur. En mullvadsfest går till på följande sätt:

  1. Vid tid t=0 startar några mullvadar festen genom att sticka upp sina huvuden ovanför marken och dansa på stället. Detta räknas för mullvadar som att vara aktiv i festen.
  2. För varje tidpunkt t > 0 så bestämmer sig varje mullvad för om de ska vara aktiva eller inte, baserat på hur festen såg ut vid tidpunkt t-1. Eftersom de gillar udda tal så kommer mullvad m_i att vara aktiv vid tidpunkt t om det vid tidpunkt t-1 var ett udda antal (1 eller 3) aktiva mullvadar i närheten. I närheten av m_i räknas dels m_i själv samt dess två grannar ett steg till höger respektive vänster, m_{i-1} och m_{i+1}.

För att Axel ska hinna stoppa festen i tid behöver han veta hur många mullvadar som kommer vara aktiva vid en viss tid t. Hjälp honom genom att räkna ut detta.

Indata

På första raden finns en sträng bestående av N (1 ≤ N ≤ 100) tecken som beskriver området där festen startar, “A” för en aktiv mullvad och “.” för en inaktiv. Notera att detta bara är området där festen startar, det är inte garanterat att festen stannar inom detta område.

Den andra innehåller talet t (0 ≤ t ≤ 10^18), antalet sekunder som festen pågår.

Utdata

Skriv ut ett tal: antalet aktiva mullvadar vid tid t.

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=1 och den första raden består av exakt ett 'A'.
280Inga ytterligare begränsningar.

Förklaring av exempelfall 1

Nedan följer en illustration av en exempelfest:

  • t=0: ..A.AAA..
  • t=1: .AA..A.A.
  • t=2: A..AAA.AA

예제

예제 1

입력
A.AAA
2
출력
6

예제 2

입력
.
1337
출력
0

예제 3

입력
.A.A..AAA.AA.A...AAA.A.A.A
537
출력
126

출처 표기

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