A Elephant
An elephant decided to visit his friend. It turned out that the elephant's house is located at point 0 and his friend's house is located at point x(x > 0) of the coordinate line. In one step the elephant can move 1, 2, 3, 4 or 5 positions forward. Determine, what is the minimum number of steps he need to make in order to get to his friend's house.
Input
The first line of the input contains an integer x (1 ≤ x ≤ 1 000 000) — The coordinate of the friend's house.
Output
Print the minimum number of steps that elephant needs to make to get from point 0 to point x.
Sample test(s)
input
5
output
1
input
12
output
3
Note
In the first sample the elephant needs to make one step of length 5 to reach the point x.
In the second sample the elephant can get to point x if he moves by 3, 5 and 4. There are other ways to get the optimal answer but the elephant cannot reach x in less than three moves.
题目类型：简单构造
算法分析：由于每次可以走1~5步，所以每5步可以走一次，注意要向上取整
|
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 |
/************************************************* Author :supermaker Created Time :2016/1/27 18:39:21 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #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; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; int main() { //CFF; //CPPFF; int n; scanf ("%d", &n); if (n % 5 == 0) printf ("%d\n", n / 5); else printf ("%d\n", n / 5 + 1); return 0; } |
B Chocolate
Bob loves everything sweet. His favorite chocolate bar consists of pieces, each piece may contain a nut. Bob wants to break the bar of chocolate into multiple pieces so that each part would contain exactly one nut and any break line goes between two adjacent pieces.
You are asked to calculate the number of ways he can do it. Two ways to break chocolate are considered distinct if one of them contains a break between some two adjacent pieces and the other one doesn't.
Please note, that if Bob doesn't make any breaks, all the bar will form one piece and it still has to have exactly one nut.
Input
The first line of the input contains integer n (1 ≤ n ≤ 100) — the number of pieces in the chocolate bar.
The second line contains n integers ai (0 ≤ ai ≤ 1), where 0 represents a piece without the nut and 1 stands for a piece with the nut.
Output
Print the number of ways to break the chocolate into multiple parts so that each part would contain exactly one nut.
Sample test(s)
input
3
0 1 0
output
1
input
5
1 0 1 0 1
output
4
Note
In the first sample there is exactly one nut, so the number of ways equals 1 — Bob shouldn't make any breaks.
In the second sample you can break the bar in four ways:
10|10|1
1|010|1
10|1|01
1|01|01
题目类型：简单计数
算法分析：由于题目说每个1都要被分到一个块中，且只分一个。所以相邻1之间的距离决定了最后的分配方案中这两个1的分配数。利用分布乘法原理，最后的结果就是序列中所有相邻1之间距离的乘积。注意当所有的点都是0时，最后的结果要特判为0！！！
|
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 |
/************************************************* Author :supermaker Created Time :2016/1/27 18:51:06 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #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; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 100 + 66; int aa[maxn], pos[maxn]; int main() { //CFF; //CPPFF; int n; scanf ("%d", &n); int zero = 0; for (int i = 1; i <= n; i++) { scanf ("%d", &aa[i]); if (!aa[i]) zero++; } if (zero == n) puts ("0"); else { LL res = 1; int len = 0; for (int i = 1; i <= n; i++) if (aa[i]) pos[++len] = i; for (int i = 2; i <= len; i++) res *= (pos[i] - pos[i-1]); printf ("%I64d\n", res); } return 0; } |
C Watering Flowers
A flowerbed has many flowers and two fountains.
You can adjust the water pressure and set any values r1(r1 ≥ 0) and r2(r2 ≥ 0), giving the distances at which the water is spread from the first and second fountain respectively. You have to set such r1 and r2 that all the flowers are watered, that is, for each flower, the distance between the flower and the first fountain doesn't exceed r1, or the distance to the second fountain doesn't exceed r2. It's OK if some flowers are watered by both fountains.
You need to decrease the amount of water you need, that is set such r1 and r2 that all the flowers are watered and the r12 + r22 is minimum possible. Find this minimum value.
Input
The first line of the input contains integers n, x1, y1, x2, y2 (1 ≤ n ≤ 2000, - 107 ≤ x1, y1, x2, y2 ≤ 107) — the number of flowers, the coordinates of the first and the second fountain.
Next follow n lines. The i-th of these lines contains integers xi and yi ( - 107 ≤ xi, yi ≤ 107) — the coordinates of thei-th flower.
It is guaranteed that all n + 2 points in the input are distinct.
Output
Print the minimum possible value r12 + r22. Note, that in this problem optimal answer is always integer.
Sample test(s)
input
2 -1 0 5 3
0 2
5 2
output
6
input
4 0 0 5 0
9 4
8 3
-1 0
1 4
output
33
Note
The first sample is (r12 = 5, r22 = 1):The second sample is (r12 = 1, r22 = 32):
题目类型：暴力枚举
算法分析：先枚举圆1半径的平方和，找没有被圆1所覆盖的点，然后由圆2覆盖(找最大的)。最后更新minval即可。这道题还有一个优化就是先按照圆1半径的平方和递增排序，然后定义maxval[i]表示第比i点到圆1的距离大的点到圆2距离的最大值，maxval[i]=max (maxval[i+1], val[i].second)，从后更新
|
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 |
/************************************************* Author :supermaker Created Time :2016/1/27 20:34:07 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #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; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 2000 + 66; vector <pair <LL, LL> > val; LL Dist2 (LL px1, LL py1, LL px2, LL py2) { return (px2 - px1) * (px2 - px1) + (py2 - py1) * (py2 - py1); } int main() { //CFF; //CPPFF; int n, x1, y1, x2, y2; while (scanf ("%d%d%d%d%d", &n, &x1, &y1, &x2, &y2) != EOF) { val.clear (); for (int i = 1; i <= n; i++) { LL x, y; scanf ("%I64d%I64d", &x, &y); LL tt1 = Dist2 (x1, y1, x, y); LL tt2 = Dist2 (x2, y2, x, y); val.push_back (pair <LL, LL> (tt1, tt2)); } val.push_back (pair <LL, LL> (0, 0)); LL minval = 3e17; for (int i = 0; i < n + 1; i++) { LL ta = val[i].first, tb = 0; for (int j = 0; j < n + 1; j++) if (val[j].first > ta) tb = max (tb, val[j].second); minval = min (minval, ta + tb); } printf ("%I64d\n", minval); } return 0; } |
D Polyline
There are three points marked on the coordinate plane. The goal is to make a simple polyline, without self-intersections and self-touches, such that it passes through all these points. Also, the polyline must consist of only segments parallel to the coordinate axes. You are to find the minimum number of segments this polyline may consist of.
Input
Each of the three lines of the input contains two integers. The i-th line contains integers xi and yi( - 109 ≤ xi, yi ≤ 109) — the coordinates of the i-th point. It is guaranteed that all points are distinct.
Output
Print a single number — the minimum possible number of segments of the polyline.
Sample test(s)
input
1 -1
1 1
1 2
output
1
input
-1 -1
-1 3
4 3
output
2
input
1 1
2 3
3 2
output
3
Note
The variant of the polyline in the first sample:The variant of the polyline in the second sample:The variant of the polyline in the third sample:
题目类型：简单构造
算法分析：易知答案只有1、2和3。若三个点的x或者是y坐标都相同，则输出1。否则枚举所有点对，看第三个点是否在以枚举的点对为对角线的矩形的边上，若是则输出2。否则输出3
|
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 |
/************************************************* Author :supermaker Created Time :2016/1/27 21:51:01 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #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; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; vector <PII> val; int main() { //CFF; //CPPFF; for (int i = 1; i <= 3; i++) { int x, y; scanf ("%d%d", &x, &y); val.push_back (PII (x, y)); } if (val[0].first == val[1].first && val[1].first == val[2].first) puts ("1"); else if (val[0].second == val[1].second && val[1].second == val[2].second) puts ("1"); else { bool vis[6]; memset (vis, false, sizeof (vis)); bool is_find = false; for (int i = 0; i < 3; i++) for (int j = 0; j < 3 && !is_find; j++) { if (i == j) continue; vis[i] = vis[j] = true; for (int k = 0; k < 3 && !is_find; k++) if (!vis[k]) { int minx = min (val[i].first, val[j].first); int maxx = max (val[i].first, val[j].first); int miny = min (val[i].second, val[j].second); int maxy = max (val[i].second, val[j].second); if ((val[k].first == val[i].first || val[k].second == val[j].second) && minx <= val[k].first && val[k].first <= maxx && miny <= val[k].second && val[k].second <= maxy) { is_find = true; break; } } vis[i] = vis[j] = false; } if (is_find) puts ("2"); else puts ("3"); } return 0; } |
- « 上一篇：poj2187
- poj3348：下一篇 »