|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||128 MB||18||13||13||81.250%|
Farmer John wants to position N (1 <= N <= 100,000) cows and bulls in a single row to present at the annual fair.
FJ has observed that the bulls have been quite pugnacious lately; if two bulls too close together in the line, they will argue and begin to fight, ruining the presentation. Ever resourceful, FJ calculated that any two bulls must have at least K (0 <= K < N) cows between them in order to avoid a fight.
FJ would like you to help him by counting the number of possible sequences of N bulls and cows that avoid any fighting. FJ considers all bulls the to be the same and all cows to be the same; thus, two sequences are only different if they have different kinds of cattle in some position.
The following are the six possible sequences FJ could create (note that 'C' stands for cow and 'B' stands for bull):
CCCC BCCC CBCC CCBC CCCB BCCB