Informatica Online Judge

  안다/모른다 게임 [1301 / 0515]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 2   Total Tried : 231


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (32nd 안형서)]

Background

두 사람 A,B 가 있다.

다른 사람 C 가 n이하의 두 자연수를 골라 둘의 곱을 A에게, 둘의 합을 B에게 알려주었다. 이제 A와 B가 그 두 자연수를 맞추려고 한다.

A를 시작으로 A와 B가 번갈아 가며, 자기가 알겠는지 모르겠는지 말한다.

이 때 한 명이 알게 되면 끝이다. 대화에서 A,B가 서로 ‘모른다’라고 k번 주고 받았을 때, 두 수를 구하라. 만약 불가능하다면 -1을 출력한다.

(k=2 라면 A: 모른다 B: 모른다 A: 모른다 B: 모른다 A: 알겠다 의 상황이다.다른 경우는 없다.)


예를 들어 n=6일 때 C가 3,4를 골랐다고 하자.

그렇다면 A,B는 각각 12와 7을 받았을 것이다.

먼저 A는 예상을 한다.

‘내가 12이니 가능한 쌍은 2,6 또는 3,4 이네, 하지만 둘 중 뭐 인지는 모르겠다. ’

따라서 A는 모른다고 말한다.

다음 B가 예상을 한다.

‘내가 7이니 가능한 쌍은 1,6과 2,5와 3,4이네’

만약 1,6이었다면 A는 6을 받았을 테고, 그러면 A는 1,6인지 2,3인지 모를 테니까 모른다고 할거야.


만약 2,5라면 A는 10을 받았을 테고, A는 1,10과 2,5가 될 거지만 n=6이기 때문에 2,5만 가능하다는 걸 알고 알았다고 말했을 거야. 그러니까 2,5일 가능성은 없어.


만약 3,4였다면, A는 12를 받았을 테고, A는 2,6과 3,4를 생각할 테니, 모른다고 할거야.

결론적으로 나는 2,5가 아닌걸 알지만 1,6 인지 3,4인지 모르겠어‘ 따라서 B는 모른다고 한다.

다음은 A가 다시 예상을 한다. ‘만약 2,6이었다고 하자, 그러면 B는 8을 받았을 테지, 그러면 B입장에서 4,4과 3,5와 2,6을 생각할 수 있어.

그러면 B가 예상하길, 4,4였다면 내가 16을 받았을 테니 바로 알았을 테고, 3,5였다면 내가 15를 받았으니 바로 알았을 테고, 2,6이였다면 내가 12였을 테니 모른다고 했을 거야.

실제로 내가 모른다고 했으니까, B는 4,4와3,5가 아닌걸 알고 답이 2,6인걸 알았을 거야. 그러면 B가 처음에 알았다고 했어야해.

그런데 B가 실제론 모른다고 했으니 2,6은 아니야, 따라서 3,4가 답이네“ 라고 알게된다.

Input

첫 줄에 n과 k가 입력된다.

[입력값의 정의역]
1 <= n <= 2,000
0 <= k <= 2,000

[SubTask Info]
#1 : n <= 200, k <= 10
#2 : n <= 1,000, k <= 2,000
#3 : n <= 2,000, k <= 2,000

Output

가능한 순서쌍을 (a,b)라 할 때 항상 a<=b이고 a가 작은것이 위로, 같다면 b가 작은것이 위로 가도록 한다.

IO Example

입력1
10 2

출력1
1 6

입력2
10 9

출력2
-1

입력2
6 1

출력2
1 4
3 4

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]