해결한 사람
0
명
정답률
0.00
%
시간 제한
2000
ms
메모리 제한
245
MB
Valentin은 "Shockers"라는 쇼에 참가한다. 규칙은 꽤 간단하다. 심사위원단은 Valentin이 모르는 글자 하나를 선택한다. 그는 짧은 연설을 해야 하지만, 선택된 글자가 포함된 단어를 말할 때마다 전기 충격을 받는다. 그는 어떤 글자가 선택되었는지 추측할 수 있지만, 틀린 추측을 할 때마다 역시 전기 충격을 받는다. Valentin이 선택된 글자를 정확히 맞히면 쇼가 끝난다.
Valentin은 모든 것을 기억할 수 없으므로, 선택된 글자를 유일하게 알아낼 수 있게 된 시점보다 훨씬 나중에야 그 글자를 추측하여 불필요한 전기 충격을 받을 수도 있다. 불필요한 전기 충격이란 선택된 글자를 유일하게 알아낼 수 있게 된 시점 이후에 Valentin이 받은 전기 충격을 뜻한다. 불필요한 전기 충격의 횟수를 구해야 한다.
첫 번째 줄에는 Valentin이 수행한 행동의 수를 나타내는 하나의 정수 n (1 ≤ n ≤ 105)이 주어진다.
다음 n개의 줄에는 그의 행동에 대한 설명이 주어지며, 각 줄에는 행동 하나에 대한 설명이 주어진다. 각 행동은 다음 세 가지 유형 중 하나이다:
모든 단어는 영어 소문자로만 이루어진다. 모든 단어의 길이의 합은 105를 초과하지 않는다.
마지막 행동은 선택된 글자에 대한 추측임이 보장된다. 또한 Valentin이 마지막 행동 전에는 선택된 글자를 정확히 추측하지 않았음이 보장된다. 더 나아가, Valentin이 어떤 단어를 말한 뒤 전기 충격을 받았다면 그 단어에는 선택된 글자가 포함되어 있으며, Valentin이 어떤 단어를 말한 뒤 전기 충격을 받지 않았다면 그 단어에는 선택된 글자가 포함되어 있지 않음이 보장된다.
선택된 글자를 유일하게 알아낼 수 있게 된 직후에 Valentin이 그 글자를 말했다면 피할 수 있었던 전기 충격의 횟수를 나타내는 하나의 정수를 출력한다.
7
! ababahalamaha
? a
? b
? a
? b
? a
? h
0
5
! abc
. ad
. b
! cd
? c
1
8
! hello
! codeforces
? c
. o
? d
? h
. l
? e
2
첫 번째 테스트 케이스에서는 첫 번째 행동 후 선택된 글자가 a, b, c 중 하나라는 것이 분명해진다. 두 번째 행동 후에는 선택된 글자가 a가 아님을 알 수 있다. Valentin은 "b"라는 단어를 말하고 전기 충격을 받지 않는다. 그 후 선택된 글자가 c라는 것이 분명해지지만, Valentin은 cd라는 단어를 말하여 불필요한 전기 충격을 받는다.
두 번째 테스트 케이스에서는 처음 두 번의 전기 충격 후 선택된 글자가 e 또는 o임을 알 수 있다. Valentin은 이 글자들로 이루어진 몇몇 단어를 시도하며, 두 번째 단어 후 선택된 글자가 e라는 것이 분명해지지만, 정확한 추측을 하기 전에 행동을 3번 더 수행한다.
세 번째 예제에서는 Valentin이 선택된 글자를 추측할 때에야 그 글자를 유일하게 알아낼 수 있으므로, 불필요한 전기 충격을 받지 않았다.