만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

지연 평가

면접 대비

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

요약
1부터 1234567890123까지의 수가 담긴 배열에 덧셈, 곱셈, 앞쪽 원소 제거 명령을 수행하고 가장 작은 값을 출력합니다.
난이도

쉬움10점 중 3점

유형
수학, 구현
정답자
아직 제출이 없습니다

문제

지연이는 자신이 가진 배열 SS의 상태를 평가하려고 한다. 처음에 SS에는 11부터 1 234 567 890 1231\,234\,567\,890\,123까지의 모든 정수가 11개씩 들어 있다.

지연이를 도와 다음 명령을 수행하는 프로그램을 작성하시오.

  • 0 x: SS의 모든 원소에 x를 더한다. (−100 000≤(-100\,000 \leq x ≤100 000)\leq 100\,000)
  • 1 x: SS의 모든 원소에 x를 곱한다. (1≤(1 \leq x ≤100)\leq 100)
  • 2 n: SS에서 작은 원소부터 차례대로 n개를 제거한다. (1≤(1 \leq n ≤100 000 000)\leq 100\,000\,000)
  • 3: SS에서 가장 작은 원소를 출력한다.

이 문제의 풀이를 작성하기 전에 아래 힌트를 참고할 수 있다.

입력

첫 줄에 명령의 개수 QQ가 주어진다. (1≤Q≤170 000)(1 \leq Q \leq 170\,000)

다음 줄부터 위에서 설명한 네 개의 명령 중 하나가 주어진다. x, n은 정수이다.

하나의 테스트케이스에서 2번 명령으로 들어오는 모든 n의 합은 1 234 567 890 1201\,234\,567\,890\,120 이하이다.

하나의 테스트케이스에서 배열 SS에 들어 있는 어떤 수든지 그 절댓값이 언제나 101810^{18} 이하가 되도록 하는 명령만이 주어진다.

마지막 명령은 항상 3이다.

출력

3번 명령이 들어올 때마다 그 시점에서 SS에서 가장 작은 값을 한 줄에 하나씩 출력한다.

힌트

Python 사용자라면, 간단한 테스트로 다음 두 프로그램을 로컬에서 돌려 보자.

a = [0] * (10 ** 15) # 10**15 byte is 1 Petabyte
print("calculating done!")

a = range(10 ** 15)
print("calculating done!")

두 번째 프로그램은 바로 끝나지만, 첫 번째 프로그램은 메모리 에러가 발생한다. range(10 ** 15) 구문은 0부터 1015−110^{15} - 1까지의 모든 수를 즉시 생성하지 않기 때문이다. 대신 start, stop, step이라는 단 3개의 정수만을 내부에 저장하고, 0, 1, 2, 3, ... 순으로 필요할 때마다 수를 만들어 준다. 이처럼 결과가 필요할 때까지 표현식의 평가를 미루는 기법을 지연 평가(Lazy evaluation)라고 한다. 실제로 101510^{15}까지의 수가 모두 필요한 것이 아니라면, 예를 들어 100번째 소수를 발견했을 때 for문을 멈추고 그 값을 리턴하고 싶다면 지연 평가가 많은 도움이 된다. 이 문제도 11부터 1 234 567 890 1231\,234\,567\,890\,123까지의 자연수를 하나씩 직접 생성하면 시간과 메모리를 엄청나게 잡아먹는다. 지연 평가를 사용해서 이 문제를 더 효율적으로 푸는 방법을 찾아보자.

range에 대한 자세한 내용은 Python 문서를 참고하자.

예제3

  1. 예제 1

    입력
    10
3
2 999999
3
1 2
3
0 2
1 2
0 2
2 7
3
    예상 출력
    1
1000000
2000000
4000034

  2. 예제 2

    입력
    9
3
0 -10000
3
2 100000000
3
1 99
3
2 8244353
3
    예상 출력
    1
-9999
99990001
9899010099
10715201046

  3. 예제 3

    입력
    12
0 1
1 2
2 3
3
0 5
1 6
2 7
3
0 9
1 10
2 11
3
    예상 출력
    10
174
3150