战队：Computer room white give (CRWG)
队员：刘凯 董海铮 马鸿儒
A: Birthday Cake
B: Bumped!
问题描述：
Peter returned from the recently held ACM ICPC World finals only to find that his return flight was overbooked and he was bumped from the flight! Well, at least he wasn’t beat up by the
airline and he’s received a voucher for one free flight between any two destinations he wishes.
He is already planning next year’s trip. He plans to travel by car where necessary, but he may be using his free flight ticket for one leg of the trip. He asked for your help in his planning.
He can provide you a network of cities connected by roads, the amount it costs to buy gas for traveling between pairs of cities, and a list of available flights between some of those cities. Help Peter by finding the minimum amount of money he needs to spend to get from his hometown to next year’s destination!
输入
The input consists of a single test case. The first line lists five space-separated integers n, m, f, s, and t, denoting the number of cities n (0 < n ≤ 50 000), the number of roads m (0 ≤ m ≤ 150 000), the number of flights f (0 ≤ f ≤ 1 000), the number s (0 ≤ s < n) of the city in which Peter’s trip starts, and the number t (0 ≤ t < n) of the city Peter is trying to travel to. (Cities are numbered from 0 to n − 1.)
The first line is followed by m lines, each describing one road. A road description contains three space-separated integers i, j, and c (0 ≤ i, j < n, i 6= j and 0 < c ≤ 50 000), indicating there is a road connecting cities i and j that costs c cents to travel. Roads can be used in either direction for the same cost. All road descriptions are unique.
Each of the following f lines contains a description of an available flight, which consists of two space-separated integers u and v (0 ≤ u, v < n, u 6= v) denoting that a flight from city u to city v is available (though not from v to u unless listed elsewhere). All flight descriptions are unique.
输出
Output the minimum number of cents Peter needs to spend to get from his home town to the competition,using at most one flight. You may assume that there is a route on which Peter can reach his destination.
INPUT:
8 11 1 0 5
0 1 10
0 2 10
1 2 10
2 6 40
6 7 10
5 6 10
3 5 15
3 6 40
3 4 20
1 4 20
1 3 20
4 7
OUTPUT:
45
题意，peter要从一个地点S到地点T求最小花费，每条道路都是可以双向走的，且都有一个花费。另外peter可以从f条免费的航线选一条可以不花钱直接从点A飞到点B，求peter到终点的最小花费。
分析，若没有免费航线，就跑一边最短路dijkstra就可以，有免费航线可以这么考虑，比如有一条免费航线是从A到B，那么起点S到终点T的最小花费有两种情况，一种是直接从S到T，另一种是S到A，然后经过AB免费航线从B到T，那么最小花费即是这两种情况的最小值，因为有f条免费航线题目说只能用一条，那么我们把这f条航线都试一遍即可。其中需要用到B到T的距离，这里在算法开始预处理出S到所有点的最短路和T到所有点的最短路即可，即跑两边最短路。最后还要注意free的航线是单向的，不是双向的，我刚开始写的双向的，结果wa了，如果是双向的也没问题，那就是三种情况了。综合算法复杂度：O(2*NlogN+F)
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int n, m, s, t, f;
struct edge
{
int p;
long long v;
};
struct node
{
int x;
long long d;
bool operator<(const node &a) const
{
return d > a.d;
}
};
struct abc
{
int l;
int r;
} e[150010];
vector<edge> P[50010];
long long dis1[50010];
long long dis2[50010];
int vis[50010];
priority_queue<node> Q;
void dij1()
{
for (int i = 0; i <= n; i++)
dis1[i] = 9999999900009;
dis1[s] = 0;
vis[s] = 1;
Q.push({s, 0});
while (!Q.empty())
{
node a = Q.top();
Q.pop();
if (dis1[a.x] != a.d)
continue;
vis[a.x] = 1;
int maxx = P[a.x].size();
for (int i = 0; i < maxx; i++)
if (!vis[P[a.x][i].p])
{
if (dis1[P[a.x][i].p] > dis1[a.x] + P[a.x][i].v)
{
dis1[P[a.x][i].p] = dis1[a.x] + P[a.x][i].v;
Q.push((node){P[a.x][i].p, dis1[P[a.x][i].p]});
}
}
}
}
void dij2()
{
for (int i = 0; i <= n; i++)
dis2[i] = 9999999900009;
memset(vis, 0, sizeof(vis));
dis2[t] = 0;
vis[t] = 1;
Q.push({t, 0});
while (!Q.empty())
{
node a = Q.top();
Q.pop();
if (dis2[a.x] != a.d)
continue;
vis[a.x] = 1;
int maxx = P[a.x].size();
for (int i = 0; i < maxx; i++)
if (!vis[P[a.x][i].p])
{
if (dis2[P[a.x][i].p] > dis2[a.x] + P[a.x][i].v)
{
dis2[P[a.x][i].p] = dis2[a.x] + P[a.x][i].v;
Q.push((node){P[a.x][i].p, dis2[P[a.x][i].p]});
}
}
}
}
int main()
{
cin >> n >> m >> f >> s >> t;
for (int i = 0; i < m; i++)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
P[x].push_back({y, z});
P[y].push_back({x, z});
}
for (int i = 0; i < f; i++)
scanf("%d%d", &e[i].l, &e[i].r);
dij1();
dij2();
long long ans = dis1[t];
for (int i = 0; i < f; i++)
{
long long a = dis1[e[i].l] + dis2[e[i].r];
ans = min(a, ans);
}
cout << ans;
return 0;
}
C: Canonical Coin Systems
问题描述
A coin system S is a finite (nonempty) set of distinct positive integers corresponding to coin values, also called denominations, in a real or imagined monetary system. For example, the coin system in common use in Canada is {1, 5, 10, 25, 100, 200}, where 1 corresponds to a 1-cent coin and 200 corresponds to a 200-cent (2-dollar) coin. For any coin system S, we assume that there is an unlimited supply of coins of each denomination, and we also assume that S contains 1,since this guarantees that any positive integer can be written as a sum of (possibly repeated) values in S.
Cashiers all over the world face (and solve) the following problem: For a given coin system and a positive integer amount owed to a customer, what is the smallest number of coins required to dispense exactly that amount? For example, suppose a cashier in Canada owes a customer 83 cents. One possible solution is 25+25+10+10+10+1+1+1, i.e.,8 coins, but this is not optimal, since the cashier could instead dispense 25 + 25 + 25 + 5 + 1 + 1 + 1, i.e., 7 coins (which is optimal in this case). Fortunately, the Canadian coin system has the nice property that the greedy algorithm always yields an optimal solution, as do the coin systems used in most countries. The greedy algorithm involves repeatedly choosing a coin of the
largest denomination that is less than or equal to the amount still owed, until the amount owed reaches zero. A coin system for which the greedy algorithm is always optimal is called canonical.
Your challenge is this: Given a coin system S = {c1, c2, . . . , cn }, determine whether S is canonical or non-canonical. Note that if S is non-canonical then there exists at least one counterexample, i.e., a positive integer x such that the minimum number of coins required to dispense exactly x is less than the number of coins used by the greedy algorithm. An example of a non-canonical coin system is {1, 3, 4}, for which 6 is a counterexample, since the greedy algorithm yields 4 + 1 + 1 (3 coins), but an optimal solution is 3 + 3 (2 coins). A useful fact (due to Dexter Kozen and Shmuel Zaks) is that if S is non-canonical, then the smallest counterexample is less than the sum of the two largest denominations.
输入
Input consists of a single case. The first line contains an integer n (2 ≤ n ≤ 100), the number of denominations in the coin system. The next line contains the n denominations as space-separated integers c1 c2 . . . cn, where c1 = 1 and c1 < c2 < . . . < cn ≤ 106.
输出
Output “canonical” if the coin system is canonical, or “non-canonical” if the coin system is non-canonical.
题意：题目给出一种算法，对于一个钱数怎么求出搭配需要的最小硬币数，问你算法是否是正确的。
解析：参考队员HaiZheng Tung 的博客
D: Cat and Mice
E: Company Picnic
F: GlitchBot
题目描述
One of our delivery robots is malfunctioning! The job of the robot is simple; it should follow a list of instructions in order to reach a target destination. The list of instructions is originally correct to get the robot to the target. However, something is going wrong as we upload the instructions into the robot’s memory. During the upload, one random instruction from the list takes on a different value than intended. Yes,there is always a single bad instruction in the robot’s memory and it always results in the robot arriving at an incorrect destination as it finishes executing the list of instructions.
The robot can execute the instructions “Left”, “Right”, and “Forward”. The “Left” and “Right” instructions do not result in spatial movement but result in a 90-degree turn in the corresponding direction. “Forward” is the only instruction that results in spatial movement, causing the robot to move one unit in the direction it is facing. The robot always starts at the origin (0, 0) of a grid and faces north along the positive y-axis.
Given the coordinates of the target destination and the list of instructions that the robot has in its memory, you are to identify a correction to the instructions to help the robot reach the proper destination.
输入
The first line of the input contains the x and y integer coordinates of the target destination, where −50 ≤ x ≤ 50 and −50 ≤ y ≤ 50. The following line contains an integer n representing the number of instructions in the list, where 1 ≤ n ≤ 50. The remaining n lines each contain a single instruction. These instructions may be: “Left”, “Forward”, or “Right”.
输出
Identify how to correct the robot’s instructions by printing the line number (starting at 1) of an incorrect input instruction, followed by an instruction substitution that would make the robot reach the target destination. If there are multiple ways to fix the instructions, report the fix that occurs for the earliest line number in the sequence of instructions. There is always exactly one unique earliest fix.
INPUT:
3 2
11
Forward
Right
Forward
Forward
Left
Forward
Forward
Left
Forward
Right
Forward
OUTPUT:
8 Right
题意：就是给你一串命令，告诉你其中有一条命令是错的，那么你能不能找出是哪一条命令是错的来，并且把它改正呢？
分析：数据量巨小，那么我们就挨个改改试试呗？试试就试试，AC！就是每一步改一次试试能不能走到终点。
(代码为现场提交代码，没再优化和美化，可能比较挫)
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
int ins[1000];
int fx, fy;
int main()
{
int t;
cin >> fx >> fy;
cin >> t;
for (int i = 1; i <= t; i++)
{
string s;
cin >> s;
if (s[0] == 'F')
ins[i] = 1;
else if (s[0] == 'L')
ins[i] = 2;
else if (s[0] == 'R')
ins[i] = 3;
}
int ok = 0;
int anst;
int ansk;
for (int i = 1; i <= t && !ok; i++)
{
int d = 4;
int x = 0, y = 0;
int key = ins[i];
for (int j = 1; j <= 3 && !ok; j++)
{
d = 4;
x = 0;
y = 0;
ins[i] = j;
for (int k = 1; k <= t; k++)
{
if (ins[k] == 1)
{
if (d == 1)
x--;
else if (d == 2)
x++;
else if (d == 3)
y--;
else if (d == 4)
y++;
}
else if (ins[k] == 2)
{
if (d == 1)
d = 3;
else if (d == 2)
d = 4;
else if (d == 3)
d = 2;
else if (d == 4)
d = 1;
}
else if (ins[k] == 3)
{
if (d == 1)
d = 4;
else if (d == 2)
d = 3;
else if (d == 3)
d = 1;
else if (d == 4)
d = d = 2;
}
if (x == fx && y == fy && k == t)
{
ok = 1;
anst = i;
ansk = j;
break;
}
}
}
ins[i] = key;
}
cout << anst << " ";
if (ansk == 1)
cout << "Forward";
else if (ansk == 2)
cout << "Left";
else if (ansk == 3)
cout << "Right";
return 0;
}
G: Greeting Card
题目描述
Quido plans to send a New Year greeting to his friend Hugo. He has recently acquired access to an advanced high-precision plotter and he is planning to print the greeting card on the plotter.
Here’s how the plotter operates. In step one, the plotter plots an intricate pattern of n dots on the paper. In step two, the picture in the greeting emerges when the plotter connects by a straight segment each pair of dots that are exactly 2 018 length units apart.
The plotter uses a special holographic ink, which has a limited supply.Quido wants to know the number of all plotted segments in the picture to be sure that there is enough ink to complete the job.
输入
The first line of input contains a positive integer n specifying the number of plotted points. The following n lines each contain a pair of space-separated integer coordinates indicating one plotted point. Each coordinate is non-negative and less than 231. There are at most 105 points, all of them are distinct.
In this problem, all coordinates and distances are expressed in plotter length units, the length of the unit in the x-direction and in the y-direction is the same.
输出
The output contains a single integer equal to the number of pairs of points which are exactly 2018 length units apart.
INPUT：
4
20180000 20180000
20180000 20182018
20182018 20180000
20182018 20182018
OUTPUT:
4
题意 给你N个点，让你求有多少对点之间的距离是2018，Haizheng第一感觉，2018之下有多少队数可以平方和再开方是2018呢，结果只有1118和1680 ，那爽了，直接开个桶判断对于某个点是否有这种情况就是了，这里注意要把2维的点转化为1维的数字...开map，把一个二维点hash成一个数即可。一发AC，对于这个想法有一个需要注意的地方就是点对是成对关系的所以最后答案要除以2输出
#include <iostream>
#include <map>
using namespace std;
long long p = 2147483648;
int a[500];
int n;
struct edge
{
long long x;
long long y;
} e[100010];
map<unsigned long long, int> m;
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> e[i].x >> e[i].y;
m[e[i].x * p + e[i].y]++;
}
int ans = 0;
for (int i = 0; i < n; i++)
{
unsigned long long x = e[i].x * p + e[i].y + 2018;
ans += m[x];
x = e[i].x * p + e[i].y - 2018;
ans += m[x];
x = (e[i].x + 2018) * p + e[i].y;
ans += m[x];
x = (e[i].x - 2018) * p + e[i].y;
ans += m[x];
x = (e[i].x - 1118) * p + (e[i].y - 1680);
ans += m[x];
x = (e[i].x + 1118) * p + (e[i].y - 1680);
ans += m[x];
x = (e[i].x + 1118) * p + (e[i].y + 1680);
ans += m[x];
x = (e[i].x - 1118) * p + (e[i].y + 1680);
ans += m[x];
x = (e[i].x - 1680) * p + (e[i].y - 1118);
ans += m[x];
x = (e[i].x + 1680) * p + (e[i].y - 1118);
ans += m[x];
x = (e[i].x - 1680) * p + (e[i].y + 1118);
ans += m[x];
x = (e[i].x + 1680) * p + (e[i].y + 1118);
ans += m[x];
}
cout << ans / 2;
return 0;
}
H: Imperfect GPS
题目描述
Lots of runners use personal Global Positioning System (GPS) receivers to track how many miles they run. No GPS is perfect,
though: it only records its position periodically rather than continuously, so it can miss parts of the true running path. For this problem we’ll consider a GPS that works in the following way when tracking a run:
• At the beginning of the run, the GPS first records the runner’s starting position at time 0.
• It then records the position every t units of time.
• It always records the position at the end of the run, even if the total running time is not a multiple of t.
The GPS assumes that the runner goes in a straight line between each consecutive pair of recorded positions. Because of this, a GPS can underestimate the total distance run.
For example, suppose someone runs in straight lines and at constant speed between the positions on the left side of Table 1. The time they reach each position is shown next to the position. They stopped running at time 11. If the GPS records a position every 2 units of time, its readings would be the records on the right side of Table 1.
image
The total distance run is approximately 14.313708 units, while the GPS measures the distance as approximately 11.650281 units. The difference between the actual and GPS distance is approximately 2.663427 units, or approximately 18.607525% of the total run distance.
Given a sequence of positions and times for a running path, as well as the GPS recording time interval t, calculate the percentage of the total run distance that is lost by the GPS. Your computations should assume that the runner goes at a constant speed in a straight line between consecutive positions.
输入
The input consists of a single test case. The first line contains two integers n (2 ≤ n ≤ 100) and t(1 ≤ t ≤ 100), where n is the total number of positions on the running path, and t is the recording time interval of the GPS (in seconds).
The next n lines contain three integers per line. The i-th line has three integers xi, yi (−106 ≤ xi, yi ≤106), and ti (0 ≤ ti ≤ 106), giving the coordinates of the i-th position on the running path and the time (in seconds) that position is reached. The values of ti’s are strictly increasing. The first and last positions are the start and end of the run. Thus, t1 is always zero.
It is guaranteed that the total run distance is greater than zero.
输出
Output the percentage of the actual run distance that is lost by the GPS. The answer is considered correct if it is within 10−5 of the correct answer.
INPUT:
6 2
0 0 0
0 3 3
-2 5 5
0 7 7
2 5 9
0 3 11
OUTPUT:
18.60752550117103
解析：from mhr :题目题意远大于题目本身难度，实际上就是求原先的记录与后来的记录的偏差，后来的记录因为是一个给定的范围的T，所以如果要跟原来的记录扯上关系，那么应该最先想到用点与方向向量的方式表示一个向量然后计算这个方向上对应位置的点。也就是Q=P+t*v这样把t算出来Q算出来就是GPS偏差的点然后算距离求差值算百分数就行了
#include <bits/stdc++.h>
using namespace std;
double sum1, sum2;
struct v
{
double x, y, t;
} num[6666];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> num[i].x >> num[i].y >> num[i].t;
for (int i = 2; i <= n; i++)
sum1 += hypot((num[i].x - num[i - 1].x), (num[i].y - num[i - 1].y));
v st = num[1];
for (int i = 1; i <= n - 1; i++)
{
while (st.t + m <= num[i + 1].t)
{
sum2 += hypot(num[i].x + (num[i + 1].x - num[i].x) / (num[i + 1].t - num[i].t) * (st.t + m - num[i].t) - st.x, num[i].y + (num[i + 1].y - num[i].y) / (num[i + 1].t - num[i].t) * (st.t + m - num[i].t) - st.y);
st.x = num[i].x + (num[i + 1].x - num[i].x) / (num[i + 1].t - num[i].t) * (st.t + m - num[i].t);
st.y = num[i].y + (num[i + 1].y - num[i].y) / (num[i + 1].t - num[i].t) * (st.t + m - num[i].t);
st.t += m;
}
}
sum2 += hypot(num[n].x - st.x, num[n].y - st.y);
cout << fixed << setprecision(14) << (sum1 - sum2) / sum1 * 100;
}
I: Odd Gnome
题目描述
According to the legend of Wizardry and Witchcraft, gnomes live in burrows underground, known as gnome holes. There they dig
up and eat the roots of plants, creating little heaps of earth around gardens, causing considerable damage to them.
Mrs. W, very annoyed by the damage, has to regularly de-gnome her garden by throwing the gnomes over the fence. It is a lot of work to throw them one by one because there are so many. Fortunately, the species is so devoted to their kings that each group always follows its king no matter what. In other words, if she were to throw just the king over the fence, all the other gnomes in that group would leave.
So how does Mrs. W identify the king in a group of gnomes? She knows that gnomes travel in a certain order, and the king, being special, is always the only gnome who does not follow that order.
Here are some helpful tips about gnome groups:
• There is exactly one king in a group.
• Except for the king, gnomes arrange themselves in strictly increasing ID order.
• The king is always the only gnome out of that order.
• The king is never the first nor the last in the group, because kings like to hide themselves.
Help Mrs. W by finding all the kings!
输入
The input starts with an integer n, where 1 ≤ n ≤ 100, representing the number of gnome groups. Each of the n following lines contains one group of gnomes, starting with an integer g, where 3 ≤ g ≤ 1 000,representing the number of gnomes in that group. Following on the same line are g space-separated integers, representing the gnome ordering. Within each group all the integers (including the king) are unique and in the range [0, 10 000]. Excluding the king, each integer is exactly one more than the integer preceding it.
输出
For each group, output the king’s position in the group (where the first gnome in line is number one).
解析：签到题，找出那个破坏升序排列的家伙！
wa了一次，是因为把数组开小了，WTF？！
#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <iostream>
using namespace std;
int a[110000];
int main()
{
int t;
cin >> t;
while (t--)
{
memset(a, 0, sizeof(a));
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 1; i < n - 1; i++)
if (a[i] - a[i - 1] != 1)
{
cout << i + 1 << endl;
break;
}
}
return 0;
}
J: Progressive Scramble
题目描述
You are a member of a naive spy agency. For secure communication,members of the agency use a very simple encryption algorithm – which changes each symbol in the message ‘progressively’, i.e., based on the symbols preceding it. The allowed symbols are space and the 26 lowercase English letters. For encryption purposes we assign them the values 0 (for space) and 1 through 26 (for a–z). We’ll let v(s) represent the numeric value of symbol s.
Consider a message with symbols s1, s2, . . . , sn. The encryption algorithm starts by converting the first symbol s1 into its associated value u1 = v(s1). Then for each subsequent symbol si in the message, the computed value is ui = v(si) + ui−1 — the sum of its associated value and the computed value for the previous symbol. (Note that when there is a space in the input
message, the previous scrambled letter is repeated.) This process continues until all the ui are computed.
At this point, the message is a sequence of numeric values. We need to convert it back to symbols to print it out. We do this by taking the value ui modulo 27 (since there are 27 valid symbols), and replacing that value with its corresponding symbol. For example, if ui = 32, then 32 mod 27 = 5, which is the symbol ‘e’ (since v(e) = 5).
Let’s look at an example. Suppose we want to encrypt the string “my pie”.
- First, convert each symbol si into v(si): [13, 25, 0, 16, 9, 5].
- Next, compute each ui: [13, 38, 38, 54, 63, 68].
- Then, use modulus on the ui: [13, 11, 11, 0, 9, 14].
- Finally, convert these back to symbols: “mkk in”.
Create a program that takes text and encrypts it using this algorithm, and also decrypts text that has been encrypted with this algorithm.
输入
The input to your program consists of a single integer 1 ≤ n ≤ 100 on its own line. This number is followed by n lines, each containing the letter ‘e’ or ‘d’, a single space, and then a message made up of lowercase letters (a–z) and spaces, continuing to the end of the line. Each message is between 1 and 80 characters long. The letters ‘d’ and ‘e’ indicate that your program decrypts or encrypts the subsequent string, respectively.
输出
Output the result of encrypting or decrypting each message from the input on its own separate line. Note that differences in whitespace are significant in this problem. Therefore your output must match the correct output character-for-character, including spaces.
解析：因为这题有坑，出了点小差错，导致我队mhr同学....算了，不说了，很气，
#include <bits/stdc++.h>
using namespace std;
long long num[6666], pre[6666], ans[6666], now;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
while (n--)
{
char x;
cin >> x;
string a;
getline(cin, a);
a.erase(0, 1);
if (x == 'e')
{
for (int i = 0; i < a.size(); i++)
{
if (isspace(a[i]))
num[i] = 0;
else
num[i] = a[i] - 'a' + 1;
}
for (int i = 0; i < a.size(); i++)
{
if (i == 0)
pre[i] = num[i];
else
pre[i] = pre[i - 1] + num[i];
pre[i] %= 27;
}
for (int i = 0; i < a.size(); i++)
{
if (pre[i])
cout << char(pre[i] + 'a' - 1);
else
cout << ' ';
}
cout << "\n";
}
else
{
string t = "";
for (int i = 0; i < a.size(); i++)
{
if (isspace(a[i]))
num[i] = 0;
else
num[i] = a[i] - 'a' + 1;
}
for (int i = 0; i < a.size(); i++)
{
if (i == 0)
pre[i] = num[i], now = pre[i] / 27;
else
{
long long re = 27 * now + num[i];
if (re < pre[i - 1])
re += 27;
pre[i] = re;
now = re / 27;
}
}
ans[0] = pre[0];
for (int i = 1; i < a.size(); i++)
ans[i] = pre[i] - pre[i - 1];
for (int i = 0; i < a.size(); i++)
{
if (ans[i])
t += char(ans[i] + 'a' - 1);
else
t += ' ';
}
cout << t << "\n";
}
}
}
K: Space Probe
L: Suspension Bridges
题目描述
Mountain villages like to attract tourists by building suspension bridges, such as the one depicted here in the Harz Mountains in Germany. These bridges allow adventurously-inclined people to seek their thrills by crossing over deep gorges. To make sure that everyone gets just the right amount of excitement, the sag at the deepest point of the bridge should be significant relative to the distance the bridge covers.
Given the distance between the anchor points where the bridge is attached, and given a desired amount of sag, compute how long each of the cables holding the suspension bridge needs to be!
To help you solve this task, here is some background: A free-hanging suspension bridge will take on the form of a catenary curve (catena is Latin for chain), just like a free-hanging chain between two poles. Given the horizontal distance d between two anchor points and the desired amount s the cable is sagging in the center, there exists a positive parameter a such that a + s = a · cosh(d/2a). The length of the cable is then given by `(a, d) = 2a · sinh(d/2a).
The functions sinh and cosh denote the hyperbolic sine and hyperbolic cosine, respectively, which are defined as follows:
输入
The input consists of a single test case with two space-separated integers d and s given on a single line such that 0 < d ≤ 1 000 and 0 < s ≤ 1 000. The number d denotes the distance between the anchor points and s is the desired sag at the center of the bridge.
输出
Output the length of cable needed to cover the distance between the anchor points to achieve the desired sag. Your answer should be correct within an absolute error of 10−4.
INPUT:
400 40
OUTPUT:
410.474747252
这二分不能更裸了，只是当时没人做，我也没敢做这题啊，又被带偏节奏了。。。
#include <bits/stdc++.h>
using namespace std;
double d, s;
double check(double x)
{
return x + s - x * cosh(d / 2.0 / x);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> d >> s;
double l = 0, r = INT_MAX;
for (int i = 0; i < 100; i++)
{
double mid = (r + l) / 2.0;
if (check(mid) < 1e-9)
l = mid;
else
r = mid;
}
cout << fixed << setprecision(10) << (2.0 * l * sinh(d / 2.0 / l));
}
