Alternating Current

题面翻译

题目描述

两条电线分别插入了正确的位置，但是缠绕在一起，如下图所示。

电线不能被剪断或断开，插入的设备也不能被移动，请问是否可以在这种情况下解开电线？

为了更好地理解题意，请阅读样例的解释。

输入格式

输入一行包含字符为 + 和 - 的字符序列$(1\le n\le 1000000)$。

第 $i$ 个位置上如果是 +，说明此位置正极在负极上方；如果是 -，说明此位置负极在正极上方。

输出格式

输出一行，若能解开则输出 Yes，否则则输出 No。

题目描述

Mad scientist Mike has just finished constructing a new device to search for extraterrestrial intelligence!

He was in such a hurry to launch it for the first time that he plugged in the power wires without giving it a proper glance and started experimenting right away.

After a while Mike observed that the wires ended up entangled and now have to be untangled again.

The device is powered by two wires “plus” and “minus”.

The wires run along the floor from the wall (on the left) to the device (on the right).

Both the wall and the device have two contacts in them on the same level, into which the wires are plugged in some order.

The wires are considered entangled if there are one or more places where one wire runs above the other one.

For example, the picture below has four such places (top view):

Mike knows the sequence in which the wires run above each other.

Mike also noticed that on the left side, the “plus” wire is always plugged into the top contact (as seen on the picture).

He would like to untangle the wires without unplugging them and without moving the device.

Determine if it is possible to do that.

A wire can be freely moved and stretched on the floor, but cannot be cut.

To understand the problem better please read the notes to the test samples.

输入格式

The single line of the input contains a sequence of characters “+” and “-” of length $n$ ( $1<=n<=100000$ ).

The $i$ -th ( $1<=i<=n$ ) position of the sequence contains the character “+”, if on the $i$ -th step from the wall the “plus” wire runs above the “minus” wire, and the character “-” otherwise.

输出格式

Print either “Yes” (without the quotes) if the wires can be untangled or “No” (without the quotes) if the wires cannot be untangled.

样例 #1

样例输入 #1

-++-
1

样例输出 #1

Yes
1

样例 #2

样例输入 #2

+-
1

样例输出 #2

No
1

样例 #3

样例输入 #3

++
1

样例输出 #3

Yes
1

样例 #4

样例输入 #4

-
1

样例输出 #4

No
1

提示

The first testcase corresponds to the picture in the statement.

To untangle the wires, one can first move the “plus” wire lower, thus eliminating the two crosses in the middle, and then draw it under the “minus” wire, eliminating also the remaining two crosses.

In the second testcase the “plus” wire makes one full revolution around the “minus” wire.

Thus the wires cannot be untangled:

In the third testcase the “plus” wire simply runs above the “minus” wire twice in sequence.

The wires can be untangled by lifting “plus” and moving it higher:

In the fourth testcase the “minus” wire runs above the “plus” wire once.

The wires cannot be untangled without moving the device itself:

#include
using namespace std;
const int N=1e6+10;
typedef long long ll;
string s;
stack<char> a;
char b;
int main(){
	cin>>s;
	for(int i=0;i<s.size();i++){
		if(a.size()) b=a.top();
		a.push(s[i]);
		if(a.size()>=2&&b==s[i]) a.pop(),a.pop(); 
	}
	if(!a.size()) puts("Yes");
	else puts("No");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Vasya and Basketball

题面翻译

题意简述

Vasya 记录了一场篮球赛中两支队伍每次命中的投篮离篮筐的距离。他知道每一次成功的投篮可以得到 $2$ 分或 $3$ 分

如果一次命中的投篮离篮筐不超过 $d(d\ge 0)$ 米则得 $2$ 分，否则得 $3$ 分

Vasya 可以指定一个 $d$，同时他希望第一支队伍的分数 $a$ 减去第二支队伍的分数 $b$ 最大。

请你帮他求出这个 $d$。

输入格式

第一行一个正整数 $n(1\le n\le 2\cdot 10^5)$，表示第一支队伍的命中数。

接下来一行 $n$ 个正整数 $a_1,a_2,\cdots ,a_n(1\le a_i\le 2\cdot 10^9)$，表示每一次命中离篮筐的距离。

第一行一个正整数 $m(1\le m\le 2\cdot 10^5)$，表示第二支队伍的命中数。

接下来一行 $m$ 个正整数 $b_1,b_2,\cdots ,b_n(1\le b_i\le 2\cdot 10^9)$，表示每一次命中离篮筐的距离。

输出格式

输出一行两个整数 $a$，$b$，分别表示两队的分数，中间用符号 : 分隔。您应该最大化 $a-b$，如果有相同的 $a-b$，应该最大化 $a$。

翻译贡献者 U108949

题目描述

Vasya follows a basketball game and marks the distances from which each team makes a throw.

He knows that each successful throw has value of either 2 or 3 points.

A throw is worth 2 points if the distance it was made from doesn’t exceed some value of $d$ meters, and a throw is worth 3 points if the distance is larger than $d$ meters, where $d$ is some non-negative integer.

Vasya would like the advantage of the points scored by the first team (the points of the first team minus the points of the second team) to be maximum.

For that he can mentally choose the value of $d$ .

Help him to do that.

输入格式

Vasya follows a basketball game and marks the distances from which each team makes a throw.

He knows that each successful throw has value of either 2 or 3 points.

A throw is worth 2 points if the distance it was made from doesn’t exceed some value of $d$ meters, and a throw is worth 3 points if the distance is larger than $d$ meters, where $d$ is some non-negative integer.

Vasya would like the advantage of the points scored by the first team (the points of the first team minus the points of the second team) to be maximum.

For that he can mentally choose the value of $d$ .

Help him to do that.

输出格式

Print two numbers in the format a:b — the score that is possible considering the problem conditions where the result of subtraction $a-b$ is maximum.

If there are several such scores, find the one in which number $a$ is maximum.

样例 #1

样例输入 #1

3
1 2 3
2
5 6
1
2
3
4

样例输出 #1

9:6
1

样例 #2

样例输入 #2

5
6 7 8 9 10
5
1 2 3 4 5
1
2
3
4

样例输出 #2

15:10
1

#include
using namespace std;
const int N=1e6+10;
typedef long long ll;
ll n,a[N],m,b[N],ka,kb,ansa,ansb;
int main(){
	cin>>n;
	for(ll i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	sort(a+1,a+1+n);
	cin>>m;
	for(int i=1;i<=m;i++){
		scanf("%lld",&b[i]);
	}
	sort(b+1,b+1+m);
	ka=ansa=n*2;
	kb=ansb=m*2;
	for(int i=n,j=m;i>0;i--){
		ka++;
		for(;j>0&&b[j]>=a[i];j--) kb++;
		if(ansa-ansb<=ka-kb){
			ansa=ka,ansb=kb;
		}
	}
	cout<<ansa<<":"<<ansb;
    return 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

Balancer

题面翻译

题目描述

佩蒂娅有 $k$ 根火柴，她要把这些火柴放在 $n$ 个火柴盒里

佩蒂娅希望所有盒子里的火柴数量相同，也就是每个火柴盒里面要放 $\frac{k}{n}$ 根火柴

她可以一步把 $1$ 根火柴从这个盒子里移到相邻的盒子里

问他需要多少次操作才能使得每个盒子都有 $\frac{k}{n}$ 根火柴。

输入格式

共两行，第一行只有一个整数 $n$，第二行包含 $n$ 个正整数，分别表示一开始每个火柴盒里面包含的火柴数

输出格式

只有一个整数，表示至少要操作的次数。

题目描述

Petya has $k$ matches, placed in $n$ matchboxes lying in a line from left to right.

We know that $k$ is divisible by $n$ .

Petya wants all boxes to have the same number of matches inside.

For that, he can move a match from its box to the adjacent one in one move.

How many such moves does he need to achieve the desired configuration?

输入格式

The first line contains integer $n$ ( $1<=n<=50000$ ).

The second line contains $n$ non-negative numbers that do not exceed $10^9$ , the $i$ -th written number is the number of matches in the $i$ -th matchbox.

It is guaranteed that the total number of matches is divisible by $n$ .

输出格式

Print the total minimum number of moves.

样例 #1

样例输入 #1

6
1 6 2 5 3 7
1
2

样例输出 #1

12
1

#include
using namespace std;
const int N=1e6+10;
typedef long long ll;
ll n,a[N],k=0,ans=0;
int main(){
	cin>>n;
	for(ll i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		k+=a[i];
	}
	k/=n;
	for(ll i=1;i<=n;i++){
		a[i+1]+=(a[i]-k);
		ans+=abs(a[i]-k);
	}
	cout<<ans<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Vitaly and Strings

题面翻译

维塔利是一个勤奋的学生，在大学阶段，他从来没有逃过一堂课。他总是按时做作业，并顺利通过考试。

在上一节课，老师给了他两个字符串s和t。

这两个字符串的长度相同，由小写英文字母组成，字符串s的字典序比串t小。

维塔利想知道是否有这样的字符串：字典序比字符串s大，同时字典序小于串t。

此字符串也应包括小写英文字母和相同的长度。

让我们帮维塔利解决这个简单的问题！

第一行包含字符串s（1≤|s| ≤100），由小写英文字母组成。这里，|s| 表示字符串s的长度。

第二行包含字符串t（|t|=|s| ），由小写英文字母组成。

保证字符串s和t的长度是相同的，字符串s字典顺序小于字符串t。

如果满足要求的字符串不存在，则输出No such string。

如果这样的字符串存在，就输出任何一个满足条件的字符串。( 也只能由小写英文字母a-z组成）

Translated by @馒头精

题目描述

Vitaly is a diligent student who never missed a lesson in his five years of studying in the university.

He always does his homework on time and passes his exams in time.

During the last lesson the teacher has provided two strings $s$ and $t$ to Vitaly.

The strings have the same length, they consist of lowercase English letters, string $s$ is lexicographically smaller than string $t$ .

Vitaly wondered if there is such string that is lexicographically larger than string $s$ and at the same is lexicographically smaller than string $t$ .

This string should also consist of lowercase English letters and have the length equal to the lengths of strings $s$ and $t$ .

Let’s help Vitaly solve this easy problem!

输入格式

The first line contains string $s$ ( $1<=|s|<=100$ ), consisting of lowercase English letters.

Here, $|s|$ denotes the length of the string.

The second line contains string $t$ ( $|t|=|s|$ ), consisting of lowercase English letters.

It is guaranteed that the lengths of strings $s$ and $t$ are the same and string $s$ is lexicographically less than string $t$ .

输出格式

If the string that meets the given requirements doesn’t exist, print a single string “No such string” (without the quotes).

If such string exists, print it. If there are multiple valid strings, you may print any of them.

样例 #1

样例输入 #1

a
c
1
2

样例输出 #1

b
1

样例 #2

样例输入 #2

aaa
zzz
1
2

样例输出 #2

kkk
1

样例 #3

样例输入 #3

abcdefg
abcdefh
1
2

样例输出 #3

No such string
1

提示

String $s=s_1{s}_2...s_n$ is said to be lexicographically smaller than $t=t_1{t}_2...t_n$ , if there exists such $i$ , that $s_1=t_1,s_2=t_2,...s_{i-1}=t_{i-1},s_i<t_i$ .

#include
using namespace std;
const int N=1e6+10;
typedef long long ll;
string s,t;
int l;
int main(){
	cin>>s>>t;
	l=s.size()-1;
	s[l]++;
	if(s>=t){
		puts("No such string");
		return 0;
	}
	while(s[l]=='{') s[l]='a',s[--l]++;
	if(s>=t){
		puts("No such string");
		return 0;
	}
	cout<<s<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Booking System

题面翻译

一家餐厅有k张桌子,每一张有一个最大的容纳人数.这家餐厅收到了n份预定,每份预定有c,p,表示这一餐要来的人数以及要消费的金额.

对于每一份预定,这些人必须要坐在同一桌,人数不能超过桌子最大的容纳人数.

该餐厅可以拒绝一些预约.求餐厅最大盈利的估计值,以及它将哪一份预约的客户安排到哪一桌(输入顺序的编号).

感谢@Fuko_Ibuki 提供的翻译

题目描述

Innovation technologies are on a victorious march around the planet.

They integrate into all spheres of human activity!

A restaurant called “Dijkstra’s Place” has started thinking about optimizing the booking system.

There are $n$ booking requests received by now.

Each request is characterized by two numbers: $c_i$ and $p_i$ — the size of the group of visitors who will come via this request and the total sum of money they will spend in the restaurant, correspondingly.

We know that for each request, all $c_i$ people want to sit at the same table and are going to spend the whole evening in the restaurant, from the opening moment at 18:00 to the closing moment.

Unfortunately, there only are $k$ tables in the restaurant.

For each table, we know $r_i$ — the maximum number of people who can sit at it.

A table can have only people from the same group sitting at it.

If you cannot find a large enough table for the whole group, then all visitors leave and naturally, pay nothing.

Your task is: given the tables and the requests, decide which requests to accept and which requests to decline so that the money paid by the happy and full visitors was maximum.

输入格式

The first line of the input contains integer $n$ ( $1<=n<=1000$ ) — the number of requests from visitors.

Then $n$ lines follow.

Each line contains two integers: $c_i,p_i$ $(1<=c_i,p_i<=1000$ ) — the size of the group of visitors who will come by the $i$ -th request and the total sum of money they will pay when they visit the restaurant, correspondingly.

The next line contains integer $k$ ( $1<=k<=1000$ ) — the number of tables in the restaurant.

The last line contains $k$ space-separated integers: $r_1,r_2,...,r_k$ $(1<=r_i<=1000)$ — the maximum number of people that can sit at each table.

输出格式

In the first line print two integers: $m,s$ — the number of accepted requests and the total money you get from these requests, correspondingly.

Then print $m$ lines — each line must contain two space-separated integers: the number of the accepted request and the number of the table to seat people who come via this request.

The requests and the tables are consecutively numbered starting from $1$ in the order in which they are given in the input.

If there are multiple optimal answers, print any of them.

样例 #1

样例输入 #1

3
10 50
2 100
5 30
3
4 6 9
1
2
3
4
5
6

样例输出 #1

2 130
2 1
3 2
1
2
3

#include
using namespace std;
const int N=1e6+10;
typedef long long ll;
int n,k,ans1[N],ans2[N],ans=0,kk=0;
bool ok[N];
struct stu1{
	int c,p,sign;
}s[N];
struct stu2{
	int shu,sign;
}ss[N];
bool cmp1(stu1 x,stu1 y){return x.p>y.p;}
bool cmp2(stu2 x,stu2 y){return x.shu<y.shu;}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d%d",&s[i].c,&s[i].p);
		s[i].sign=i;
	}
	sort(s+1,s+1+n,cmp1);
	cin>>k;
	for(int i=1;i<=k;i++){
		scanf("%d",&ss[i].shu);
		ss[i].sign=i;
	}
	sort(ss+1,ss+1+k,cmp2);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=k;j++){
			if(!ok[j]&&s[i].c<=ss[j].shu){
				ok[j]=1;
				ans+=s[i].p;
				kk++;
				ans1[kk]=s[i].sign;
				ans2[kk]=ss[j].sign;
				break;
			}
		}
	}
	cout<<kk<<" "<<ans<<endl;
	for(int i=1;i<=kk;i++){
		printf("%d %d\n",ans1[i],ans2[i]);
	}
    return 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