Programming Challenges #40

 

For 10 > N > 2 numbers we form N ∗(N −1)/2 sums by adding every pair of the  numbers. Your task is to find the N numbers given the sums.

10 > N > 2인 숫자들을 사용하여 N*(N-1)/2개의 합을 만듭니다. 이때 각 숫자들의 모든 조합을 더해서 합을 구합니다. 주어진 합을 기반으로 N개의 숫자를 찾는 것이 당신의 과제입니다.

Input

Each line of input contains N followed by N ∗ (N − 1)/2 integer numbers separated by a space.

각 입력 줄은 N 다음에 N * (N - 1) / 2 개의 정수 숫자가 공백으로 구분되어 나옵니다.

Output

For each line of input, output one line containing N integers in non-descending order such that the input numbers are pairwise sums of the N numbers. If there is more than one solution, any one will do; if there is no solution, print ‘Impossible’.

각 입력 줄마다, N개의 정수를 비내림차순으로 출력하는 한 줄을 출력합니다. 이때 입력 숫자들은 N개의 숫자의 합으로 구성됩니다. 여러 가지 해결책이 있는 경우, 어떤 해결책을 선택해도 됩니다. 해결책이 없는 경우에는 'Impossible'을 출력합니다.

Sample Input

3 1269 1160 1663
3111
5 226 223 225 224 227 229 228 226 225 227
5 216 210 204 212 220 214 222 208 216 210
5 -1 0 -1 -2 1 0 -1 1 0 -1
5 79950 79936 79942 79962 79954 79972 79960 79968 79924 79932 

Sample Output

383 777 886
Impossible
111 112 113 114 115
101 103 107 109 113
-1 -1 0 0 1
39953 39971 39979 39983 39989

 

---

function get_num_pairs(n) {
    return ((n) * ((n) - 1) / 2);
}
let sum = new Array()
let checked = new Array()
let ans = new Array();
let n = 0;
let num_pairs = 0;

function solve() {

    let t = sum.filter((e,i,arr) => {
        return i < 3;
    }).reduce((acc, e) => {
        return acc = acc + e;
    }, 0)

    if (t%2 == 0){
        t /= 2;
    }else{
        return false;
    }

    sum.filter((e,i,arr) => {
        return i < 3;
    }).reverse().forEach((e, i, arr) => {
        ans[i] = t - e;
        checked[i] = 1;   
    })

    for (let i = 3, t = 0; i < n; i++, t = 0) {

        checked.filter((e,i,arr) => {
            return i > t;
        }).forEach((e, i, arr) =>{
            if (e == 1) {
                t++;
                return true;
            } else {
                return false;
            }
        });

        ans[i] = sum[t] - ans[0];

        for (let j = 0; j < i; j++) {
            while (t < num_pairs && ( (checked[t] == 1 ? true : false) || (sum[t] != ans[i] + ans[j]))) {
                t++;                        
            }
            if (t == num_pairs) {
                return false;
            }
            checked[t] = 1;
        }

    }

    console.log(`정답 : ${ans.join()}`)

    return true;
}

function main() {
    let solved = false;            
    for (let i = 2; i < n; i++) {
        [sum[2] = sum[i]] = [sum[i] = sum[2]];
        if (solved = solve()) {
            break;
        }
    }
    if (!solved) {
        console.log('Impossible')
    }
}

// n = 3;
// sum = [1269, 1160, 1663];
n = 5;
sum = [226,223,225,224,227,229,228,226,225,227];
num_pairs = get_num_pairs(n);
sum = sum.sort((a, b) => a - b)
console.log(JSON.stringify(sum))

main()

 

1. get_num_pairs(n): 이 함수는 입력된 수 n에 대한 조합의 개수를 계산하는 역할을 합니다. n개의 원소 중에서 2개를 선택하는 조합의 개수를 구합니다. 이는 수학적으로 (n * (n - 1)) / 2로 계산됩니다.
2. solve(): 이 함수는 문제를 해결하는 역할을 합니다. 주어진 배열 sum을 이용하여 조건을 만족하는 숫자들을 찾습니다.
   • 먼저, 배열 sum의 처음 3개의 원소를 이용하여 변수 t에 합을 계산합니다.
   • t가 짝수인 경우, t를 2로 나눈 값을 저장합니다. 만약 t가 홀수인 경우, 조건을 만족하는 숫자들을 찾을 수 없으므로 false를 반환합니다.
   • 배열 sum의 처음 3개의 원소를 역순으로 순회하면서 조건을 만족하는 숫자들을 계산하여 ans 배열과 checked 배열에 저장합니다.
   • 반복문을 통해 나머지 숫자들에 대해 처리를 수행합니다. 변수 t를 0으로 초기화하고, checked 배열에서 선택되지 않은 숫자 중 가장 작은 인덱스를 찾습니다.
   • 조건을 만족하는 숫자들을 계산하여 ans 배열에 저장하고, 이전에 선택한 숫자들과의 합이 배열 sum에 존재하지 않거나 이미 선택된 숫자인 경우 다음 인덱스를 확인하도록 반복문을 진행합니다.
   • 모든 숫자에 대해 처리를 완료한 후, ans 배열에는 조건을 만족하는 숫자들이 저장되어 있습니다.
   • ans 배열을 출력하고 true를 반환합니다.
3. main(): 이 함수는 주요 실행 로직을 담고 있습니다.
   • 먼저, 변수 solved를 false로 초기화합니다.
   • 반복문을 통해 i를 2부터 n까지 증가시킵니다. 배열 sum의 두 번째 요소와 sum[i] 값을 교환하여 숫자들을 재배열합니다.
   • solve() 함수를 호출하여 문제를 해결합니다. 만약 조건을 만족하는 숫자들을 찾은 경우, solved를 true로 설정하고 반복문을 종료합니다.
   • 해결할 수 없는 경우 "Impossible"을 출력합니다.
4. 주석 처리된 n과 sum 변수에 주어진 값들을 할당합니다.
5. get_num_pairs(n) 함수를 호출하여 조합의 개수인 num_pairs를 계산합니다.
6. 배열 sum을 오름차순으로 정렬합니다.
7. main() 함수를 호출하여 문제를 해결합니다.
   • 만약 조건을 만족하는 숫자들을 찾은 경우, solved가 true가 되고 반복문을 종료합니다.
   • 해결할 수 없는 경우 "Impossible"을 출력합니다.

코드 분석을 통해 배열 sum에 대해 조건을 만족하는 숫자들을 찾고, 이를 출력합니다.