首页 > 代码库 > 2017-4-23-Train:Codeforces Round #308 (Div. 2)
2017-4-23-Train:Codeforces Round #308 (Div. 2)
A. Vanya and Table(思考)
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.
Input
The 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.
Output
In a single line print the sum of all values in the cells of the table.
Examples
input
2
1 1 2 3
2 2 3 3
output
10
input
2
1 1 3 3
1 1 3 3
output
18
Note
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 firt three rows and columns will be as follows:
222
222
222
So, the sum of values will be equal to 18.
Means:
给定一个数n,然后有n行,每行两个坐标,前两个为左下角左边,后两个为右上角左边,每次操作都会使得矩形(x1 , y1) -> (x2 , y2)内的所有格子+1,(初始都是0,问你这个矩形内总和是多少)
Solve:
其实就是求每一行给出的矩形面积之和啦
Code:
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define LSON id << 1 , l , mid 4 #define RSON id << 1 | 1 , mid + 1 , r 5 #define ROOT 1 , 1 , n 6 #define CLR(x , y) memset(x , y , sizeof(x)) 7 #define LOWBIT(x) x & (-x) 8 #define FORN(i , a , n) for(int i = (a) ; i <= (n) ; ++i) 9 #define FORP(i , n , a) for(int i = (n) ; i >= (a) ; --i)10 #define CASE(x) printf("Case %d: ", x)11 #define SFD(x) scanf("%lf" , &x)12 #define SFC(x) scanf(" %c" , &x)13 #define SFS(x) scanf(" %s" , x)14 #define SFI(x) scanf("%d" , &x)15 #define SFL(x) scanf("%lld" , &x)16 #define PFF(x) printf("%f\n" , x)17 #define PFD(x) printf("%lf\n" , x)18 #define PFI(x) printf("%d\n" , x)19 #define PFC(x) printf("%c\n" , x)20 #define PFS(x) printf("%s\n" , x)21 #define PFL(x) printf("%lld\n" , x)22 #define LOCAL23 static const double PI = acos(-1.0);24 static const double EPS = 1e-8;25 static const int INF = 0X3fffffff;26 typedef __int64 LL;27 typedef double DB;28 template<class T> inline29 T read(T &x)30 {31 x = 0;32 int f = 1 ; char ch = getchar();33 while (ch < ‘0‘ || ch > ‘9‘) {if (ch == ‘-‘) f = -1; ch = getchar();}34 while (ch >= ‘0‘ && ch <= ‘9‘) {x = x * 10 + ch - ‘0‘; ch = getchar();}35 x *= f;36 }37 int main()38 {39 #ifdef LOCAL40 //freopen("D:\\系统优化\\Desktop\\littlepea\\in.data" , "r" , stdin);41 #endif42 int n;43 read(n);44 int ans = 0;45 while(n--)46 {47 int x1 , y1 , x2 , y2;48 read(x1);read(y1);read(x2);read(y2);49 ans += (x2 - x1 + 1) * (y2 - y1 + 1);50 }51 PFI(ans);52 }
B. Vanya and Books(水题)
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.
Input
The first line contains integer n (1 ≤ n ≤ 109) — the number of books in the library.
Output
Print the number of digits needed to number all the books.
Examples
input
13
output
17
input
4
output
4
Note
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.
Means:
给定一个数,问你从1到这个数一共有几位
Solve:
直接10倍10倍增加就行了
Code:
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define LSON id << 1 , l , mid 4 #define RSON id << 1 | 1 , mid + 1 , r 5 #define ROOT 1 , 1 , n 6 #define CLR(x , y) memset(x , y , sizeof(x)) 7 #define LOWBIT(x) x & (-x) 8 #define FORN(i , a , n) for(int i = (a) ; i <= (n) ; ++i) 9 #define FORP(i , n , a) for(int i = (n) ; i >= (a) ; --i)10 #define CASE(x) printf("Case %d: ", x)11 #define SFD(x) scanf("%lf" , &x)12 #define SFC(x) scanf(" %c" , &x)13 #define SFS(x) scanf(" %s" , x)14 #define SFI(x) scanf("%d" , &x)15 #define SFI64(x) scanf("%I64d" , &x)16 #define PFF(x) printf("%f\n" , x)17 #define PFD(x) printf("%lf\n" , x)18 #define PFI(x) printf("%d\n" , x)19 #define PFC(x) printf("%c\n" , x)20 #define PFS(x) printf("%s\n" , x)21 #define PFI64(x) printf("%I64d\n" , x)22 #define LOCAL23 static const double PI = acos(-1.0);24 static const double EPS = 1e-8;25 static const int INF = 0X3fffffff;26 typedef __int64 LL;27 typedef double DB;28 template<class T> inline29 T read(T &x)30 {31 x = 0;32 int f = 1 ; char ch = getchar();33 while (ch < ‘0‘ || ch > ‘9‘) {if (ch == ‘-‘) f = -1; ch = getchar();}34 while (ch >= ‘0‘ && ch <= ‘9‘) {x = x * 10 + ch - ‘0‘; ch = getchar();}35 x *= f;36 }37 38 /************************Little Pea****************************/39 40 static const LL a[12]= {0 , 9 , 99 , 999 , 9999 , 99999 , 999999 , 9999999 , 99999999 , 999999999 , 9999999999};41 int main()42 {43 #ifdef LOCAL44 //freopen("D:\\系统优化\\Desktop\\littlepea\\in.data" , "r" , stdin);45 #endif46 LL n;47 SFI64(n);48 LL pos = 1;49 LL ans = 0;50 for(int i = 1 ; i < 12 ; ++i)51 {52 pos *= 10;53 if(n < pos)54 {55 ans += (n - pos / 10 + 1) * i;56 break;57 }58 else59 ans += (a[i] - a[i - 1]) * i;60 }61 PFI64(ans);62 }
C. Vanya and Scales(数学 + 进制思想)
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.
Input
The 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.
Output
Print word ‘YES‘ if the item can be weighted and ‘NO‘ if it cannot.
Examples
input
3 7
output
YES
input
100 99
output
YES
input
100 50
output
NO
Note
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.
Means:
Solve:
Code:
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define LSON id << 1 , l , mid 4 #define RSON id << 1 | 1 , mid + 1 , r 5 #define ROOT 1 , 1 , n 6 #define CLR(x , y) memset(x , y , sizeof(x)) 7 #define LOWBIT(x) x & (-x) 8 #define FORN(i , a , n) for(int i = (a) ; i <= (n) ; ++i) 9 #define FORP(i , n , a) for(int i = (n) ; i >= (a) ; --i)10 #define CASE(x) printf("Case %d: ", x)11 #define SFD(x) scanf("%lf" , &x)12 #define SFC(x) scanf(" %c" , &x)13 #define SFS(x) scanf(" %s" , x)14 #define SFI(x) scanf("%d" , &x)15 #define SFI64(x) scanf("%I64d" , &x)16 #define PFF(x) printf("%f\n" , x)17 #define PFD(x) printf("%lf\n" , x)18 #define PFI(x) printf("%d\n" , x)19 #define PFC(x) printf("%c\n" , x)20 #define PFS(x) printf("%s\n" , x)21 #define PFI64(x) printf("%I64d\n" , x)22 #define LOCAL23 static const double PI = acos(-1.0);24 static const double EPS = 1e-8;25 static const int INF = 0X3fffffff;26 typedef __int64 LL;27 typedef double DB;28 template<class T> inline29 T read(T &x)30 {31 x = 0;32 int f = 1 ; char ch = getchar();33 while (ch < ‘0‘ || ch > ‘9‘) {if (ch == ‘-‘) f = -1; ch = getchar();}34 while (ch >= ‘0‘ && ch <= ‘9‘) {x = x * 10 + ch - ‘0‘; ch = getchar();}35 x *= f;36 }37 38 /************************Little Pea****************************/39 40 41 static const LL a[12]= {0 , 9 , 99 , 999 , 9999 , 99999 , 999999 , 9999999 , 99999999 , 999999999 , 9999999999};42 int main()43 {44 #ifdef LOCAL45 //freopen("D:\\系统优化\\Desktop\\littlepea\\in.data" , "r" , stdin);46 #endif47 LL w , m;48 read(w);read(m);49 while(m)50 {51 if(!((m - 1) % w))52 --m;53 else if(!((m + 1) % w))54 ++m;55 else if(m % w)56 {57 PFS("NO");58 return 0;59 }60 m /= w;61 }62 PFS("YES");63 }
D. Vanya and Triangles(计算几何)
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.
Input
The 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.
Output
In the first line print an integer — the number of triangles with the non-zero area among the painted points.
Examples
input
4
0 0
1 1
2 0
2 2
output
3
input
3
0 0
1 1
2 0
output
1
input
1
1 1
output
0
Note
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.
Means:
给定n个点,问你能组成多少个三角形
Solve:
三角形矢量向量面积公式暴力怼,公式详见该篇的第I题
Code:
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define LSON id << 1 , l , mid 4 #define RSON id << 1 | 1 , mid + 1 , r 5 #define ROOT 1 , 1 , n 6 #define CLR(x , y) memset(x , y , sizeof(x)) 7 #define LOWBIT(x) x & (-x) 8 #define FORN(i , a , n) for(int i = (a) ; i <= (n) ; ++i) 9 #define FORP(i , n , a) for(int i = (n) ; i >= (a) ; --i)10 #define CASE(x) printf("Case %d: ", x)11 #define SFD(x) scanf("%lf" , &x)12 #define SFC(x) scanf(" %c" , &x)13 #define SFS(x) scanf(" %s" , x)14 #define SFI(x) scanf("%d" , &x)15 #define SFI64(x) scanf("%I64d" , &x)16 #define PFF(x) printf("%f\n" , x)17 #define PFD(x) printf("%lf\n" , x)18 #define PFI(x) printf("%d\n" , x)19 #define PFC(x) printf("%c\n" , x)20 #define PFS(x) printf("%s\n" , x)21 #define PFI64(x) printf("%I64d\n" , x)22 #define LOOP(i , j , k) for(int i = j ; i <= k ; ++i)23 #define PB(x) push_back(x)24 #define LOCAL25 static const double PI = acos(-1.0);26 static const double EPS = 1e-8;27 static const int INF = 0X3fffffff;28 typedef __int64 LL;29 typedef double DB;30 template<class T> inline31 T read(T &x)32 {33 x = 0;34 int f = 1 ; char ch = getchar();35 while (ch < ‘0‘ || ch > ‘9‘) {if (ch == ‘-‘) f = -1; ch = getchar();}36 while (ch >= ‘0‘ && ch <= ‘9‘) {x = x * 10 + ch - ‘0‘; ch = getchar();}37 x *= f;38 }39 40 /************************Little Pea****************************/41 42 43 static const int MAXN = 2017;44 struct Node45 {46 int x , y;47 };48 vector <Node> vec;49 Node data[MAXN];50 int n;51 int Area(int x1 , int y1 , int x2 , int y2 , int x3 , int y3)52 {53 return abs(x1 * y2 + x2 * y3 + x3 * y1 - (x3 * y2 + x2 * y1 + x1 * y3));54 }55 int main()56 {57 #ifdef LOCAL58 //freopen("D:\\系统优化\\Desktop\\littlepea\\in.data" , "r" , stdin);59 #endif60 read(n);61 for(int i = 1 ; i <= n ; ++i)62 {63 read(data[i].x);64 read(data[i].y);65 }66 /*for(int i = 1 ; i <= n ; ++i)67 {68 for(int j = i + 1 ; j <= n ; ++j)69 {70 vec.push_back({abs(data[i].x - data[j].x) , abs(data[i].y - data[j].y)});71 }72 }*/73 LL ans = 0;74 for(int i = 1 ; i <= n ; ++i)75 {76 for(int j = i + 1 ; j <= n ; ++j)77 {78 for(int k = j + 1 ; k <= n ; ++k)79 {80 int x1 = data[i].x , y1 = data[i].y;81 int x2 = data[j].x , y2 = data[j].y;82 int x3 = data[k].x , y3 = data[k].y;83 if(Area(x1 , y1 , x2 , y2 , x3 , y3))84 ++ans;85 }86 87 }88 }89 PFI64(ans);90 }
2017-4-23-Train:Codeforces Round #308 (Div. 2)