想吃冰卻又敏感保護不足?5檔高息股比定存強10倍輕忽小中風,當心變殘障黃國昌嗆周祝瑛 教室一...
2012-04-21 18:16:43 人氣(166) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][Math] 11470 - Square Sums

0
收藏
0
推薦

J

Square Sums

Input: Standard Input

Output: Standard Output

 

Do you know that there are squares within a square. This might seem confusing, but take a look at this.

 

Suppose you have a square grid of size 5 X 5 completely filled with integers.

 

5

3

2

7

9

1

7

4

2

4

5

3

2

4

6

1

3

4

5

1

1

4

5

6

3

 

You can make three squares from the table above… well there are more but we will consider only concentric squares. The squares are denoted using different fonts.

In this problem you have to find the sum of the numbers of each square.

For the above case the sums are

5 + 3 + 2 + 7 + 9 + 1 + 4 + 5 + 6 + 1 + 1 + 1 + 4 + 5 + 6 + 3 = 63

7 + 4 + 2 + 3 + 4 + 3 + 4 + 5 = 32

2 = 2

 

Input

There will be several lines in the input file. Each case starts with an integer n(n<=10) that determines the dimension of the square grid. Each of the next n lines will contain n integers each that will fill the square table in row major order. Input is terminated by a case where n == 0.

 

Output

Each line of output will start with “Case #:” where # is replaced by the case number. Then you have to output ceil(n/2) space separated numbers that will represent the sums from outer to inner. Follow the sample for exact details.

 

Sample Input                             Output for Sample Input

5

5 3 2 7 9

1 7 4 2 4

5 3 2 4 6

1 3 4 5 1

1 4 5 6 3

1

1

0

Case 1: 63 32 2

Case 2: 1

 

 

 

 

 

 



用數學代替 BFS

#include <stdio.h>

int main() {
    int n, Case = 0, i, j;
    while(scanf("%d", &n) == 1 && n) {
        int sum[10] = {}, x;
        for(i = 0; i < n; i++) {
            for(j = 0; j < n; j++) {
                scanf("%d", &x);
                if(j < n-i) {
                    int min = i < j ? i : j;
                    sum[min] += x;
                } else {
                    int max = i > j ? i : j;
                    sum[n-max-1] += x;
                }
            }
        }
        printf("Case %d:", ++Case);
        for(i = 0; i < n/2+n%2; i++) {
            printf(" %d", sum[i]);
        }
        puts("");
    }
    return 0;
}

11470Square Sums
台長:Morris
人氣(166) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][map] 755 - 487--3279
此分類上一篇:[UVA][Random] 10167 - Birthday Cake

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文