A. Restoring Three Numbers
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Polycarp has guessed three positive integers ?a, ?b and ?c. He keeps these numbers in secret, but he writes down four numbers on a board in arbitrary order — their pairwise sums (three numbers) and sum of all three numbers (one number). So, there are four numbers on a board in random order: ?+?a+b, ?+?a+c, ?+?b+c and ?+?+?a+b+c.
You have to guess three numbers ?a, ?b and ?c using given numbers. Print three guessed integers in any order.
Pay attention that some given numbers ?a, ?b and ?c can be equal (it is also possible that ?=?=?a=b=c).
Input
The only line of the input contains four positive integers ?1,?2,?3,?4x1,x2,x3,x4 (2≤??≤1092≤xi≤109) — numbers written on a board in random order. It is guaranteed that the answer exists for the given number ?1,?2,?3,?4x1,x2,x3,x4.
Output
Print such positive integers ?a, ?b and ?c that four numbers written on a board are values ?+?a+b, ?+?a+c, ?+?b+c and ?+?+?a+b+c written in some order. Print ?a, ?b and ?c in any order. If there are several answers, you can print any. It is guaranteed that the answer exists.
Examples
input
Copy
3 6 5 4
output
Copy
2 1 3
input
Copy
40 40 40 60
output
Copy
20 20 20
input
Copy
201 101 101 200
output
Copy
1 100 100
签到题
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define esp 1e-6
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
int a[5];
int main()
{
for(int i=1; i<=4; i++) scanf("%d", &a[i]);
sort(a + 1, a + 5);
printf("%d %d %d\n", a[4] - a[1], a[4] - a[2], a[4] - a[3]);
return 0;
}
B. Make Them Equal
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given a sequence ?1,?2,…,??a1,a2,…,an consisting of ?n integers.
You can choose any non-negative integer ?D (i.e. ?≥0D≥0), and for each ??ai you can:
- add ?D (only once), i. e. perform ??:=??+?ai:=ai+D, or
- subtract ?D (only once), i. e. perform ??:=??−?ai:=ai−D, or
- leave the value of ??ai unchanged.
It is possible that after an operation the value ??ai becomes negative.
Your goal is to choose such minimum non-negative integer ?D and perform changes in such a way, that all ??ai are equal (i.e. ?1=?2=⋯=??a1=a2=⋯=an).
Print the required ?D or, if it is impossible to choose such value ?D, print -1.
For example, for array [2,8][2,8] the value ?=3D=3 is minimum possible because you can obtain the array [5,5][5,5] if you will add ?D to 22 and subtract ?D from 88. And for array [1,4,7,7][1,4,7,7] the value ?=3D=3 is also minimum possible. You can add it to 11 and subtract it from 77 and obtain the array [4,4,4,4][4,4,4,4].
Input
The first line of the input contains one integer ?n (1≤?≤1001≤n≤100) — the number of elements in ?a.
The second line of the input contains ?n integers ?1,?2,…,??a1,a2,…,an (1≤??≤1001≤ai≤100) — the sequence ?a.
Output
Print one integer — the minimum non-negative integer value ?D such that if you add this value to some ??ai, subtract this value from some ??ai and leave some ??ai without changes, all obtained values become equal.
If it is impossible to choose such value ?D, print -1.
需要判断，有几种值，然后分类讨论，就是个贪心思想。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define esp 1e-6
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 107;
int N, a[maxN], b[5];
set<int> st;
set<int>::iterator it;
int main()
{
scanf("%d", &N);
for(int i=1; i<=N; i++) { scanf("%d", &a[i]); st.insert(a[i]); }
sort(a + 1, a + N + 1);
if(st.size() == 1) printf("0\n");
else if(st.size() == 2)
{
int ans = a[N] - a[1];
if(ans & 1) printf("%d\n", ans);
else printf("%d\n", ans>>1);
}
else if(st.size() == 3)
{
int i = 1;
for(it = st.begin(); it!=st.end(); it++) b[i++] = *it;
sort(b + 1, b + 4);
if(b[2] - b[1] == b[3] - b[2]) printf("%d\n", b[3] - b[2]);
else printf("-1\n");
}
else printf("-1\n");
return 0;
}
C. Gourmet Cat
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Polycarp has a cat and his cat is a real gourmet! Dependent on a day of the week he eats certain type of food:
- on Mondays, Thursdays and Sundays he eats fish food;
- on Tuesdays and Saturdays he eats rabbit stew;
- on other days of week he eats chicken stake.
Polycarp plans to go on a trip and already packed his backpack. His backpack contains:
- ?a daily rations of fish food;
- ?b daily rations of rabbit stew;
- ?c daily rations of chicken stakes.
Polycarp has to choose such day of the week to start his trip that his cat can eat without additional food purchases as long as possible. Print the maximum number of days the cat can eat in a trip without additional food purchases, if Polycarp chooses the day of the week to start his trip optimally.
Input
The first line of the input contains three positive integers ?a, ?b and ?c (1≤?,?,?≤7⋅1081≤a,b,c≤7⋅108) — the number of daily rations of fish food, rabbit stew and chicken stakes in Polycarps backpack correspondingly.
Output
Print the maximum number of days the cat can eat in a trip without additional food purchases, if Polycarp chooses the day of the week to start his trip optimally.
贪心
除了需要考虑几个周之后，我们对于剩下的材料，我们从周一～周日分别算作第一天开始，去跑最大值。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define esp 1e-6
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define MIN3(x, y, z) min(min(x, y), z)
const int week[7] = { 0, 1, 2, 0, 2, 1, 0 };
int a[3], b[3], minn, day;
int solve(int s)
{
int ans = 0;
for(int i=s, u; i<s+7; i++)
{
u = i % 7;
if(b[week[u]]--) ans++;
else break;
}
return ans;
}
int main()
{
for(int i=0; i<3; i++) scanf("%d", &a[i]);
minn = MIN3(a[0]/3, a[1]/2, a[2]/2);
day += minn * 7;
a[0] -= minn * 3;
a[1] -= minn<<1;
a[2] -= minn<<1;
int tmp = 0;
for(int i=0; i<7; i++)
{
for(int j=0; j<3; j++) b[j] = a[j];
tmp = max(tmp, solve(i));
}
printf("%d\n", tmp + day);
return 0;
}
D. Walking Robot
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
There is a robot staying at ?=0X=0 on the ??Ox axis. He has to walk to ?=?X=n. You are controlling this robot and controlling how he goes. The robot has a battery and an accumulator with a solar panel.
The ?i-th segment of the path (from ?=?−1X=i−1 to ?=?X=i) can be exposed to sunlight or not. The array ?s denotes which segments are exposed to sunlight: if segment ?i is exposed, then ??=1si=1, otherwise ??=0si=0.
The robot has one battery of capacity ?b and one accumulator of capacity ?a. For each segment, you should choose which type of energy storage robot will use to go to the next point (it can be either battery or accumulator). If the robot goes using the battery, the current charge of the battery is decreased by one (the robot can't use the battery if its charge is zero). And if the robot goes using the accumulator, the current charge of the accumulator is decreased by one (and the robot also can't use the accumulator if its charge is zero).
If the current segment is exposed to sunlight and the robot goes through it using the battery, the charge of the accumulator increases by one (of course, its charge can't become higher than it's maximum capacity).
If accumulator is used to pass some segment, its charge decreases by 1 no matter if the segment is exposed or not.
You understand that it is not always possible to walk to ?=?X=n. You want your robot to go as far as possible. Find the maximum number of segments of distance the robot can pass if you control him optimally.
Input
The first line of the input contains three integers ?,?,?n,b,a (1≤?,?,?≤2⋅1051≤n,b,a≤2⋅105) — the robot's destination point, the battery capacity and the accumulator capacity, respectively.
The second line of the input contains ?n integers ?1,?2,…,??s1,s2,…,sn (0≤??≤10≤si≤1), where ??si is 11 if the ?i-th segment of distance is exposed to sunlight, and 00 otherwise.
Output
Print one integer — the maximum number of segments the robot can pass if you control him optimally.
贪心
我们在蓄电池没满电的时候遇到1优先充电，然后遇到0优先使用自身的电池，就是个贪心。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define esp 1e-6
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define MIN3(x, y, z) min(min(x, y), z)
const int maxN = 2e5 + 7;
int N, A, B, up, a[maxN];
int main()
{
scanf("%d%d%d", &N, &B, &up); A = up;
for(int i=1; i<=N; i++) scanf("%d", &a[i]);
for(int i=1; i<=N; i++)
{
if(a[i])
{
if(up > A && B)
{
B--;
A++;
}
else if(A == up) A--;
else if(up > A && A) A--;
else { printf("%d\n", i-1); return 0; }
}
else
{
if(A) A--;
else if(B) B--;
else { printf("%d\n", i-1); return 0; }
}
}
printf("%d\n", N);
return 0;
}
E. Two Teams
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
There are ?n students standing in a row. Two coaches are forming two teams — the first coach chooses the first team and the second coach chooses the second team.
The ?i-th student has integer programming skill ??ai. All programming skills are distinct and between 11 and ?n, inclusive.
Firstly, the first coach will choose the student with maximum programming skill among all students not taken into any team, and ?k closest students to the left of him and ?k closest students to the right of him (if there are less than ?k students to the left or to the right, all of them will be chosen). All students that are chosen leave the row and join the first team. Secondly, the second coach will make the same move (but all students chosen by him join the second team). Then again the first coach will make such move, and so on. This repeats until the row becomes empty (i. e. the process ends when each student becomes to some team).
Your problem is to determine which students will be taken into the first team and which students will be taken into the second team.
Input
The first line of the input contains two integers ?n and ?k (1≤?≤?≤2⋅1051≤k≤n≤2⋅105) — the number of students and the value determining the range of chosen students during each move, respectively.
The second line of the input contains ?n integers ?1,?2,…,??a1,a2,…,an (1≤??≤?1≤ai≤n), where ??ai is the programming skill of the ?i-th student. It is guaranteed that all programming skills are distinct.
Output
Print a string of ?n characters; ?i-th character should be 1 if ?i-th student joins the first team, or 2 otherwise.
数据结构+STL
用了双set来做，一个存值，另一个存对应的连续位置，就是要捋清楚地址的继承性。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define esp 1e-6
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 4e5 + 70;
set<int> num, pos;
set<int>::iterator it;
int a[maxN], b[maxN], N, K, ans[maxN];
int main()
{
scanf("%d%d", &N, &K);
for(int i=1; i<=N; i++)
{
scanf("%d", &a[i]);
b[a[i]] = i; //对应值的位置
num.insert(i); //插入值
pos.insert(i); //插入位子
}
int sum = 0, id, team = 2;
while(sum < N)
{
team = team == 1 ? 2 : 1;
it = --num.end();
id = b[*it];
ans[id] = team;
it = pos.find(id);
for(int i=1; i<=K; i++)
{
it = --num.end();
id = b[*it];
it = pos.find(id);
if(it == pos.begin()) break;
if(it == pos.end()) break;
sum++;
it--;
ans[*it] = team;
num.erase(a[*it]);
pos.erase(it);
}
for(int i=1; i<=K; i++)
{
it = --num.end();
id = b[*it];
it = pos.find(id);
if(it == pos.end()) break;
if(it == --pos.end()) break;
it++;
if(it == pos.end()) break;
sum++;
ans[*it] = team;
num.erase(a[*it]);
pos.erase(*it);
}
sum++;
it = --num.end();
id = b[*it];
num.erase(*it);
pos.erase(id);
}
for(int i=1; i<=N; i++) printf("%d", ans[i]);
printf("\n");
return 0;
}
