Vanya has a table consisting of 100 rows, each row contains 100 cells. The rows are numbered by integers from 1 to 100 from bottom to top, the columns are numbered from 1 to 100 from left to right.
In this table, Vanya chose n rectangles with sides that go along borders of squares (some rectangles probably occur multiple times). After that for each cell of the table he counted the number of rectangles it belongs to and wrote this number into it. Now he wants to find the sum of values in all cells of the table and as the table is too large, he asks you to help him find the result.
InputThe first line contains integer n (1 ≤ n ≤ 100) — the number of rectangles.
Each of the following n lines contains four integers x1, y1, x2, y2 (1 ≤ x1 ≤ x2 ≤ 100, 1 ≤ y1 ≤ y2 ≤ 100), where x1 and y1 are the number of the column and row of the lower left cell and x2 and y2 are the number of the column and row of the upper right cell of a rectangle.
OutputIn a single line print the sum of all values in the cells of the table.
Sample test(s) input2 1 1 2 3 2 2 3 3output
10input
2 1 1 3 3 1 1 3 3output
18Note
Note to the first sample test:
Values of the table in the first three rows and columns will be as follows:
121
121
110
So, the sum of values will be equal to 10.
Note to the second sample test:
Values of the table in the first three rows and columns will be as follows:
222
222
222
So, the sum of values will be equal to 18.
題意：給你n個矩形，問你面積之和
轉載請注明出處：尋找&星空の孩子
題目鏈接： http://codeforces.com/contest/552/problem/A
1 #include <stdio.h>
2 #include <string.h>
3 #include <algorithm>
4 #include<string>
5 #include<map>
6 using namespace std;
7 const int MAXN = 1005;
8 int a[105][105];
9
10 int main()
11 {
12 int i,j,k,n,m,x1,x2,y1,y2,ans = 0;
13 int maxx = 0,maxy=0,minx=9999,miny=9999;
14 scanf("%d",&n);
15 memset(a,0,sizeof(a));
16 while(n--)
17 {
18 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
19 /* maxx = max(maxx,max(x1,x2));
20 maxy = max(maxy,max(y1,y2));
21 minx = max(minx,max(x1,x2));
22 miny = max(miny,max(y1,y2));*/
23 for(i = x1;i<=x2;i++)
24 {
25 for(j = y1;j<=y2;j++)
26 ans++;
27 }
28 }
29 printf("%d\n",ans);
30 // int ans = 0;
31
32 return 0;
33 }
Vanya got an important task — he should enumerate books in the library and label each book with its number. Each of the n books should be assigned with a number from 1 to n. Naturally, distinct books should be assigned distinct numbers.
Vanya wants to know how many digits he will have to write down as he labels the books.
InputThe first line contains integer n (1 ≤ n ≤ 109) — the number of books in the library.
OutputPrint the number of digits needed to number all the books.
Sample test(s) input13output
17input
4output
4Note
Note to the first test. The books get numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, which totals to 17 digits.
Note to the second sample. The books get numbers 1, 2, 3, 4, which totals to 4 digits.
題意 ：給你一個整數n，問你從1到n一共有多少位。比如n = 13，1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13一共17位。
f[i]表示從1到10i一共有多少位，以753為例，從100到753都是3位數，所以答案就是f[2]+653*3。
轉載請注明出處：尋找&星空の孩子
題目鏈接：http://codeforces.com/contest/552/problem/B
1 #include <stdio.h>
2 #include <string.h>
3 #include <algorithm>
4 #include<string>
5 #include<map>
6 #define LL __int64
7 using namespace std;
8 const int MAXN = 1005;
9 LL n;
10 LL ans = 0;
11 LL a[12]= {0,9,99,999,9999,99999,999999,9999999,99999999,999999999,9999999999};
12
13 int main()
14 {
15 while(~scanf("%I64d",&n))
16 {
17 ans = 0;
18 LL i,j,k = 1;
19 if(n<10)
20 {
21 printf("%I64d\n",n);
22 return 0;
23 }
24 for(i = 1; i<=10; i++)
25 {
26 k *= 10;
27 if(n<k)
28 {
29 ans+=(n-k/10+1)*i;
30 // printf("%I64d %I64d %I64d\n",i,ans,(n-k/10+1)*i);
31 break;
32 }
33 /* else if(n==k)
34 {
35 ans+=(i+1);
36 break;
37 }*/
38 else
39 {
40 ans+=(a[i]-a[i-1])*i;
41 }
42 // printf("%d %I64d\n",i,ans);
43 }
44 printf("%I64d\n",ans);
45 }
46
47 return 0;
48 }
Vanya has a scales for weighing loads and weights of masses w0, w1, w2, ..., w100 grams where w is some integer not less than 2(exactly one weight of each nominal value). Vanya wonders whether he can weight an item with mass m using the given weights, if the weights can be put on both pans of the scales. Formally speaking, your task is to determine whether it is possible to place an item of mass m and some weights on the left pan of the scales, and some weights on the right pan of the scales so that the pans of the scales were in balance.
InputThe first line contains two integers w, m (2 ≤ w ≤ 109, 1 ≤ m ≤ 109) — the number defining the masses of the weights and the mass of the item.
OutputPrint word 'YES' if the item can be weighted and 'NO' if it cannot.
Sample test(s) input3 7output
YESinput
100 99output
YESinput
100 50output
NONote
Note to the first sample test. One pan can have an item of mass 7 and a weight of mass 3, and the second pan can have two weights of masses 9 and 1, correspondingly. Then 7 + 3 = 9 + 1.
Note to the second sample test. One pan of the scales can have an item of mass 99 and the weight of mass 1, and the second pan can have the weight of mass 100.
Note to the third sample test. It is impossible to measure the weight of the item in the manner described in the input.
要用質量為w0,w1,...,w100的砝碼各1個稱出重量m，砝碼可以放在天平左邊也可以放在右邊。問是否可以稱出，輸出YES或NO。
如樣例3，7：左邊放3和物品，右邊放1和9即可。
假設可以稱出，則用w進制表示m，每一位上一定是0，1或w - 1，否則一定不行。
而如果某一位是w - 1則說明當前砝碼跟物品放在一起，相當於給物品加上了這個砝碼的重量。
我們只需要模擬這個過程，提取m的每一位然後計算即可。
轉載請注明出處：尋找&星空の孩子
題目鏈接：http://codeforces.com/contest/552/problem/C
1 #include<string.h>
2 #include<stdio.h>
3 #define LL __int64
4 LL w,m;
5 int main()
6 {
7 scanf("%I64d%I64d",&w,&m);
8 if(w<=3)
9 {
10 printf("YES\n");
11 return 0;
12 }
13 while(m)
14 {
15 if(!((m-1)%w)) m--;
16 else if(!((m+1)%w)) m++;
17 else if(m%w) {printf("NO\n");return 0;}
18 m=m/w;
19 }
20 printf("YES\n");
21 return 0;
22 }
Vanya got bored and he painted n distinct points on the plane. After that he connected all the points pairwise and saw that as a result many triangles were formed with vertices in the painted points. He asks you to count the number of the formed triangles with the non-zero area.
InputThe first line contains integer n (1 ≤ n ≤ 2000) — the number of the points painted on the plane.
Next n lines contain two integers each xi, yi ( - 100 ≤ xi, yi ≤ 100) — the coordinates of the i-th point. It is guaranteed that no two given points coincide.
OutputIn the first line print an integer — the number of triangles with the non-zero area among the painted points.
Sample test(s) input4 0 0 1 1 2 0 2 2output
3input
3 0 0 1 1 2 0output
1input
1 1 1output
0Note
Note to the first sample test. There are 3 triangles formed: (0, 0) - (1, 1) - (2, 0); (0, 0) - (2, 2) - (2, 0); (1, 1) - (2, 2) - (2, 0).
Note to the second sample test. There is 1 triangle formed: (0, 0) - (1, 1) - (2, 0).
Note to the third sample test. A single point doesn't form a single triangle.
給你二維坐標下的n個點，問一共能構成多少個面積不為0的三角形。
轉載請注明出處：尋找&星空の孩子
題目鏈接：http://codeforces.com/contest/552/problem/D
1 #include<cstdio>
2 #include<cmath>
3 #include<iostream>
4 #define PI acos(-1.0)
5 using namespace std;
6
7 struct Point
8 {
9 double x,y;
10 Point(double x=0,double y=0):x(x),y(y){}
11
12 };
13
14 typedef Point Vector;
15
16
17 Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}
18
19
20 Vector operator - (Point A,Point B){return Vector(A.x-B.x,A.y-B.y);}
21
22
23 Vector operator * (Vector A,double p){return Vector(A.x*p,A.y*p);}
24
25
26 Vector operator / (Vector A,double p){return Vector(A.x/p,A.y/p);}
27
28
29 bool operator < (const Point& a,const Point& b){return a.x<b.x||(a.x==b.x && a.y<b.y);}
30
31
32 const double eps = 1e-10;
33
34 int dcmp(double x){if(fabs(x)<eps)return 0;else return x < 0 ? -1 : 1;}
35
36 bool operator == (const Point& a,const Point& b){return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0;}
37
38
39 double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}
40 double length(Vector A){return sqrt(Dot(A,A));}
41 double Angle(Vector A,Vector B){return acos(Dot(A,B)/length(A)/length(B));}
42
43 double Cross(Vector A,Vector B){return A.x*B.y-B.x*A.y;}
44 double Area2(Point A,Point B,Point C){return Cross(B-A,C-A);}
45
46
47 inline Point read_point(Point &P)
48 {
49 scanf("%lf%lf",&P.x,&P.y);
50 return P;
51 }
52 int main()
53 {
54 int n;
55 Point po[2005];
56 scanf("%d",&n);
57 for(int i=0;i<n;i++)
58 read_point(po[i]);
59 if(n<3){printf("0\n");return 0;}
60 int cnt=0;
61 for(int i=0;i<n;i++)
62 {
63 for(int j=i+1;j<n;j++)
64 {
65 for(int k=j+1;k<n;k++)
66 {
67 if(Area2(po[i],po[j],po[k])!=0) cnt++;
68 }
69 }
70 }
71 printf("%d\n",cnt);
72 return 0;
73 }
Vanya is doing his maths homework. He has an expression of form 
, where x1, x2, ..., xn are digits from 1 to 9, and sign 
represents either a plus '+' or the multiplication sign '*'. Vanya needs to add one pair of brackets in this expression so that to maximize the value of the resulting expression.
The first line contains expression s (1 ≤ |s| ≤ 5001, |s| is odd), its odd positions only contain digits from 1 to 9, and even positions only contain signs + and * .
The number of signs * doesn't exceed 15.
OutputIn the first line print the maximum possible value of an expression.
Sample test(s) input3+5*7+8*4output
303input
2+3*5output
25input
3*4*5output
60Note
Note to the first sample test. 3 + 5 * (7 + 8) * 4 = 303.
Note to the second sample test. (2 + 3) * 5 = 25.
Note to the third sample test. (3 * 4) * 5 = 60 (also many other variants are valid, for instance, (3) * 4 * 5 = 60).
給你一個表達式，只有乘號和加號，數字都是1到9，要求加一個括號，使得表達式的值最大，問最大是多少。乘號個數<=15。
左括號一定在乘號右邊，右括號一定在乘號左邊，因為如果不是這樣的話，一定可以調整括號的位置使表達式的值增大。這個應該不難想。
於是只要枚舉括號的位置然後計算表達式即可。
轉載請注明出處：尋找&星空の孩子
題目鏈接：http://codeforces.com/contest/552/problem/E
1 #include<stdio.h>
2 #include<iostream>
3 #include<string.h>
4 #include<math.h>
5 using namespace std;
6 const int N = 5005;
7 #define LL __int64
8
9 char fh[N],s[N];
10 LL num[N];
11 int ftop,ntop ,slen;
12 void calculate(){
13 if(fh[ftop]=='+')
14 num[ntop-1]+=num[ntop],ntop--;
15 else if(fh[ftop]=='-')
16 num[ntop-1]-=num[ntop],ntop--;
17 else if(fh[ftop]=='*')
18 num[ntop-1]*=num[ntop],ntop--;
19 else if(fh[ftop]=='/')
20 num[ntop-1]/=num[ntop],ntop--;
21 ftop--;
22 }
23 void countfuction(int l,int r){
24 ftop=0;ntop=0;
25 int flagNum=0;
26 LL ans=0;
27 for(int i=0; i<=slen; ++i){
28
29 if(i!=slen&&(s[i]>='0'&&s[i]<='9')){
30 ans=ans*10+s[i]-'0';
31 flagNum=1;
32 }
33 else{
34 if(flagNum)num[++ntop]=ans; flagNum=0; ans=0;
35 if(i==slen)break;
36 if(s[i]=='+'||s[i]=='-'){
37 while(ftop&&fh[ftop]!='(') calculate();
38 fh[++ftop]=s[i];
39 }
40 else if(s[i]=='*'&&i==r){
41 while(ftop&&fh[ftop]!='(') calculate(); ftop--;
42 while(ftop&&(fh[ftop]=='*'||fh[ftop]=='/')) calculate();
43 fh[++ftop]=s[i];//printf("# ");
44 }
45 else if(s[i]=='*'||i==l){
46 while(ftop&&(fh[ftop]=='*'||fh[ftop]=='/')) calculate();
47 fh[++ftop]=s[i];
48 if(i==l)
49 fh[++ftop]='(';
50 }
51 }
52 }
53 while(ftop) calculate();
54
55 }
56 int main(){
57
58 while(scanf("%s",s)>0){
59 LL ans=0;
60 int id[20],k=0;
61 for(int i=strlen(s); i>=0; i--)
62 s[i+2]=s[i];
63 s[0]='1'; s[1]='*';
64 slen=strlen(s);
65 s[slen]='*'; s[slen+1]='1'; s[slen+2]='\0';
66 slen=strlen(s);
67 for(int i=0; i<slen; i++)
68 if(s[i]=='*')
69 id[k++]=i;
70
71 for(int i=0; i<k-1; i++)
72 for(int j=i+1; j<k; j++){
73 countfuction(id[i],id[j]);
74 if(num[1]>ans)
75 ans=num[1];
76 }
77 printf("%I64d\n",ans);
78 }
79 }
