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,b,c;
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<<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≤?≤?2x1≤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.x,ans.y,ans.x,ans.y);
return 0;
}

0 评论