음머 언어

농부 존은 자신의 소들과 더 잘 소통하고 싶어서, 음머(moo) 언어를 배우기로 결심했다!

음머 언어는 사실 영어와 꽤 비슷하지만, 더 단순하다. 단어의 종류는 명사, 타동사, 자동사, 접속사의 네 가지뿐이다. 연속한 두 단어는 반드시 공백으로 구분되어야 한다. 문장 부호도 마침표와 쉼표의 두 종류뿐이다. 마침표나 쉼표가 단어 뒤에 올 때는 단어 바로 뒤에 붙으며, 다음에 다른 단어가 이어지면 공백이 뒤따른다.

문장은 다음 형식 중 하나를 따라야 한다:

• 유형 1: 명사 + 자동사.
• 유형 2: 명사 + 타동사 + 명사(들). 구체적으로, 타동사 뒤에는 적어도 하나의 명사가 와야 하며, 첫 번째 뒤따르는 명사를 제외한 모든 뒤따르는 명사 앞에는 쉼표가 있어야 한다.

두 문장 사이에 접속사를 놓으면 두 문장을 하나의 복합 문장으로 연결할 수 있다. 만들어진 복합 문장은 다른 문장이나 다른 복합 문장과 더 이상 연결될 수 없다. 모든 문장(또는 두 문장이 연결된 경우 복합 문장)은 마침표로 끝나야 한다.

농부 존은 \(N\)개의 단어, \(C\)개의 쉼표, \(P\)개의 마침표로 이루어진 단어장을 가지고 있다 (\(1 \leq P,C\le N \leq 10^3\)). 그는 단어나 문장 부호를 단어장에 나타난 횟수만큼만 사용할 수 있다. 가능한 한 많은 단어를 포함하는 문장들의 나열을 출력하도록 도와주자.

각 입력 파일은 이 문제의 독립적인 인스턴스 \(T\) (\(1\le T\le 100\))개를 포함한다.

출제자: Chongtian Ma

배점

• 입력 2-6: \(N\le 10\)
• 입력 7-11: \(N\le 100\)
• 입력 12-16: \(N\le 1000\)
• 5로 나눈 나머지가 2인 입력: 타동사가 없다.
• 5로 나눈 나머지가 3인 입력: 자동사가 없다.
• 5로 나눈 나머지가 4인 입력: 접속사가 없다.

출제자: Chongtian Ma

첫째 줄에 인스턴스의 개수 \(T\)가 주어진다. 각 인스턴스는 다음과 같이 주어진다:

첫째 줄에 세 정수 \(N\), \(C\), \(P\)가 주어진다.

다음 \(N\)개의 줄에는 각각 두 문자열이 주어진다. 첫 번째 문자열은 농부 존이 사용할 수 있는 단어 자체(길이 1 이상 10 이하의 소문자 문자열)이고, 두 번째 문자열은 noun, transitive-verb, intransitive-verb, conjunction 중 하나로, 단어의 종류를 나타낸다. 같은 단어가 농부 존의 단어장에 두 번 이상 나타날 수 있지만, 나타날 때마다 항상 같은 종류를 가진다.

첫째 줄에 가능한 최대 단어 개수를 출력한다.

둘째 줄에 가능한 최대 단어 개수를 갖는 문장들의 나열을 아무거나 출력한다. 유효한 나열이면 모두 정답으로 인정된다.

채점기는 공백에 민감하므로, 특히 각 줄의 끝에 불필요한 공백을 출력하지 않도록 주의하라.

riseoj 작성

출처 올림피아드 > USACO > 2022-2023 > US Open > Bronze