레이팅 미적용농부 존(Farmer John)은 가능한 한 많은 서로 다른 유형의 소를 모으는 것을 좋아한다. 실제로 존은 생각할 수 있는 거의 모든 유형의 소를 모았는데, 몇 가지만 없다. 없는 유형들은 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가지의 서로 다른 조합이 있으며, 농부 존에게는 목록에 명시된 것들을 제외한 각 조합에 해당하는 소가 있다. 농부 존은 자신의 소가 최대 1,000,000,000마리라고 확신한다.
농부 존이 소들을 알파벳순으로 나열한다면, 이 목록에서 K번째 소는 무엇인가?
(이 문제는 USACO 2013년 11월 대회 브론즈 3번 및 실버 1번 문제로 동일하게 출제되었다. 형용사 값들의 상대적 순서는 입력에 처음 나타나는 순서로 결정된다.)
첫째 줄: 두 정수 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 noisyOutput details: The 7th cow in alphabetical order is described as "small spotted noisy".
riseoj 작성
출처 올림피아드 > USACO > 2013-2014 > November > Bronze