보름달 아래 소의 울음
시간 제한1초메모리 제한128 MB
초기값에서 시작해 두 개의 단조 증가 선형 바닥 함수를 모든 생성값에 반복 적용하며, 서로 다른 값들을 정렬했을 때 N번째 값을 구한다.
문제
보름달이 뜨면 소들은 사촌 격인 늑대나 코요테처럼 달을 향해 웁니다. 물론 하울링 대신 "음메(moo)" 소리를 냅니다.
각 "음메"는 일정한 시간 동안 지속됩니다. 짧은 울음은 길이가 1일 수도 있고, 긴 울음은 24나 심지어 1000000000 이상일 수도 있습니다(소는 마음만 먹으면 정말 길게 웁니다). 단, 어떤 울음도 길이가 2^63 이상이 되지는 않습니다.
소들의 울음에는 규칙이 있습니다. 먼저 베시(Bessie)가 첫 울음의 길이가 되는 정수 c(1 ≤ c ≤ 100)를 고릅니다.
그다음, 지금까지 나온 각 울음 길이에 아래 두 함수를 적용해 새로운 울음 길이를 만듭니다(나눗셈은 모두 내림 정수 나눗셈입니다).
f1(x) = a1 * x / d1 + b1
f2(x) = a2 * x / d2 + b2
새로 얻은 길이에 다시 두 함수를 적용하는 식으로 계속 진행하며, 지금까지 나온 모든 울음 길이를 오름차순으로 정렬한 하나의 목록으로 관리합니다. 이때 중복된 값은 하나만 남깁니다.
소들은 최대 N번(1 ≤ N ≤ 4000000) 울 수 있습니다. 정렬된 목록에서 앞에서부터 N번째 값, 즉 N번 우는 동안 나온 가장 긴 울음의 길이를 구하세요.
각 상수는 다음 조건을 만족합니다: 1 ≤ d1 < a1 ≤ 20, 0 ≤ b1 ≤ 20, 1 ≤ d2 < a2 ≤ 20, 0 ≤ b2 ≤ 20.
예를 들어 c = 3, N = 10이고 상수가 다음과 같다고 합시다.
a1 = 4 b1 = 3 d1 = 3
a2 = 17 b2 = 8 d2 = 2
첫 울음 길이는 c 값인 3입니다. 울음 길이 목록은 다음과 같이 만들어집니다.
1. c = 3 -> 3 6. f2(3) = 17*3/2 + 8 -> 33
2. f1(3) = 4*3/3 + 3 -> 7 7. f1(28) = 4*28/3 + 3 -> 40
3. f1(7) = 4*7/3 + 3 -> 12 8. f1(33) = 4*33/3 + 3 -> 47
4. f1(12) = 4*12/3 + 3 -> 19 9. f1(40) = 4*40/3 + 3 -> 56
5. f1(19) = 4*19/3 + 3 -> 28 10. f1(47) = 4*47/3 + 3 -> 65
10번째 값은 65이며, 이 입력에 대한 정답이 됩니다.
입력
- 첫째 줄: 공백으로 구분된 두 정수
c와N - 둘째 줄: 공백으로 구분된 세 정수
a1,b1,d1 - 셋째 줄: 공백으로 구분된 세 정수
a2,b2,d2
출력
- 첫째 줄:
N번째 울음의 길이를 나타내는 정수 하나