32295번 - 잘못 생성된 데이터 인터랙티브

문제

영희는 1,2,ドル\cdots,n$의 순열을 무작위로 생성하는 알고리즘을 가지고 있습니다. 이 알고리즘의 의사코드는 아래와 같습니다.

# 클래스 node는 이진 트리의 노드를 구성합니다.
# node는 클래스 변수로 L,R,Lc,Rc,x를 가집니다.
# L,R은 왼쪽과 오른쪽 자식 노드를 가리키는 포인터 또는 인덱스입니다.
# Lc와 Rc는 왼쪽과 오른쪽에 추가할 수 있는 리프 노드의 수를 나타냅니다.
# 예를 들어 새로운 노드에 대해 Lc와 Rc는 기본적으로 1입니다.
# x는 노드가 저장하는 정수 값입니다.
def makenode(a):
 return ("'x=a인 새로운 node의 포인터 또는 인덱스"')
def insert(rt,a):
 while True:
 range = rt.Lc+rt.Rc
 v = ("'0 이상 range 미만의 무작위 정수"')
 if v < rt.Lc: # 라인 A
 rt.Lc += 1
 if rt.Lc == 2:
 rt.L = makenode(a)
 return
 rt = ("'rt.L이 가리키는 node"')
 else:
 rt.Rc += 1
 if rt.Rc == 2:
 rt.R = makenode(a)
 return
 rt = ("'rt.R이 가리키는 node"')
def inorder(rt):
 if rt.Lc > 1:
 inorder("'rt.L이 가리키는 node"')
 print(rt.x)
 if rt.Rc > 1:
 inorder("'rt.R이 가리키는 node"')
# ...
# 데이터를 생성하는 방법
root="'makenode(1)의 반환값이 가리키는 node"'
for i in range(2,n+1):
 insert(root,i)
# 이제 inorder(root)의 출력은 무작위 순열이 됩니다.

알고리즘을 실행하면 출력으로 1,2,ドル\cdots,n$의 순열을 무작위로 얻으며, $n!$가지 순열 각각은 얻을 확률이 동일합니다. 또한 이 알고리즘은 놀랍게도 $\mathcal{O}(n \log n)$이라는 평균 시간 복잡도를 가집니다.

영희에게 이 알고리즘을 배운 철수는 혼자서 이 알고리즘을 구현해 보았습니다. 하지만, 기억력이 좋지 않은 철수는 주석 처리된 "라인 A"의 코드 v < rt.Lc를 v >= rt.Lc로 잘못 작성하고 말았습니다! 오타가 있었다는 사실을 알아냈을 때, 철수는 이미 길이 $n=1,000円$의 순열을 무수히 많이 생성한 뒤였습니다.

철수의 실수는 생각보다 심각했습니다. 영희의 알고리즘은 모든 순열을 같은 확률로 반환하지만, 철수가 잘못 구현한 알고리즘은 그렇지 않습니다. 따라서 잘못 구현된 알고리즘이 어떤 문제의 채점 데이터를 생성하는데 사용되었다는 사실이 밝혀질 경우 논란이 생길 것이 분명합니다. 하지만 이미 어떤 문제의 채점 데이터에 잘못 생성된 데이터가 섞이고 말았습니다. 데이터를 새로 생성하기에는 시간이 부족하므로, 여러분이 잘못 생성된 데이터를 걸러내 주어야 합니다.

영희의 알고리즘을 알고리즘 A, 철수의 알고리즘을 알고리즘 B라고 합시다. 길이 $n=1,000円$의 순열이 $m=1,000円$개 있으며, 각각은 알고리즘 A와 알고리즘 B 중 하나로 생성되었습니다. 순열을 생성하는 알고리즘은 공정한 동전을 던져서 결정되었습니다. 다시 말해, 순열이 알고리즘 A로 생성될 확률이 50ドル\%,ドル 알고리즘 B로 생성될 확률이 50ドル\%$입니다. 여러분은 각 순열이 어느 알고리즘에서 생성되었는지 알아내야 합니다.

물론, 두 알고리즘이 같은 순열을 생성할 수도 있으므로 모든 입력에 대해 정답을 100ドル\%$의 확률로 맞힐 수 있는 방법은 없습니다. 따라서 1ドル,000円$개의 순열 중 적어도 900ドル$개의 순열에 대해 정답을 맞혔을 경우 정답으로 인정됩니다.

입력

첫 번째 줄에 순열의 개수 $m$이 주어집니다. ($m=1,000円$)

그다음 줄부터 2ドルm$개의 줄에 걸쳐 순열의 정보가 주어집니다. 각 순열의 정보는 두 줄로 구성됩니다.

• 첫 번째 줄에 순열의 길이 $n$이 주어집니다. ($n=1,000円$)
• 두 번째 줄에 순열의 원소를 나타내는 $n$개의 정수 $a_1,a_2,\cdots,a_n$이 공백으로 구분되어 주어집니다. (1ドル \le a_i \le n$)

모든 입력은 지문에 주어진 과정에 따라 생성되었습니다. 또한, 입력 파일의 개수는 최대 150ドル$개입니다.

출력

각 순열에 대해 순열이 알고리즘 A로 생성된 경우 "Alice", 알고리즘 B로 생성된 경우 "Bob"을 새로운 줄에 출력합니다.

입력된 $m=1,000円$개의 순열 중 적어도 900ドル$개에 대해 정답을 맞힐 경우 정답으로 인정됩니다.

이 문제는 형식상 인터랙티브 문제입니다.

각 줄을 출력한 후에는 표준 출력 버퍼를 flush해 주어야 합니다. 언어별로 표준 출력 버퍼를 flush하는 방법은 다음과 같습니다.

• C: fflush(stdout)
• C++: cout.flush()
• Java: System.out.flush()
• Python: sys.stdout.flush()
• 이외의 언어: 언어별 레퍼런스를 참고합니다.

제한

노트

참가자의 편의를 위해 C++로 작성되어 testlib을 사용하는 인터랙터의 원본 소스 코드를 제공합니다.

• interactor-baddata.cpp

인터랙터는 초기에 데이터를 생성하기 위한 시드를 데이터에서 입력받으며, 문제에 설명된 대로 데이터를 생성하면서 인터랙션을 진행합니다. 맞힌 테스트 케이스의 수는 변수 cntr에 저장되어 스트림 tout을 통해 체커로 전달됩니다. 이 값이 900ドル$ 이상일 경우 체커는 이를 정답으로 판정합니다.