데이터 만들기 8
시간 제한1초메모리 제한128 MB
정해진 그래프를 그대로 출력한다. 꼭짓점 98개, 간선 1501개이며 완전 이분 그래프의 간선을 지정된 순서로 인쇄한다.
문제
프로그래밍 대회는 많다. 대회에 쓸 좋은 문제를 만드는 일은 어렵고, 그중에서도 테스트 데이터를 만드는 일이 가장 어렵다. 좋은 테스트 데이터는 문제의 의도에 맞게 짠 코드와 그렇지 않은 코드를 구별해 내야 한다. 대부분의 입력에서는 맞지만 특별한 입력에서만 틀리는 코드도 걸러 내야 한다.
이 문제는 풀이 프로그램을 제출하는 문제가 아니다. 테스트 데이터를 만드는 문제이다.
상근이는 그래프 문제 미스테리의 데이터 하나를 만들어야 한다. 데이터 는 다음을 만족해야 한다.
- 코드 A가 를 처리할 때 시간 초과(TLE)가 나면 안 된다.
- 코드 B가 를 처리할 때 시간 초과(TLE)가 나야 한다.
데이터는 작을수록 좋으므로 정수를 최대 개만 담아야 한다. 이다.
미스테리는 정점 개, 간선 개인 무향 그래프가 주어질 때, 인접한 정점의 번호가 서로 다르도록 각 정점에 이상 이하의 정수를 붙이는 문제이다. 가능한 가장 작은 를 구한다.
미스테리 입력 형식은 다음과 같다.
첫째 줄에 와 가 있다. 다음 개의 줄에 무향 간선 , 가 있다.
입력은 다음도 지켜야 한다.
- 모든 간선 에 대해 , , 이고 같은 간선은 한 번만 적는다.
코드 A는 RecursiveBacktracking이고 코드 B는 Gamble2이다. 두 코드는 힌트에 있다.
두 코드에는 counter 변수가 있다. 이 값이 을 넘으면 TLE이다.
조건을 만족하는 그래프는 여러 개일 수 있다. 그중 아래 그래프만 출력한다.
- ,
- 정점 부터 까지가 한쪽, 정점 부터 까지가 다른 쪽인 완전 이분 그래프이다.
- 간선은 를 부터 까지 올리고, 각 마다 를 부터 까지 올리며 를 한 줄에 하나씩 출력한다.
이 그래프는 정수 개를 담는다. RecursiveBacktracking은 이 그래프에서 TLE가 나지 않는다. Gamble2는 counter를 로 두므로 항상 TLE이다.
위의 그래프를 출력하는 프로그램을 작성하시오.
입력
이 문제는 입력이 없다.
출력
위에서 정한 그래프를 미스테리 입력 형식으로 출력한다.
첫째 줄에 과 을 공백으로 구분해 출력한다. 다음 개의 줄에 간선의 두 정점을 공백으로 구분해 출력한다.
힌트
RecursiveBacktracking은 를 부터 까지 올려 가며 첫 유효 색칠을 찾는다. 정점은 순서로 색을 붙인다. 정점 의 색은 항상 이다. 정점 에 색을 붙인 뒤, 아직 색이 없는 이웃을 보고 정점 에 쓸 수 있는 색을 부터 까지 작은 것부터 시도한다. counter는 재귀 호출마다 늘고, 다음 정점의 이웃을 볼 때마다 는다. counter가 을 넘으면 TLE이다.
found = false
counter = 0
for X in 2 .. V:
cur[0 .. V-1] = -1
backtrack(0, 0)
if found:
break
if counter > 1000000:
TLE
output X and cur
backtrack(u, label):
if found:
return
counter += 1
cur[u] = label
if u == V-1:
found = true
return
ok[0 .. X-1] = true
for each neighbor v of vertex u+1:
counter += 1
if counter > 1000000:
return
if cur[v] != -1:
ok[cur[v]] = false
for j in 0 .. X-1:
if ok[j]:
backtrack(u+1, j)
Gamble2는 그래프와 관계없이 아래만 수행한다.
X = V
for i in 0 .. V-1:
label[i] = i
counter = 1000001
따라서 Gamble2는 항상 TLE이다.