레이팅 미적용농부 존은 유치원생들이 흔히 쓰는 철자 판 \(N\)개(\(1 \leq N \leq 100\))를 소들에게 주어 글 읽기를 가르치려 하고 있다. 각 판의 양면에는 각각 단어 하나와 그림 하나가 있다. 예를 들어 한 면에는 고양이 그림과 함께 단어 'cat'이, 다른 면에는 개 그림과 함께 단어 'dog'이 있을 수 있다. 판들이 바닥에 놓여 있으면 \(N\)개의 단어가 보인다. 일부 판을 뒤집으면 또 다른 \(N\)개의 단어 집합이 드러날 수 있다.
소들의 철자 공부를 돕기 위해, 농부 존은 알파벳 한 글자가 새겨진 나무 블록을 여러 개 만들려고 한다. 위를 향한 판들에 어떤 \(N\)개의 단어 집합이 보이더라도 소들이 블록으로 그 단어들을 모두 만들 수 있도록, 각 글자의 블록을 충분히 많이 만들고 싶다. 예를 들어 \(N=3\)이고 단어 'box', 'cat', 'car'가 위를 향하고 있다면, 소들에게는 최소한 'b' 블록 1개, 'o' 블록 1개, 'x' 블록 1개, 'c' 블록 2개, 'a' 블록 2개, 't' 블록 1개, 'r' 블록 1개가 필요하다.
각 판의 어느 면이 보이더라도 소들이 보이는 \(N\)개의 단어를 모두 만들 수 있도록, 농부 존이 준비해야 하는 알파벳 각 글자별 블록의 최소 개수를 구해 도와주자.
문제 출제: 빅토리아 슈워츠(Viktoriia Schwartz)
문제 출제: 빅토리아 슈워츠(Viktoriia Schwartz)
첫째 줄에 정수 \(N\)이 주어진다.
다음 \(N\)개의 줄에는 공백으로 구분된 두 단어가 주어지며, 이는 한 판의 양면에 적힌 두 단어이다. 각 단어는 길이가 최대 10인 소문자 알파벳 문자열이다.
26개의 줄을 출력한다. 첫째 줄에는 필요한 'a' 블록의 개수를 출력한다. 다음 줄에는 필요한 'b' 블록의 개수를 출력하고, 이후도 같은 방식으로 이어진다.
blocks.in · 출력을 쓸 파일 blocks.out3
fox box
dog cat
car bus2
2
2
1
0
1
1
0
0
0
0
0
0
0
2
0
0
1
1
1
1
0
0
1
0
0In this example, there are \(N = 3\) boards, giving \(2^3 = 8\) possibilities for
the set of upward-facing words:
fox dog car
fox dog bus
fox cat car
fox cat bus
box dog car
box dog bus
box cat car
box cat bus
We need enough blocks for each letter of the alphabet so that we can spell all
three words, irrespective of which of these eight scenarios occurs.
riseoj 작성
출처 올림피아드 > USACO > 2016-2017 > December > Bronze