할아버지의 로또 게임

면접 대비

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

요약
일별 복권 지출과 당첨금이 주어질 때 전체 손익의 부호, 하루 최대 손실, 연속 구간 최대 누적 손실을 구한다.
난이도

보통10점 중 4점

유형
배열, 누적 합, 구현, 완전 탐색
정답자
아직 제출이 없습니다

문제

주쿠의 할아버지는 열성적인, 그리고 스스로 생각하기에 성공적인 로또 플레이어입니다. 주쿠는 그 마지막 주장에 의문을 품고, 얼마 전부터 할아버지가 로또 복권을 사는 데 얼마를 쓰고 로또로 얼마를 따는지 기록해 왔습니다.

할아버지의 로또 게임에 대해 다음 세 가지 통계를 계산하는 프로그램을 작성하세요.

  • 할아버지가 딴 금액의 총합이 복권에 쓴 금액의 총합보다 많은지 적은지 판단합니다.
  • 하루 동안 가장 많은 돈을 잃은 날이 며칠인지 찾습니다.
  • 연속한 며칠 동안 가장 많은 돈을 잃은 기간이 언제인지 찾습니다.

입력

첫째 줄에 주쿠의 일기 기록 수 NN (1≤N≤1001 \le N \le 100)이 주어집니다. 이어지는 NN개의 줄에는 각각 공백으로 구분된 두 정수가 주어집니다. ii번째 날 (1≤i≤N1 \le i \le N)에 복권에 쓴 금액 PiP_i (0≤Pi≤1000 \le P_i \le 100)와 딴 금액 ViV_i (0≤Vi≤1 000 0000 \le V_i \le 1\,000\,000)입니다.

출력

정확히 세 줄을 출력하며, 각 줄에 한 개의 답을 출력합니다.

첫째 줄에는 할아버지가 딴 금액의 총합이 복권에 쓴 금액의 총합보다 큰지, 작은지, 같은지에 따라 각각 PLUSSIS, MIINUSES, NULLIS를 출력합니다.

둘째 줄에는 공백으로 구분된 두 정수 PP와 SS를 출력합니다. PP는 할아버지가 하루 동안 가장 많은 돈을 잃은 날의 번호이고, SS는 그 날의 손실액(복권 지출에서 딴 금액을 뺀 값, 즉 Pi−ViP_i - V_i)입니다. 할아버지는 적어도 하루는 돈을 잃었다고 가정할 수 있습니다. 최대 손실액을 기록한 날이 여러 개이면 그중 날짜 번호가 가장 작은(가장 이른) 날을 출력합니다.

셋째 줄에는 공백으로 구분된 세 정수 P1P_1, P2P_2, SS를 출력합니다. 이는 할아버지가 가장 많이 잃은 기간이 P1P_1일부터 P2P_2일까지 이어졌으며, 그 기간 동안 복권 지출이 딴 금액보다 총 SS만큼 많았음을 나타냅니다. 최대 손실액을 기록한 기간이 여러 개이면 시작일 P1P_1이 가장 작은 것을, 그중에서도 종료일 P2P_2가 가장 작은 것을 출력합니다.

예제3

  1. 예제 1

    입력
    5
    1 9
    9 0
    3 5
    8 0
    1 9
    
    예상 출력
    PLUSSIS
    2 9
    2 4 15
    
  2. 예제 2

    입력
    1
    5 0
    
    예상 출력
    MIINUSES
    1 5
    1 1 5
    
  3. 예제 3

    입력
    3
    100 0
    0 100
    50 50
    
    예상 출력
    NULLIS
    1 100
    1 1 100