실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 512 MB |
승훈은 아이들에게 철자 연습을 가르치려고 합니다. 그는 단어와 그림이 적힌 카드를 사용합니다. 각 카드는 양면에 서로 다른 단어가 적혀 있습니다.
카드를 바닥에 펼쳐 놓으면 한쪽 면의 단어만 볼 수 있습니다. 승훈은 아이들이 바닥에 펼쳐진 단어를 나무 블록으로 철자할 수 있도록 하려고 합니다. 각 나무 블록에는 알파벳 한 글자씩 적혀 있습니다.
문제는 바닥에 펼쳐진 단어들을 철자할 수 있도록 충분한 알파벳 블록을 준비해야 합니다. 그리고 카드를 뒤집어서 다른 단어가 나타나면 그 단어도 철자할 수 있어야 합니다.
여러분이 할 일은 각 알파벳 글자에 필요한 블록의 최소 개수를 알아내는 것입니다. 이렇게 하면 승훈이 카드를 뒤집을 때마다 아이들이 모든 단어를 철자할 수 있게 됩니다.
첫 번째 줄에는 정수 N이 들어갑니다.
다음 N줄 각각에는 보드의 양면에 있을 두 단어가 공백으로 구분되어 입력됩니다. 각 단어는 최대 10개의 소문자로 이루어져 있습니다.
총 26줄을 출력합니다. 첫 번째 출력 줄에는 필요한 'a' 블록의 수를 나타내는 숫자가 있어야 합니다. 다음 줄에는 'b' 블록의 수가 있어야 하며, 이런 식으로 계속됩니다.
3 fox box dog cat car bus
2 2 2 1 0 1 1 0 0 0 0 0 0 0 2 0 0 1 1 1 1 0 0 1 0 0
이 예제에서, 개의 철자판이 있으므로 가지의 단어 조합이 있습니다:
여우 개 자동차
여우 개 버스
여우 고양이 자동차
여우 고양이 버스
상자 개 자동차
상자 개 버스
상자 고양이 자동차
상자 고양이 버스
우리는 이 여덟 가지 시나리오 중 어느 하나가 발생하더라도 모든 세 단어를 철자할 수 있도록 최소한 알파벳의 각 글자를 위한 충분한 블록들이 필요합니다.
출처: USACO 2016 December Contest, Bronze Problem 2. Block Game