NENU Summer Training 2014 #8

Ignatius
Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Description

Ignatius is building an Online Judge, now he has worked out all the problems except the Judge System. The system has to read data from correct output file and user's result file, then the system compare the two files. If the two files are absolutly same, then the Judge System return "Accepted", else if the only differences between the two files are spaces(' '), tabs(' '), or enters(' '), the Judge System should return "Presentation Error", else the system will return "Wrong Answer". 

Given the data of correct output file and the data of user's result file, your task is to determine which result the Judge System will return. 
 

Input

The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow. 
Each test case has two parts, the data of correct output file and the data of the user's result file. Both of them are starts with a single line contains a string "START" and end with a single line contains a string "END", these two strings are not the data. In other words, the data is between the two strings. The data will at most 5000 characters. 
 

Output

For each test cases, you should output the the result Judge System should return. 
 

Sample Input

4 START 1 + 2 = 3 END START 1+2=3 END START 1 + 2 = 3 END START 1 + 2 = 3 END START 1 + 2 = 3 END START 1 + 2 = 4 END START 1 + 2 = 3 END START 1 + 2 = 3 END
 

Sample Output

Presentation Error Presentation Error Wrong Answer Presentation Error
 

分析：

     最好的方法就是将输入的数组去除空行  , 然后再两两进行比较

代码：

#include<stdio.h>
#include<string.h>

const int maxn=5001;
char s1[maxn],s2[maxn];

void input(char *s)
{
    char temp[maxn];
    gets(temp);
    while(strcmp(temp,"START")!=0)
          gets(temp);
    while(gets(temp))
    {
        if(strcmp(temp,"END")==0)
            break;
        if(strlen(temp)!=0)
            strcat(s,temp);
        strcat(s,"
");
     }
}

void del(char *s,int l)
{
    char temp[maxn];
    int i,j;
    j=0;
    for(i=0;i<l;i++)
    {
        if(s[i]!=' '&&s[i]!='
'&&s[i]!='	')
            temp[j++]=s[i];
    }
    temp[j]='';
    strcpy(s,temp);
}

int sum()
{
    int l1,l2;
    l1=strlen(s1);
    l2=strlen(s2);
    if(l1==l2&&strcmp(s1,s2)==0)
       return 1;
    del(s1,l1);
    del(s2,l2);
    if(strcmp(s1,s2)==0)
       return 0;
    else
       return -1;
}

int main()
{
    int T,count;
    scanf("%d",&T);
    while(T--)
    {
        input(s1);
        input(s2);
        count=sum();
        if(count==1)
           printf("Accepted
");
        else if(count==0)
           printf("Presentation Error
");
        else
           printf("Wrong Answer
");
    }
    
    return 0;
}
View Code
#include<stdio.h>
#include<string.h>
const int maxn=5001;
char s1[maxn],s2[maxn],t1[maxn],t2[maxn];
char temp[maxn];

void input(char *s,char *t)
{
    gets(temp);
    while(strcmp(temp,"START")!=0)
          gets(temp);
    while(gets(temp))
    {
        if(strcmp(temp,"END")==0)
           break;
        if(strlen(temp)!=0)
           strcat(s,temp);
        strcat(s,"
");
    }
    int k=0;
    int l=strlen(s);
    int i;
    for(i=0;i<l;i++)
    {
        if(s[i]!=' '&&s[i]!='
'&&s[i]!='	')
            t[k++]=s[i];
    }
    t[k]='';
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        s1[0]='';
        s2[0]='';
        input(s1,t1);
        input(s2,t2);
        if(strcmp(s1,s2)==0)
           printf("Accepted
");
        else if(strcmp(t1,t2)==0)
            printf("Presentation Error
");
        else
            printf("Wrong Answer
");
    }
    return 0;
}
View Code
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <cstdio>
using namespace std;

#ifdef __int64
typedef __int64 LL;
#else
typedef long long LL;
#endif

const int inf=0x3f3f3f3f;
const int maxn=5050;

char t[maxn],as[maxn],bs[maxn],ap[maxn],bp[maxn];

int main()
{
    int n,ca,cb;
    scanf("%d",&n);
    getchar();
    while(n--)
    {
        gets(t);
        memset(t,0,sizeof(t));
        memset(as,0,sizeof(as));
        memset(bs,0,sizeof(bs));
        memset(ap,0,sizeof(ap));
        memset(bp,0,sizeof(bp));
        ca=cb=0;
        while(gets(t))
        {
            if(strcmp(t,"END")==0)
               break;
            strcat(as,t);
            ca++;
        }
        gets(t);
        while(gets(t))
        {
            if(strcmp(t,"END")==0)
                break;
            strcat(bs,t);
            cb++;
        }
        if(ca==cb&&strcmp(as,bs)==0)
            printf("Accepted
");
        else
        {
            int la=strlen(as),lb=strlen(bs);
            int lla=0,llb=0;
            for(int i=0;i<la;i++)
            {
                if(as[i]!=' '&&as[i]!='
'&&as[i]!='	')
                   ap[lla++]=as[i];
            }
            for(int i=0;i<lb;i++)
            {
                if(bs[i]!=' '&&bs[i]!='
'&&bs[i]!='	')
                    bp[llb++]=bs[i];
            }
            if(strcmp(ap,bp)==0)
               printf("Presentation Error
");
            else
               printf("Wrong Answer
");
        }
    }
    return 0;
}
View Code
Parabola
Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Description

Ignatius bought a land last week, but he didn't know the area of the land because the land is enclosed by a parabola and a straight line. The picture below shows the area. Now given all the intersectant points shows in the picture, can you tell Ignatius the area of the land? 

Note: The point P1 in the picture is the vertex of the parabola. 


 

Input

The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow. 
Each test case contains three intersectant points which shows in the picture, they are given in the order of P1, P2, P3. Each point is described by two floating-point numbers X and Y(0.0<=X,Y<=1000.0). 
 

Output

For each test case, you should output the area of the land, the result should be rounded to 2 decimal places. 
 

Sample Input

2 5.000000 5.000000 0.000000 0.000000 10.000000 0.000000 10.000000 10.000000 1.000000 1.000000 14.000000 8.222222
 

Sample Output

33.33 40.69

Hint

 For float may be not accurate enough, please use double instead of float.
 

分析：

      一道高数题 就是求出曲线和直线的方程在积分就好了！（曲线的方程可用顶点式  y = a(x-h)^2+l, (h,L) 为顶点坐标）

代码：

1.

设二次函数为y=a*x^2+b*x+c
（1）由于p1为二次函数顶点，所以b=-2*a*x1 （2）代入二次函数式子 1 里得y=a*x^2-2*a*x1*x+c（3）把p1,p2坐标代入 3 中，算出a，
然后由 2 算出b ,然后a、b、p3坐标代入 1 中算出c。这样下来就算出a、b、c了，那么ans=微积分求面积-梯形面积。
#include<stdio.h>
int main()
{
    int n;
    double x1,x2,x3,y1,y2,y3;
    double s,a,b,c,k,h;
    while(~scanf("%d",&n))
    {
        while(n--)
        {
            scanf("%lf %lf %lf %lf %lf %lf",&x1,&y1,&x2,&y2,&x3,&y3);
            a=(y2-y1)/((x2-x1)*(x2-x1));
            b=-2*a*x1;
            c=y1-a*x1*x1-b*x1;
            k=(y2-y3)/(x2-x3);
            h=y2-k*x2;
            s=(a*(x3*x3*x3-x2*x2*x2)/3)+((b-k)*(x3*x3-x2*x2)/2)+((c-h)*(x3-x2));
            printf("%.2lf
",s);
        }
    }
    return 0;
}
View Code

2.
这里我们设抛物线顶点式方程y=a*(x-h)^2+k；顶点坐标为（h,k)。h=x1；k=y1；a=(y-k)/(x-h)^2；

由积分可得（x2，x3）之间的面积，再减去梯形的面积即可

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <cstdio>
#include <cmath>
using namespace std;
 
#ifdef __int64
typedef __int64 LL;
#else
typedef long long LL;
#endif
 
const int inf = 0x3f3f3f3f;
const int maxn = 100000;
 
int main() {
    int n;
    double x1,y1,x2,y2,x3,y3;
    scanf("%d",&n);
    while(n--) {
        scanf("%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3);
        double b=x1;
        double c=y1;
        double a=(y2-c)/(x2-b)/(x2-b);
        double k=(y3-y2)/(x3-x2);
        double b1=y2-k*x2;
        double s1=a*x3*x3*x3/3-(2*a*b+k)*x3*x3/2+(a*b*b+c-b1)*x3;
        double s2=a*x2*x2*x2/3-(2*a*b+k)*x2*x2/2+(a*b*b+c-b1)*x2;
        printf("%.2f
",s1-s2);
    }
    return 0;
}
View Code
MOD-X
Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Description

求在小于等于N的正整数中有多少个X满足：X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2], …, X mod a[i] = b[i], … (0 < a[i] <= 10)。
 

Input

输入数据的第一行为一个正整数T，表示有T组测试数据。每组测试数据的第一行为两个正整数N，M (0 < N <= 1000,000,000 , 0 < M <= 10)，表示X小于等于N，数组a和b中各有M个元素。接下来两行，每行各有M个正整数，分别为a和b中的元素。
 

Output

对应每一组输入，在独立一行中输出一个正整数，表示满足条件的X的个数。
 

Sample Input

3 10 3 1 2 3 0 1 2 100 7 3 4 5 6 7 8 9 1 2 3 4 5 6 7 10000 10 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9
 

Sample Output

1 0 3
 

分析：

      解线性同余方程组

       法一：

      comes from lyminghao
      a[i]<=10 and m <=10 . 所以我们可以枚举到{a[0],a[1],...a[n-1]}的lcm

代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

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

int lcm(int x,int y)
{
    return x*y/gcd(x,y);
}
    
int a[11],b[11];

int main()
{
    int n,m;
    int cse;
    cin>>cse;
    while(cse--)
    {
        scanf("%d %d",&n,&m);
        for(int i=0;i<m;i++)
           scanf("%d",&a[i]);
        for(int i=0;i<m;i++)
           scanf("%d",&b[i]);
        
        int ans=a[0];
        for(int i=1;i<m;i++)
            ans=lcm(ans,a[i]);
            
        int cnt=0;
        for(int i=0;i<=n&&i<=ans;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(i%a[j]!=b[j])
                   break;
                if(j==m-1)
                   cnt=(n-i)/ans+1;
            }
        }
        cout<<cnt<<endl;
    }
    return 0;
}
View Code

注：gcd(x,y)为大整数的最大公约数

欧几里德算法(Euclid)阐述了一种gcd算法。gcd(greatest common divisor)，简言之，我们想求gcd(x,y)，假设(x>y)，如果存在下式:x =  q*y + r，那么则有gcd(x,y) = gcd(y,r) ，其实上式也称为gcd递归定理，即gcd(a,b) = gcd (b,a mod  b)。
这个递归式看似很简单。实则它还是很值得推敲的，首先，它怎么证明？其次，该算法的运行时间为如何？
在密码学中，欧几里德算法有着相当广泛的应用，譬如求乘法逆元，大整数分解等等。。
在<<编程之美>>一书中，给出了不少gcd算法的简单实现。因为gcd算法的实现是递归，所以要特别注意栈溢出。先做个标记，以后会把栈详细分析一下。
 最简单的gcd算法：
         

1int gcd(int x, int y)
2{
3     if(y == 0) return x;    
4     if(x < y)      return gcd(y,x);    
5     else        return gcd(y, x%y); 
6} 


ACM中常用的gcd算法：

1int gcd(int a, int b){ return a == 0 ? b : gcd(b % a, a); } 


经过优化的gcd算法(分成奇偶两种情况)：

int gcd(int x,int y )
 2{
 3    if(x < y) return gcd(y,x);  // x>y
 4    if( y == 0) return x;  // if y=0, x is GCD 
 5    else
 6    {
 7         if( !(x%2) )
 8         {                 
 9           if( !(y%2) )  //x,y both even
10               return 2*gcd(x >> 1, y >> 1);    
11           else      // x is even, y is odd
12               return gcd(x >> 1, y );  
13         }
14         else 
15         {
16           if( !(y%2) )  // x is  odd,  y is even
17               return gcd(x, y >> 1);
18           else       // x, y both odd
19               return gcd(y,x-y); 
20         }
21    }
22}
23

lcm:最小公倍数

返回整数参数的最小公倍数。最小公倍数是所有整数参数 number1、number2 等等的最小正整数倍数。

LCM(number1,number2, ...)
Number1, number2,... 可计算最小公倍数的 1 至 255 个参数。如果参数不是整数，则截尾取整。
如果参数为非数值型，函数 LCM 返回错误值 #VALUE!。
如果有任何参数小于 0，函数 LCM 返回错误值 #NUM!。
如果 LCM(a,b) >=2^53，则 LCM 返回 错误值 #NUM!。

法二：

中国剩余定理.

http://zh.wikipedia.org/wiki/%E4%B8%AD%E5%9B%BD%E5%89%A9%E4%BD%99%E5%AE%9A%E7%90%86

代码：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <cstdio>
#include <cmath>
using namespace std;
 
#ifdef __int64
typedef __int64 LL;
#else
typedef long long LL;
#endif
 
const int inf = 0x3f3f3f3f;
const int maxn = 15;
 
LL a[maxn],b[maxn];
 
LL exgcd(LL a,LL b,LL &x,LL &y) {
    if(b==0) {
        x=1;
        y=0;
        return a;
    }
    LL d=exgcd(b,a%b,x,y);
    LL tmp=x;
    x=y;
    y=tmp-a/b*y;
    return d;
}
int main() {
    int t,n,m;
    LL x,y,g,c;
    scanf("%d",&t);
    while(t--) {
        scanf("%d%d",&n,&m);
        for(int i=0; i<m; i++) {
            scanf("%I64d",&a[i]);
        }
        for(int i=0; i<m; i++) {
            scanf("%I64d",&b[i]);
        }
        for(int i=0; i<m; i++) {
            if(a[i]<=b[i]) {
                puts("0");
                continue;
            }
        }
        bool flag=1;
        for(int i=1; i<m; i++) {
            g=exgcd(a[i-1],a[i],x,y);
            c=b[i]-b[i-1];
            if(c%g) {
                flag=0;
                break;
            }
            x*=c/g;
            y*=c/g;
            a[i]=a[i-1]/g*a[i];
            b[i]=(a[i-1]*x+b[i-1])%a[i];
            b[i]=(b[i]+a[i])%a[i];
        }
        if(flag==0||n<b[m-1]) {
            puts("0");
            continue;
        }
        LL ans=(n-b[m-1])/a[m-1]+1;
        if(b[m-1]==0){
            ans--;
        }
        printf("%I64d
",ans);
    }
    return 0;
}
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/lipching/p/3931393.html