Problem C: Square

Problem C: Square

时间: 1ms        内存:128M

描述:

Problem C: Square

Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square?

The first line of input contains N, the number of test cases. Each test case begins with an integer 4 <= M <= 20, the number of sticks. M integers follow; each gives the length of a stick - an integer between 1 and 10,000.

For each case, output a line containing "yes" if is is possible to form a square; otherwise output "no".

输入:

输出:

示例输入:

3
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5

示例输出:

yes
no
yes

提示:

参考答案(内存最优[752]):

#include <stdio.h>

int C,N,i,j,k,area,best;

main(){
   scanf("%d",&C);
   while (C--) {
      scanf("%d",&N);
      best = 1000*1000*1000;
      for (i=1;i*i*i<=N;i++) {
         for (j=i;i*j*j<=N;j++) {
            if (N%(i*j)) continue;
            k = N/(i*j);
            area = 2*i*j + 2*i*k + 2*j*k;
            if (area < best) best = area;
         }
      }
      printf("%d\n",best);
   }
}

参考答案(时间最优[4]):

#include <stdio.h>

int C,N,i,j,k,area,best;

main(){
   scanf("%d",&C);
   while (C--) {
      scanf("%d",&N);
      best = 1000*1000*1000;
      for (i=1;i*i*i<=N;i++) {
         for (j=i;i*j*j<=N;j++) {
            if (N%(i*j)) continue;
            k = N/(i*j);
            area = 2*i*j + 2*i*k + 2*j*k;
            if (area < best) best = area;
         }
      }
      printf("%d\n",best);
   }
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注