시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 155 24 9 36.000%

문제

디디가 좋아하는 랜덤게임 ~! 무슨 게임~! 게임 스타트 !!

딸기당근수박참외메론게임♪

디디대학에서의 딸기당근수박참외메론게임의 룰은 다음과 같은 규칙으로 진행된다.

  1. 게임에 쓰일 단어의 수 n과 박자 수 b를 정한다. 단, 박자수는 단어의 수보다 크거나 같아야 하며, 같은 단어가 여러 번 들어갈 수 있다.
  2. 앞서 정한 n만큼, 사용할 단어(S1, S2, ..., Sn)를 정한다.
  3. 각 i(1, 2, ...) 차례마다 단어들을 아래 코드와 같은 결과로 말해야 한다.
if(b == 1) printf("%s", S[1]);
else {
    if ((i - 1) % (2 * (b - 1)) + 1 < b) {
        for (int j = 1; j <= (i - 1) % (b - 1) + 1; j++) printf("%s ", S[(j - 1) % n + 1]);
    }
    else {
        for (int j = 1; j <= b - ((i - 1) % (b - 1)); j++)
            printf("%s ", S[(j - 1) % n + 1]);
    }
}

단어 집합 S는 번호가 1부터 시작됨에 유의하라.

예를 들어, n은 3, b는 5, 집합 S = {king, god, gd}일 때,

  • king
  • king god
  • king god gd
  • king god gd king
  • king god gd king god
  • king god gd king
  • king god gd
  • king god
  • king
  • king god
  • ...

각 차례마다 위와 같은 순서대로 말해야한다.

디디는 문득 게임내에서 임의의 단어 k가 외쳐진 횟수가 X번째가 될 때, 그 차례가 몇번 째 인지 궁금해지기 시작했다. 그런 디디의 궁금증을 해결해 줄 프로그램을 작성하라.

입력

첫째 줄에 n(1 ≤ n ≤ 2 × 105)과 b(n ≤ b ≤ 1012)가 주어진다.

둘째 줄에는 임의의 단어 k와 X(1 ≤ X ≤ 1012)가 주어진다.

셋째 줄에는 게임에 쓰일 단어 n개가 공백으로 구분되어 주어진다. 모든 단어는 알파벳 소문자로 구성되어 있으며, 각 단어의 길이는 10을 넘지 않는다.

출력

문제의 정답을 출력하라. 정답이 항상 존재하는 경우만 입력으로 주어지는 것이 보장된다.

예제 입력 1

3 5
king 8
king god gd

예제 출력 1

6

예제 입력 2

3 5
king 8
king god king

예제 출력 2

5

출처

Contest > 네블컵 > 제1회 네블컵 J번