Nordic Collegiate Programming Contest 2017 题解
前几天打了一场外国人的比赛，感觉那边的题目质量还是很好的，区分度很鲜明，题目没有国内的难，坑点比较少，比较注重思维，基础算法。
B题：
Best Relay Team
As the name of the event implies, such a sprint relay consist of legs, meters each. One would think that the best team would simply consist of the fastest m runners in the nation, but there is an important detail to take into account: flying start. In the nd, rd and th leg, the runner is already running when the baton is handed over. This means that some runners – those that have a slow acceleration phase – can perform relatively better in a relay if they are on the nd, rd or th leg.
You have a pool of runners to choose from. Given how fast each runner in the pool is, decide which four runners should represent your national team and which leg they should run. You are given two times for each runner – the time the runner would run the st leg, and the time the runner would run any of the other legs. A runner in a team can only run one leg.
Input
The first line of input contains an integer , the number of runners to choose from (). Then follow lines describing the runners. The ’th of these lines contains the name of the ’th runner, the time for the runner to run the st leg, and the time for the runner to run any of the other legs (). The names consist of between and (inclusive) uppercase letters ‘A’-‘Z’, and no two runners have the same name. The times are given in seconds with exactly two digits after the decimal point.
Output
First, output a line containing the time of the best team, accurate to an absolute or relative error of at most . Then output four lines containing the names of the runners in that team. The first of these lines should contain the runner you have picked for the st leg, the second line the runner you have picked for the nd leg, and so on. Any solution that results in the fastest team is acceptable.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 ASHMEADE 9.90 8.85 BLAKE 9.69 8.72 BOLT 9.58 8.43 CARTER 9.78 8.93 FRATER 9.88 8.92 POWELL 9.72 8.61 |
35.54 CARTER BOLT POWELL BLAKE |
| Sample Input 2 | Sample Output 2 |
|---|---|
9 AUSTRIN 15.60 14.92 DRANGE 15.14 14.19 DREGI 15.00 14.99 LAAKSONEN 16.39 14.97 LUNDSTROM 15.83 15.35 MARDELL 13.36 13.20 POLACEK 13.05 12.55 SANNEMO 15.23 14.74 SODERMAN 13.99 12.57 |
52.670000 MARDELL POLACEK SODERMAN DRANGE |
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500 + 10;
int n;
double eps = 0.0000000001;
struct node{
string name;
double speed1, speed2;
bool operator <(const node &res) const{
return speed2 < res.speed2;
}
}Node[maxn];
vector<node> g;
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
cin>>Node[i].name>>Node[i].speed1>>Node[i].speed2;
}
double Min = 1000000000000.0;
string s1, s2, s3, s4;
for(int i = 1; i <= n; i++)
{
g.clear();
double sum = Node[i].speed1;
for(int j = 1; j <= n; j++)
{
if(j != i) g.push_back(Node[j]);
}
sort(g.begin(), g.end());
for(int j = 0; j <= 2; j++)
{
sum += g[j].speed2;
}
if(sum - Min < eps)
{
Min = sum;
s1 = Node[i].name;
s2 = g[0].name;
s3 = g[1].name;
s4 = g[2].name;
}
}
printf("%.2lf\n", Min);
cout<<s1<<endl<<s2<<endl<<s3<<endl<<s4<<endl;
return 0;
}D题：
Distinctive Character
The similarity between two characters and is calculated as follows: for each feature , if both and have feature or if none of them have feature , the similarity increases by one.
Tira does not have a character yet. She would like to create a new, very original character so that the maximum similarity between Tira’s character and any other character is as low as possible.
Given the characters of the other players, your task is to create a character for Tira that fulfils the above requirement. If there are many possible characters, you can choose any of them.
Input
The first line of input contains two integers and , where is the number of players (excluding Tira) and is the number of features.
Then follow lines describing the existing characters. Each of these lines contains a string of digits which are either or . A in position means the character has the ’th feature, and a means that it does not have the ’th feature.
Output
Output a single line describing the features of Tira’s character in the same format as in the input. If there are multiple possible characters with the same smallest maximum similarity, any one of them will be accepted.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 5 01001 11100 10111 |
00010 |
| Sample Input 2 | Sample Output 2 |
|---|---|
1 4 0000 |
1111 |
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000000 + 200000;
int inf = 0x3f3f3f3f;
int n, tot, k;
int head[maxn];
bool visit[maxn];
char ch[30];
int digit[30];
int dis[maxn];
int sum;
struct edge{
int v, w, Nxt;
}Edge[maxn<<5];
vector<int> g;
void init()
{
tot = 0;
memset(head, -1, sizeof(head));
memset(visit, false, sizeof(visit));
g.clear();
}
int Transform(char *s)
{
int ans = 0;
int len = strlen(s);
for(int i = 0; i < len; i++)
{
if(s[i] == '1') ans += (1<<i);
}
return ans;
}
void add(int u, int v, int w)
{
Edge[tot].v = v;
Edge[tot].w = w;
Edge[tot].Nxt = head[u];
head[u] = tot++;
}
void build(int u)
{
for(int i = 0; i < k; i++)
{
digit[i] = (u>>i)&1;
}
for(int i = 0; i < k; i++)
{
int x = 0;
for(int j = 0; j < k; j++)
{
int value;
if(i == j) value = digit[j]^1;
else value = digit[j];
if(value) x += (1<<j);
}
add(u, x, 1);
}
}
struct node{
int u, w;
node(){}
node(int _u, int _w){
u = _u;
w = _w;
}
bool operator <(const node &res) const {
return w > res.w;
}
};
void bfs()
{
memset(dis, inf, sizeof(dis));
priority_queue<node> q;
while(!q.empty()) q.pop();
q.push(node(sum, 0));
dis[sum] = 0;
while(!q.empty())
{
node nx = q.top();
q.pop();
int u = nx.u;
int w = nx.w;
if(dis[u] < w) continue;
for(int i = head[u]; i != -1; i = Edge[i].Nxt)
{
int v = Edge[i].v;
int ww = Edge[i].w;
if(dis[v] > dis[u] + ww)
{
dis[v] = dis[u] + ww;
q.push(node(v, dis[v]));
}
}
}
}
int main()
{
init();
scanf("%d%d", &n, &k);
int judge = 0;
for(int i = 1; i <= n; i++)
{
scanf("%s", ch);
int num = Transform(ch);
if(!visit[num])
{
visit[num] = true;
g.push_back(num);
judge++;
}
}
sum = (1<<k);
if(judge >= sum)
{
for(int i = 1; i <= k; i++)
{
cout<<"0";
}
cout<<endl;
return 0;
}
for(int i = 0; i < sum; i++) build(i);
for(int i = 0; i < g.size(); i++)
{
add(sum, g[i], 0);
add(g[i], sum, 0);
}
int Max = 0;
int st = 0;
bfs();
for(int i = 0; i <= sum; i++)
{
if(visit[i]) continue;
if(dis[i] > Max)
{
Max = dis[i];
st = i;
}
}
for(int i = 0; i < k; i++)
{
int value = (st>>i)&1;
cout<<value;
}
cout<<endl;
return 0;
}
E题：Emptying the Baltic
First, Gunnar wants to build a floodbank connecting Denmark and Norway to separate the Baltic from the Atlantic Ocean. The floodbank will also help protect Nordic countries from rising sea levels in the ocean. Next, Gunnar installs a device that can drain the Baltic from the seafloor. The device will drain as much water as needed to the Earth’s core where it will disappear forever (because that is how physics works, at least as far as Gunnar is concerned). However, depending on the placement of the device, the entire Baltic might not be completely drained – some pockets of water may remain.
To simplify the problem, Gunnar is approximating the map of the Baltic using a -dimensional grid with meter squares. For each square on the grid, he computes the average altitude. Squares with negative altitude are covered by water, squares with non-negative altitude are dry. Altitude is given in meters above the sea level, so the sea level has altitude of exactly . He disregards lakes and dry land below the sea level, as these would not change the estimate much anyway.
Water from a square on the grid can flow to any of its neighbours, even if the two squares only share a corner. The map is surrounded by dry land, so water never flows outside of the map. Water respects gravity, so it can only flow closer to the Earth’s core – either via the drainage device or to a neighbouring square with a lower water level.
Gunnar is more of an idea person than a programmer, so he has asked for your help to evaluate how much water would be drained for a given placement of the device.
Input
The first line contains two integers and , , denoting the height and width of the map.
Then follow lines, each containing integers. The first line represents the northernmost row of Gunnar’s map. Each integer represents the altitude of a square on the map grid. The altitude is given in meters and it is at least and at most .
The last line contains two integers and , , indicating that the draining device is placed in the cell corresponding to the ’th column of the ’th row. You may assume that position has negative altitude (i.e., the draining device is not placed on land).
Output
Output one line with one integer – the total volume of sea water drained, in cubic meters.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 3 -5 2 -5 -1 -2 -1 5 4 -5 2 2 |
10 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 3 -2 -3 -4 -3 -2 -3 2 1 |
16 |
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 510;
int h, w, s, t;
LL M[maxn][maxn];
LL Level[maxn][maxn];
LL dis[maxn][maxn];
int dx[4] = {0, 1, -1};
int dy[4] = {0, 1, -1};
LL up;
bool visit[maxn][maxn];
bool judge(int xx, int yy)
{
if(xx < 1 || xx > h) return false;
if(yy < 1 || yy > w) return false;
return true;
}
struct node{
int x, y;
LL d;
node(){}
node(int _x, int _y, LL _d){
x = _x;
y = _y;
d = _d;
}
bool operator <(const node &res) const {
return d < res.d;
}
};
LL ans;
void solve()
{
priority_queue<node> q;
while(!q.empty()) q.pop();
q.push(node(s, t, -M[s][t]));
dis[s][t] = -M[s][t];
up = -M[s][t];
while(!q.empty())
{
node nx = q.top();
q.pop();
int x = nx.x;
int y = nx.y;
LL d = nx.d;
if(dis[x][y] > d) continue;
for(int i = 0; i <= 2; i++)
{
for(int j = 0; j <= 2; j++)
{
if(i == j && i == 0) continue;
int nowx = x + dx[i];
int nowy = y + dy[j];
if(!judge(nowx, nowy)) continue;
if(M[nowx][nowy] >= 0) continue;
LL Max = min(dis[x][y], abs(M[nowx][nowy]));
Max = min(Max, up);
if(dis[nowx][nowy] < Max)
{
dis[nowx][nowy] = Max;
q.push(node(nowx, nowy, Max));
}
}
}
}
}
int main()
{
scanf("%d%d", &h, &w);
for(int i = 1; i <= h; i++)
{
for(int j = 1; j <= w; j++)
{
scanf("%lld", &M[i][j]);
}
}
scanf("%d%d", &s, &t);
memset(visit, false, sizeof(visit));
memset(dis, 0, sizeof(dis));
ans = 0;
solve();
for(int i = 1; i <= h; i++)
{
for(int j = 1; j <= w; j++)
{
ans += dis[i][j];
}
}
printf("%lld\n", ans);
return 0;
}
G题：
Galactic Collegiate Programming Contest
This year there are teams in the contest. The teams are numbered , and your favorite team has number .
Like today, the score of a team is a pair of integers where is the number of solved problems and is the total penalty of that team. When a team solves a problem there is some associated penalty (not necessarily calculated in the same way as in the NCPC – the precise details are not important in this problem). The total penalty of a team is the sum of the penalties for the solved problems of the team.
Consider two teams and whose scores are and . The score of team is better than that of if either , or if and . The rank of a team is where is the number of teams whose score is better.
You would like to follow the performance of your favorite team. Unfortunately, the organizers of GCPC do not provide a scoreboard. Instead, they send a message immediately whenever a team solves a problem.
Input
The first line of input contains two integers and , where is the number of teams, and is the number of events.
Then follow lines that describe the events. Each line contains two integers and ( and ), meaning that team has solved a problem with penalty . The events are ordered by the time when they happen.
Output
Output lines. On the ’th line, output the rank of your favorite team after the first events have happened.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 4 2 7 3 5 1 6 1 9 |
2 3 2 1 |
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 100000 + 10;
int n, m;
LL inf = -(1e8 + 1);
LL H[maxn * 2];
int Tree[maxn<<1];
int cnt;
int lowbit(int x)
{
return x&(-x);
}
void add(int loc, int value)
{
for(int i = loc; i <= cnt; i += lowbit(i))
{
Tree[i] += value;
}
}
int get(int loc)
{
int ans = 0;
for(int i = loc; i >= 1; i -= lowbit(i))
{
ans += Tree[i];
}
return ans;
}
int Hash(LL value)
{
return lower_bound(H, H + cnt, value) - H + 1;
}
void init()
{
sort(H, H + cnt);
cnt = unique(H, H + cnt) - H;
memset(Tree, 0, sizeof(Tree));
}
struct node{
int team, t;
}Node[maxn];
LL Time[maxn];
int main()
{
scanf("%d%d", &n, &m);
memset(Time, 0, sizeof(Time));
cnt = 0;
for(int i = 1; i <= m; i++)
{
scanf("%d%d", &Node[i].team, &Node[i].t);
int team = Node[i].team;
int tt = Node[i].t;
Time[team] += (inf + tt);
H[cnt++] = Time[team];
}
init();
memset(Time, 0, sizeof(Time));
for(int i = 1; i <= m; i++)
{
int team = Node[i].team;
int tt = Node[i].t;
int before = Hash(Time[team]);
add(before, -1);
Time[team] += (inf + tt);
int now = Hash(Time[team]);
add(now, 1);
int loc = Hash(Time[1]);
printf("%d\n", get(loc - 1) + 1);
}
return 0;
}
补上这题集合的代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 10;
int n, m;
int p[maxn], t[maxn];
struct team{
int pp, tt;
team(){};
team(int _pp, int _tt){
pp = _pp;
tt = _tt;
}
bool operator <(const team &res) const{
if(pp == res.pp) return tt > res.tt;
else return pp < res.pp;
}
bool operator ==(const team &res) const{
return (pp == res.pp && tt == res.tt);
}
};
multiset<team> s;
multiset<team>::iterator it;
int main()
{
scanf("%d%d", &n, &m);
s.clear();
memset(p, 0, sizeof(p));
memset(t, 0, sizeof(t));
int id, value;
for(int i = 1; i <= m; i++)
{
scanf("%d%d", &id, &value);
if(id == 1)
{
p[1]++;
t[1] += value;
team n1 = team(p[1], t[1]);
while(!s.empty())
{
it = s.begin();
team nx = *it;
if(nx < n1 || nx == n1) s.erase(it);
else break;
}
}
else
{
int p1 = p[id] + 1;
int t1 = t[id] + value;
team n1 = team(p1, t1);
team n2 = team(p[1], t[1]);
if(n2 < n1)
{
it = s.find(team(p[id], t[id]));
if(it != s.end()) s.erase(it);
p[id]++;
t[id] += value;
s.insert(team(p[id], t[id]));
}
else
{
p[id]++;
t[id] += value;
}
}
printf("%d\n", s.size() + 1);
}
return 0;
}
I题：
Import Spaghetti
As you sit down and think, you decide that the first thing to do is to eliminate the cycles in the dependency graph. So you start by finding a shortest dependency cycle.
Input
The first line of input contains a number , , the number of files. Then follows one line with distinct names of files. Each name is a string with at least and at most lower case letters ‘a’ to ‘z’. Then follow sections, one section per file name, in the order they were given on the second line. Each section starts with one line containing the name of the file and an integer , followed by lines, each starting with “import”.
Each “import” line is a comma-space separated line of dependencies. No file imports the same file more than once, and every file imported is listed in the second line of the input. Comma-space separated means that every line will start with “import”, then have a list of file names separated by “, ” (see sample inputs for examples). Each import statement is followed by at least one file name.
Output
If the code base has no cyclic dependencies, output “SHIP IT”. Otherwise, output a line containing the names of files in a shortest cycle, in the order of the cycle (i.e., the th file listed must import the st file listed, and the last file listed must import the first). If there are many shortest cycles, any one will be accepted.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 a b c d a 1 import d, b, c b 2 import d import c c 1 import c d 0 |
c |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 classa classb myfilec execd libe classa 2 import classb import myfilec, libe classb 1 import execd myfilec 1 import libe execd 1 import libe libe 0 |
SHIP IT |
| Sample Input 3 | Sample Output 3 |
|---|---|
5 classa classb myfilec execd libe classa 2 import classb import myfilec, libe classb 1 import execd myfilec 1 import libe execd 1 import libe, classa libe 0 |
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500 + 10;
int n;
map<string, int> mp;
map<int, string> mmpp;
vector<int> g[maxn];
bool visit[maxn];
char ch[1000000];
char test[1000000];
struct node{
int v, depth;
node(){}
node(int _v = 0, int _depth = 0){
v = _v;
depth = _depth;
}
};
int pre[maxn];
vector<int> ans;
int bfs(int s)
{
queue<node> q;
while(!q.empty()) q.pop();
memset(visit, false, sizeof(visit));
memset(pre, -1, sizeof(pre));
q.push(node(s, 0));
visit[s] = true;
while(!q.empty())
{
node nx = q.front();
q.pop();
int u = nx.v;
int depth = nx.depth;
for(int i = 0; i < g[u].size(); i++)
{
if(g[u][i] == s)
{
pre[s] = u;
return depth;
}
int v = g[u][i];
if(!visit[v])
{
visit[v] = true;
pre[v] = u;
q.push(node(v, depth + 1));
}
}
}
return -1;
}
void debug()
{
for(int i = 1; i <= n; i++)
{
cout<<"i == "<<i<<endl;
cout<<mmpp[i]<<endl;
for(int j = 0; j < g[i].size(); j++)
{
cout<<mmpp[g[i][j]]<<" ";
}
cout<<endl;
}
}
int main()
{
scanf("%d", &n);
string s;
mp.clear();
mmpp.clear();
for(int i = 1; i <= n; i++)
{
cin>>s;
mp[s] = i;
mmpp[i] = s;
//cout<<"s == "<<s<<endl;
}
int num;
for(int i = 1; i <= n; i++)
{
cin>>s>>num;
int id = mp[s];
//cout<<"num == "<<num<<endl;
getchar();
for(int j = 1; j <= num; j++)
{
gets(ch);
//printf("ch == %s\n", ch);
int len = strlen(ch);
int res = 0;
for(int k = 7; k < len; k++)
{
if(ch[k] == ' ') continue;
else if(ch[k] != ',')
{
test[res++] = ch[k];
}
else if(ch[k] == ',')
{
test[res] = '\0';
string tt = string(test);
g[id].push_back(mp[tt]);
res = 0;
}
}
if(res)
{
test[res] = '\0';
string tt = string(test);
g[id].push_back(mp[tt]);
}
}
}
//debug();
int Min = 100000;
int flag = false;
for(int i = 1; i <= n; i++)
{
int judge = bfs(i);
//cout<<"i == "<<i<<endl;
//cout<<"judge == "<<judge<<endl;
if(judge != -1)
{
flag = true;
if(judge < Min)
{
Min = judge;
ans.clear();
int xx = pre[i];
//cout<<"xx == "<<xx<<endl;
while(xx != i)
{
//cout<<"xx == "<<xx<<endl;
ans.push_back(xx);
xx = pre[xx];
}
ans.push_back(i);
}
}
}
if(flag)
{
for(int i = ans.size() - 1; i >= 0; i--)
{
if(i == 0) cout<<mmpp[ans[i]]<<endl;
else cout<<mmpp[ans[i]]<<" ";
}
}
else cout<<"SHIP IT"<<endl;
return 0;
}
J题：
Judging Moose
The point system works like this: If the number of tines on the left side and the right side match, the moose is said to have the even sum of the number of points. So, “an even -point moose”, would have three tines on each side. If the moose has a different number of tines on the left and right side, the moose is said to have twice the highest number of tines, but it is odd. So “an odd -point moose” would have tines on one side, and or less tines on the other side.
Can you figure out how many points a moose has, given the number of tines on the left and right side?
Input
The input contains a single line with two integers and , where is the number of tines on the left, and is the number of tines on the right.
Output
Output a single line describing the moose. For even pointed moose, output “Even ” where is the points of the moose. For odd pointed moose, output “Odd ” where is the points of the moose. If the moose has no tines, output “Not a moose”
| Sample Input 1 | Sample Output 1 |
|---|---|
2 3 |
Odd 6 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 3 |
Even 6 |
| Sample Input 3 | Sample Output 3 |
|---|---|
0 0 |
Not a moose |
#include<bits/stdc++.h>
using namespace std;
int main()
{
int l,r;
while(~scanf("%d%d",&l,&r))
{
if(l==r&&(l||r))
{
cout<<"Even "<<l+r<<endl;
}
else if(l!=r&&(l||r))
{
cout<<"Odd "<<2*max(l,r)<<endl;
}
else
cout<<"Not a moose"<<endl;
}
return 0;
}K题：
Kayaking Trip
The kayaks are of different types and have different amounts of packing, so some are more easily paddled than others. This is captured by a speed factor that you have already figured out for each kayak. The final speed of a kayak, however, is also determined by the strengths and of the two people in the kayak, by the relation . In your group you have some beginners with a kayaking strength of , a number of normal participants with strength and some quite experienced strong kayakers with strength .
Input
The first line of input contains three non-negative integers , , and , denoting the number of beginners, normal participants, and experienced kayakers, respectively. The total number of participants, , will be even, at least , and no more than . This is followed by a line with three integers , , and , giving the strengths of the corresponding participants (). The third and final line contains integers ( for each ), each giving the speed factor of one kayak.
Output
Output a single integer, the maximum speed that the slowest kayak can get by distributing the participants two in each kayak.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 1 0 40 60 90 18 20 |
1600 |
| Sample Input 2 | Sample Output 2 |
|---|---|
7 0 7 5 10 500 1 1 1 1 1 1 1 |
505 |
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1000000 + 10;
int b, n, e;
int sb, sn, se;
int m;
int value[maxn];
double eps = 1e-7;
struct node{
int numb, numn, nume;
int sum;
bool operator <(const node &res) const{
return sum < res.sum;
}
}Node[maxn];
bool judge(int x)
{
int bb = b;
int nn = n;
int ee = e;
for(int i = 1; i <= m; i++)
{
double down = (double)x / (double)value[i];
int cnt = 0;
if(bb >= 2)
{
Node[cnt].numb = 2;
Node[cnt].numn = 0;
Node[cnt].nume = 0;
Node[cnt++].sum = sb + sb;
}
if(nn >= 2)
{
Node[cnt].numb = 0;
Node[cnt].numn = 2;
Node[cnt].nume = 0;
Node[cnt++].sum = sn + sn;
}
if(ee >= 2)
{
Node[cnt].numb = 0;
Node[cnt].numn = 0;
Node[cnt].nume = 2;
Node[cnt++].sum = se + se;
}
if(bb && nn)
{
Node[cnt].numb = 1;
Node[cnt].numn = 1;
Node[cnt].nume = 0;
Node[cnt++].sum = sb + sn;
}
if(bb && ee)
{
Node[cnt].numb = 1;
Node[cnt].numn = 0;
Node[cnt].nume = 1;
Node[cnt++].sum = sb + se;
}
if(nn && ee)
{
Node[cnt].numb = 0;
Node[cnt].numn = 1;
Node[cnt].nume = 1;
Node[cnt++].sum = sn + se;
}
sort(Node, Node + cnt);
int flag = false;
for(int j = 0; j < cnt; j++)
{
if(down - (double)Node[j].sum <= eps)
{
flag = true;
bb -= Node[j].numb;
nn -= Node[j].numn;
ee -= Node[j].nume;
break;
}
}
if(!flag) return false;
}
return true;
}
int main()
{
scanf("%d%d%d", &b, &n, &e);
m = (b + n + e) / 2;
scanf("%d%d%d", &sb, &sn, &se);
for(int i = 1; i <= m; i++)
{
scanf("%d", &value[i]);
}
int l = 0, r = 1000000000;
int re = -1;
while(l <= r)
{
int mid = (l + r)>>1;
if(judge(mid))
{
re = mid;
l = mid + 1;
}
else r = mid - 1;
}
printf("%d\n", re);
return 0;
}推荐阅读
-
Nordic Collegiate Programming Contest 2017 题解
-
2015-2016 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2015) Goblin Garden Guards (数论)
-
German Collegiate Programming Contest 2015 ：
-
【Codeforces】2015-2016 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2015) A Adjoin the Netwo
-
Nordic Collegiate Programming Contest 2019 部分题解
-
ICPC Arab Collegiate Programming Contest 2013（部分题解）
-
2020年04月10日UCF Local Programming Contest 2017
-
L Clock Master(2020 China Collegiate Programming Contest Weihai Site)补题
-
2015 ACM Amman Collegiate Programming Contest I.Bahosain and Digits【思维+暴力枚举】
-
2011-2012 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2011)Problem A Robots on a grid（迷宫dp）