[Silver II] 이 사람 왜 이렇게 1122를 좋아함? - 26597

문제 링크

성능 요약

메모리: 110760 KB, 시간: 148 ms

분류

구현

제출 일자

2026년 04월 25일 22:04:59

문제 설명

ZOAC 5 대회 개최를 위해 준성이가 만든 문제를 검수하던 준호는 문뜩 그런 생각이 들었다.

'이 사람 왜 이렇게 1122를 좋아함?'

하지만 사실 준성이의 최애 수는 1122가 아니다!!!

준성이의 최애 수에 대해 알려진 사실은 구간 $\left[-10^{18}, 10^{18}\right]$에 있는 정수 중 하나라는 것뿐이다.

아무래도 이 사실을 믿을 수 없는 준호는 준성이에게 최애 수가 뭔지에 대해서 질문을 하려고 한다. 질의응답은 다음과 같이 이루어진다.

1. 준호가 구간 $\left[-10^{18}, 10^{18}\right]$에 있는 정수를 하나 제시한다.
2. 준성이는 최애 수가 제시한 수보다 크다면 up, 작다면 down을 외친다.
3. 준호가 제시한 수가 최애 수와 똑같은 경우는 절대 일어나지 않는다.

준호와 준성이의 검수는 아직 끝나지 않았기 때문에, 질의응답은 $Q$번만 하고 마저 검수를 하러 갔다.

대회가 시작된 지금 준호는 참가자들의 질문을 받느라 정신이 없다! 바쁜 준호를 위해 질의응답 내용을 확인하여 준성이의 최애 수를 대신 알아보도록 하자!

입력

첫째 줄에 질의응답을 진행한 횟수 $Q$가 주어진다. $\left(1 \leq Q \leq 111\,222\right)$

다음 $Q$ 개의 줄에 걸쳐서 질의응답에 대한 정보가 x ^또는 x v와 같은 형태로 한 줄에 하나씩 순서대로 주어진다. $\left(-10^{18} \leq x \leq 10^{18}\right)$

x ^은 준성이의 최애 수가 $x$보다 크다는 것을 의미하고, x v는 준성이의 최애 수가 $x$보다 작다는 것을 의미한다.

주어지는 수는 모두 정수다.

출력

질의응답에 모순된 내용이 있다면 첫째 줄에 Paradox!를 출력하고, 둘째 줄에 처음으로 모순이 발견된 질의응답이 몇 번째인지 출력한다.

준성이의 최애 수가 무엇인지 정확히 알아낼 수 있다면 첫째 줄에 I got it!을 출력하고, 둘째 줄에 처음으로 정확히 알아낼 수 있었던 질의응답이 몇 번째인지 출력한다.

정확히 알아낼 수 없다면 첫째 줄에 Hmm...을 출력한다.

---

💡 해결 방법

💻 코드

import sys
input = sys.stdin.readline
 
q = int(input())
 
b = pow(10, 18) + 1
a = - b
 
#a초과 b 미만이 간격, 이 간격이 1 이되면 알수 있다, b - a == 1, 1 - (-1)  == 2 (0이 최애)
#모순은 !(b - a >= 1) 이면 될듯
 
ans = 0
 
for i in range(1, q+1):
    x = input().split()
    x, y = int(x[0]), x[1]
    # print(x, y)
    if y == '^':#a를 갱신
        a = max(a, x)
 
    elif y == 'v':#b를 갱신
        b = min(b, x)
 
    else:
        print("????")   
 
 
 
 
    if not(b - a >= 2):
        if (ans >= 0):
            ans = -i
 
 
 
 
    elif b - a == 2: 
        if ans == 0: #모순이면 알아냄의 의미 x
            ans = i
            #print(x, y)
    
 
 
 
 
 
 
 
if ans == 0:
    print('Hmm...')
elif ans < 0:
        print('Paradox!')
        print(-ans)
else:
    print('I got it!')
    print(ans)