Codeforces Round #551 (Div. 2)

A. Serval and Bus

time limit per test1 second memory limit per test256 megabytes

It is raining heavily. But this is the first day for Serval, who just became 3 years old, to go to the kindergarten. Unfortunately, he lives far from kindergarten, and his father is too busy to drive him there. The only choice for this poor little boy is to wait for a bus on this rainy day. Under such circumstances, the poor boy will use the first bus he sees no matter where it goes. If several buses come at the same time, he will choose one randomly.

Serval will go to the bus station at time 𝑡t, and there are 𝑛n bus routes which stop at this station. For the 𝑖i-th bus route, the first bus arrives at time 𝑠𝑖si minutes, and each bus of this route comes 𝑑𝑖di minutes later than the previous one.

As Serval’s best friend, you wonder which bus route will he get on. If several buses arrive at the same time, you can print any of them.Input

The first line contains two space-separated integers 𝑛n and 𝑡t (1≤𝑛≤1001≤n≤100, 1≤𝑡≤1051≤t≤105) — the number of bus routes and the time Serval goes to the station.

Each of the next 𝑛n lines contains two space-separated integers 𝑠𝑖si and 𝑑𝑖di (1≤𝑠𝑖,𝑑𝑖≤1051≤si,di≤105) — the time when the first bus of this route arrives and the interval between two buses of this route.Output

Print one number — what bus route Serval will use. If there are several possible answers, you can print any of them.
Examples
input

2 2 
6 4
9 5

output

1

input

5 5 
3 3
2 5
5 6
4 9
6 1

output

3

input

3 7 
2 2
2 3
2 4

output

1

Note

In the first example, the first bus of the first route arrives at time 66, and the first bus of the second route arrives at time 99, so the first route is the answer.

In the second example, a bus of the third route arrives at time 55, so it is the answer.

In the third example, buses of the first route come at times 22, 44, 66, 88, and so fourth, buses of the second route come at times 22, 55, 88, and so fourth and buses of the third route come at times 22, 66, 1010, and so on, so 11 and 22 are both acceptable answers while 33 is not.

傻逼题

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
const int max=(int)1e5+100;
int main(){
	int n,t;cin>>n>>t;
	int ans=0,mint=INF;
	for(int i=1,x,s;i<=n;++i){
		cin>>s>>x;
		if(s<t){
			int d=(t-s)/x;
			if((t-s)%x) d++;
			if((s+d*x)-t<mint) mint=(s+d*x)-t,ans=i;
		}
		else{
			if(s-t<mint) mint=s-t,ans=i;
		}
	}
	cout<<ans<<endl;
}

 


B. Serval and Toy Bricks

time limit per test1 second memory limit per test256 megabytes

Luckily, Serval got onto the right bus, and he came to the kindergarten on time. After coming to kindergarten, he found the toy bricks very funny.

He has a special interest to create difficult problems for others to solve. This time, with many 1×1×11×1×1 toy bricks, he builds up a 3-dimensional object. We can describe this object with a 𝑛×𝑚n×m matrix, such that in each cell (𝑖,𝑗)(i,j), there are ℎ𝑖,𝑗hi,j bricks standing on the top of each other.

However, Serval doesn’t give you any ℎ𝑖,𝑗hi,j, and just give you the front view, left view, and the top view of this object, and he is now asking you to restore the object. Note that in the front view, there are 𝑚m columns, and in the 𝑖i-th of them, the height is the maximum of ℎ1,𝑖,ℎ2,𝑖,…,ℎ𝑛,𝑖h1,i,h2,i,…,hn,i. It is similar for the left view, where there are 𝑛n columns. And in the top view, there is an 𝑛×𝑚n×m matrix 𝑡𝑖,𝑗ti,j, where 𝑡𝑖,𝑗ti,j is 00 or 11. If 𝑡𝑖,𝑗ti,j equals 11, that means ℎ𝑖,𝑗>0hi,j>0, otherwise, ℎ𝑖,𝑗=0hi,j=0.

However, Serval is very lonely because others are bored about his unsolvable problems before, and refused to solve this one, although this time he promises there will be at least one object satisfying all the views. As his best friend, can you have a try?Input

The first line contains three positive space-separated integers 𝑛,𝑚,ℎn,m,h (1≤𝑛,𝑚,ℎ≤1001≤n,m,h≤100) — the length, width and height.

The second line contains 𝑚m non-negative space-separated integers 𝑎1,𝑎2,…,𝑎𝑚a1,a2,…,am, where 𝑎𝑖ai is the height in the 𝑖i-th column from left to right of the front view (0≤𝑎𝑖≤ℎ0≤ai≤h).

The third line contains 𝑛n non-negative space-separated integers 𝑏1,𝑏2,…,𝑏𝑛b1,b2,…,bn (0≤𝑏𝑗≤ℎ0≤bj≤h), where 𝑏𝑗bj is the height in the 𝑗j-th column from left to right of the left view.

Each of the following 𝑛n lines contains 𝑚m numbers, each is 00 or 11, representing the top view, where 𝑗j-th number of 𝑖i-th row is 11 if ℎ𝑖,𝑗>0hi,j>0, and 00 otherwise.

It is guaranteed that there is at least one structure satisfying the input.Output

Output 𝑛n lines, each of them contains 𝑚m integers, the 𝑗j-th number in the 𝑖i-th line should be equal to the height in the corresponding position of the top view. If there are several objects satisfying the views, output any one of them.
Examples
input

3 7 3 
2 3 0 0 2 0 1
2 1 3
1 0 0 0 1 0 0
0 0 0 0 0 0 1
1 1 0 0 0 0 0

output

1 0 0 0 2 0 0 
0 0 0 0 0 0 1
2 3 0 0 0 0 0

input

4 5 5 
3 5 2 0 4
4 2 5 4
0 0 0 0 1
1 0 1 0 0
0 1 0 0 0
1 1 1 0 0

output

0 0 0 0 4 
1 0 2 0 0
0 5 0 0 0
3 4 1 0 0

Note

The graph above illustrates the object in the first example.

The first graph illustrates the object in the example output for the second example, and the second graph shows the three-view drawing of it.

详见代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=(int)1e5+100;
int main(){
	int n,m,h;cin>>n>>m>>h;
	int a[110],b[110],c[110][110];
	for(int i=0;i<m;++i) cin>>a[i];
	for(int i=0;i<n;++i) cin>>b[i];
	for(int i=0;i<n;++i)
		for(int j=0,x;j<m;++j){
			cin>>x;
			if(x) c[i][j]=min(a[j],b[i]);
			else c[i][j]=0;
		}
	for(int i=0;i<n;++i){
		for(int j=0;j<m;++j) cout<<c[i][j]<<" ";
		puts("");
	}
}

 


C. Serval and Parenthesis Sequence

time limit per test1 second memory limit per test256 megabytes

Serval soon said goodbye to Japari kindergarten, and began his life in Japari Primary School.

In his favorite math class, the teacher taught him the following interesting definitions.

parenthesis sequence is a string, containing only characters “(” and “)”.

correct parenthesis sequence is a parenthesis sequence that can be transformed into a correct arithmetic expression by inserting characters “1” and “+” between the original characters of the sequence. For example, parenthesis sequences “()()”, “(())” are correct (the resulting expressions are: “(1+1)+(1+1)”, “((1+1)+1)”), while “)(” and “)” are not. Note that the empty string is a correct parenthesis sequence by definition.

We define that |𝑠||s| as the length of string 𝑠s. A strict prefix 𝑠[1…𝑙]s[1…l] (1≤𝑙<|𝑠|)(1≤l<|s|) of a string 𝑠=𝑠1𝑠2…𝑠|𝑠|s=s1s2…s|s| is string 𝑠1𝑠2…𝑠𝑙s1s2…sl. Note that the empty string and the whole string are not strict prefixes of any string by the definition.

Having learned these definitions, he comes up with a new problem. He writes down a string 𝑠s containing only characters “(“, “)” and “?”. And what he is going to do, is to replace each of the “?” in 𝑠s independently by one of “(” and “)” to make all strict prefixes of the new sequence not a correct parenthesis sequence, while the new sequence should be a correct parenthesis sequence.

After all, he is just a primary school student so this problem is too hard for him to solve. As his best friend, can you help him to replace the question marks? If there are many solutions, any of them is acceptable.Input

The first line contains a single integer |𝑠||s| (1≤|𝑠|≤3⋅1051≤|s|≤3⋅105), the length of the string.

The second line contains a string 𝑠s, containing only “(“, “)” and “?”.Output

A single line contains a string representing the answer.

If there are many solutions, any of them is acceptable.

If there is no answer, print a single line containing “:(” (without the quotes).
Examples
input

6
(?????

output

(()())

input

10
(???(???(?

output

🙁

Note

It can be proved that there is no solution for the second sample, so print “:(“.

贪心,先放左括号再放右括号

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=(int) 1e5+100;
int main(){
	int n;cin>>n;
	string s;cin>>s;
	if(n%2){cout<<":(\n";exit(0);}
	int l=0,r=0;
	for(int i=0;i<s.length();++i){
		if(s[i]=='(') l++;
		else if(s[i]==')') r++;
	}
	int nn=s.length()/2;
	l=nn-l;r=nn-r;
	if(l<0||r<0){cout<<":(\n";exit(0);}
	int nl=0,nr=0,tem=0;
	for(int i=0;i<s.length()-1;++i){
		if(s[i]=='(') nl++;
		else if(s[i]==')') nr++;
		else{
			if(nl<nn){
				if(l){nl++;l--;s[i]='(';}
				else if(r){nr++;r--;s[i]=')';}
				else {cout<<":(\n";exit(0);}
				tem=nl-nr;
				if(tem<=0){cout<<":(\n";exit(0);}				
			}
			else{nr++;r--;s[i]=')';}
		}
			tem=nl-nr;
			if(tem<=0){cout<<":(\n";exit(0);}		
	}
	if(l) s[s.length()-1]='(';
	else s[s.length()-1]=')';
	cout<<s<<endl;
}

 


D. Serval and Rooted Tree

time limit per test2 seconds memory limit per test256 megabytes

Now Serval is a junior high school student in Japari Middle School, and he is still thrilled on math as before.

As a talented boy in mathematics, he likes to play with numbers. This time, he wants to play with numbers on a rooted tree.

A tree is a connected graph without cycles. A rooted tree has a special vertex called the root. A parent of a node 𝑣v is the last different from 𝑣v vertex on the path from the root to the vertex 𝑣v. Children of vertex 𝑣v are all nodes for which 𝑣v is the parent. A vertex is a leaf if it has no children.

The rooted tree Serval owns has 𝑛n nodes, node 11 is the root. Serval will write some numbers into all nodes of the tree. However, there are some restrictions. Each of the nodes except leaves has an operation maxmax or minmin written in it, indicating that the number in this node should be equal to the maximum or minimum of all the numbers in its sons, respectively.

Assume that there are 𝑘k leaves in the tree. Serval wants to put integers 1,2,…,𝑘1,2,…,k to the 𝑘k leaves (each number should be used exactly once). He loves large numbers, so he wants to maximize the number in the root. As his best friend, can you help him?Input

The first line contains an integer 𝑛n (2≤𝑛≤3⋅1052≤n≤3⋅105), the size of the tree.

The second line contains 𝑛n integers, the 𝑖i-th of them represents the operation in the node 𝑖i. 00 represents minmin and 11 represents maxmax. If the node is a leaf, there is still a number of 00 or 11, but you can ignore it.

The third line contains 𝑛−1n−1 integers 𝑓2,𝑓3,…,𝑓𝑛f2,f3,…,fn (1≤𝑓𝑖≤𝑖−11≤fi≤i−1), where 𝑓𝑖fi represents the parent of the node 𝑖i.Output

Output one integer — the maximum possible number in the root of the tree.
Examples
input

6 
1 0 1 1 0 1
1 2 2 2 2

output

1

input

5 
1 0 1 0 1
1 1 1 1

output

4

input

8 
1 0 0 1 0 1 1 0
1 1 2 2 3 3 3

output

4

input

9 
1 1 0 0 1 0 1 0 1
1 1 2 2 3 3 4 4

output

5

Note

Pictures below explain the examples. The numbers written in the middle of the nodes are their indices, and the numbers written on the top are the numbers written in the nodes.

In the first example, no matter how you arrange the numbers, the answer is 11.

In the second example, no matter how you arrange the numbers, the answer is 44.

In the third example, one of the best solution to achieve 44 is to arrange 44 and 55 to nodes 44 and 55.

In the fourth example, the best solution is to arrange 55 to node 55.

简单树形DP,dp[i]表示以i为根结点的子树对答案的贡献,也即它能表示的它叶子数量的最小的值(排序后最靠近前面的,第k大的数),min时就是只能是子树的叶子的数量了;max时就能是儿子最小的了(最靠前);ans就是叶子数量减去根的值;

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define INF 0x3f3f3f3f
const int maxn=(int)3e5+100;
int n,op[maxn];
vector<int> g[maxn];
int dp[maxn];
int tot;
void dfs(int x){
	if(g[x].empty()){
		tot++;dp[x]=1;return;
	}
	if(op[x]) dp[x]=INF;
	for(auto u:g[x]){
		dfs(u);
		if(op[x]) dp[x]=min(dp[x],dp[u]);
		else dp[x]+=dp[u];
	}
}
int main(){
	int n;cin>>n;
	for(int i=1;i<=n;++i) scanf("%d",&op[i]);
	for(int i=2,x;i<=n;++i){scanf("%d",&x);g[x].pb(i);}
	tot=0;dfs(1);cout<<tot+1-dp[1]<<endl;
}

 


E. Serval and Snake

time limit per test1 second memory limit per test256 megabytes

This is an interactive problem.

Now Serval is a senior high school student in Japari Middle School. However, on the way to the school, he must go across a pond, in which there is a dangerous snake. The pond can be represented as a 𝑛×𝑛n×n grid. The snake has a head and a tail in different cells, and its body is a series of adjacent cells connecting the head and the tail without self-intersecting. If Serval hits its head or tail, the snake will bite him and he will die.

Luckily, he has a special device which can answer the following question: you can pick a rectangle, it will tell you the number of times one needs to cross the border of the rectangle walking cell by cell along the snake from the head to the tail. The pictures below show a possible snake and a possible query to it, which will get an answer of 44.

Today Serval got up too late and only have time to make 20192019 queries. As his best friend, can you help him find the positions of the head and the tail?

Note that two cells are adjacent if and only if they have a common edge in the grid, and a snake can have a body of length 00, that means it only has adjacent head and tail.

Also note that the snake is sleeping, so it won’t move while Serval using his device. And what’s obvious is that the snake position does not depend on your queries.Input

The first line contains a single integer 𝑛n (2≤𝑛≤10002≤n≤1000) — the size of the grid.Output

When you are ready to answer, you should print ! x1 y1 x2 y2, where (𝑥1,𝑦1)(x1,y1) represents the position of the head and (𝑥2,𝑦2)(x2,y2)represents the position of the tail. You can print head and tail in any order.Interaction

To make a query, you should print ? x1 y1 x2 y2 (1≤𝑥1≤𝑥2≤𝑛1≤x1≤x2≤n, 1≤𝑦1≤𝑦2≤𝑛1≤y1≤y2≤n), representing a rectangle consisting of all cells (𝑥,𝑦)(x,y) such that 𝑥1≤𝑥≤𝑥2×1≤x≤x2 and 𝑦1≤𝑦≤𝑦2y1≤y≤y2. You will get a single integer as the answer.

After printing a query, do not forget to output the end of line and flush the output, otherwise you will get Idleness limit exceeded. To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
  • see documentation for other languages.

Answer −1−1 instead of a valid answer means that you made an invalid query or exceeded the maximum number of queries. Exit immediately after receiving −1−1 and you will see Wrong answer verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream.

If your program cannot find out the head and tail of the snake correctly, you will also get a Wrong Answer verdict.

Hacks

To make a hack, print a single integer 𝑛n (2≤𝑛≤10002≤n≤1000) in the first line, indicating the size of the grid.

Then print an integer 𝑘k (2≤𝑘≤𝑛22≤k≤n2) in the second line, indicating the length of the snake.

In the next 𝑘k lines, print 𝑘k pairs of integers 𝑥𝑖,𝑦𝑖xi,yi (1≤𝑥𝑖,𝑦𝑖≤𝑛1≤xi,yi≤n), each pair in a single line, indicating the 𝑖i-th cell of snake, such that the adjacent pairs are adjacent, and all 𝑘k pairs are distinct.
Examples
input

2 
1
0
0

output

? 1 1 1 1 
? 1 2 1 2
? 2 2 2 2
! 1 1 2 1

input

3 
2
0

output

? 2 2 2 2 
? 2 1 2 3
! 2 1 2 3

Note

The pictures above show our queries and the answers in the first example. We first made a query for (1,1)(1,1) and got an answer 11, then found that it must be connected to exactly one other cell. Then we made a query for (1,2)(1,2) and got an answer of 00, then knew that the snake never entered it. So the cell connected to (1,1)(1,1) must be (2,1)(2,1). Then we made a query for (2,2)(2,2) and got an answer 00, then knew that it never entered (2,2)(2,2) as well. So the snake cannot leave (2,1)(2,1), which implies that the answer is (1,1)(1,1) and (2,1)(2,1).

The pictures above show our queries and the answers in the second example. By making query to (2,2)(2,2) and receiving 22, we found that the snake occupies (2,2)(2,2). And by making query to rectangle from (2,1)(2,1) to (2,3)(2,3) and receiving answer 00, we knew that it never goes out of the rectangle from (2,1)(2,1) to (2,3)(2,3). Since the first answer is 22, both (2,1)(2,1) and (2,3)(2,3) must be occupied but none of others, so the answer is (2,1)(2,1) and (2,3)(2,3).

有趣的交互题。

首先我们可以知道,查询任意矩形,如果矩形里面有蛇的头或者有尾,那么答案一定是奇数,如果是偶数,可以证明蛇身不在矩形里,或者头和尾都在矩形里。

那么首先询问每一行,如果答案全都是偶数则证明头和尾在同一行,否则就确定了头尾的行号,再二分找一下列号就好了;
对于在同一行的情况,我们再查找每一列,最坏只要找n-1次就可以了,因为如果之前n-1次只找到一个奇数,那么第n个肯定是奇数;
因此我们可以证明最坏的情况需要查找1000+999+2*log(n) =2019次,符合题目要求;

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
const int maxn=(int)1e5+100;
struct node{int x,y;};
vector<node> ans;
int n;
int query(int x1,int y1,int x2,int y2){
	printf("? %d %d %d %d\n",x1,y1,x2,y2);
	fflush(stdout);scanf("%d",&x1);return x1&1;
}
void work(int cur,int op){
	int l=1,r=n;
	while(l<r){
		int mid=(l+r)>>1;
		if(op?query(cur,l,cur,mid):query(l,cur,mid,cur)) r=mid;
		else l=mid+1;
	}
	if(op) ans.pb((node){cur,l}); else ans.pb((node){l,cur});
}
int main(){
	scanf("%d",&n);
	rep(i,1,n) if(query(i,1,i,n)) work(i,1);
	rep(i,1,n-1){
			int flag=0,ct=ans.size()-1;
			rep(j,0,ct) if(i==ans[j].y) flag=1;
			if(flag) continue;
			if(query(1,i,n,i)) work(i,0);
		}
	if(ans.size()<2) work(n,0);
	printf("! %d %d %d %d\n",ans[0].x,ans[0].y,ans[1].x,ans[1].y);
	return 0;
}

 

发表评论,支持MarkDown语法