codeforces每日5题(均1500)-第八天

Cola

题面翻译

有a瓶0.5升，b瓶1升，c瓶2升的可乐，求买n升可乐的方案数

输入 $n$ , $a$ , $b$ , $c$ ( $1<=n<=10000$ , $0<=a,b,c<=5000$ ).

题目描述

To celebrate the opening of the Winter Computer School the organizers decided to buy in $n$ liters of cola.

However, an unexpected difficulty occurred in the shop: it turned out that cola is sold in bottles $0.5$ , $1$ and $2$ liters in volume.

At that, there are exactly $a$ bottles $0.5$ in volume, $b$ one-liter bottles and $c$ of two-liter ones.

The organizers have enough money to buy any amount of cola.

What did cause the heated arguments was how many bottles of every kind to buy, as this question is pivotal for the distribution of cola among the participants (and organizers as well).

Thus, while the organizers are having the argument, discussing different variants of buying cola, the Winter School can’t start.

Your task is to count the number of all the possible ways to buy exactly $n$ liters of cola and persuade the organizers that this number is too large, and if they keep on arguing, then the Winter Computer School will have to be organized in summer.

All the bottles of cola are considered indistinguishable, i.e. two variants of buying are different from each other only if they differ in the number of bottles of at least one kind.

输入格式

The first line contains four integers — $n$ , $a$ , $b$ , $c$ ( $1<=n<=10000$ , $0<=a,b,c<=5000$ ).

输出格式

Print the unique number — the solution to the problem.

If it is impossible to buy exactly $n$ liters of cola, print $0$ .

样例 #1

样例输入 #1

10 5 5 5

样例输出 #1

9

样例 #2

样例输入 #2

3 0 0 2

样例输出 #2

0

#include<bits/stdc++.h>
using namespace std; 
const int N=1e5+10;
typedef long long ll;
int n,a,b,c,s=0;
int main(){
    
	cin>>n>>a>>b>>c;
	for(int i=0;i<=c&&i*2<=n;i++)
	{
    
		int k=n-i*2;
		if(k<=b) s+=min(a/2,k)+1;
		else 
		{
    
			if((k-b)*2<=a)
			s+=min((a-(k-b)*2)/2,b)+1;
		}
	}
	cout<<s;
	return 0;
}

Winner

题面翻译

题目描述：

在 Berland 流行着纸牌游戏 Berlogging，这个游戏的赢家是根据以下规则确定的：

1. 在每一轮中，玩家获得或失去一定数量的分数，在游戏过程中，分数被记录在 名称和得分 行中，其中名字是玩家的名字，得分是在这一轮中获得的分数。得分是负值意味着玩家失去了相应的分数。
2. 如果在比赛结束时只有一名玩家分数最多，他就是获胜者。
3. 如果两名或两名以上的玩家在比赛结束时都有最大的分数 $m$ ，那么其中首先获得至少 $m$ 分的玩家胜利。开始时，每个玩家都是 $0$ 分。

保证在比赛结束时至少有一个玩家的分数为正。

【输入格式】

第一行包含整数 $n$，表示是游戏进行的的回合数。

第 $2\sim n+1$ 行，按照时间顺序输入 名称和得分 行的信息，其中名称是长度不大于 $32$ 的小写字母组成的字符串，分数的绝对值不大于 $1000$。

【输出格式】

输出获胜者的名称。

题目描述

The winner of the card game popular in Berland “Berlogging” is determined according to the following rules.

If at the end of the game there is only one player with the maximum number of points, he is the winner.

The situation becomes more difficult if the number of such players is more than one.

During each round a player gains or loses a particular number of points.

In the course of the game the number of points is registered in the line “name score”, where name is a player’s name, and score is the number of points gained in this round, which is an integer number.

If score is negative, this means that the player has lost in the round.

So, if two or more players have the maximum number of points (say, it equals to $m$ ) at the end of the game, than wins the one of them who scored at least $m$ points first.

Initially each player has 0 points.

It’s guaranteed that at the end of the game at least one player has a positive number of points.

输入格式

The first line contains an integer number $n$ ( $1<=n<=1000$ ), $n$ is the number of rounds played.

Then follow $n$ lines, containing the information about the rounds in “name score” format in chronological order, where name is a string of lower-case Latin letters with the length from 1 to 32, and score is an integer number between -1000 and 1000, inclusive.

输出格式

Print the name of the winner.

样例 #1

样例输入 #1

3
mike 3
andrew 5
mike 2

样例输出 #1

andrew

样例 #2

样例输入 #2

3
andrew 3
andrew 2
mike 5

样例输出 #2

andrew

#include<bits/stdc++.h>
using namespace std; 
const int N=1e5+10;
typedef long long ll;
map<string,int> a,b;
string s[N],da;
int n,mmax=-INT_MAX,aa[N];
int main(){
    
	cin>>n;
	for(int i=1;i<=n;i++){
    
		cin>>s[i]>>aa[i];
		a[s[i]]+=aa[i];
	}
	for(int i=1;i<=n;i++){
    
		mmax=max(mmax,a[s[i]]);
	}
	for(int i=1;i<=n;i++){
    
		b[s[i]]+=aa[i];
		if(b[s[i]]>=mmax&&a[s[i]]==mmax){
    
			da=s[i];
			break;
		}
	}
	cout<<da<<endl;
	return 0;
}

Traffic Lights

题面翻译

题目描述

一辆汽车以$v$ 米每秒的速度由A点驶向B点。这个动作发生在X轴上。
在距离A点$d$ 米的地方有一个红绿灯。
从0时刻开始，在第一个$g$ 秒里绿灯是亮的，然后在接下来的$r$ 秒内红灯亮起，在接下来$g$ 秒，绿灯亮起，如此反复。

这辆车可以瞬间从$0$ 加速到$v$ ，反之亦然，也可以从$v$ 瞬间减速至$0$ 。
车在绿灯时可以立刻通过。
如果车在红灯亮起的那一刻到达红绿灯处，那么车不能够通过。但如果在绿灯亮起时到达，则可以通过。车从0时刻离开A点。

在不违反交通规则的前提下，车从A点移动到B点最少需要多长时间？

输入格式：

第一行包含整数$l,d,v,g,r$ （$1\le l,d,v,g,r\le 1000,d<l$ ）— A与B间的距离（米），A与红绿灯的距离，车的速度，绿灯的持续时间和红灯的持续时间。

输出格式：

输出一个数 — 车从A到B所需要的最少时间。你的输出需要和标准输出相差不超过$10^{-6}$

题目描述

A car moves from point A to point B at speed $v$ meters per second.

The action takes place on the X-axis.

At the distance $d$ meters from A there are traffic lights.

Starting from time 0, for the first $g$ seconds the green light is on, then for the following $r$ seconds the red light is on, then again the green light is on for the $g$ seconds, and so on.

The car can be instantly accelerated from $0$ to $v$ and vice versa, can instantly slow down from the $v$ to $0$ .

Consider that it passes the traffic lights at the green light instantly.

If the car approaches the traffic lights at the moment when the red light has just turned on, it doesn’t have time to pass it.

But if it approaches the traffic lights at the moment when the green light has just turned on, it can move.

The car leaves point A at the time 0.

What is the minimum time for the car to get from point A to point B without breaking the traffic rules?

输入格式

The first line contains integers $l$ , $d$ , $v$ , $g$ , $r$ ( $1<=l,d,v,g,r<=1000,d<l$ ) — the distance between A and B (in meters), the distance from A to the traffic lights, car’s speed, the duration of green light and the duration of red light.

输出格式

Output a single number — the minimum time that the car needs to get from point A to point B.

Your output must have relative or absolute error less than $10^{-6}$ .

样例 #1

样例输入 #1

2 1 3 4 5

样例输出 #1

0.66666667

样例 #2

样例输入 #2

5 4 3 1 1

样例输出 #2

2.33333333

#include<bits/stdc++.h>
using namespace std; 
const int N=1e5+10;
typedef long long ll;
map<string,int> a,b;
string s[N],da;
double l,d,v,g,r,t;
int main(){
    
	cin>>l>>d>>v>>g>>r;
	t=d/v;
	while(t>g+r) t-=g+r;
	if(t<g){
    
		printf("%.8lf\n",l/v);
	}
	else{
    
		printf("%.8lf\n",l/v+(g+r-t));
	}
	return 0;
}

Sum

题面翻译

题目描述：
Vasya终于学会了进位制，但他经常忘记写算式的基数。

有一次，他看到他的笔记本上写着a+b=？，但是没有写明基数。

现在Vasya认为算式的基数为p。

他知道算式在不同的基数下，会有不同的结果，甚至在有些基数下是没有意义的。

算式78+87的值在十六进制下为FF，在十五进制下为110，十进制下为165，九进制下为176，更小的基数下就没有意义了。

现在，Vasya想要知道算式结果的最大长度。

我们定义数字的长度为数字的字符个数，在不同的进制下，同一个数字有不同的数字长度。

输入输出格式

输入格式：

共一行，包含两个数a，b。

输出格式：

共一行，输出算式的最大长度。

题目描述

Vasya studies positional numeral systems.

Unfortunately, he often forgets to write the base of notation in which the expression is written.

Once he saw a note in his notebook saying $a+b=?$ , and that the base of the positional notation wasn’t written anywhere.

Now Vasya has to choose a base $p$ and regard the expression as written in the base $p$ positional notation.

Vasya understood that he can get different results with different bases, and some bases are even invalid.

For example, expression $78+87$ in the base 16 positional notation is equal to $F{F}_{16}$ , in the base 15 positional notation it is equal to $110_{15}$ , in the base 10 one — to $165_{10}$ , in the base 9 one — to $176_9$ , and in the base 8 or lesser-based positional notations the expression is invalid as all the numbers should be strictly less than the positional notation base.

Vasya got interested in what is the length of the longest possible expression value.

Help him to find this length.

The length of a number should be understood as the number of numeric characters in it.

For example, the length of the longest answer for $78+87=?$ is 3.

It is calculated like that in the base 15 ( $110_{15}$ ), base 10 ( $165_{10}$ ), base 9 ( $176_9$ ) positional notations, for example, and in some other ones.

输入格式

The first letter contains two space-separated numbers $a$ and $b$ ( $1<=a,b<=1000$ ) which represent the given summands.

输出格式

Print a single number — the length of the longest answer.

样例 #1

样例输入 #1

78 87

样例输出 #1

3

样例 #2

样例输入 #2

1 1

样例输出 #2

2

#include<bits/stdc++.h>
using namespace std; 
const int N=1e5+10;
typedef long long ll;
int a,b,aa[N],aaa=0,bb[N],bbb=0,mmax=0,cc[N];
int main(){
    
	cin>>a>>b;
	while(a){
    
		aa[++aaa]=a%10;
		a/=10;
		mmax=max(mmax,aa[aaa]);
	}
	while(b){
    
		bb[++bbb]=b%10;
		b/=10;
		mmax=max(mmax,bb[bbb]);
	}
	int s=max(aaa,bbb);
	for(int i=1;i<=s;i++){
    
		cc[i]+=aa[i]+bb[i];
		if(cc[i]>mmax) cc[i+1]++;
	}
	if(cc[s+1]) s++;
	cout<<s<<endl;
	return 0;
}

Permutations

题面翻译

题目描述
“排列”是指一个长度为n的序列，且其中1到n的每个数刚好出现一次。例如，(1) (4,3,5,1,2) (3,2,1)都是排列，而(1,1) (4,3,1) (2,3,4)则不是。

假设某人拿了几个排列（长度不一定相同），把它们连在一起写成了一个数列，并将这个数列打乱顺序。

你的任务是将这个数列重新组成原来的几个排列（如果可能的话）。

输入输出格式
输入格式：
第1行是一个整数n（1<=n<=10^{5）。下一行是这个打乱后的n个整数，用一个空格隔开。这个数列中的数在1到10}5的范围内。

输出格式：
如果这个数列能被分成若干的排列，且数列中的每个数恰好属于一个排列，请在第1行输出排列的个数。第2行有n个数，对应着给定数列的n个数：如果第i个元素属于第1个排列，输出的这一行的第i个数就是1，如果它属于第2个排列，那么它对应的输出中的数就是2，等等。这些排列的顺序无关紧要。

如果有多种答案，输出其中任意一个。如果没有答案，在第1行输出-1.

说明
在第1个样例中数组被分成了三个排列：(2,1) (3,2,1,4,5) (1,2)。第1个排列由原数列的第2和4个数组成，第2个排列由第3、5、6、7、9个元素组成，第3个排列由第1和8个元素组成。显然，还有另外几种分组的方式。

题目描述

A permutation is a sequence of integers from $1$ to $n$ of length $n$ containing each number exactly once.

For example, $(1)$ , $(4,3,5,1,2)$ , $(3,2,1)$ are permutations, and $(1,1)$ , $(4,3,1)$ , $(2,3,4)$ are not.

There are many tasks on permutations.

Today you are going to solve one of them.

Let’s imagine that somebody took several permutations (perhaps, with a different number of elements), wrote them down consecutively as one array and then shuffled the resulting array.

The task is to restore the initial permutations if it is possible.

输入格式

The first line contains an integer $n$ ( $1<=n<=10^5$ ).

The next line contains the mixed array of $n$ integers, divided with a single space.

The numbers in the array are from $1$ to $10^5$ .

输出格式

If this array can be split into several permutations so that every element of the array belongs to exactly one permutation, print in the first line the number of permutations.

The second line should contain $n$ numbers, corresponding to the elements of the given array.

If the $i$ -th element belongs to the first permutation, the $i$ -th number should be $1$ , if it belongs to the second one, then its number should be $2$ and so on.

The order of the permutations’ numbering is free.

If several solutions are possible, print any one of them.

If there’s no solution, print in the first line $-1$ .

样例 #1

样例输入 #1

9
1 2 3 1 2 1 4 2 5

样例输出 #1

3
3 1 2 1 2 2 2 3 2

样例 #2

样例输入 #2

4
4 3 2 1

样例输出 #2

1
1 1 1 1

样例 #3

样例输入 #3

4
1 2 2 3

样例输出 #3

-1

提示

In the first sample test the array is split into three permutations: $(2,1)$ , $(3,2,1,4,5)$ , $(1,2)$ .

The first permutation is formed by the second and the fourth elements of the array, the second one — by the third, the fifth, the sixth, the seventh and the ninth elements, the third one — by the first and the eigth elements.

Clearly, there are other splitting variants possible.

#include<bits/stdc++.h>
using namespace std; 
const int N=1e6+10;
typedef long long ll;
int n,mmax=0,a[N],tong[N],s[N];
int main(){
    
	cin>>n;
	for(int i=1;i<=n;i++){
    
		scanf("%d",&a[i]);
		tong[a[i]]++;
		mmax=max(mmax,a[i]);
	}
	for(int i=2;i<=mmax;i++){
    
		if(tong[i]>tong[i-1]){
    
			puts("-1");
			return 0;
		}
	}
	cout<<tong[1]<<endl;
	for(int i=1;i<=n;i++){
    
		s[a[i]]++;
		cout<<s[a[i]]<<" ";
	}
	return 0;
}