四校训练 warm up 14

A:Pythagoras's Revenge

代码：

 1 #include<cstdio>
 2 #define ll long long
 3 using namespace std;
 4 int main()
 5 {
 6     ll a;
 7     while(scanf("%lld",&a)!=EOF)
 8     {
 9         if (a==0) break;
10         ll aa=a*a;
11         int ans=0;
12         for(ll i=1;i<a;i++)
13         {
14             ll x=i;
15             if (aa%i!=0) continue;
16             ll y=aa/i;
17             if ((x+y)*(y-x)%2!=0) continue;
18             if ((y-x)/2>a) ans++;
19         }
20         printf("%d
",ans);
21     }
22     return 0;
23 }

View Code

B:Digit Solitaire

代码：

 1 #include<cstdio>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int b;
 7     while(scanf("%d",&b)&&b)
 8     {
 9         printf("%d",b);
10         while(b/10>0)
11         {
12             int tmp=1;
13             while(b>0)
14             {
15                 tmp*=b%10;
16                 b/=10;
17             }
18             b=tmp;
19             printf(" %d",tmp);
20         }
21         printf("
");
22     }
23     return 0;
24 }

View Code

C：Any Way You Slice It

计算几何

代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 #define maxn 150
 6 #define pi acos(-1)
 7 #define eps 1e-5
 8 using namespace std;
 9 
10 struct point
11 {
12     double x,y;
13     point(double x=0,double y=0):x(x),y(y){}
14 } p[maxn];
15 point operator-(point a,point b){return point(a.x-b.x,a.y-b.y);}
16 double cross(point a,point b){return a.x*b.y-a.y*b.x;}
17 int dcmp(double x)
18 {
19     if(fabs(x)<eps)return 0;
20     else return x<0?-1:1;
21 }
22 bool xiangjiao(point a1,point a2,point b1,point b2)
23 {
24     double c1=cross(a2-a1,b1-a1),c2=cross(a2-a1,b2-a1);
25     double c3=cross(b2-b1,a1-b1),c4=cross(b2-b1,a2-b1);
26     return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
27 }
28 
29 
30 int main()
31 {
32     int n;
33     double d,x;
34     while(scanf("%d",&n)&&n)
35     {
36         bool flag=1;
37         int ans=0;
38         p[0]= point(0,0);
39         double ang=pi/2;
40         for(int i=0; i<n; i++)
41         {
42             scanf("%lf%lf",&d,&x);
43             ang+=d/180*pi;
44             p[i+1].x=p[i].x+cos(ang)*x;
45             p[i+1].y=p[i].y+sin(ang)*x;
46             if(i>1&&flag==1)
47             {
48                 for(int j=0; j<i; j++)
49                 {
50                     if(xiangjiao(p[j],p[j+1],p[i],p[i+1])==1)
51                         {
52                             flag=0;
53                             ans=i+1;
54                         }
55                 }
56             }
57 
58         }
59         if(flag==1)puts("SAFE");
60         else printf("%d
",ans);
61     }
62     return 0;
63 }

View Code

D：Is the Name of This Problem

代码：

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<string>
  4 #include<iostream>
  5 #define maxn 109
  6 using namespace std;
  7 
  8 char s1[maxn];
  9 char s2[maxn];
 10 int main()
 11 {
 12 //    freopen("in.txt","r",stdin);
 13     while(gets(s1))
 14     {
 15         bool flag=1;
 16         memset(s2,0,sizeof s2);
 17         if(s1[0]=='E'&&s1[1]=='N'&&s1[2]=='D'&&!s1[3])break;
 18         int l=strlen(s1);
 19         if(s1[0]!='"')
 20         {
 21             puts("not a quine");
 22             continue;
 23         }
 24         int i,cnt=0;
 25         for(i=1; i<l; i++)
 26         {
 27             if(s1[i]=='"')break;
 28             s2[cnt++]=s1[i];
 29         }
 30         if(cnt==0)
 31         {
 32             puts("not a quine");
 33             continue;
 34         }
 35         i++;
 36         if(s1[i]!=' ')
 37         {
 38             flag=0;
 39         }
 40         i++;
 41         int j=0;
 42         for(;j<cnt;j++)
 43         {
 44             if(s2[j]>='A'&&s2[j]<='Z')continue;
 45             else if(s2[j]==' ')continue;
 46             else
 47             {
 48                 flag=0;break;
 49             }
 50         }
 51         j=0;
 52         for(;i<l;i++)
 53         {
 54             if(s1[i]!=s2[j])
 55             {
 56                 flag=0;break;
 57             }
 58             j++;
 59             if(j>cnt){flag=0;break;}
 60         }
 61         if(j<cnt)flag=0;
 62         if(flag)printf("Quine(%s)
",s2);
 63         else puts("not a quine");
 64     }
 65     return 0;
 66 }
 67 #include<cstdio>
 68 #include<cstring>
 69 #include<string>
 70 #include<iostream>
 71 #define maxn 109
 72 using namespace std;
 73 
 74 char s1[maxn];
 75 char s2[maxn];
 76 int main()
 77 {
 78 //    freopen("in.txt","r",stdin);
 79     while(gets(s1))
 80     {
 81         bool flag=1;
 82         memset(s2,0,sizeof s2);
 83         if(s1[0]=='E'&&s1[1]=='N'&&s1[2]=='D'&&!s1[3])break;
 84         int l=strlen(s1);
 85         if(s1[0]!='"')
 86         {
 87             puts("not a quine");
 88             continue;
 89         }
 90         int i,cnt=0;
 91         for(i=1; i<l; i++)
 92         {
 93             if(s1[i]=='"')break;
 94             s2[cnt++]=s1[i];
 95         }
 96         if(cnt==0)
 97         {
 98             puts("not a quine");
 99             continue;
100         }
101         i++;
102         if(s1[i]!=' ')
103         {
104             flag=0;
105         }
106         i++;
107         int j=0;
108         for(;j<cnt;j++)
109         {
110             if(s2[j]>='A'&&s2[j]<='Z')continue;
111             else if(s2[j]==' ')continue;
112             else
113             {
114                 flag=0;break;
115             }
116         }
117         j=0;
118         for(;i<l;i++)
119         {
120             if(s1[i]!=s2[j])
121             {
122                 flag=0;break;
123             }
124             j++;
125             if(j>cnt){flag=0;break;}
126         }
127         if(j<cnt)flag=0;
128         if(flag)printf("Quine(%s)
",s2);
129         else puts("not a quine");
130     }
131     return 0;
132 }

View Code

F：LRU Caching

代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define maxn 1000009
 5 using namespace std;
 6 int frecount;
 7 int n;
 8 struct node
 9 {
10     int id;
11     int fre;
12     bool operator <(const node &t)const
13     {
14         return fre<t.fre;
15     }
16 } no[30];
17 
18 void shuchu()
19 {
20     sort(no,no+n);
21     for(int i=0; i<n; i++)
22     {
23         if(no[i].id>0)
24             printf("%c",no[i].id+'A'-1);
25     }
26     puts("");
27 }
28 
29 void add(char s)
30 {
31     bool flag=0;
32     frecount++;
33     for(int i=0; i<n; i++)
34         if(no[i].id==s-'A'+1)
35         {
36             no[i].fre=frecount;
37             flag=1;
38             break;
39         }
40     if(flag==0)
41     {
42         sort(no,no+n);
43         no[0].id=s-'A'+1;
44         no[0].fre=frecount;
45     }
46 }
47 
48 char s[maxn];
49 
50 int main()
51 {
52 //    freopen("in.txt","r",stdin);
53     int ca=1;
54     while(scanf("%d",&n)&&n)
55     {
56         printf("Simulation %d
",ca++);
57         frecount=1;
58         for(int i=0; i<n; i++)
59         {
60             no[i].id=-1;
61             no[i].fre=-1;
62         }
63         scanf("%s",s);
64         int l=strlen(s);
65         for(int i=0; i<l; i++)
66         {
67             if(s[i]=='!')
68                 shuchu();
69             else add(s[i]);
70         }
71     }
72     return 0;
73 }

View Code

G：Jugglefest

代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 int p[10];
 5 char s[40];
 6 int main()
 7 {
 8 //    freopen("in.txt","r",stdin);
 9     int n;
10     while(scanf("%d",&n)&&n)
11     {
12         bool flag=1;
13         memset(p,0,sizeof p);
14         memset(s,0,sizeof s);
15         for(int i=0; i<n; i++)
16         {
17             scanf("%d",&p[i]);
18         }
19         int cnt=0,num=0;
20         for(int i=0; i<20; i++)
21         {
22             if(s[i]==0)s[i]='A'+cnt++;
23             if(s[i+p[num%n]]!=0&&(i+p[num%n]<20))flag=0;
24             else s[i+p[num%n]]=s[i];
25             num++;
26         }
27         if(flag)
28         {
29             for(int i=0;i<20;i++)
30                 putchar(s[i]);
31             puts("");
32         }
33         else puts("CRASH");
34     }
35     return 0;
36 }

View Code