A.Vanya and Table
Vanya has a table consisting of 100 rows, each row contains 100 cells. The rows are numbered by integers from 1to 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 x1and 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.
Sample test(s)
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 first three rows and columns will be as follows:
222
222
222
So, the sum of values will be equal to 18.
题目类型：简单模拟
算法分析：由于n比较小，所以直接使用O(n^3)的暴力模拟可以过掉，将每个位置自加1后，统计最后所有数的和即可，当然最好的方法是直接算出每一次要加的值，时间复杂度是O(n)的
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; const int INF = 0x7FFFFFFF; const int MOD = 1000000000 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 100 + 66; int a[maxn][maxn]; int main() { // ifstream cin("aaa.txt"); memset (a, 0, sizeof (a)); int n; cin >>n; for (int i = 1; i <= n; i++) { int x1, x2, y1, y2; cin >> x1 >> y1 >> x2 >> y2; for (int j = x1; j <= x2; j++) for (int k = y1; k <= y2; k++) a[j][k]++; } long long sum = 0; for (int i = 1; i <= 100; i++) for (int j = 1; j <= 100; j++) sum += a[i][j]; cout << sum << endl; return 0; } |
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.
Sample test(s)
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.
题目类型：简单模拟
算法分析：首先得到所求数n的位数，然后考虑到1~9中有9个数字，10~99中有90*2个数字，以此类推。直接先求出小于n的整范围的值，最后再加上当前位数的数字个数和
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; const int INF = 0x7FFFFFFF; const int MOD = 1000000000 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 100 + 66; const long long flag[] = {0, 9, 90, 900, 9000, 90000, 900000, 9000000, 90000000, 900000000, 9000000000, 90000000000}; long long power (int val) { long long sum = 1; for (int i =1 ; i <= val - 1; i++) sum *= 10; return sum; } int main() { // ifstream cin ("aaa.txt"); long long n; cin >>n; int a = floor (log10 ((double) n)) + 1; long long sum = 0; for (int i = 1; i <= a - 1; i++) sum += flag[i] * i; sum += (n - power (a) + 1) * a; cout << sum << endl; return 0; } |
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 massm 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.
Sample test(s)
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.
题目类型：进制转换
算法分析：本题要求的是是否存在m = A0 * w^0 + A1 * w^1 + A2 * w^2 + …… A100 * w^100。其中Ai只能取值0、1和w - 1(因为题目中说砝码最多用一个)，取其他的值是无解的。其中Ai = 0表示w^i这种砝码不取，Ai = 1表示w^i这种砝码取，而Ai = w - 1表示在待称重物品一侧放置砝码w^i。解释最后这种情况，由于有Ai * w^i = (w - 1) * w^i = w^(i+1) – w^i。方程左边减去一个w^i等价于右边加上一个w^i。由分析可知，可以使用进制转换的思想从低位到高位判断位上的数字。由于转换时方程左右要同时不断地除以w。如果有m = 1 * w^0 + 0 * w^1 + (w-1) * w^2 + …… 1 * w^100。则m / w ^ 2 = w - 1 + …… 1 * w^100，此时要在方程的左边加上一个1，切记！！！！！！本题还可以使用贪心的方法，就是每次先拿最大砝码去称，直到称完或者还留下一些没有称完(无解)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; const int INF = 0x7FFFFFFF; const int MOD = 1000000000 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 100 + 66; int main() { // ifstream cin ("aaa.txt"); long long w, m; cin >> w >> m; long long temp; bool is_valid = true; while (m) { temp = m % w; m /= w; if (temp == 0) continue; else if (temp == 1) continue; else if (temp == w - 1) m++; else { is_valid = false; break; } } if (!is_valid) cout << "NO" << endl; else cout << "YES" << endl; return 0; } |
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.
Sample test(s)
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.
题目类型：斜率分块+组合
算法分析：用总的方案数减去不满足条件的方案数即可，其中总的方案数为C(n, 3)，不满足条件的方案数是那些共线点所组成的方案。所以可以先按照标号枚举每一个点，然后计算该点和其它点(标号比它大的点)之间的斜率，最后对计算出来的斜率进行排序，判断共线点的个数temp，然后累加C(temp, 2)到sum上。最后直接输出C(n, 3) - sum即可。时间复杂度是O(n(n + nlog(n)+n))
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; const int INF = 0x7FFFFFFF; const int MOD = 1000000000 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 2000 + 66; struct Node { int x, y; }; Node ans[maxn]; double b[maxn]; int len; long long res; long long Com (long long n, long long r) { if(n - r < r) r = n - r; long long s = 1; long long j = 1, i; for(i = 0;i < r; i++) { s *= (n - i); while (j <= r && s % j == 0) { s /= j; j++; } } return s; } void Solve () { long long tempsum = 1; for (int i = 1; i < len; ) { if (fabs (b[i] - b[i-1]) < EPS) { while (i < len && fabs (b[i] - b[i-1]) < EPS) { tempsum++; i++; } } else { if (tempsum >= 2) res += Com (tempsum, 2); tempsum = 1; i++; } } if (tempsum > 1) res += Com (tempsum, 2); } int main() { // ifstream cin ("aaa.txt"); int n; cin >> n; if (n < 3) { cout << "0" << endl; return 0; } for (int i = 1; i <= n; i++) cin >> ans[i].x >> ans[i].y; res = 0; for (int i = 1; i <= n; i++) { len = 0; for (int j = i + 1; j <= n; j++) { if (ans[i].x == ans[j].x) b[len++] = INF; else if (ans[i].y == ans[j].y) b[len++] = 0; else b[len++] = (ans[i].y - ans[j].y) * 10.0 / 10 / (ans[i].x - ans[j].x); } sort (b, b + len); Solve (); } cout << Com (n, 3) - res << endl; return 0; } |
E.Vanya and Brackets
Vanya is doing his maths homework. He has an expression of form , where x1, x2, ..., xnare digits from 1 to 9, and sign represents either a plus '+' or the multiplication sign '*'. Vanya needs to add onepair of brackets in this expression so that to maximize the value of the resulting expression.
Input
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.
Output
In the first line print the maximum possible value of an expression.
Sample test(s)
input
3+5*7+8*4
output
303
input
2+3*5
output
25
input
3*4*5
output
60
Note
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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; const int INF = 0x7FFFFFFF; const int MOD = 1000000000 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 2000 + 66; stack <long long> a; stack <char> b; string s; long long Cal (int aa, int bb) { while (!a.empty ()) a.pop (); while (!b.empty ()) b.pop (); for (int k = aa + 1; k <= bb - 1; k++) { if (s[k] >= '0' && s[k] <= '9') { a.push (s[k] - '0'); while (!b.empty () && b.top () == '*') { long long temp = a.top (); a.pop (); temp *= a.top (), a.pop (); b.pop (); a.push (temp); } } else b.push (s[k]); } while (!b.empty ()) { long long temp = a.top (); a.pop (); if (b.top () == '+') temp += a.top (); else temp *= a.top (); a.pop (), b.pop (); a.push (temp); } return a.top (); } int main() { // ifstream cin ("aaa.txt"); cin >> s; int len = s.size (); long long maxval = Cal (-1, len), val; for (int i = 0; i < len; i++) { for (int j = i + 1; j < len; j++) { if ((s[i] == '*' && s[j] == '*') || (i == 0 && s[j] == '*') || (s[i] == '*' && j == len - 1)) { int L, R; if (s[i] == '*' && s[j] == '*') L = i, R = j; else if (i == 0 && s[j] == '*') L = -1, R = j; else if (s[i] == '*' && j == len - 1) L = i, R = len; val = Cal (L, R); while (!a.empty()) a.pop (); while (!b.empty ()) b.pop (); bool is_first = true; for (int k = 0; k < len; k++) { if (k > L && k < R && !is_first) continue; if (k > L && k < R && is_first) { is_first = false; a.push (val); } else { if (s[k] >= '0' && s[k] <= '9') { a.push (s[k] - '0'); while (!b.empty () && b.top () == '*') { long long temp = a.top (); a.pop (); temp *= a.top () , a.pop (), b.pop (); a.push (temp); } } else b.push (s[k]); } } while (!b.empty ()) { long long temp = a.top (); a.pop (); if (b.top () == '+') temp += a.top (); else temp *= a.top (); a.pop (), b.pop (); a.push (temp); } maxval = max (maxval, a.top ()); } } } cout << maxval << endl; return 0; } |