물 끓이기

면접 대비

시간 제한1초메모리 제한512 MB

요약
N번의 물 끓이기에서 에드워드가 보지 않은 시간 구간이 주어질 때, 모든 구간에 들어가는 한 시각이 존재하는지 판정한다.
난이도

보통10점 중 4점

유형
구간, 구현, 그리디
정답자
아직 제출이 없습니다

문제

"보는 냄비는 끓지 않는다"는 속담이 있다. 셰프 에드워드는 오랫동안 요리를 해 왔는데, 그의 부엌에서는 그 속담이 실제로 맞는 것처럼 보인다. 냄비가 실제로 끓기 시작하는 모습은 아직 한 번도 보지 못했다. 그의 아내 구닐라는 에드워드의 주장이 좀 수상하다고 여긴다. 그녀는 에드워드가 얼마 지나면 자주 집중을 잃는다는 사실을 알고 있고, 냄비를 불에 올린 뒤 대략 같은 시간이 흐르면 지켜보는 데 지쳐 버릴 가능성이 크다고 생각한다.

과학적인 사고방식을 지닌 구닐라는 냄비가 끓는 현상에 대해 에드워드가 더 많은 통찰을 얻을 수 있도록 실험을 설계했다. 지난 일주일 동안 에드워드가 냄비에 물을 끓일 때마다, 그는 냄비를 지켜보지 않은 시간 구간을 적어 두었다. 이제 그는 이 구간들로 이루어진 방대한 기록을 가지고 있으며, 구닐라의 말이 맞는지 (즉, 에드워드가 냄비가 끓기 시작할 때마다 우연히 매번 자리를 비웠을 수 있는지), 아니면 자신의 가설이 맞는지 궁금해한다.

이 데이터가 주어졌을 때, 냄비가 매번 같은 시간이 지난 뒤에 실제로 끓기 시작했을 가능성이 있는가?

입력

입력의 첫 줄에는 지난 일주일 동안 에드워드가 물을 끓인 횟수 1≤N≤1 0001 \le N \le 1\,000이 주어진다. 그 다음 NN개의 끓임에 대한 설명이 이어진다. 각 설명은 두 수 0≤a≤b≤1 0000 \le a \le b \le 1\,000을 포함한다. 이는 에드워드가 [a,b][a, b]초 동안 (즉 aa초가 시작될 때부터 bb초가 끝날 때까지) 다른 곳을 보았고, 다시 봤을 때 냄비가 끓고 있는 것을 처음 목격했음을 뜻한다.

출력

모든 냄비가 실제로 같은 시점에 끓기 시작했을 가능성이 없다면 edward is right를 출력한다. 그렇지 않다면 gunilla has a point를 출력한다.

예제2

  1. 예제 1

    입력
    2
    1 7
    5 5
    
    예상 출력
    gunilla has a point
    
  2. 예제 2

    입력
    3
    4 6
    4 8
    7 8
    
    예상 출력
    edward is right