POJ 3086 Triangular Sums(내 수제의 길-삼각수 누적)

Triangular Sums
Time Limit: 1000MS
 
Memory Limit: 65536K
Total Submissions: 5437
 
Accepted: 3845
Description
The nth Triangular number, T(n) = 1 + … + n, is the sum of the first n integers. It is the number of points in a triangular array with n points on side. For example T(4):
X
X X
X X X
X X X X

Write a program to compute the weighted sum of triangular numbers:
W(n) =  SUM[k = 1…nk * T(k + 1)]
Input
The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of datasets that follow.
Each dataset consists of a single line of input containing a single integer n, (1 ≤ n ≤300), which is the number of points on a side of the triangle.
Output
For each dataset, output on a single line the dataset number (1 through N), a blank, the value of n for the dataset, a blank, and the weighted sum ,W(n), of triangular numbers for n.
Sample Input
4
3
4
5
10

Sample Output
1 3 45
2 4 105
3 5 210
4 10 2145

Source
Greater New York 2006
삼각형으로 증가하는 대기열 T[i]가 있는데, 그 중에서 성장 간격은 매번 1을 더한다.위의 삼각형처럼 1, 3, 6, 10, 15, 21, 28, 36, 45, 55...이제 키보드에서 숫자 n(n<=300)을 읽고 W[n]=SUM(k*T[k+1]), (k=1,2,...n)을 구하십시오.
사실 직접 폭력적으로 해답을 구해도 괜찮을 것 같지만 시계를 먼저 치고 출력하는 문제풀이 방법에 익숙해졌다.전체 문제의 결과는 입력의 변화로 바뀌지 않기 때문에 초기화하면 시계를 잘 쳐서 출력을 읽습니다.
참고 사항:
1) 출력 형식입니다.
2) 계산 결과의 최대 값은 10^9로 int 형식을 직접 사용할 수 있다
3) T의 계산은 적어도 301까지 계산해야 한다.
코드(1AC):
#include <cstdio>
#include <cstdlib>
#include <cstring>

int T[310];
int W[310];

void init(){
    int i, j;

    memset(W, 0, sizeof(W));
    T[1] = 1;
    for (i = 2; i <= 304; i++){
        T[i] = T[i - 1] + i;
    }
    W[1] = T[2];
    for (i = 2; i<= 303; i++){
        W[i] = W[i - 1] + i * T[i + 1];
    }
}

int main(void){
    int ii, casenum;
    int n;

    init();
    scanf("%d", &casenum);
    for (ii = 1; ii <= casenum; ii++){
        scanf("%d", &n);
        printf("%d %d %d
", ii, n, W[n]); } return 0; }

좋은 웹페이지 즐겨찾기