2021-01-20 灵动ICPC寒假集训
学习内容：几何初步、欧几里得、概率论微积分初步、矩阵计算、数学初步
1.Birthday Cake
试题来源：Randy Game - Programming Contest 2001A
题目
Lucy and Lily are twins. Today is their birthday.
Mother buys a birthday cake for them. Now we put the cake onto a Descartes coordinate. Its center is at(0, 0), and the cake’s length of radius is 100.There are 2N (N is a integer, 1 ≤ N ≤ 50) cherries on the cake. Mother wants to cut the cake into two halves with a knife (of course a beeline). The twins would like to be treated fairly, that means, the shape of the two halves must be the same (that means the beeline must go through the center of the cake) , and each half must have N cherrie(s). Can you help her?Note: the coordinate of a cherry (x, y) are two integers.You must give the line as form two integers A,B (stands for Ax + By = 0) each number mustn’t in[−500, 500]. Cherries are not allowed lying on the beeline.For each dataset there is at least one solution.
Input
The input file contains several scenarios. Each of them consists of 2 parts:
The first part consists of a line with a number N, the second part consists of 2N lines, each line
has two number, meaning (x, y). There is only one space between two border numbers. The input file
is ended with N = 0.
Output
For each scenario, print a line containing two numbers A and B. There should be a space between
them. If there are many solutions, you can only print one of them.
Sample Input
2
-20 20
-30 20
-10 -50
10 -5
0
Sample Output
0 1
思考过程
樱桃会有两种状态，存在和不存在，当樱桃存在时应有三种情况1、樱桃在直线上方 2、樱桃在直线下方 3、樱桃在直线上方，题采取枚举方法，在[-500, 500]的范围内枚举A和B，将樱桃坐标代入直线方程Ax+By，如果Ax+By大于0，则樱桃在直线上方；小于0，则樱桃在直线下方；等于0，则不允许，因为樱桃不能在直线上。枚举直至产生第一个解。
源代码
#include<iostream>
#include<cstdio>
const int N=100;
using namespace std;
struct point
{
int x;
int y;
};
int main()
{
int n,cou;
int up,down;
int correct;
int A=0,B=0;
point p[N];
while(~scanf("%d",&n))
{
if(n==0)
break;
correct=0;
for(cou=0;cou<2*n;cou++)
{
scanf("%d%d",&p[cou].x,&p[cou].y);
}
int i,j,k;
for(i=-500;i<500;i++)
{
for(j=-500;j<500;j++)
{
up=0;
down=0;
if(i==0||j==0)
continue;
for(k=0;k<cou;k++)
{
if(p[k].x>100||p[k].y>100||p[k].x<-100||p[k].y<-100)
continue;
else if(p[k].x*i+p[k].y*j==0)
break;
else if(p[k].x*i+p[k].y*j>0)
up++;
else
down++;
}
if(up==down&&up+down==cou)
{
A=i;
B=j;
correct=1;
break;
}
}
if(correct==1)
break;
}
cout<<A<<" "<<B<<endl;
}
return 0;
}
问题
记录第一个出现的解需要设置状态
2.Is This Integration ?
试题来源：Math & Number Theory Lovers’ Contest 2001
题目
In the image below you can see a squareABCD, where AB = BC = CD = DA =a. Four arcs are drawn taking the four
vertexes A, B, C, D as centers and a as the radius. The arc that is drawn taking A as center, starts at neighboring vertex B and ends at neighboring vertex D.All other arcs are drawn in a similar fashion.Regions of three different shapes are created in this fashion. You will have to determine the total area if these different shaped regions.
Input
The input file contains a floating-point number a (0 ≤ a ≤ 10000) in each line which indicates the length of one side of the square. Input is terminated by end of file.
Output
For each line of input, output in a single line the total area of the three types of region (filled with different patterns in the image above).These three numbers will of course be floating point numbers with three digits after the decimal
point. First number will denote the area of the striped region, the second number will denote the total area of the dotted regions and the third number will denote the area of the rest of the regions.
Sample Input
0.1
0.2
0.3
Sample Output
0.003 0.005 0.002
0.013 0.020 0.007
0.028 0.046 0.016
思考过程
源代码
#include<cstdio>
#include<iostream>
#include<cmath>
double p=acos(-1);
using namespace std;
int main()
{
double a;
double b=sqrt(3.0);
while(~scanf("%lf",&a))
{
double x=(1-b+p/3) *a*a;
double y=((-1+b/2)+p/12)*a*a;
double z=a*a-(x+4*y);
printf("%.3lf %.3lf %.3lf\n",x,4*y,z);
}
return 0;
}
问题
需要找出x、y、z三组面积之间的数学关系
3. Simple division
试题来源：November 2002 Monthly Contest
题目
Integer division between a dividend n and a divisor d yields a quotient q and a remainder r. q is the integer which maximizes q ∗ d such that q ∗ d ≤ n and r = n − q ∗ d.For any set of integers there is an integer d such that each of the given integers when divided by d leaves the same remainder.
Input
Each line of input contains a sequence of nonzero integer numbers separated by a space. The last number on each line is 0 and this number does not belong to the sequence. There will be at least 2 and no more than 1000 numbers in a sequence; not all numbers occuring in a sequence are equal. The last line of input contains a single 0 and this line should not be processed.
Output
For each line of input, output the largest integer which when divided into each of the input integers leaves the same remainder.
Sample Input
701 1059 1417 2312 0
14 23 17 32 122 0
14 -22 17 -31 -124 0
0
Sample Output
179
3
3
思考过程
被除数n和除数d之间的整数除运算产生商q和余数r。q是最大化qd的整数，使得qd≤n，并且r=n−q*d，可用欧几里得函数计算出d。
源代码
#include <iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
int a1, a;
while(~scanf("%d", &a1) && a1) {
int g = 0;
while(scanf("%d", &a) == 1 && a) {
int d = a - a1;
if(d) {if(g) g = gcd(g, d); else g = d;}
a1 = a;
}
printf("%d\n", abs(g));
}
return 0;
}
问题
需自行推导一下欧几里得公式
4.Euclid Problem
试题来源：Sergant Pepper’s Lonely Programmers Club. Junior Contest 2001
题目
From Euclid it is known that for any positive integers A and B there exist such integers X and Y that AX + BY = D，where D is the greatest common divisor of A and B. The problem is to find for given A and B corresponding X, Y and D.
Input
The input will consist of a set of lines with the integer numbers A and B, separated with space(A, B < 1000000001).
Output
For each input line the output line should consist of three integers X, Y and D, separated with space.If there are several such X and Y , you should output that pair for which |X| + |Y | is the minimal. If there are several X and Y satisfying the minimal criteria, output the pair for which X ≤ Y .
Sample Input
4 6
17 17
Sample Output
-1 1 2
0 1 17
思考过程
由欧几里得的辗转相除法可知，对于任何正整数A 和B，都存在这样的整数X和Y，AX+BY=D，其中D是 A和B的最大公约数。扩展的欧几里得算法如下：
int exgcd(int a, int b, int &x, int &y)
{ if (b==0)
{
x=1; y=0;
return a;
}
int t=exgcd(b, a%b, x, y);
int x0=x, y0=y;
x=y0; y=x0-(a/b)*y0;
return t;
}
源代码
#include <iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
int a1, a;
while(~scanf("%d", &a1) && a1) {
int g = 0;
while(scanf("%d", &a) == 1 && a) {
int d = a - a1;
if(d) {if(g) g = gcd(g, d); else g = d;}
a1 = a;
}
printf("%d\n", abs(g));
}
return 0;
}
5.Dead Fraction（未理解）
试题来源：Waterloo local 2003.09.27
题目
Mike is frantically scrambling to finish his thesis at the last minute. He needs to assemble all his research notes into vaguely coherent form in the next 3 days. Unfortunately, he notices that he had been extremely sloppy in his calculations. Whenever he needed to perform arithmetic, he just plugged it into a calculator and scribbled down as much of the answer as he felt was relevant. Whenever a repeating fraction was displayed, Mike simply reccorded the first few digits followed by “…”. For instance, instead of “1/3” he might have written down “0.3333…”. Unfortunately, his results require exact fractions! He doesn’t have time to redo every calculation, so he needs you to write a program (and FAST!) to automatically deduce the original fractions.
To make this tenable, he assumes that the original fraction is always the simplest one that produces the given sequence of digits; by simplest, he means the the one with smallest denominator. Also, he assumes that he did not neglect to write down important digits; no digit from the repeating portion of the decimal expansion was left unrecorded (even if this repeating portion was all zeroes).
Input
There are several test cases. For each test case there is one line of input of the form “0.dddd…” where dddd is a string of 1 to 9 digits, not all zero. A line containing 0 follows the last case.
Output
For each case, output the original fraction.
Sample Input
0.2…
0.20…
0.474612399…
0
Sample Output
2/9
1/5
1186531/2500000
Hint
Note that an exact decimal fraction has two repeating expansions (e.g. 1/5 = 0.2000… = 0.19999…).
思考过程
无限循环小数转分数（0.xxxxx…）
小数部分 n位
循环部分 a位
非循环部分 (n-a)位 ①分子为：n*10^n - n/10^a
②分母为：(10^(a)-1) * (10^(n-a))
最后通过 gcd()化简为最简分数
如果循环小数不确定，要循环全部情况，最后输出分母最小的
源代码
#include <cstdio>
#include <iostream>
#include <string>
#define in std::cin
#define out std::cout
#define string std::string
typedef long long ll;
ll z[11] = {1};
string s;
void pre()
{
for (int i = 1; i <= 10; ++i)
{
z[i] = (z[i-1]<<3) + (z[i-1]<<1);
}
}
ll gcd(ll a, ll b)
{
ll c;
while (b)
{
c = a % b;
a = b;
b = c;
}
return a;
}
int main()
{
pre();
while ((in >> s) && s.size() > 1)
{
ll num = 0;
ll b = 0;
for (int i = 2; s[i] != '.'; ++i)
{
num = num*10 + s[i]-'0';
b++;
}
ll minfz = -1;
ll minfm = -1;
ll fz, fm;
for (int i = 1; i <= b; ++i)
{
fz = num - num/z[i];
fm = (z[i]-1) * (z[b-i]);
ll g = gcd(fz, fm);
if (fm/g<minfm || minfm==-1)
{
minfz = fz / g;
minfm = fm / g;
}
}
printf("%lld/%lld\n", minfz, minfm);
}
return 0;
}
6.What is the Probability ?
试题来源：Bangladesh 2001 Programming Contest
题目
Probability has always been an integrated part of computer algorithms. Where the deterministic
algorithms have failed to solve a problem in short time, probabilistic algorithms have come to the rescue. In this problem we are not dealing with any probabilistic algorithm. We will just try to determine the winning probability of a certain player. A game is played by throwing a dice like thing (it should not be assumed that it has six sides like an ordinary dice). If a certain event occurs when a player throws the dice (such as getting a 3, getting green side on top or whatever) he is declared the winner. There can be N such player. So the first player will throw the dice, then the second and at last the N-th player and again the first player and so on. When a player gets the desired event he or she is declared winner and playing stops. You will have to determine the winning probability of one (The I-th) of these players.
Input
Input will contain an integer S (S ≤ 1000) at first, which indicates how many sets of inputs are there.The next S lines will contain S sets of inputs. Each line contain an integer N (N ≤ 1000) which denotes the number players, a floating point number p which indicates the probability of the happening of a successful event in a single throw (If success means getting 3 then p is the probability of getting 3 in a single throw. For a normal dice the probability of getting 3 is 1/6), and I (I ≤ N) the serial of the player whose winning probability is to be determined (Serial no varies from 1 to N). You can assume that no invalid probability § value will be given as input.
Output
For each set of input, output in a single line the probability of the I-th player to win. The output floating point number will always have four digits after the decimal point as shown in the sample output.
Sample Input
2
2 0.166666 1
2 0.166666 2
Sample Output
0.5455
0.4545
思考过程
源代码
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int t,n,i;
double p;
scanf("%d",&t);
while(t--)
{
scanf("%d%lf%d",&n,&p,&i);
double m; m=1-p;
int j;
for(j=1;j<n;j++)
m=m*(1-p);
double a=1;
for(j=1;j<i;j++)
a=a*(1-p);
double result=(p==0?0:p*a/(1-m));
printf("%.4lf\n",result);
}
return 0;
}
问题
需要找规律推导数学公式
7.Burger
试题来源：ACM Northwestern European Regionals 1996
题目
When Mr. and Mrs. Clinton’s twin sons Ben and Bill had their tenth birthday, the party was heldat the McDonald’s restaurant at South Broadway 202, New York. There were 20 kids at the party,including Ben and Bill. Ronald McDonald had made 10 hamburgers and 10 cheeseburgers and when he served the kids he started with the girl directly sitting left of Bill. Ben was sitting to the right of Bill.Ronald flipped a (fair) coin to decide if the girl should have a hamburger or a cheeseburger, head for
hamburger, tail for cheeseburger. He repeated this procedure with all the other 17 kids before serving
Ben and Bill last. Though, when coming to Ben he didn’t have to flip the coin anymore because there were no cheeseburgers left, only 2 hamburgers. Ronald McDonald was quite surprised this happened, so he would like to know what the probability is of this kind of events. Calculate the probability that Ben and Bill will get the same type of burger using the procedure described above. Ronald McDonald always grills the same number of hamburgers and cheeseburgers.
Input
The first line of the input-file contains the number of problems n , followed by n times:a line with an even number [2,4,6,…,100000], which indicates the number of guests present at the party including Ben and Bill.
Output
The output consists of n lines with on each line the probability (4 decimals precise) that Ben and Bill get the same type of burger.Note: a variance of ±0.0001 is allowed in the output due to rounding differences.
Sample Input
3
6
10
256
Sample Output
0.6250
0.7266
0.9500
思考过程
考虑之前哪个汉堡被拿完的概率较为复杂，所以反向考虑，如果剩的汉堡不同，则除Ben和Bill前面的2i-2个人，选i-1个牛肉汉堡，i-1个芝士汉堡
源代码
#include<cstdio>
#include<cstring>
const int N = 50005;
int n;
double p[N];
void init()
{
p[1] = 1.0;
for(int i = 1 ; i < N ; i++)
{
p[i + 1] = (1 - 0.5 / i) * p[i];
}
}
int main()
{
init();
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("%.4lf\n",1 - p[n / 2]);
}
return 0;
}
8. Coin Toss （未解决）
试题来源：ACM Rocky Mountain 2007
题目
In a popular carnival game, a coin is tossed onto a table with an area that is covered with square tiles in a grid. The prizes are determined by the number of tiles covered by the coin when it comes to rest: the more tiles it covers, the better the prize. In the following diagram, the results from five coin tosses are shown:
In this example:
coin 1 covers 1 tile
coin 2 covers 2 tiles
coin 3 covers 3 tiles
coin 4 covers 4 tiles
coin 5 covers 2 tiles
Notice that it is acceptable for a coin to land on the boundary of the playing area (coin 5). In order for a coin to cover a tile, the coin must cover up a positive area of the tile. In other words, it is not enough to simply touch the boundary of the tile. The center of the coin may be at any point of the playing area with uniform probability. You may assume that (1) the coin always comes to a rest lying flat, and (2) the player is good enough to guarantee that the center of the coin will always come to rest on the playing area (or the boundary).
The probability of a coin covering a certain number of tiles depends on the tile and coin sizes, as well as the number of rows and columns of tiles in the playing area. In this problem, you will be required to write a program which computes the probabilities of a coin covering a certain number of tiles.
Input
The first line of input is an integer specifying the number of cases to follow. For each case, you will be given 4 integers m, n, t, and c on a single line, separated by spaces. The playing area consists of m rows and n columns of tiles, each having side length t. The diameter of the coin used is c. You may assume that 1 <= m, n <= 5000, and 1 <= c < t <= 1000.
Output
For each case, print the case number on its own line. This is followed by the probability of a coin covering 1 tile, 2 tiles, 3 tiles, and 4 tiles each on its own line. The probability should be expressed as a percentage rounded to 4 decimal places. Use the format as specified in the sample output. You should use double-precision floating-point numbers to perform the calculations. “Negative zeros” should be printed without the negative sign.
Separate the output of consecutive cases by a blank line.
Sample Input
3
5 5 10 3
7 4 25 20
10 10 10 4
Sample Output
Case 1:
Probability of covering 1 tile = 57.7600%
Probability of covering 2 tiles = 36.4800%
Probability of covering 3 tiles = 1.2361%
Probability of covering 4 tiles = 4.5239%
Case 2:
Probability of covering 1 tile = 12.5714%
Probability of covering 2 tiles = 46.2857%
Probability of covering 3 tiles = 8.8293%
Probability of covering 4 tiles = 32.3135%
Case 3:
Probability of covering 1 tile = 40.9600%
Probability of covering 2 tiles = 46.0800%
Probability of covering 3 tiles = 2.7812%
Probability of covering 4 tiles = 10.1788%
思考过程
思路为：圆心的可行面积，除以总面积，就是每种情况下的概率了。
如图5*5的矩形
红色代表硬币覆盖一个正方形的圆心可行面积。
蓝色代表硬币覆盖两个正放行的圆心可行面积。
白色代表硬币覆盖三个正方形的圆心可行面积。
绿色代表硬币覆盖四个正方形的圆心可行面积。 这个应该能看懂，对于每种可行面积，找边界连接就可以了。
摘自（同学少年[ACM] POJ 3440 Coin Toss (几何概率））
源代码
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
double area[5];
const double PI=acos(-1.0);
double n,m,t,c;//n行，m列，t小方块的边长，c硬币直径
int main()
{
int cas;cin>>cas;
for(int i=1;i<=cas;i++)
{
cin>>n>>m>>t>>c;
area[0]=t*t*n*m;//总面积
double d11=(t-c/2)*(t-c/2)*4;//角上的四个
double d12=(t-c/2)*(t-c)*(n+m-4)*2;//外边一圈除去角上的
double d13=(t-c)*(t-c)*(n*m-(2*(n+m)-4));//除去一圈里面的
area[1]=d11+d12+d13;
double d21=c*(t-c/2)*((m-1)*2+(n-1)*2);//在边上的
double d22=c*(t-c)*((m-1)*n+(n-1)*m-(m-1)*2-(n-1)*2);//其它上的
area[2]=d21+d22;
area[3]=(c*c-PI*(c/2)*(c/2))*(n-1)*(m-1);
area[4]=PI*c*c/4*(n-1)*(m-1);
cout<<"Case "<<i<<":"<<endl;
for(int i=1;i<=4;i++)
{
cout<<"Probability of covering "<<i;
if(i==1)
cout<<" tile = ";
else
cout<<" tiles = ";
cout<<setiosflags(ios::fixed)<<setprecision(4)<<area[i]/area[0]*100<<"%"<<endl;
}
cout<<endl;
}
return 0;
}
9.498-bis
题目
Looking throw the “Online Judge’s Problem Set Archive” I found a very interesting problem number498, titled “Polly the Polynomial”. Frankly speaking, I did not solve it, but I derived from it thisproblem.
Everything in this problem is a derivative of something from 498. In particular, 498 was “… designed to help you remember … basic algebra skills, make the world a better place, etc., etc.”. This problem is designed to help you remember basic derivation algebra skills, increase the speed in which world becomes a better place, etc., etc.
In 498 you had to evaluate the values of polynomial
a0xn + a1xn−1 + . . . + an−1x + an.
In this problem you should evaluate its derivative. Remember that derivative is defined as
a0nxn−1 + a1(n − 1)xn−2 + . . . + an−1.
All the input and output data will fit into integer, i.e. its absolute value will be less than 231
Input
Your program should accept an even number of lines of text. Each pair of lines will represent one problem. The first line will contain one integer - a value for x. The second line will contain a list of integers a0, a1, …, an−1, an, which represent a set of polynomial coefficients.
Input is terminated by EOF
Output
For each pair of lines, your program should evaluate the derivative of polynomial for the given value x and output it in a single line.
Sample Input
7
1 -1
2
1 1 1
Sample Output
1
5
思考过程
本题的多项式项数是不定的，并且未给出上限，所以不适合用数组保存。所以考虑以下的一种输入方式。因为所给的多项式的次数是从高到低排列的，所以可以将整个多项式分成 个阶段。第 i+1个阶段可以由第 A（i+1）=A（i）*x+a个阶段来表示。
源代码
#include<cstdio>
#include<cmath>
using namespace std;
int main()
{
int x,a;
char c;
while(scanf("%d",&x)!=EOF)
{
int origin=0;
int first=0;
while(scanf("%d",&a)!=EOF)
{
first=first*x+origin;
origin=origin*x+a;
scanf("%c",&c);
if(c=='\n')
break;
}
printf("%d\n",first);
}
return 0;
}
问题
遇到难以直接用代码暴力输出 的问题，应学会找规律