取石子游戏
有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。 阅读全文 »
poj1064
maksyuki 发表于 oj 分类，标签: 数值-二分\三分\折半枚举
15
9月
2015
Cable master
Inhabitants of the Wonderland have decided to hold a regional programming contest. The Judging Committee has volunteered and has promised to organize the most honest contest ever. It was decided to connect computers for the contestants using a "star" topology - i.e. connect them all to a single central hub. To organize a truly honest contest, the Head of the Judging Committee has decreed to place all contestants evenly around the hub on an equal distance from it.To buy network cables, the Judging Committee has contacted a local network solutions provider with a request to sell for them a specified number of cables with equal lengths. The Judging Committee wants the cables to be as long as possible to sit contestants as far from each other as possible.
The Cable Master of the company was assigned to the task. He knows the length of each cable in the stock up to a centimeter,and he can cut them with a centimeter precision being told the length of the pieces he must cut. However, this time, the length is not known and the Cable Master is completely puzzled.
You are to help the Cable Master, by writing a program that will determine the maximal possible length of a cable piece that can be cut from the cables in the stock, to get the specified number of pieces.
Input
The first line of the input file contains two integer numb ers N and K, separated by a space. N (1 = N = 10000) is the number of cables in the stock, and K (1 = K = 10000) is the number of requested pieces. The first line is followed by N lines with one number per line, that specify the length of each cable in the stock in meters. All cables are at least 1 meter and at most 100 kilometers in length. All lengths in the input file are written with a centimeter precision, with exactly two digits after a decimal point.
Output
Write to the output file the maximal length (in meters) of the pieces that Cable Master may cut from the cables in the stock to get the requested number of pieces. The number must be written with a centimeter precision, with exactly two digits after a decimal point.
If it is not possible to cut the requested number of pieces each one being at least one centimeter long, then the output file must contain the single number "0.00" (without quotes).
Sample Input
4 11
8.02
7.43
4.57
5.39
Sample Output
2.00
Source
题目类型：二分
算法分析：在[0, INF]之间二分枚举长度。对于每一次枚举的长度，判断使用该长度是否能够将k个电缆割好。如果能，则向上枚举长度，否则向下枚举长度，注意本题的坑点是精度！！！！！！
|
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 |
#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> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int MOD = 7; const int maxn = 16000 + 66; double ans[maxn]; int n, k; bool Solve (double val) { int i, sum = 0; for (i = 0; i < n; i++) { sum += (int) (ans[i] / val); } if (sum >= k) return true; return false; } int main() { // freopen ("aaa.txt", "r", stdin); while (scanf ("%d%d", &n, &k) != EOF) { int i; for (i = 0; i < n; i++) scanf ("%lf", &ans[i]); double L = 0, R = INF * 1.0, mid; int cnt = 1; while (cnt <= 100) { mid = (L + R) / 2.0; if (Solve (mid)) L = mid; else R = mid; cnt++; } printf ("%.2f\n", floor (L * 100) / 100); } return 0; } |
poj1061
maksyuki 发表于 oj 分类，标签: 数论-线性同余方程(组)
15
9月
2015
青蛙的约会
两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征， 阅读全文 »
poj1060
15
9月
2015
Modular multiplication of polynomials
Consider polynomials whose coefficients are 0 and 1. Addition of two polynomials is achieved by 'adding' the coefficients for the corresponding powers in the polynomials. The addition of coefficients is performed by addition modulo 2, i.e., (0 + 0) mod 2 = 0, (0 + 1) mod 2 = 1, (1 + 0) mod 2 = 1, and (1 + 1) mod 2 = 0. Hence, it is the same as the exclusive-or operation. Description
(x^6 + x^4 + x^2 + x + 1) + (x^7 + x + 1) = x^7 + x^6 + x^4 + x^2
Subtraction of two polynomials is done similarly. Since subtraction of coefficients is performed by subtraction modulo 2 which is also the exclusive-or operation, subtraction of polynomials is identical to addition of polynomials.
(x^6 + x^4 + x^2 + x + 1) - (x^7 + x + 1) = x^7 + x^6 + x^4 + x^2
Multiplication of two polynomials is done in the usual way (of course, addition of coefficients is performed by addition modulo 2).
(x^6 + x^4 + x^2 + x + 1) (x^7 + x + 1) = x^13 + x^11 + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + 1
Multiplication of two polynomials f(x) and g(x) modulo a polynomial h(x) is the remainder of f(x)g(x) divided by h(x).
(x^6 + x^4 + x^2 + x + 1) (x^7 + x + 1) modulo (x^8 + x^4 + x^3 + x + 1) = x^7 + x^6 + 1
The largest exponent of a polynomial is called its degree. For example, the degree of x^7 + x^6 + 1 is 7.
Given three polynomials f(x), g(x), and h(x), you are to write a program that computes f(x)g(x) modulo h(x).
We assume that the degrees of both f(x) and g(x) are less than the degree of h(x). The degree of a polynomial is less than 1000.
Since coefficients of a polynomial are 0 or 1, a polynomial can be represented by d+1 and a bit string of length d+1, where d is the degree of the polynomial and the bit string represents the coefficients of the polynomial. For example, x^7 + x^6 + 1 can be represented by 8 1 1 0 0 0 0 0 1.
Input
The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case consists of three lines that contain three polynomials f(x), g(x), and h(x), one per line. Each polynomial is represented as described above.
Output
The output should contain the polynomial f(x)g(x) modulo h(x), one per line.
Sample Input
2
7 1 0 1 0 1 1 1
8 1 0 0 0 0 0 1 1
9 1 0 0 0 1 1 0 1 1
10 1 1 0 1 0 0 1 0 0 1
12 1 1 0 1 0 0 1 1 0 0 1 0
15 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1
Sample Output
8 1 1 0 0 0 0 0 1
14 1 1 0 1 1 0 0 1 1 1 0 1 0 0
Source
题目类型：模拟+高精度
算法分析：按照题目的要求模拟计算的过程即可
|
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 |
#include <cstdio> #include <iostream> #include <fstream> using namespace std; #define maxl 1006 int compare (int a[], int la, int b[], int lb) { int i; if (la > lb) return 1; if (la < lb) return -1; for (i = la - 1; i >= 0; i--) { if (a[i] && !b[i]) return 1; else if (!a[i] && b[i]) return -1; } return 0; } int main() { int loop, i, j; //fstream cin ("aaa.txt"); cin >> loop; while (loop--) { int f[maxl], g[maxl], h[maxl]; int lf, lg, lh; cin >> lf; for (i = lf - 1; i >= 0; i--) cin >> f[i]; cin >> lg; for (i = lg - 1; i >= 0; i--) cin >> g[i]; cin >> lh; for (i = lh - 1; i >= 0; i--) cin >> h[i]; int sum[maxl+maxl], ls = lf + lg - 1; for (i = 0; i < ls; i++) sum[i] = 0; for (i = 0; i < lf; i++) for (j = 0; j < lg; j++) sum[i+j] ^= (f[i] & g[j]); while (compare (sum, ls, h, lh) >= 0) { int d = ls - lh; for (i = 0; i < lh; i++) sum[i+d] ^= h[i]; while (ls && !sum[ls-1]) --ls; } if (!ls) ls = 1; cout << ls << ' '; for (i = ls - 1; i > 0; i--) cout << sum[i] <<' '; cout << sum[0] << endl; } return 0; } |
poj1050
15
9月
2015
To the Max
Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1*1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle.
As an example, the maximal sub-rectangle of the array:
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
is in the lower left corner:
9 2
-4 1
-1 8
and has a sum of 15.
Input
The input consists of an N * N array of integers. The input begins with a single positive integer N on a line by itself, indicating the size of the square two-dimensional array. This is followed by N^2 integers separated by whitespace (spaces and newlines). These are the N^2 integers of the array, presented in row-major order. That is, all numbers in the first row, left to right, then all numbers in the second row, left to right, etc. N may be as large as 100. The numbers in the array will be in the range [-127,127].
Output
Output the sum of the maximal sub-rectangle.
Sample Input
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1
8 0 -2
Sample Output
15
Source
题目类型：线性dp扩展
算法分析： 使用变量i和j(i <= j)枚举所有的行下标，然后将同列的数压缩成一个数。使得二维的矩阵变成了一个一维的数组，然后直接求解最大连续子段和即可
|
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 |
#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> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int MOD = 7; const int maxn = 100 + 6; short ans[maxn][maxn], sum[maxn][maxn], dp[maxn][maxn][maxn]; int main() { // ifstream cin ("aaa.txt"); int n; while (cin >> n) { for (int i = 1;i <= n; i++) for (int j = 1; j <= n; j++) cin >> ans[i][j]; memset (sum, 0, sizeof (sum)); memset (dp, 0, sizeof (dp)); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) sum[i][j] = sum[i-1][j] + ans[i][j]; for (int i = 1; i <= n; i++) for (int j = i; j <= n; j++) for (int k = 1; k <= n; k++) { int temp = sum[j][k] - sum[i-1][k]; dp[i][j][k] = max (dp[i][j][k-1] + temp, temp); } short maxval = -INF; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int k = 1; k <= n; k++) maxval = max (maxval, dp[i][j][k]); cout << maxval << endl; } return 0; } |
不使用dp数组来存储中间结果，直接边算边更新最大值，可以优化空间复杂度
|
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 |
#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> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int MOD = 7; const int maxn = 100 + 6; int ans[maxn][maxn], sum[maxn][maxn]; int main() { // ifstream cin ("aaa.txt"); int n; while (cin >> n) { for (int i = 1;i <= n; i++) for (int j = 1; j <= n; j++) cin >> ans[i][j]; memset (sum, 0, sizeof (sum)); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) sum[i][j] = sum[i-1][j] + ans[i][j]; int maxval = -INF, tempsum, tempval; for (int i = 1; i <= n; i++) for (int j = i; j <= n; j++) { tempsum = -INF, tempval = 0; for (int k = 1; k <= n; k++) { int temp = sum[j][k] - sum[i-1][k]; if (tempval > 0) tempval += temp; else tempval = temp; tempsum = max (tempsum, tempval); } maxval = max (maxval, tempsum); } cout << maxval << endl; } return 0; } |
poj1047
15
9月
2015
Round and Round We Go
A cyclic number is an integer n digits in length which, when multiplied by any integer from 1 to n, yields a"cycle"of the digits of the original number. That is, if you consider the number after the last digit to "wrap around"back to the first digit, the sequence of digits in both numbers will be the same, though they may start at different positions.For example, the number 142857 is cyclic, as illustrated by the following table:
142857 *1 = 142857
142857 *2 = 285714
142857 *3 = 428571
142857 *4 = 571428
142857 *5 = 714285
142857 *6 = 857142
Input
Write a program which will determine whether or not numbers are cyclic. The input file is a list of integers from 2 to 60 digits in length. (Note that preceding zeros should not be removed, they are considered part of the number and count in determining n. Thus, "01"is a two-digit number, distinct from "1" which is a one-digit number.)
Output
For each input integer, write a line in the output indicating whether or not it is cyclic.
Sample Input
142857
142856
142858
01
0588235294117647
Sample Output
142857 is cyclic
142856 is not cyclic
142858 is not cyclic
01 is not cyclic
0588235294117647 is cyclic
Source
题目类型：简单数学
算法分析：若循环节的位数为6，将上式乘以10 ^ 6得 =>10 ^ 6 / 7 = 142857.142857142857...
=>(10 ^ 6 - 1) / 7 = 142857 => 999999 / 7 = 142857。对于其他数num，如果其位数是n，如果num * (n + 1)得到的结果是n个9，那么这个数就是可循环的
|
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 |
#include <cstdio> #include <iostream> #include <fstream> #include <cstring> using namespace std; int main() { int i, length; char number[66]; bool cyclic; while (gets (number)) { length = strlen (number); for (i = 0; i < length; i++) number[i] -= '0'; int ans = 0; cyclic = true; for (i = length - 1; i >= 0; i--) { ans += number[i] * (length + 1); if (ans % 10 != 9) { cyclic = false; break; } ans /= 10; } if (ans) cyclic = false; for (i = 1; i < length && cyclic; i++) { cyclic = false; if (number[i] != number[0]) { cyclic = true; break; } } if (cyclic) { for (i = 0; i < length; i++) printf ("%d", number[i]); printf (" is cyclic\n"); } else { for (i = 0; i < length; i++) printf ("%d", number[i]); printf (" is not cyclic\n"); } } return 0; } |
poj1045
15
9月
2015
Bode Plot
Consider the AC circuit below. We will assume that the circuit is in steady-state. Thus, the voltage at nodes 1 and 2 are given 阅读全文 »
poj1028
15
9月
2015
Web Navigation
Standard web browsers contain features to move backward and forward among the pages recently visited. One way to implement these features is to use two stacks to keep track of the pages that can be reached by moving backward and forward. In this problem, you are asked to implement this.The following commands need to be supported:
BACK: Push the current page on the top of the forward stack. Pop the page from the top of the backward stack, making it the new current page. If the backward stack is empty, the command is ignored.
FORWARD: Push the current page on the top of the backward stack. Pop the page from the top of the forward stack, making it the new current page. If the forward stack is empty, the command is ignored.
VISIT : Push the current page on the top of the backward stack, and make the URL specified the new current page. The forward stack is emptied.
QUIT: Quit the browser.
Assume that the browser initially loads the web page at the URL http://www.acm.org/
Input
Input is a sequence of commands. The command keywords BACK, FORWARD, VISIT, and QUIT are all in uppercase. URLs have no whitespace and have at most 70 characters. You may assume that no problem instance requires more than 100 elements in each stack at any time. The end of input is indicated by the QUIT command.
Output
For each command other than QUIT, print the URL of the current page after the command is executed if the command is not ignored. Otherwise, print "Ignored". The output for each command should be printed on its own line. No output is produced for the QUIT command.
Sample Input
VISIT http://acm.ashland.edu/
VISIT http://acm.baylor.edu/acmicpc/
BACK
BACK
BACK
FORWARD
VISIT http://www.ibm.com/
BACK
BACK
FORWARD
FORWARD
FORWARD
QUIT
Sample Output
http://acm.ashland.edu/
http://acm.baylor.edu/
acmicpc/http://acm.ashland.edu/
http://www.acm.org/
Ignored
http://acm.ashland.edu/
http://www.ibm.com/
http://acm.ashland.edu/
http://www.acm.org/
http://acm.ashland.edu/
http://www.ibm.com/
Ignored
Source
East Central North America 2001
题目类型：模拟
算法分析：按照题目的要求直接模拟即可。注意“VISIT“命令要将栈forw清空
|
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 |
#include <cstdio> #include <iostream> #include <fstream> #include <string> #include <stack> using namespace std; stack <string> forw, backw; string current = "http://www.acm.org/"; int main() { string com; //ifstream cin ("aaa.txt"); while (cin >> com) { if (com == "QUIT") break; if (com == "VISIT") { string URL; cin >> URL; backw.push (current); current = URL; while (!forw.empty ()) forw.pop (); cout << current << endl; } if (com == "BACK") { if (!backw.empty ()) { forw.push (current); string temp = backw.top (); backw.pop (); current = temp; cout << current << endl; } else cout << "Ignored" << endl; } if (com == "FORWARD") { if (!forw.empty ()) { backw.push (current); string temp = forw.top (); forw.pop (); current = temp; cout << current << endl; } else cout << "Ignored" << endl; } } return 0; } |
poj1011
maksyuki 发表于 oj 分类，标签: 基础算法-搜索(DFS\BFS)\记忆化
15
9月
2015
Sticks
George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.
Input
The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.
Output
The output should contains the smallest possible length of original sticks, one per line.
Sample Input
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
Sample Output
6
5
Source
题目类型：搜索
算法分析：本题采用DFS算法：
1首先将数据按照降序排序。
2从数据数值最大的开始，依次减去长度值，直到棒子的长度变为0为止，同时标记用到的数值。
3如果长度变为0，则把length恢复原值，再执行一次。
4如果失败，则返回到前一个状态。
5如果做出sum/length个长度是length的棒子就成功了。
|
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 |
#include <cstdio> #include <cstring> #include <iostream> #include <fstream> using namespace std; int in[56]; int length; int finish; void check (int counts, int len, int plen) { int j; in[plen]--; if (counts == 0) finish = 1; if (finish == 0) { len -= plen; if (len) { j = len < plen ? len : plen; for (; j > 0; j--) if (in[j]) check (counts, len, j); } else { for (j = 50; !in[j]; ) j--; check (counts - 1, length, j); } } in[plen]++; } int main() { int b, n, sum, maxs; //ifstream cin ("aaa.txt"); while (cin >> n && n) { memset (in, 0, sizeof (in)); sum = 0; maxs = 0; finish = 0; for (; n--; ) { cin >> b; in[b]++; sum += b; if (maxs < b) maxs = b; } for (length = maxs; !finish; length++) if (sum % length == 0) check (sum / length, length, maxs); printf ("%d\n", length - 1); } return 0; } |
poj1006
15
9月
2015
Biorhythms
Some people believe that there are three cycles in a person's life that start the day he or she is born. These three cycles are the physical, emotional, and intellectual cycles, and they have periods of lengths 23, 阅读全文 »
poj1005
15
9月
2015
I Think I Need a Houseboat
Fred Mapper is considering purchasing some land in Louisiana to build his house on. In the process of investigating the land, he learned that the state of Louisiana is actually shrinking by 50 square 阅读全文 »
poj1003
maksyuki 发表于 oj 分类，标签: 基础算法-简单数学, 数值-二分\三分\折半枚举
15
9月
2015
Hangover
How far can you make a stack of cards overhang a table? If you have one card, you can create a maximum overhang of half a card length. (We're assuming that the cards must be perpendicular to the table.) With two cards you can make the top card overhang the bottom one by half a card length, and the bottom one overhang the table by a third of a card length, for a total maximum overhang of 1/2 + 1/3 = 5/6 card lengths. In general you can make n cards overhang by 1/2 + 1/3 + 1/4 + ... + 1/(n + 1) card lengths, where the top card overhangs the second by 1/2, the second overhangs tha third by 1/3, the third overhangs the fourth by 1/4, etc., and the bottom card overhangs the table by 1/(n + 1). This is illustrated in the figure below.
Input
The input consists of one or more test cases, followed by a line containing the number 0.00 that signals the end of the input. Each test case is a single line containing a positive floating-point number c whose value is at least 0.01 and at most 5.20; c will contain exactly three digits.
Output
For each test case, output the minimum number of cards necessary to achieve an overhang of at least c card lengths. Use the exact output format shown in the examples.
Sample Input
1.00
3.71
0.04
5.19
0.00
Sample Output
3 card(s)
61 card(s)
1 card(s)
273 card(s)
Source
题目类型：简单数学+二分
算法分析：先将所有的值预先处理出来，然后对于每一次的查询，二分答案
|
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 |
#include <cstdio> #include <iostream> #include <fstream> using namespace std; #define maxn 300 const double delta = 1e-8; int zero (double x) { if (x < -delta) return -1; return x > delta; } int main() { double len[maxn]; int i; len[0] = 0.0; for (i = 1; zero (len[i-1] - 5.20) < 0; i++) len[i] = len[i-1] + 1.0 / (i + 1); double x; //fstream cin ("aaa.txt"); cin >> x; while (zero (x)) { int left, right; left = 0, right = i; while (left + 1 < right) { int mid = (left + right) / 2; if (zero (len[mid] - x) < 0) left = mid; else right = mid; } printf ("%d card(s)\n", right); cin >> x; } return 0; } |
poj1001
15
9月
2015
Exponentiation
Problems involving the computation of exact values of very large magnitude and precision are common. For example, the computation of the national debt is a taxing experience for many computer systems.
This problem requires that you write a program to compute the exact value of Rn where R is a real number ( 0.0 < R < 99.999 ) and n is an integer such that 0 < n <= 25.
Input
The input will consist of a set of pairs of values for R and n. The R value will occupy columns 1 through 6, and the n value will be in columns 8 and 9.
Output
The output will consist of one line for each line of input giving the exact value of R^n. Leading zeros should be suppressed in the output. Insignificant trailing zeros must not be printed. Don't print the decimal point if the result is an integer.
Sample Input
95.123 12
0.4321 20
5.1234 15
6.7592 9
98.999 10
1.0100 12
Sample Output
548815620517731830194541.899025343415715973535967221869852721
.00000005148554641076956121994511276767154838481760200726351203835429763013462401
43992025569.928573701266488041146654993318703707511666295476720493953024
29448126.764121021618164430206909037173276672
90429072743629540498.107596019456651774561044010001
1.126825030131969720661201
Hint
If you don't know how to determine wheather encounted the end of input:
s is a string and n is an integer
C++
while(cin>>s>>n)
{
...
}
c
while(scanf("%s%d",s,&n)==2) //to see if the scanf read in as many items as you want
/*while(scanf(%s%d",s,&n)!=EOF) //this also work */
{
...
}
Source
East Central North America 1988
题目类型：高精度计算
算法分析：在计算小数乘法时要注意小数点的位置。首先把R乘上适当的数值变成自然数，为了方便之后找到小数点的位置，因此乘的数值是固定值。计算的时候为了避免清除数组，就要为每一个循环准备局部数组，用完就丢掉
|
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 |
#include <cstdio> #include <iostream> #include <fstream> using namespace std; int n, i, j; int top, bottom, show; double f; int main() { //ifstream cin ("aaa.txt"); while (cin >> f >> n) { int p[300] = {1}, temp = 0; f *= 1e6; for (i = 0; i++ < n; ) { for (j = 0; j < i * 9; ) { temp += p[j] * f; p[j++] = temp % 10; temp /= 10; } } for (bottom = 0; !p[++bottom] && bottom < n * 6; ) ; show = 0; for (top = j; bottom < top; ) { if (top-- == n * 6 || p[top]) show = 1; if (show) printf (top == n * 6 - 1 ? ".%d" : "%d", p[top]); } printf ("\n"); } return 0; } |
hdu4763
15
9月
2015
Theme Section
Problem Description
It's time for music! A lot of popular musicians are invited to join us in the music festival. Each of them will play one of their representative songs. To make the programs more interesting and challenging, the hosts are going to add some constraints to the rhythm of the songs, i.e., each song is required to have a 'theme section'. The theme section shall be played at the beginning, the middle, and the end of each song. More specifically, given a theme section E, the song will be in the format of 'EAEBE', where section A and section B could have arbitrary number of notes. Note that there are 26 types of notes, denoted by lower case letters 'a' - 'z'.
To get well prepared for the festival, the hosts want to know the maximum possible length of the theme section of each song. Can you help us?
Input
The integer N in the first line denotes the total number of songs in the festival. Each of the following N lines consists of one string, indicating the notes of the i-th (1 <= i <= N) song. The length of the string will not exceed 10^6.
Output
There will be N lines in the output, where the i-th line denotes the maximum possible length of the theme section of the i-th song.
Sample Input
5
xy
abc
aaa
aaaaba
aaxoaaaaa
Sample Output
0
0
1
1
2
Source
2013 ACM/ICPC Asia Regional Changchun Online
题目类型：KMP
算法分析：使用next数组从大到小枚举相等的前后缀的长度，然后在中间再使用一次KMP构建一个next，然后进行一次匹配，直到找到结果或者返回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 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
#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 lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1000000 + 66; char s[maxn], pp[maxn]; int Next[maxn]; void Get (char *s) { int lens = strlen (s); Next[0] = -1, Next[1] = 0; int k = 0; for (int i = 2; i <= lens; i++) { while (k != -1 && s[k] != s[i-1]) k = Next[k]; Next[i] = ++k; } } bool Solve (char *s, char *p, int sa, int sb) { int lenp = strlen (p); int i = sa, j = 0; while (i <= sb) { if (j == -1 || s[i] == p[j]) i++, j++; else j = Next[j]; if (j == lenp) return true; } return false; } int main() { // ifstream cin("aaa.txt"); // freopen ("aaa.txt", "r", stdin); int t; cin >> t; while (t--) { cin >> s; Get (s); int len = strlen (s); int po = Next[len]; bool is_valid = false; while (po) { for (int i = 0; i < po; i++) pp[i] = s[i]; pp[po] = 0; Get (pp); if (Solve (s, pp, po, len - po - 1)) break; po = Next[po]; } cout << po << endl; } return 0; } |