Educational Codeforces Round 112 (Rated for Div. 2)A,B,C题解(cf1555a-1555c)_edu round 112

Educational Codeforces Round 112 (Rated for Div. 2)A,B,C题解

A.PizzaForces

A. PizzaForces
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
PizzaForces is Petya’s favorite pizzeria. PizzaForces makes and sells pizzas of three sizes: small pizzas consist of 6 slices, medium ones consist of 8 slices, and large pizzas consist of 10 slices each. Baking them takes 15, 20 and 25 minutes, respectively.

Petya’s birthday is today, and n of his friends will come, so he decided to make an order from his favorite pizzeria. Petya wants to order so much pizza that each of his friends gets at least one slice of pizza. The cooking time of the order is the total baking time of all the pizzas in the order.

Your task is to determine the minimum number of minutes that is needed to make pizzas containing at least n slices in total. For example:

if 12 friends come to Petya’s birthday, he has to order pizzas containing at least 12 slices in total. He can order two small pizzas, containing exactly 12 slices, and the time to bake them is 30 minutes;
if 15 friends come to Petya’s birthday, he has to order pizzas containing at least 15 slices in total. He can order a small pizza and a large pizza, containing 16 slices, and the time to bake them is 40 minutes;
if 300 friends come to Petya’s birthday, he has to order pizzas containing at least 300 slices in total. He can order 15 small pizzas, 10 medium pizzas and 13 large pizzas, in total they contain 15⋅6+10⋅8+13⋅10=300 slices, and the total time to bake them is 15⋅15+10⋅20+13⋅25=750 minutes;
if only one friend comes to Petya’s birthday, he can order a small pizza, and the time to bake it is 15 minutes.
Input
The first line contains a single integer t (1≤t≤104) — the number of testcases.

Each testcase consists of a single line that contains a single integer n (1≤n≤1016) — the number of Petya’s friends.

Output
For each testcase, print one integer — the minimum number of minutes that is needed to bake pizzas containing at least n slices in total.

Example
inputCopy
6
12
15
300
1
9999999999999999
3
outputCopy
30
40
750
15
25000000000000000
15

题意：

patya有n个朋友，每个朋友都需要吃到一片披萨，现有小中大三种披萨，分别可以分为6，8，10片，需要制作时间为15，20，25minutes，现问满足每人最少一片披萨需要多少时间制作

思路：

**我们发现当n<=6时 ，6<n<= 8，8<n<=10时，分别只需15，20，25分钟，这是特殊情况，当n>10时，任意一个偶数都可以由6，8，10构造而出，最少时间为n*2.5，而奇数时无论如何不能用6，8，10构造，而分别构造n-1与1则最小时间为（n-1）2.5+15，构造n+1则为（n+1）2.5,显然构造n+1时间更短

代码如下：

void solve()
{
	int t;
	scanf("%d",&t);
	while(t--){
		ll n;
		scanf("%lld",&n);
		if(n <= 6) printf("15");
		else if(n > 6 && n <= 8) printf("20");
		else if(n > 8 && n <= 10) printf("25");
		else{
			ll sum = 0;
			sum = (n+1)/2*5;
			printf("%lld",sum);
		}
 
		printf("\n");
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

B.Two Tables

B. Two Tables
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You have an axis-aligned rectangle room with width W and height H, so the lower left corner is in point (0,0) and the upper right corner is in (W,H).

There is a rectangular table standing in this room. The sides of the table are parallel to the walls, the lower left corner is in (x1,y1), and the upper right corner in (x2,y2).

You want to place another rectangular table in this room with width w and height h with the width of the table parallel to the width of the room.

The problem is that sometimes there is not enough space to place the second table without intersecting with the first one (there are no problems with tables touching, though).

You can’t rotate any of the tables, but you can move the first table inside the room.

Example of how you may move the first table.
What is the minimum distance you should move the first table to free enough space for the second one?

Input
The first line contains the single integer t (1≤t≤5000) — the number of the test cases.

The first line of each test case contains two integers W and H (1≤W,H≤108) — the width and the height of the room.

The second line contains four integers x1, y1, x2 and y2 (0≤x1<x2≤W; 0≤y1<y2≤H) — the coordinates of the corners of the first table.

The third line contains two integers w and h (1≤w≤W; 1≤h≤H) — the width and the height of the second table.

Output
For each test case, print the minimum distance you should move the first table, or −1 if there is no way to free enough space for the second table.

Your answer will be considered correct if its absolute or relative error doesn’t exceed 10−6.

Example
inputCopy
5
8 5
2 1 7 4
4 2
5 4
2 2 5 4
3 3
1 8
0 3 1 6
1 5
8 1
3 0 6 1
5 1
8 10
4 5 7 8
8 5
outputCopy
1.000000000
-1
2.000000000
2.000000000
0.000000000
Note
The configuration of the first test case is shown in the picture. But the movement of the first table is not optimal. One of the optimal movement, for example, is to move the table by (0,−1), so the lower left corner will move from (2,1) to (2,0). Then you can place the second table at (0,3)−(4,5).

In the second test case, there is no way to fit both tables in the room without intersecting.

In the third test case, you can move the first table by (0,2), so the lower left corner will move from (0,3) to (0,5).

题意：

给定一个空间大小W*H， 一张已放置的桌子的位置，现需要放入一张w*h的桌子，不能旋转任意一张桌子，问你第一张桌子移动最小距离多少时第二张桌子可以放下，若不能放下则输出-1

思路：

最短距离一定是沿竖直或者水平方向移动，先求出四个角中里边界最远的距离，再判断这个距离内是否可以放入第二张桌子，若不能放下，则计算沿水平或者竖直方向移动最小距离

代码：

 
void solve()
{
	
	int t;
	scanf("%d",&t);
	while(t--){
		int w,h;
		scanf("%d %d",&w,&h);//读入空间长宽
		int x1,y1,x2,y2;
		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);//桌子位置
		int x,y;
		scanf("%d %d",&x,&y);//第二张桌子长宽
		if(x+(x2-x1) > w && y+(y2-y1) > h){
			printf("-1");//判断是否可以放下第二张桌子
		}else{
			int w1 = max(x1,w-x2);
			//计算桌子离左右两边界最大距离
			int h1 = max(y1,h-y2);
			//桌子离上下两边界最大距离
		if(x2-x1 + x <= w){//判断能否左右相邻
			if(x<=w1) w1 = 0;//若第二张桌子宽小于第一张桌子和边界间距离，则移动距离为0
			else w1 = x - w1;
			//否则移动距离为x-w1
		} 
		else w1 = 1e9+1;//如果不能相邻，则让w1无穷大
		//宽同理计算
		if(y2-y1 + y <= h){
			if(y <= h1) h1 = 0;
			else h1 = y - h1;
		} 
		else h1 = 1e9+1;
			printf("%.9lf",1.0*min(w1,h1));
		}
		printf("\n");
	}
}
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

C.Coin Rows

C. Coin Rows
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Alice and Bob are playing a game on a matrix, consisting of 2 rows and m columns. The cell in the i-th row in the j-th column contains ai,j coins in it.

Initially, both Alice and Bob are standing in a cell (1,1). They are going to perform a sequence of moves to reach a cell (2,m).

The possible moves are:

Move right — from some cell (x,y) to (x,y+1);
Move down — from some cell (x,y) to (x+1,y).
First, Alice makes all her moves until she reaches (2,m). She collects the coins in all cells she visit (including the starting cell).

When Alice finishes, Bob starts his journey. He also performs the moves to reach (2,m) and collects the coins in all cells that he visited, but Alice didn’t.

The score of the game is the total number of coins Bob collects.

Alice wants to minimize the score. Bob wants to maximize the score. What will the score of the game be if both players play optimally?

Input
The first line contains a single integer t (1≤t≤104) — the number of testcases.

Then the descriptions of t testcases follow.

The first line of the testcase contains a single integer m (1≤m≤105) — the number of columns of the matrix.

The i-th of the next 2 lines contain m integers ai,1,ai,2,…,ai,m (1≤ai,j≤104) — the number of coins in the cell in the i-th row in the j-th column of the matrix.

The sum of m over all testcases doesn’t exceed 105.

Output
For each testcase print a single integer — the score of the game if both players play optimally.

Example
inputCopy
3
3
1 3 7
3 5 1
3
1 3 9
3 5 1
1
4
7
outputCopy
7
8
0

题意：

两人分别从（1，1）走到（2，m）的位置，每个人走到（i，j）点时会捡取当点的金币，而游戏最终结果为第二个人捡取的金币数，第一个人会选择让二个人捡取金币尽可能少，第二个人会让金币尽可能多，两人都十分聪明，问游戏分数最小为多少

思路：

由于只有两行，且只能玩下方或者右方走，所以设在位置x时向下走，则第二个人捡取的金币数量最多的便只能走玩第一行剩下位置或者第二行剩下位置的金币，则对于每一种向下走的情况，第二个人只有两种情况需要讨论：
1.第一行剩下所有位置的金币数；
2.第二行剩下所有位置的金币数
对两种情况取最大值，在对所以可能向下走的位置遍历取最小值得到的结果就是所求，故可用dp来做对于arr[1][n]表示为在n-1点向下走后第一行剩余金币总数，arr[2][n-1]表示n点向下走时（2，1）-（2，n-1）的所有点金币总数，然后取arr[1][n]与arr[2][n-1]的最大值，最后遍历n可能的所有情况取最小值即可

代码：

ll arr[3][N],brr[3][N];
void solve()
{
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		
		for(int i = 1 ; i <= 2 ; i ++)
			for(int j = 1 ; j <= n ; j ++ ){
				scanf("%lld",&arr[i][j]);
			}
		for(int i = 2 ; i <= n ; i++){
			arr[2][i] += arr[2][i-1];
		}//将arr[2][i]更新为arr[2][1]到arr[2][i]的和
		for(int i = n - 1; i >= 0 ; i--){
			arr[1][i] = arr[1][i+1]+arr[1][i]; 
		}//将arr[1][i]更新为arr[1][i]到arr[1][n]的和
		
		ll q = 1e9+7;
		arr[2][0] = 0;
		arr[1][n+1] = 0;
		for(int i = 1 ; i <= n ; i ++){
			q = min(q,max(arr[1][i+1],arr[2][i-1]));//对于所有可能向下走的点遍历，取最小值
		}
		
		cout<<q<<endl;	 
	}
}
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