아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

막심의 트라이앵글

면접 대비

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

요약
일련의 탐침 주파수와 각 주파수가 미지의 값에 더 가까운지 먼지를 나타내는 기록이 주어질 때, 미지의 값이 될 수 있는 최솟값과 최댓값을 구한다.
난이도

보통10점 중 6점

유형
수학, 이분 탐색, 구간, 기하
정답자
아직 제출이 없습니다

문제

막심은 어릴 때부터 음악에 재능이 있었고 손재주도 좋았다. 최근에는 간단한 타악기인 트라이앵글을 직접 만들었다. 그는 이 악기에서 나는 소리의 주파수가 얼마인지 알아내려 한다.

막심에게는 지정한 주파수의 음을 재생할 수 있는 전문 음악 튜너가 있다. 막심은 다음과 같이 행동한다. 튜너에서 서로 다른 주파수의 음을 켜고, 각 음마다 그 음이 트라이앵글 소리에 이전 음보다 더 가까운지 더 먼지를 귀로 판단한다. 막심은 절대음감이 있어서 이 판단을 항상 정확하게 한다.

막심은 튜너에 설정한 주파수들의 수열과, 두 번째 음부터 각 음이 이전 음보다 트라이앵글 소리에 더 가까운지 더 먼지를 적은 기록을 보여 주었다. 막심의 트라이앵글 소리 주파수는 30헤르츠 이상 4000헤르츠 이하라는 것을 미리 알고 있다.

트라이앵글 소리 주파수가 있을 수 있는 구간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 막심이 튜너로 재생한 음의 개수 nn이 정수로 주어진다 (2≤n≤10002 \le n \le 1000). 다음 nn개 줄에는 막심의 기록이 주어지며, 각 줄은 두 요소로 이루어진다. 실수 fif_i는 튜너에 설정한 주파수(헤르츠)이고 (30≤fi≤400030 \le f_i \le 4000), 첫 번째 주파수를 제외한 각 주파수에는 단어 closer 또는 further가 따라온다.

closer는 이 음의 주파수가 이전 음의 주파수보다 트라이앵글 소리 주파수에 더 가깝다는 뜻이며, 형식적으로는 ∣fi−fтреуг.∣<∣fi−1−fтреуг.∣|f_i - f_{\text{треуг.}}| < |f_{i-1} - f_{\text{треуг.}}|로 나타낼 수 있다.

further는 이 음의 주파수가 이전 음보다 더 멀다는 뜻이다.

어떤 음이 트라이앵글 소리에 이전 음만큼 가깝다면, 막심은 위의 두 단어 중 아무거나 적을 수 있었다.

막심이 얻은 결과는 모순이 없다고 보장된다.

출력

막심이 만든 트라이앵글 소리 주파수의 가능한 최솟값과 최댓값을 공백으로 구분해 출력한다.

예제2

  1. 예제 1

    입력
    3
    440.0
    220.0 closer
    300.0 further
    
    예상 출력
    30.0 260.0
    
  2. 예제 2

    입력
    4
    554.0
    880.0 further
    440.0 closer
    622.0 closer
    
    예상 출력
    531.0 660.0