CF--训练交流(一)

发表于 更新于 分类于 阅读次数：
本文字数： 12k 阅读时长 ≈ 11 分钟

A-Watermelon CodeForces

One hot summer day Pete and his friend Billy decided to buy a watermelon. They chose the biggest and the ripest one, in their opinion. After that the watermelon was weighed, and the scales showed w kilos. They rushed home, dying of thirst, and decided to divide the berry, however they faced a hard problem.

Pete and Billy are great fans of even numbers, that’s why they want to divide the watermelon in such a way that each of the two parts weighs even number of kilos, at the same time it is not obligatory that the parts are equal. The boys are extremely tired and want to start their meal as soon as possible, that’s why you should help them and find out, if they can divide the watermelon in the way they want. For sure, each of them should get a part of positive weight.

输入:

The first (and the only) input line contains integer number w (1 ≤ w ≤ 100) — the weight of the watermelon bought by the boys.

输出:

样例输入:

1
8

样例输出:

1
YES

NOTE：For example, the boys can divide the watermelon into two parts of 2 and 6 kilos respectively (another variant — two parts of 4 and 4 kilos).

大体意思就是输入一个数 看它能不能拆分成两个偶数 不要求两个偶数大小相同.

代码如下:

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
int main()
{
	long long n;
	scanf("%lld",&n);
	if(n%2==0&&n>2)	//有坑 去2的情况 2是偶数却只能拆分成两个1
		printf("YES");
	else
		printf("NO");		
	return 0;
}

B - Theatre Square

Theatre Square in the capital city of Berland has a rectangular shape with the size n × m meters. On the occasion of the city’s anniversary, a decision was taken to pave the Square with square granite flagstones. Each flagstone is of the size a × a.

What is the least number of flagstones needed to pave the Square? It’s allowed to cover the surface larger than the Theatre Square, but the Square has to be covered. It’s not allowed to break the flagstones. The sides of flagstones should be parallel to the sides of the Square.

输入:

The input contains three positive integer numbers in the first line: n,  m and a (1 ≤  n, m, a ≤ 109).

输出:

Write the needed number of flagstones.

样例输入:

1
6 6 4

样例输出:

1
4

大体意思就是给你一个n乘m的面积 再给你一个a乘a的方形地板 求最少需要多少块才可以完全覆盖

思路:求出长需要的块数 求出宽需要的块数 相乘即可

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
int main()
{
	long long n,m,a;
	scanf("%lld%lld%lld",&n,&m,&a);
	long long i=n/a;	
	long long j=m/a;
	if(n%a!=0)	//保证长度够长
		i++;
	if(m%a!=0)
		j++;
	printf("%lld",i*j);
	return 0;
}

C - IQ test

Bob is preparing to pass IQ test. The most frequent task in this test is to find out which one of the given n numbers differs from the others. Bob observed that one number usually differs from the others in evenness. Help Bob — to check his answers, he needs a program that among the given n numbers finds one that is different in evenness.

输入:

The first line contains integer n (3 ≤ n ≤ 100) — amount of numbers in the task. The second line contains n space-separated natural numbers, not exceeding 100. It is guaranteed, that exactly one of these numbers differs from the others in evenness.

输出:

Output index of number that differs from the others in evenness. Numbers are numbered from 1 in the input order.

样例输入:

1
2
5
2 4 7 8 10

样例输出:

1
3

样例输入:

1
2
4
1 2 1 1

样例输出:

1
2

大体意思就是输入一个数 仅包含一个偶数或者奇数 求出该数的位置

优化后的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
int a[101];
int main()
{
	int n;
	scanf("%d",&n);
	scanf("%d%d%d",&a[0],&a[1],&a[2]);
	int o=(a[0]%2+a[1]%2+a[2]%2)/2;
	for(int i=0;i<n;i++)
	{
		if(i>2)
			scanf("%d",&a[i]);
		if((a[i]%2)!=o)
			printf("%d",i+1); 
	} 
	return 0;
}

D - Vanya and Lanterns

Vanya walks late at night along a straight street of length l, lit by n lanterns. Consider the coordinate system with the beginning of the street corresponding to the point 0, and its end corresponding to the point l. Then the i-th lantern is at the point ai. The lantern lights all points of the street that are at the distance of at most d from it, where d is some positive number, common for all lanterns.

Vanya wonders: what is the minimum light radius d should the lanterns have to light the whole street?

输入:

The first line contains two integers n, l (1 ≤ n ≤ 1000, 1 ≤ l ≤ 109) — the number of lanterns and the length of the street respectively.

The next line contains n integers ai (0 ≤ ai ≤ l). Multiple lanterns can be located at the same point. The lanterns may be located at the ends of the street.

输出:

样例输入:

1
2
7 15
15 5 3 7 9 14 0

样例输出:

1
2.5000000000

样例输入:

1
2
2 5
2 5

样例输出:

1
2.0000000000

Note:Consider the second sample. At d = 2 the first lantern will light the segment [0, 4] of the street, and the second lantern will light segment [3, 5]. Thus, the whole street will be lit.

大体意思就是给你一段道路的长度，每个路灯所在位置，求路灯所至少要照亮的范围，才可保证所有路灯能照亮这段道路

注意:路灯的第一个位置或者最后一个位置可能不在道路两边.

我的代码如下:

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
#include <bits/stdc++.h>
using namespace std;
int main()
{	
	long long a[1010];
	int n;
	long long l;
	double d=0;
	scanf("%d%lld",&n,&l);
	for(int i=0;i<n;i++)
		scanf("%lld",&a[i]);		
	sort(a,a+n);
	if(a[0]!=0)
		d=a[0];
	for(int i=1;i<n;i++)
	{
		double temp=(a[i]-a[i-1])/2.0;
		if(temp>d)
			d=temp;
	}
	if(a[n-1]!=l)
	{
		double temp=l-a[n-1];
		if(temp>d)
			d=temp;
	}
	printf("%.10f",d);
	return  0;
}

优化后的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
int a[110];
int main()
{
	int n,l;
	scanf("%d%d",&n,&l);
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	sort(a,a+n);
	double m=max(a[0],l-a[n-1]);
	for(int i=1;i<n;i++)
		m=max(m,(a[i]-a[i-1])/2.0);
	printf("%.10f",m);
	return 0;
}

E - Registration system

A new e-mail service “Berlandesk” is going to be opened in Berland in the near future. The site administration wants to launch their project as soon as possible, that’s why they ask you to help. You’re suggested to implement the prototype of site registration system. The system should work on the following principle.

Each time a new user wants to register, he sends to the system a request with his name. If such a name does not exist in the system database, it is inserted into the database, and the user gets the response OK, confirming the successful registration. If the name already exists in the system database, the system makes up a new user name, sends it to the user as a prompt and also inserts the prompt into the database. The new name is formed by the following rule. Numbers, starting with 1, are appended one after another to name (name1, name2, …), among these numbers the least i is found so that namei does not yet exist in the database.

输入:

The first line contains number n (1 ≤ n ≤ 105). The following n lines contain the requests to the system. Each request is a non-empty line, and consists of not more than 32 characters, which are all lowercase Latin letters.

输出:

样例输入:

1
2
3
4
5
4
abacaba
acaba
abacaba
acab

样例输出:

1
2
3
4
OK
OK
abacaba1
OK

样例输入:

1
2
3
4
5
6
7
6
first
first
second
second
third
third

样例输出:

1
2
3
4
5
6
OK
first1
OK
second1
OK
third1

大体意思就是输入一个字符串 如果是第一次输入 直接输出该字符串 否则的话 将该字符串重命名输出 即在字符串后面加上序号 从1开始

思路:用结构体解题 存字符串和出现的次数

我的代码如下:

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
#include <bits/stdc++.h>
using namespace std;
struct p
{
	char n[35];
	int count=0;
}pp[10010];
int main()
{
	int n;
	char m[35];
	scanf("%d",&n);
	int c=1; 
	for(int i=0;i<n;i++)
	{
		memset(m,0,35);
		scanf("%s",m);
		int j=0;
		for(j=0;j<c;j++)
		{
			if(strcmp(m,pp[j].n)==0)
			{
				pp[j].count++;
				printf("%s%d\n",m,pp[j].count);
				break; 
			}	
		}
		if(j==c)
		{
			strcpy(pp[c].n,m);
			printf("OK\n");
			c++;
		}
	}
	return 0;
}

优化的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	scanf("%d",&n);
	map<string,int> m;
	string a;
	for(int i=0;i<n;i++)
	{
		cin>>a;
		if(m[a]==0)
			printf("OK\n");
		else
			cout<<a<<m[a]<<endl;		
		m[a]++;
	}
	return 0;
}

F - Cut Ribbon

Polycarpus has a ribbon, its length is n. He wants to cut the ribbon in a way that fulfils the following two conditions:

After the cutting each ribbon piece should have length a, b or c.

After the cutting the number of ribbon pieces should be maximum.

Help Polycarpus and find the number of ribbon pieces after the required cutting.

输入:

The first line contains four space-separated integers n, a, b and c (1 ≤ n, a, b, c ≤ 4000) — the length of the original ribbon and the acceptable lengths of the ribbon pieces after the cutting, correspondingly. The numbers a, b and c can coincide.

输出:

样例输入:

1
5 5 3 2

样例输出:

1
2

样例输入:

1
7 5 5 2

样例输出:

1
2

大体意思就是给你一个长色带 给出三个切割长度 求最多可以切割成几段

代码如下:

1
暂无代码

G - T-primes

We know that prime numbers are positive integers that have exactly two distinct positive divisors. Similarly, we’ll call a positive integer t Т-prime, if t has exactly three distinct positive divisors.

You are given an array of n positive integers. For each of them determine whether it is Т-prime or not..

输入:

The first line contains a single positive integer, n (1 ≤ n ≤ 105), showing how many numbers are in the array. The next line contains n space-separated integers xi (1 ≤ xi ≤ 1012).

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is advised to use the cin, cout streams or the %I64d specifier.

输出:

样例输入:

1
2
3
4 5 6

样例输出:

1
2
3
YES
NO
NO

大体意思就是给你一堆数 然后求出这些数中因子为三个的数

代码如下:

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
#include <bits/stdc++.h>
using namespace std;
const int M=1e6+10;
bool a[M]={0};
void isprime()		//判断素数 进行预处理打表 直接打表会TLE
{
	for(int i=2;i<M;i++)
	{
		if(a[i]==false)
			for(int j=2*i;j<M;j=j+i)
				a[j]=true;	
	}		
} 
int main()
{
	int n;
	scanf("%d",&n);
	isprime();
	for(int i=0;i<n;i++)
	{
		long long x,sx;
		scanf("%I64d",&x);	//注意该处输入I64d 有些编译器不支持lld
		sx=sqrt(x);
		if(sx>1&&sx*sx==x&&a[sx]==false)//如果该数的平方根为素数 并且不为1的话 该数符合条件
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}

H - Cheap Travel

Ann has recently started commuting by subway. We know that a one ride subway ticket costs a rubles. Besides, Ann found out that she can buy a special ticket for m rides (she can buy it several times). It costs b rubles. Ann did the math; she will need to use subway n times. Help Ann, tell her what is the minimum sum of money she will have to spend to make n rides?

输入:

The single line contains four space-separated integers n, m, a, b (1 ≤ n, m, a, b ≤ 1000) — the number of rides Ann has planned, the number of rides covered by the m ride ticket, the price of a one ride ticket and the price of an m ride ticket.

输出:

样例输入:

1
6 2 1 2

样例输出:

1
6

样例输入:

1
5 2 2 3

样例输出:

1
8

大体意思就是给你一段路程 有每公里的票p 和每m公里的票价mp，求出经过该段路程所需要的费用最小为多少.

注意：该题有坑 mp不一定小于m乘p 如果mp小的话 注意最后的余数乘p和mp比较

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n,m,p,mp;
	scanf("%d%d%d%d",&n,&m,&p,&mp);
	long long price=0;
	if(m*p<mp)
		price=n*p;
	else
	{
		int k=n/m;
		if((n%m)*p<mp)
			price=k*mp+(n-k*m)*p;
		else
			price=k*mp+mp;
	}
	printf("%lld",price);
	return 0;
}
小礼物走一个哟
0%