杞人憂天

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

요약
N개의 카드로 정수 X를 감추는 A의 전략과 그것을 복원하는 B의 전략을 함께 설계하는 문제.
난이도

어려움10점 중 9점

유형
조합론, 게임 이론, 구현, 수학
정답자
아직 제출이 없습니다

문제

이 문제는 투 스텝 문제입니다.

A는 B에게 메시지를 보내고 싶다. 메시지는 정수 XX로 나타낼 수 있지만 그냥 보내면 누군가 그 내용을 감청할지도 모른다. 그래서 주변에 있던 NN개의 카드를 이용해 메시지를 감추기로 했다. 각 카드의 앞면과 뒷면에는 11 이상 2N2N 이하의 정수가 11개씩 적혀 있으며 카드들에 적혀 있는 2N2N개의 수는 모두 다르다.

A는 카드마다 앞면과 뒷면의 수 중 하나를 선택하여, 순서를 섞어 B에게 전송한다. B는 A와 사전에 전략을 상의할 순 있지만 각 카드에 어떤 수가 적혀 있었는지는 알 수 없다. B는 XX의 값을 알아맞혀야 한다.

A와 B의 전략을 구현해보자.

입력

당신의 프로그램은 채점 데이터 하나당 총 두 번 실행된다. 당신은 하나의 소스코드에 두 가지 실행 과정을 모두 구현해야 한다.

첫째 줄에 입력의 종류를 나타내는 정수 TT가 주어진다. (T \in \left\\{1,2\right\\})

T=1T=1인 경우 A의 역할을 수행하고 T=2T=2인 경우 B의 역할을 수행해야 한다.

힌트

예제는 이해를 돕기 위한 것으로 실제로 채점하지는 않는다.

예제2

  1. 예제 1

    입력
    1
    4 10
    1 3
    8 2
    7 4
    5 6
    
    예상 출력
    3 2 7 5
    
  2. 예제 2

    입력
    2
    4
    2 3 5 7
    
    예상 출력
    10