시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 613 | 525 | 460 | 87.121% |
천하제일코딩대회를 마치고 $N$명의 운영진은 회전 초밥집으로 회식을 가서 스시를 먹기로 했다. 이 식당에는 총 26가지의 스시가 있으며, 이는 문자 A
부터 Z
까지에 대응하여 생각할 수 있다.
회전 초밥집은 아래 그림과 같이 $N+1$개의 의자와 $N+1$개의 접시로 이루어져 있다. 사람들은 계속 자신의 자리에 앉아 있으며, 매 분마다 접시들은 시계방향으로 한 칸씩 이동한다.
$S_0$에는 셰프가 앉아 있으며, 매 분마다 셰프는 자신 앞에 온 접시가 비어있지 않으면 아무 행동도 하지 않고, 자신 앞에 온 접시가 비어있으면, 한 점의 스시를 만들어 접시에 올린다. 하지만, 현재 상태에서 셰프가 더 이상 스시를 만들지 않아도 모든 손님이 유한한 시간안에 식사를 마칠 수 있음이 보장된다면, 셰프는 더 이상의 스시를 만들지 않는다.
$N$명의 대회 운영진은 각각 $S_1, S_2, \cdots, S_N$의 자리 중 한 곳에 앉았고, 그들 외의 손님은 없다고 가정한다. $N$명의 대회 운영진 각각은 자신이 오늘 먹고 싶은 스시의 목록이 있고, 목록에 있는 순서대로 먹고자 한다.
매 분마다 각 손님(대회 운영진)은 다음과 같이 행동한다:
초기에 모든 접시는 비어있고, 손님들이 식사를 시작하는(모두 자리에 앉은) 시점부터 셰프는 음식을 만든다고 가정한다.
모든 손님들이 유한한 시간 안에 식사를 마치기 위해 셰프가 만들어야 하는 스시의 최소 개수를 구하여라.
입력의 첫 줄에 $N$이 주어진다.
이후 $i (1 \le i \le N)$번째 줄에는 손님 $i$가 먹고 싶어하는 스시의 목록을 나타내는 문자열 $B_i$가 주어진다.
한 종류의 스시가 한 손님의 목록에 두 번 이상 속할 수 있음에 유의하라.
문제의 답을 나타내는 정수 하나를 출력한다.
2 ABCDE FGH
8
1 ABCDE
5
High School > 선린인터넷고등학교 > 제4회 천하제일 코딩대회 예선 C번