Programming Challenges #42

You are given an elliptical shaped land and you are asked to choose n arbitrary points on its boundary. Then you connect all these points with one another with straight lines (that’s n ∗ (n − 1)/2 connections for n points). What is the maximum number of pieces of land you will get by choosing the points on the boundary carefully?

주어진 타원형 땅에서 n개의 임의의 점을 경계선 위에 선택하고, 이러한 점들을 직선으로 서로 연결합니다 (n * (n - 1) / 2개의 연결이 n개의 점에 대해 생성됩니다). 경계선 위의 점들을 신중하게 선택하여 얻을 수 있는 땅의 최대 개수는 얼마인가요?

 

Input

The first line of the input file contains one integer S (0 < S < 3500), which indicates how many sets of input are there. The next S lines contain S sets of input. Each input contains one integer N (0≤N <231).

입력 파일의 첫 번째 줄에는 정수 S (0 < S < 3500)가 포함되어 있으며, 이는 입력 세트의 개수를 나타냅니다. 다음 S개의 줄에는 S개의 입력 세트가 포함됩니다. 각 입력 세트는 하나의 정수 N (0 ≤ N < 231)을 포함합니다.

Output

For each set of input you should output in a single line the maximum number pieces of land possible to get for the value of N.

각 입력 세트에 대해 가능한 최대 토지 조각 수를 한 줄에 출력해야 합니다.

Sample Input

4 1 2 3 4

Sample Output

1 2 4

---

const NUMBERLENGTH = 20;
const ONEDIGIT = 10000;

class O {
    constructor() {
        this.h = new Array();
    }
}

let n = 0;
let result = new O(),
    cresult = new O();

function assign(a, b) {
    for (let i = 0; i < NUMBERLENGTH; i++) {
        a.h[i] = b % ONEDIGIT;
        b /= ONEDIGIT;
    }
}

function add(c, a, b) {
    let i, carry = 0;
    for (i = 0; i < NUMBERLENGTH; i++) {
        c.h[i] = a.h[i] + b.h[i] + carry;
        carry = c.h[i] / ONEDIGIT;
        c.h[i] %= ONEDIGIT;
    }
}

function mul(c, a, b) {
    let i, j, carry;
    let temp;
    let _in, _jn;
    let d = new O();
    for (i = 0; i < NUMBERLENGTH; i++) {
        d.h[i] = 0;
    }
    _in = _jn = NUMBERLENGTH - 1;
    while (a.h[_in] == 0) {
        _in++;
    }
    _in++;
    while (b.h[_jn] == 0) {
        _jn++;
    }
    _jn++;
    for (let i = 0; i < _in + 1; i++) {
        carry = 0;
        for (j = 0; j < _jn + 1; j++) {
            if (i + j < NUMBERLENGTH) {
                temp = (d.h[i + j] + a.h[i] * b.h[j] + carry) % ONEDIGIT;
                carry = (d.h[i + j] + a.h[i] * b.h[j] + carry) / ONEDIGIT;
                d.h[i + j] = temp;
            }
        }
    }
    for (i = 0; i < NUMBERLENGTH; i++) {
        c.h[i] = d.h[i];
    }
}

function combi(n, k) {
    let i, j, temp;
    let check = new Array(4).fill(0);
    let longtemp = new O();
    assign(cresult, 1);
    for (i = n; i > n - k; i--) {
        temp = i;
        for (j = k; j > 0; j--) {
            if (check[j - 1]) {
                continue;
            }
            if (temp % j == 0) {
                check[j - 1] = 1;
                temp /= j;
            }
        }
        assign(longtemp, temp);
        mul(cresult, cresult, longtemp);
    }
}

function solve() {
    assign(result, 1);
    combi(n, 2);
    add(result, result, cresult);
    combi(n, 4);
    add(result, result, cresult);
}

function print(a) {
    let sw = 0,
        i;
    for (i = NUMBERLENGTH - 1; i >= 0; i--) {
        if (!(sw == 0 && a.h[i] == 0)) {
            if (sw == 0) {
                // console.log(Math.floor(a.h[i]));
                sw = 1;
            } else {
				if(Math.floor(a.h[i]) > 0) {
					console.log(Math.floor(a.h[i]));
					break;
				}
            }
        }
    }
}

function main() {
    let i, j;
    let input = [1, 2, 3, 4];
    for (i = 0; i < 4; i++) {
        n = input[i];
        solve();
        print(result);
    }
}

main();

• O 클래스는 큰 정수를 표현하기 위한 클래스입니다. h라는 배열 속성을 가지고 있습니다.
• assign(a, b) 함수는 a 배열에 b 값을 할당합니다. b 값이 큰 수이므로 ONEDIGIT로 나누어서 a 배열에 저장합니다.
• add(c, a, b) 함수는 a와 b 배열을 더하여 c 배열에 저장합니다. 자릿수 올림(carry)을 고려합니다.
• mul(c, a, b) 함수는 a와 b 배열을 곱하여 c 배열에 저장합니다. 큰 수의 곱셈은 일반적인 곱셈 알고리즘을 사용합니다.
• combi(n, k) 함수는 조합(nCk)을 계산합니다. cresult 배열에 계산 결과를 저장합니다.
• solve() 함수는 주어진 입력값 n에 대해 조합을 계산합니다. result 배열에 계산 결과를 저장합니다.
• print(a) 함수는 배열 a를 역순으로 순회하며 결과를 출력합니다. 숫자의 앞부분 0을 제거하여 출력합니다.
• main() 함수는 주어진 input 배열에 대해 solve()와 print() 함수를 호출하여 결과를 출력합니다.