레이팅 미적용농부 존은 가능한 한 많은 서로 다른 종류의 소를 수집하는 것을 좋아한다. 실제로 그는 생각할 수 있는 거의 모든 종류의 소를 수집했는데, N줄 (1 <= N <= 100)의 짧은 목록에 적힌 몇 가지만 예외이다. 목록은 다음과 같다.
Farmer John has no large brown noisy cow. Farmer John has no small white silent cow. Farmer John has no large spotted noisy cow.
목록의 각 항목은 짧은 형용사 목록으로 없는 소를 묘사하며, 각 항목은 같은 개수의 형용사를 포함한다 (이 경우 3개). 줄당 형용사 개수는 2..30 범위이다.
농부 존은 목록에 없는 다른 모든 가능한 형용사 조합에 해당하는 소를 가지고 있다. 이 예에서 첫 번째 형용사는 large 또는 small, 두 번째는 brown, white, spotted 중 하나, 세 번째는 noisy 또는 silent가 될 수 있다. 이는 2 x 3 x 2 = 12가지 서로 다른 조합을 만들며, 농부 존은 목록에 명시적으로 언급된 것을 제외한 각 조합에 해당하는 소를 가지고 있다. 이 예에서 large, white, noisy 소는 그의 9마리 소 중 하나이다. 농부 존은 소가 많아야 1,000,000,000마리라고 확신한다.
농부 존이 소들을 알파벳순으로 나열하면, 이 목록에서 K번째 소는 무엇인가?
부분 점수 기회: 이 문제의 10개 테스트 케이스 중 케이스 2..4는 농부 존의 목록에서 줄당 형용사가 최대 두 개이다. 케이스 2..6에서는 각 형용사가 정확히 두 개의 가능한 값을 가진다 (다른 모든 케이스에서는 각 형용사가 1개에서 N개 사이의 가능한 값을 가진다).
문제 제공: Brian Dean, 2013
첫째 줄: 두 정수 N과 K.
둘째 줄부터 1+N번째 줄까지: 각 줄은 "Farmer John has no large spotted noisy cow."와 같은 문장이다. 문장의 각 형용사는 최대 10개의 소문자로 이루어진 문자열이다. 마침표로 끝나는 문자열 "cow."를 보면 문장의 끝에 도달했음을 알 수 있다.
첫째 줄: 농장에서 K번째 소의 묘사.
nocow.in · 출력을 쓸 파일 nocow.out3 7
Farmer John has no large brown noisy cow.
Farmer John has no small white silent cow.
Farmer John has no large spotted noisy cow.small spotted noisyInput details: The input matches the sample given in the problem statement above. Farmer John would like to know the 7th cow on his farm, when listed in alphabetical order.
Output details: Farmer john has cows matching the following descriptions, listed in alphabetical order:
large brown silent large spotted silent large white noisy large white silent small brown noisy small brown silent small spotted noisy small spotted silent small white noisy
The 7th cow in this list is described as "small spotted noisy".
riseoj 작성
출처 올림피아드 > USACO > 2013-2014 > November > Silver