출처: https://www.acmicpc.net/problem/2676
문제
The Rascal Triangle definition is similar to that of the Pascal Triangle. The rows are numbered from the top starting with 0. Each row n contains n + 1 numbers indexed from 0 to n. Using R(n, m) to indicate the index m item in the index n row:
R(n, m) = 0 for n < 0 OR m < 0 OR m > n
The first and last numbers in each row (which are the same in the top row) are 1:
R(n, 0) = R(n, n) = 1
The interior values are determined by (UpLeftEntry*UpRightEntry + 1)/UpEntry (see the parallelogram in the array below):
R(n + 1, m + 1) = (R(n, m)*R(n, m + 1) + 1)/R(n - 1, m)
Write a program which computes R(n, m) the m-th element of the n-th row of the Rascal Triangle.
입력
The first line of input contains a single integer P, ( 1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set is a single line of input consisting of 3 spaces separated decimal integers. The first integer is data set number, N. The second integer is row number n, and the third integer is the index m within the row of the entry for which you are to find R(n, m) the Rascal Triangle entry ( 0 ≤ m ≤ n ≤ 50000)
출력
For each data set there is one line of output. It contains the data set number, N, followed by a single space which is then followed by the Rascal Triangle entry R(n, m) accurate to the nearest integer value.
예제 입력
5 4 0 4 2 45678 12345 12345 9876 34567 11398
예제 출력
1 5 411495886 24383845 264080263
힌트
출처
ACM-ICPC > Regionals > North America > Greater New York Region > 2011 Greater New York Programming Contest B번
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | #include <fstream> #include <iostream> #include <cstring> #include <climits> #include <algorithm> #include <string> using namespace std; int main() { int n; cin >> n; for (int i = 0; i < n; i++) { int n, m; cin >> n >> m; cout << (1 + (n - m) * m) << endl; } return 0; } | cs |
'Algorithm, Data structure > Solved Algorithmic Problem' 카테고리의 다른 글
BAEKJOON 2679 - Route Redundancy (0) | 2016.12.04 |
---|---|
BACKJOON 2681 - Rancher's Gift (0) | 2016.11.27 |
BAEKJOON 2675 - Repeating Characters (0) | 2016.11.20 |
BAEKJOON 1052 - 물병 (0) | 2016.11.13 |
BAEKJOON 1051 - 숫자 정사각형 (0) | 2016.11.12 |