UP & DOWN

NYPC 2020 · 예선 연습문제

다오와 배찌는 UP & DOWN 게임을 하며 놀고 있다. UP & DOWN 게임이란, 한 사람이 11 이상 10001\,000 이하의 수를 하나 정해놓고, 다른 사람은 여러 질문을 하며 그 수가 무엇인지 맞히는 게임이다. 질문은 "네가 생각한 수가 xx보다 크니? 작니? 같니?"를 물어본다. 그러면 대답은 "크다(UP)", "작다(DOWN)", "같다(CORRECT)" 중 하나로 올바르게 해야 한다.

다오는 11 이상 10001\,000 이하의 수를 하나 생각해놓았고, 배찌는 그 수를 맞히려고 한다. 여러분은 배찌를 도와서 다오가 정한 수를 찾아가는 과정을 프로그램으로 작성해야 한다.

입력과 출력

이 문제는 대화형(interactive) 문제의 연습이다. 여러분이 작성한 프로그램은 표준 입력(stdin)과 표준 출력(stdout)을 이용하여 대회 주최 측 프로그램과 통신하며 문제를 해결해야 한다.

한 라운드에서 여러분의 프로그램은 "네가 생각한 수가 xx 보다 크니? 작니? 같니?"의 질문을 한다. 질문을 하기 위해서 문장을 출력할 필요는 없고, 단순히 수 x를 한 줄에 출력하면 된다. 이때 프로그램의 출력 버퍼에 남아있을 수 있는 내용을 반드시 내보내야 (출력 버퍼를 비워야) 한다. 출력 버퍼를 비우는 방법은 아래에서 설명할 것이다. 이후 그 질문에 대한 대답을 입력으로부터 읽을 수 있다. 주어지는 대답은 CORRECT, UP, DOWN 중 하나다. 이 질문과 대답을 반복하여 다오가 정한 수를 맞히면 된다. 단, 질문을 10001\,000번 넘게 할 수는 없으며 수를 맞춘 이후 질문을 하면 안 되고 프로그램을 정상 종료해야 한다. 즉, 질문에 대한 대답이 CORRECT인 경우 프로그램을 바로 종료해야 한다. 질문을 위해 출력하는 하는 수 xx11 이상이고 10001\,000이하라야 한다.

만약, 위에서 정해진 규칙에 어긋난 입출력을 시도할 경우, 00점을 받는다.

아래 예시 대화와 언어별 예시 코드를 참고하자. 예시 대화의 문법은 특정한 프로그래밍 언어가 아닌 가상 코드이다. 각 언어에 대한 예시 코드는 더 아래에 있다.

예시 대화

printline 10 to stdout  // 다오가 생각한 수가 10이랑 비교했을 때 큰지, 작은지, 같은지 질문
flush stdout            // 출력 버퍼를 비운다.
reply = readline()      // read DOWN, 10보다 작다는 답변을 받음
printline 6 to stdout   // 다오가 생각한 수가 6이랑 비교했을 때 큰지, 작은지, 같은지 질문
flush stdout            // 출력 버퍼를 비운다.
reply = readline()      // read UP, 6보다 크다는 답변을 받음
printline 8 to stdout   // 다오가 생각한 수가 8이랑 비교했을 때 큰지, 작은지, 같은지 질문
flush stdout            // 출력 버퍼를 비운다.
reply = readline()      // read CORRECT, 8과 같다는 답변을 받음
exit                    // 수를 찾고나서는 더이상 질문을 하지 않고 프로그램을 종료해야 함

주의 사항

질문하는 수 xx를 한 줄에 출력할 때 반드시 줄을 끝맺는 문자(줄 바꿈 문자)를 같이 출력해야 한다.

출력을 한 이후에는 내부 버퍼에 출력 내용이 쌓여 주최 측 프로그램에 전달되지 않을 수 있으니, 이를 피하기 위해 반드시 출력할 때마다 flush 연산을 해서 출력 버퍼를 비워야한다. C에서는 fflush(stdout), C++에서는 cout.flush() 혹은 cout << flush, C#에서는 Console.Out.Flush(), Java에서는 System.out.flush(), Python에서는 sys.stdout.flush()를 통해 flush 연산을 할 수 있다.

채점 방식

여러분이 작성한 프로그램은 다오가 정한 수를 항상 찾아야 한다. 여러 테스트케이스 중 하나라도 다오가 정한 수를 찾지 못하면 00점을 받는다.

다오가 정한 수를 모두 맞히면 3030점, 모든 수를 각각 질문 1010번 이내에 맞히면 100100점을 획득한다.

이 문제는 연습 문제이므로 점수가 성적에 합산되지는 않습니다.

언어별 예시 코드 (3030점을 받는 코드임)

C

#include <stdio.h>
#include <string.h>

int main()
{
    char reply[99] = {0,};
    for (int i=1;i<=1000;i++){
        printf("%d\n", i); fflush(stdout);
        scanf("%s", reply);
        if (!strcmp(reply, "CORRECT"))
            break;
        else if (!strcmp(reply, "UP"))
            continue;
        else if (!strcmp(reply, "DOWN"))
            continue;
    }
}

C++

#include <iostream>
#include <string>

int main()
{
    std::string reply;
    for (int i=1;i<=1000;i++){
        std::cout << i << std::endl; std::cout.flush();
        std::cin >> reply;
        if (reply == "CORRECT")
            break;
        else if (reply == "UP")
            continue;
        else if (reply == "DOWN")
            continue;
    }
}

C#

using System;

public class Program {
    public static void Main() {
        string reply;
        for (int i=1;i<=1000;i++){
            Console.WriteLine(i);
            Console.Out.Flush();
            reply = Console.ReadLine();
            if (reply == "CORRECT")
                break;
            else if (reply == "UP")
                continue;
            else if (reply == "DOWN")
                continue;
        }
    }
}

Java

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i=1;i<=1000;i++) {
            System.out.println(i);
            System.out.flush();
            String reply = sc.next();
            if ("CORRECT".equals(reply))
                break;
            else if ("UP".equals(reply))
                continue;
            else if ("DOWN".equals(reply))
                continue;
        }
    }
}

Python2, PyPy2

import sys

for i in range(1, 1001):
    print(i)
    sys.stdout.flush()
    reply = raw_input()
    if reply == 'CORRECT':
        break
    elif reply == 'UP':
        continue
    elif reply == 'DOWN':
        continue

Python3

import sys

for i in range(1, 1001):
    print(i)
    sys.stdout.flush()
    reply = input()
    if reply == 'CORRECT':
        break
    elif reply == 'UP':
        continue
    elif reply == 'DOWN':
        continue

해설