min 또는 max

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

요약
숨겨진 10x10 배열에서 2x2 최솟값/최댓값 질의만 사용해 전체 최솟값 또는 최댓값의 위치를 찾아 제출하는 프로그램을 자원 예산 안에서 작성한다.
난이도

어려움10점 중 9점

유형
구현, 수학, 완전 탐색, 시뮬레이션
정답자
아직 제출이 없습니다

문제

준혁이는 바쁜 하루를 끝내고 와서 Array Lab Of Helpful Alterations(ALOHA)라는 게임을 즐겨 한다.

ALOHA에는 10×1010 \times 10의 22차원 배열 AA가 있다. AA는 A_1,1A\_{1,1}와 A_10,10A\_{10,10}을 배열의 양 끝으로 가진다. 배열의 원소 A_i,jA\_{i,j}는 −109-10^9보다 크거나 같고, 10910^9보다 작거나 같다.

준혁이는 배열을 탐색해 배열에서 최댓값 혹은 최솟값을 찾아야한다. 그러기 위해 준혁이는 자원과 배열 AA의 값을 담을 배열 RR이 있다.

준혁이에게는 미네랄과 프로판가스라고 불리는 22가지 종류의 자원이 있으며 배열을 탐색하기 위해 배열에 접근할 때 마다 특정 수만큼 미네랄과 프로판가스를 사용한다.

어느날 준혁이는 게임을 하던 도중 모니터가 고장나서 배열 AA가 보이지 않게 되었다. 당신은 준혁이에게 AA를 모른 상태에서도 게임을 클리어 할 수 있는 탐색 프로그램을 만들어 달라는 부탁을 받았다.

당신의 프로그램은 다음과 같은 연산을 원하는 만큼 할 수 있다. tt는 처음에 11이다.

  • max⁡(x,y)\max(x,y)

    • A_x,yA\_{x,y}와 A_x+1,y+1A\_{x+1,y+1}를 끝으로 가지는 2×22 \times 2 사각형 영역에서의 가장 큰 값을 R_tR\_t에 넣는다.
    • 1≤x,y≤91\leq x,y \leq 9
    • 이 연산 이후 tt는 11증가된다.
    • 미네랄은 100100, 프로판가스는 7575 소모한다.
  • min⁡(x,y)\min(x,y)

    • A_x,yA\_{x,y}와 A_x+1,y+1A\_{x+1,y+1}를 끝으로 가지는 2×22 \times 2 사각형 영역에서의 가장 작은 값을 R_tR\_t에 넣는다.
    • 1≤x,y≤91\leq x,y \leq 9
    • 이 연산 이후 tt는 11증가된다.
    • 미네랄은 100100, 프로판가스는 7575 소모한다.
  • plus⁡(x,y,i)\operatorname{plus} (x,y,i)

    • A_x,yA\_{x,y}를 R_iR\_i만큼 증가시킨다.
    • 1≤x,y≤10;1≤i<t1\leq x,y \leq 10;1 \leq i < t
    • 미네랄은 1010, 프로판가스는 55 소모한다.
  • minus⁡(x,y,i)\operatorname{minus} (x,y,i)

    • A_x,yA\_{x,y}를 R_iR\_i만큼 감소시킨다.
    • 1≤x,y≤10;1≤i<t1\leq x,y \leq 10;1 \leq i < t
    • 미네랄은 1010, 프로판가스는 55 소모한다.
  • submit⁡(x,y)\operatorname{submit} (x,y)

    • 이 연산이 수행된 시점에 A_x,yA\_{x,y}가 AA의 최솟값 혹은 최댓값과 동일하다는 제출을 한다.
    • 전체 프로그램에서 올바른 submit⁡\operatorname{submit} 연산이 하나 이상 있어야 정답을 받을 수 있다.
    • 1≤x,y≤101\leq x,y \leq 10
    • 미네랄은 200200, 프로판가스는 250250 소모한다.

준혁이는 미네랄을 4,0004\\,000, 프로판가스를 3,0003\\,000 가지고 있다. 사용하는 탐색 프로그램의 모든 연산이 끝날 때 까지 어떤 자원이 00미만으로 떨어져서는 안 된다.

배열에서 최대 또는 최소지점을 찾을 수 있는 프로그램을 만들어보자.

입력

입력은 없다.

출력

첫째 줄에 프로그램이 호출하는 함수의 수 ff를 출력한다.

그 후 ff개의 줄에 사용하는 연산들을 한 줄에 하나씩 출력한다.

프로그램의 길이는 제한이 없지만 프로그램의 미네랄과 프로판가스의 사용량이 각각 4,0004\\,000과 3,0003\\,000을 넘겨서는 안 된다.

예제1

  1. 예제 1

    입력
    예상 출력
    8
    max(1,1)
    min(2,3)
    plus(1,1,1)
    plus(3,3,2)
    max(3,3)
    submit(1,1)
    minus(9,9,3)
    submit(3,3)