시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 81 12 4 33.333%

문제

채점 프로그램과 마스터마인드 게임을 해보자.

마스터마인드는 채점 프로그램이 정한 공 4개의 색상과 순서를 맞추는 게임이다. 공의 색상은 6가지가 있고, 1부터 6까지 자연수로 표현한다. 공의 색상과 순서를 맞추려면 채점 프로그램에게 질문을 해야 한다. 채점 프로그램이 정한 공의 색상과 순서는 편의상 수열 A로 표현한다.

채점 프로그램에게 수열 B를 질문하면, 빨간 핀의 수와 흰색 핀의 수를 알려준다. 빨간 핀의 수는 위치와 색이 맞은 공의 개수이고, 흰색 핀의 수는 색은 같지만, 위치가 다른 공의 개수이다.

한 게임에서 할 수 있는 질문의 수는 K번이고, 채점 프로그램에게 K번 이하의 질문을 해서 A가 무엇인지 알아내보자.

함수 목록 및 정의

제공되는 "MM.h"를 include 해야 한다.

Grader가 제공하는 함수는 다음과 같다.

  • std::pair<int,int> guess(std::vector<int> B)
    • 채점 프로그램에게 수열 B를 질문한다.
    • B의 크기가 4가 아닌 경우 "틀렸습니다"를 결과로 받는다.
    • 이 함수를 K번보다 많이 호출하는 경우 "틀렸습니다"를 받는다.
    • 수열 B가 A와 일치하는 경우에는 게임을 종료해야 하며, 새로운 게임이 시작하기 전까지 이 함수를 다시 호출하면 안된다. 수열 A를 맞춘 이후에 다시 이 함수를 호출하면 "틀렸습니다"를 받는다.
    • B에 1보다 크거나 같고, 6보다 작거나 같은 수가 들어있지 않은 경우 "틀렸습니다"를 받는다.
    • 리턴값의 첫 번째 수는 빨간 핀의 수, 두 번째 수는 흰색 핀의 수이다.

다음과 같은 함수를 작성해야 한다.

  • void init(int T, int K)
    • 프로그램이 실행된 직후, 한 번만 호출된다. T는 채점 프로그램과 하게 될 게임의 횟수이며, K은 한 게임에서 할 수 있는 질문의 최대 수이다.
  • void game()
    • 이 함수의 호출은 숫자 게임의 시작을 의미하며, 종료는 게임의 끝을 의미한다.
    • 이 함수가 호출되면, 채점 프로그램에게 질문을 해서 수열 A를 알아내야 한다.
    • 이 함수는 총 T번 호출된다.

Grader가 실행 도중 "틀렸습니다"라고 판정한 경우, 그 즉시 프로그램을 종료된다.

입력

Sample Grader는 다음과 같은 정보를 Standard Input을 통해서 읽는다.

첫째 줄에 T와 K가 주어진다. 둘째 줄부터 T개의 줄에 채점 프로그램이 정한 공의 색상과 순서 A가 한 줄에 하나씩 주어진다.

출력

Sample Grader는 다음과 같은 정보를 Standard Input을 통해서 출력한다.

T개의 게임에서 채점 프로그램이 생각한 수를 모두 맞췄다면 "AC"를, 그 외에는 "WA"를 출력한다.

제한

  • 1 ≤ T ≤ 100
  • 5 ≤ K ≤ 12

제공 파일

서브태스크 1 (10점)

  • K = 12

서브태스크 2 (30점)

  • K = 8

서브태스크 3 (60점)

  • K = 5

예제 입력 1

2 12
1 1 1 2
6 5 4 3

예제 출력 1

AC

호출 예시

다음은 위의 입출력 예제에 대해서, Sample Grader와 Interaction하는 과정을 나타낸 것이다.

MM.cpp Grader 설명
  T = 2, K = 12 Grader에서 T와 K의 값을 읽어들인다.
  init(T = 2, K = 12) 호출 init 함수는 초기에 한 번만 호출된다.
  A = {1, 1, 1, 2}  
  game() 호출  
guess({1, 2, 3, 4}) 호출    
  return {1, 1}; 빨간 핀 = 1, 흰색 핀 = 1
guess({1, 2, 1, 2}) 호출    
  return {3, 0}; 빨간 핀 = 3, 흰색 핀 = 0
guess({2, 1, 1, 1}) 호출    
  return {2, 2}; 빨간 핀 = 2, 흰색 핀 = 2
guess({1, 1, 1, 1}) 호출    
  return {3, 0}; 빨간 핀 = 3, 흰색 핀 = 0
guess({1, 1, 2, 1}) 호출    
  return {2, 2}; 빨간 핀 = 2, 흰색 핀 = 2
guess({1, 1, 1, 2}) 호출    
  return {4, 0}; 빨간 핀 = 4, 흰색 핀 = 0
game() 종료   A를 정확하게 맞추었다.
  A = {6, 5, 4, 3}  
  game() 호출  
guess({6, 5, 4, 3}) 호출    
  return {4, 0};  
game() 종료   A를 정확하게 맞추었다.
  AC  

위의 과정은 실제 정해와 전혀 관련이 없으며, 단지 이해를 돕기 위해 만든 예시이다. 위 예시는 채점 프로그램과 마스터마인드를 두 번 하면서, 두 번 모두 우연히 A를 정확하게 맞추었다.

출처

제출할 수 있는 언어

C++17, C++2a

채점

  • 예제는 채점하지 않는다.