Problem E: Faucet Flow

Problem E: Faucet Flow

时间: 1ms        内存:128M

描述:

Problem E: Faucet Flow

A faucet is pouring water into a long, thin aquarium with various vertical dividers (walls) in it. The aquarium is initially empty, and its bottom is perfectly level. How long will it take for water to spill over its left- or right-most divider? The faucet is above location x=0, and the dividers are located at x=-1, -3, -5, ..., leftx and 1, 3, 5, ..., rightx. The dividers are attached perpendicular to the floor and sides of the aquarium, and have various heights. The aquarium's length is greater than rightx-leftx, its walls are higher than the highest divider, and its width is 1 unit everywhere. Water pours from the faucet at a rate of 1 cubic unit per second. [You may assume that water is an ideal liquid: it always flows downhill and if it cannot flow downhill it spreads at an equal rate in all horizontal directions.]

输入:

Each test case consists of two integers leftx (an odd number <= -1) and rightx (an odd number >= 1). Subsequent lines contain the height (a positive integer) of each divider from left to right. There will be no more than 1000 dividers in any test case. Input is terminated with a line containing two zeros.

输出:

For each case, output an integer on a single line, indicating how long it will take, in seconds, before water starts spilling over either the left or right divider.

示例输入:

-1 1
3 5
-3 3
4 3 2 1
-3 5
1 2 2 1 1
0 0

示例输出:

6
6
8

提示:

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

#include <stdio.h>
#include <ctype.h>

int i,j,k,m,n,N;
char buf[10000];
char *b;
int val,sign,cx[2],cy[2],c[2],eq,state,coef,op;
int xnum,ynum,den;

int gcd(int a, int b){
   if (b == 0) return a;
   if (b < 0) return -gcd(a,-b);
   if (a < 0) return gcd(-a,b);
   return gcd(b,a%b);
}

void pr(int n, int d){
   if (n%d == 0) printf("%d\n",n/d);
   else printf("%d/%d\n",n/gcd(n,d),d/gcd(n,d));
}

main(){
   scanf("%d",&N); 
   gets(buf);
   while (N--) {
      if (m++) printf("\n");
      for (i=0;i<2;i++){
         gets(buf);
         b = buf;
         op = 1;
         eq = 1;
         cx[i] = cy[i] = c[i] = 0;
         while (*b) {
            while (*b == ' ') b++;
            sign = 1;
            if (*b == '+') {
               sign = 1;
               b++;
            } else if (*b == '-') {
               sign = -1;
               b++;
            }
            if (!isdigit(*b)) val = 1;
            else val = 0;
            while (isdigit(*b)) {
               val = val * 10 + (*b-'0');
               b++;
            }
            if (*b == 'x') {
               cx[i] += sign * op * val;
               b++;
            } else if (*b == 'y') {
               cy[i] += sign * op * val;
               b++;
            } else c[i] += sign * op * val;
            while (*b == ' ') b++;
            if (*b == '=') {
               eq = -1;
               op = -1;
               b++;
            } else if (*b == '+') {
               op = eq;
               b++;
            } else if (*b == '-') {
               op = -eq;
               b++;
            } else if (!*b) break;
            else printf("oops! at %s\n",b);
         }
         //printf("%dx + %dy + %d = 0\n",cx[i],cy[i],c[i]);
      }
      den = (cx[0]*cy[1]) - (cx[1] * cy[0]);
      if (den) {
         xnum = (-c[0]*cy[1]) - (-c[1] * cy[0]);
         ynum = (cx[0]*-c[1]) - (cx[1] * -c[0]);
         pr(xnum,den);
         pr(ynum,den);
      } else if (c[0] && !cx[0] && !cy[0] || cy[1] && !cx[1] && !cy[1]) {
         printf("don't know\ndon't know\n");
      } else {
         if (cx[0] && !cy[0] && !cx[1]) pr(-c[0],cx[0]);
         else if (cx[1] && !cy[1] && !cx[0]) pr(-c[1],cx[1]);
         else if (cx[1] && !cy[1] && cx[0] && !cy[0] && cx[1]*c[0] == cx[0]*c[1]) pr(-c[0],cx[0]);
         else printf("don't know\n");
         if (cy[0] && !cx[0] && !cy[1]) pr(-c[0],cy[0]);
         else if (cy[1] && !cx[1] && !cy[0]) pr(-c[1],cy[1]);
         else if (cy[1] && !cx[1] && cy[0] && !cx[0] && cy[1]*c[0] == cy[0]*c[1]) pr(-c[0],cy[0]);
         else printf("don't know\n");
      }
      gets(buf);
   }
}

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

#include <stdio.h>
#include <ctype.h>

int i,j,k,m,n,N;
char buf[10000];
char *b;
int val,sign,cx[2],cy[2],c[2],eq,state,coef,op;
int xnum,ynum,den;

int gcd(int a, int b){
   if (b == 0) return a;
   if (b < 0) return -gcd(a,-b);
   if (a < 0) return gcd(-a,b);
   return gcd(b,a%b);
}

void pr(int n, int d){
   if (n%d == 0) printf("%d\n",n/d);
   else printf("%d/%d\n",n/gcd(n,d),d/gcd(n,d));
}

main(){
   scanf("%d",&N); 
   gets(buf);
   while (N--) {
      if (m++) printf("\n");
      for (i=0;i<2;i++){
         gets(buf);
         b = buf;
         op = 1;
         eq = 1;
         cx[i] = cy[i] = c[i] = 0;
         while (*b) {
            while (*b == ' ') b++;
            sign = 1;
            if (*b == '+') {
               sign = 1;
               b++;
            } else if (*b == '-') {
               sign = -1;
               b++;
            }
            if (!isdigit(*b)) val = 1;
            else val = 0;
            while (isdigit(*b)) {
               val = val * 10 + (*b-'0');
               b++;
            }
            if (*b == 'x') {
               cx[i] += sign * op * val;
               b++;
            } else if (*b == 'y') {
               cy[i] += sign * op * val;
               b++;
            } else c[i] += sign * op * val;
            while (*b == ' ') b++;
            if (*b == '=') {
               eq = -1;
               op = -1;
               b++;
            } else if (*b == '+') {
               op = eq;
               b++;
            } else if (*b == '-') {
               op = -eq;
               b++;
            } else if (!*b) break;
            else printf("oops! at %s\n",b);
         }
         //printf("%dx + %dy + %d = 0\n",cx[i],cy[i],c[i]);
      }
      den = (cx[0]*cy[1]) - (cx[1] * cy[0]);
      if (den) {
         xnum = (-c[0]*cy[1]) - (-c[1] * cy[0]);
         ynum = (cx[0]*-c[1]) - (cx[1] * -c[0]);
         pr(xnum,den);
         pr(ynum,den);
      } else if (c[0] && !cx[0] && !cy[0] || cy[1] && !cx[1] && !cy[1]) {
         printf("don't know\ndon't know\n");
      } else {
         if (cx[0] && !cy[0] && !cx[1]) pr(-c[0],cx[0]);
         else if (cx[1] && !cy[1] && !cx[0]) pr(-c[1],cx[1]);
         else if (cx[1] && !cy[1] && cx[0] && !cy[0] && cx[1]*c[0] == cx[0]*c[1]) pr(-c[0],cx[0]);
         else printf("don't know\n");
         if (cy[0] && !cx[0] && !cy[1]) pr(-c[0],cy[0]);
         else if (cy[1] && !cx[1] && !cy[0]) pr(-c[1],cy[1]);
         else if (cy[1] && !cx[1] && cy[0] && !cx[0] && cy[1]*c[0] == cy[0]*c[1]) pr(-c[0],cy[0]);
         else printf("don't know\n");
      }
      gets(buf);
   }
}

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

点赞

发表评论

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