Problem D: Forests

Problem D: Forests

时间: 1ms        内存:128M

描述:

Problem D: Forests

If a tree falls in the forest, and there's nobody there to hear, does it make a sound? This classic conundrum was coined by George Berkeley (1685-1753), the Bishop and influential Irish philosopher whose primary philosophical achievement is the advancement of what has come to be called subjective idealism. He wrote a number of works, of which the most widely-read are Treatise Concerning the Principles of Human Knowledge (1710) and Three Dialogues between Hylas and Philonous (1713) (Philonous, the "lover of the mind," representing Berkeley himself).

A forest contains T trees numbered from 1 to T and P people numbered from 1 to P. Standard input consists of a line containing T and P followed by several lines, containing a pair of integers i and j, indicating that person i has heard tree j fall. People may have different opinions as to which trees, according to Berkeley, have made a sound. How many different opinions are represented in the input? Two people hold the same opinion only if they hear exactly the same set of trees. You may assume that P < 100 and T < 100.

输入:

输出:

示例输入:

3 4
1 2
3 3
1 3
2 2
3 2
2 4

示例输出:

2

提示:

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

#include <stdio.h>
#include <math.h>
#define hypot(x,y) sqrt((x)*(x)+(y)*(y))

double x[100], y[100];
int N;

double test(double xx, double yy) {
   double tot = 0;
   int i;
   for (i=0;i<N;i++) {
      tot += hypot(x[i]-xx,y[i]-yy);
   }
   return tot;
}

main(){
   int i,j,k;
   double xx,yy,delta;

   scanf("%d",&N);
   for (i=0;i<N;i++) scanf("%lf%lf",&x[i],&y[i]);
   
   xx = 5000;
   yy = 5000;

   for (delta=5000;delta > .0001;delta *=.9) {
      if (test(xx,yy+delta) < test(xx,yy)) yy+=delta;
      if (test(xx,yy-delta) < test(xx,yy)) yy-=delta;
      if (test(xx+delta,yy) < test(xx,yy)) xx+=delta;
      if (test(xx-delta,yy) < test(xx,yy)) xx-=delta;
   }
   printf("%0.0lf\n",test(xx,yy));
}

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

int obs[200][200];
int done[200];

main(){
   int P,T,i,j=0,k,cnt=0;
   scanf("%d%d",&P,&T);
   while (2 == scanf("%d%d",&i,&j)) {
      obs[i][j] = 1;
   }
   for (i=1;i<=P;i++) {
      if (done[i]) continue;
      cnt++;
      for (j=i;j<=P;j++) {
         for (k=1;k<=T && obs[i][k]==obs[j][k];k++);
         if (k > T) done[j] = 1;
      }
   }
   printf("%d\n",cnt);
}

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

点赞

发表评论

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