Problems
물리학자인 준혁이는 N개의 입자를 가지고 실험하고 있다.
N개의 입자는 모두 양의 정수로 표현되는 질량을 가지며 서로 질량이 다르다.
준혁이는 실험을 하면서 가능한 모든 두 입자쌍의 질량을 합한 결과를 N(N-1)/2 개의 수로 적어두었다.
그런데 준혁이가 실수를 하는 바람에 모든 입자를 잃어 버리고 기록해둔 결과의 순서마저 섞이고 말았다.
준혁이는 비록 입자를 잃어버렸지만 그 입자들의 질량 만이라도 모두 알아내고 싶다.
준혁이의 섞여버린 리스트를 보고 원래 입자들의 질량으로 가능한 경우의 수를 모두 찾아라.
가능한 경우의 수가 없는 경우는 입력으로 주어지지 않는다.
Input
첫 줄에 N이 주어진다. (3 <= N <= 300)
둘째 줄에 준혁이가 기록해둔 리스트가 N(N-1)/2개의 수로 주어진다. 각 수는 1억을 초과하지 않는다.
N<=20 이고 주어지는 각 수가 2000을 넘지 않는 경우에 대해서만 풀어도 32%에 해당하는 점수를 받을 수 있다.
Output
첫 줄에 준혁이의 리스트에 맞게 질량을 정하는 서로 다른 방법의 수를 출력하라.
여기서 두 방법이 같다는 것은 두 방법에서 입자 질량의 집합이 같다는 의미이다.
둘째 줄부터 줄마다 하나의 방법을 출력해 모든 방법을 출력하라.
방법의 순서나 한 줄에서 입자 질량의 순서 등은 원하는 대로 출력해도 좋다.
Example
4
3 5 4 7 6 5
1
1 2 3 4
Source
POI 2011/2012 stage 3
You must sign in to write code.