루미 알고리즘

#1398플래티넘Video Clips

PO 2016 훈련 캠프코딩출제 Johan Sannemo영어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

On a popular web site, the N KATT contestants can spend time watching video clips in between solving problems.

On the site, there are K funny videos of cats jumping around on the keyboard, numbered between 0 and K - 1. When one of the videos has been viewed, a suggestion for the next funny cat video is shown, which you of course click on and start watching.

For each contestant, you will be given the initial cat video he or she views. Determine what the M:th video that each contestant watches will be.

Example

In total, there are N = 2 contestants, and K = 4 cat videos. The suggestion for each of the videos are (3, 2, 1, 0). The first contestant starts to watch video 3, and the second starts to watch video 1. We wonder what the M = 3:rd clip each contestant views is.

The first contestant will start by watching video 3. From there, she looks at the suggested video 0, and is then led back to video 3.

The second contestant starts out with the second video, which links to the third video. Video 2 has video 1 as suggestion, so he ends up back on video 1.

Task

Your task is to compute, for each contestant, what the M:th video he or she will watch is. You will implement the functions videos(K, M, S) and clip(I).

• videos(K, M, S) - this function will be called exactly once by the judge at the start of the execution.

  • K: the number of funny cat videos.
  • M: the number of videos each contestant will watch.
  • S: an array with K elements. S[i] (0 ≤ i < N) contains the suggested video for the i:th video.
  • 0 ≤ S[i] < K
  • The function has no return value.

• clip(I) - this function will be called once for every contestant.

  • I: a number between 0 and K - 1; the video that a contestant starts watching.
  • The function should return the M:th video the contestant will watch, if she starts on video I.

A code skeleton containing the functions to be implemented, together with a sample grader, can be found at http://progolymp.se/uploads/kattis-attachments/videoclips.zip.

Subtasks

The problem consists of a number of subtasks. Each subtask gives some amount of points, and to pass the subtask you must pass all the test cases in the subtask.

Let N be the number of calls to clip(I).

SubtaskPointsLimits
115N, K ≤ 100000, 2 ≤ M ≤ 10^9, the i:th video will only suggest videos j such that j ≤ i.
215N, K ≤ 100000, 2 ≤ M ≤ 10^9, all videos will suggest each other in a cycle (e.g 3 suggest 2 suggest 0 suggest 1 suggest 3, för N = 4).
315N, K ≤ 1000 2 ≤ M ≤ 1000
415N, K ≤ 1000, 2 ≤ M ≤ 10^9
540N, K ≤ 100000, 2 ≤ M ≤ 10^9

Input format

The sample judge reads input in the following format:

  • line 1: K M
  • line 2: S[0] ... S[K - 1]
  • line 3: N: the number of calls made to clip(I).
  • line 4 I1 ... IN: the parameters of the N calls to clip(I).

Output format

The sample judge will write N lines with the return values of clip(I).

예제

예제 1

입력
4 2
3 2 1 0
2
3 1
출력
0 2 

출처 표기

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