CodeForces Contest: https://codeforces.com/contest/1153
Probelm Set PDF: https://file.beiyanpiki.cn/ACM/Codeforces%23551.pdf
官方英文题解: https://codeforces.com/blog/entry/59430

A. Serval and Bus

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 , and there are bus routes which stop at this station. For the -th bus route, the first bus arrives at time minutes, and each bus of this route comes 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 and (, ) — the number of bus routes and the time Serval goes to the station.

Each of the next lines contains two space-separated integers and () — 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

case 1:

input output
2 2<br>6 4<br>9 5 1

case 2:

input output
5 5<br>3 3<br>2 5<br>5 6<br>4 9<br>6 1 3

case 3:

input output
3 7<br>2 2<br>2 3<br>2 4 1

Note

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

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

In the third example, buses of the first route come at times , , , , and so fourth, buses of the second route come at times , , , and so fourth and buses of the third route come at times , , , and so on, so and are both acceptable answers while is not.

Solve

这是一道1100分的签到题。
官方标签： brute force math

题意： 今年三岁Serval要乘坐公交车前往加帕里幼儿园。 Serval会在T分钟到达公交车站，有n条公交线路在Serval的等候车站停靠。对于每条公交线路，第一班公交到达时间为分钟，每班公交与前一趟公交间隔分钟。Serval会选择他到达车站后的第一辆公交车，问Serval会选择哪个公交线路。（如果有多条线路同时到达，任意数出一条线路）

这题有两种求解方法：

  1. 对于每一条线路，循环求出第一个大于等于的时间。对于所有线路得到最小的即可；
  2. 对于每一条线路 。对于所有线路得到最小的即可。

因为数据比较小，那就用第一种方法吧。。。

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n, t;
    int mini = 0;
    int mint = 0x3f3f3f3f;
    cin >> n >> t;
    for(int i = 0; i < n; i++){
        int t1, t2;
        cin >> t1 >> t2;
        while(t1 < t){
            t1 += t2;
        }
        if(t1 < mint){
            mint = t1;
            mini = i + 1;
        }
    }
    cout << mini << endl;
}

B. Serval and Toy Bricks

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 toy bricks, he builds up a 3-dimensional object. We can describe this object with a matrix, such that in each cell , there are bricks standing on the top of each other.

However, Serval doesn't give you any , 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 columns, and in the -th of them, the height is the maximum of . It is similar for the left view, where there are columns. And in the top view, there is an matrix , where is or . If equals , that means , otherwise, .

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 () — the length, width and height.

The second line contains non-negative space-separated integers , where is the height in the -th column from left to right of the front view ().

The third line contains non-negative space-separated integers (), where is the height in the -th column from left to right of the left view.

Each of the following lines contains numbers, each is or , representing the top view, where -th number of -th row is if , and otherwise.

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

output

Output lines, each of them contains integers, the -th number in the -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

case 1:

input output
3 7 3<br>2 3 0 0 2 0 1<br>2 1 3<br>1 0 0 0 1 0 0<br>0 0 0 0 0 0 1<br>1 1 0 0 0 0 0 1 0 0 0 2 0 0<br>0 0 0 0 0 0 1<br>2 3 0 0 0 0 0

case 2:

input output
4 5 5<br>3 5 2 0 4<br>4 2 5 4<br>0 0 0 0 1<br>1 0 1 0 0<br>0 1 0 0 0<br>1 1 1 0 0 0 0 0 0 4<br>1 0 2 0 0<br>0 5 0 0 0<br>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.

Solve

这是一道1200分的贪心题。
官方标签： constructive algorithms greedy

题意： Serval准时的到达了幼儿园，到达了幼儿园之后，他觉得积木很有意思。Serval喜欢创造困难的问题去让别人解出。这次，Serval用 1 x 1 x 1 的积木搭建了一个三维物体并告诉你描述这个物体的方法：我们可以自上至下观察，用 n x m 的矩阵描述这个物体，在每个 单元格 (i, j)中，都有个积木。

现在Serval给你这个三维物体的三视图，要求你现在恢复这个物体，三视图的长为 m ， 宽为 n，高为 h。

  • 对于主视图，一共有m列，每列的高度为
  • **对于左视图，一共有n列，每列高度为 **
  • 对于顶视图，看做m × n的矩形， 对于每个单元格(i , j)，1表示有积木，0表示没积木。

现在Serval给你一个积木的长、宽、高，以及主视图、左视图、顶视图的数据。让你用本题开始Serval所表示的方法描述这个三维物体。（如果存在多种表示方法，输出任意一种）

题目很长，看起来很唬人，其实挺简单的（要不然也不会放在B题）。
首先我们先根据题目需求，读入三视图的数据。我们就分别定义为front, left 和 top吧。

既然从上至下寻找每个单元格有多少块积木，那我们就从顶视图入手。
对于每个单元格，我们先判断这个单元格里面存不存在积木，即是否等于0。如果等于0那说明不存在，跳过操作下一个单元格；如果等于1则继续之后的操作。

根据常识（真的是常识），每一个单元格的积木数.（不信可以自己验证一下）。

结果到头来就是这么一个公式嘛

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m, h;
    cin >> n >> m >> h;
    vector<int> front(m), left(n);
    vector<vector<int>> top(n, vector<int>(m, 0));

    for(int i = 0; i < m; i++){
        cin >> front[i];
    }
    for(int i = 0; i < n; i++){
        cin >> left[i];
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> top[i][j];
        }
    }

    vector<vector<int>> res(n, vector<int>(m, 0));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(!top[i][j]){
                res[i][j] = 0;
                continue;
            } else { 
                res[i][j] = min(left[i], front[j]);
            }
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cout << res[i][j] << " ";
        }
        cout << endl;
    }
}

C. Serval and Parenthesis Sequence

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.

A parenthesis sequence is a string, containing only characters "(" and ")".

A 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 as the length of string . A strict prefix of a string is string . 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 containing only characters "(", ")" and "?". And what he is going to do, is to replace each of the "?" in 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 (), the length of the string.

The second line contains a string , 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

case 1:

input output
6<br>(????? (()())

case 2:

input output
10<br>(???(???(?

Note

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

Solve

这是一道1600分的贪心题。
官方标签： string greedy

题意： Serval告别了加帕里幼儿园，开始了加帕里小学的生活。数学课的老师交给了他有趣的定义：括弧序列是一个字符串，只包含'(' 和 ')'。

正确的括弧序列可以通过字符之间插入+ 或 1 可以转化为正确的算术表达式（例如： 可以转化成; 可以转化成。而 和 是不正确的。
**我们定义字符串为 严格前缀**

Serval给你一个带’？‘的字符串，要求你填写’？‘使字符串变成：

  • 严格前缀不为括弧序列
  • 字符串s为括弧序列

如果可以，输出s（如果有多个解任意输出一个）；如果不可以，输出":("

首先先解释一下严格前缀不为括弧序列是什么意思，举个例子:
定义一个长度n = 6 的字符串

对于这个字符串来说

这6个字符串都是严格前缀，根据题目要求，我们不能让这六个中的任意一个成为括弧序列。但是很遗憾， 成为了括弧序列，那么这个字符串就不符合题目要求。输出":("

解释完严格前缀后，根据题意可以知道，如果要成为括弧序列，那么'(' 和 ')'必须是成对出现的，所以字符串长度为奇数的话可以直接知道s一定无法满足要求。

接下来题目要求字符串s要满足括弧序列的要求，只需字符串s的第一个字符和最后一个字符相匹配即可。

匹配完整个字符串之后，我们要构造严格前缀不为括弧序列。既然要使字符串不为括弧序列，我们要尽量不让')'过早的与'('进行匹配，所以遇到问号，我们需要贪心的优先填写'('，'('全部被用完后才填写')'。

构造完s后，判断一变是否存在严格前缀为括弧序列即可，注意验证时要确定'('与')'的个数相同。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    string s;
    cin >> n >> s;

    int cntl = 0, cntr = 0;
    for(int i = 0; i < n; i++){
        if(s[i] == '('){
            cntl++;
        }
        if(s[i] == ')'){
            cntr++;
        }
    }

    for(int i = 0; i < n; i++){
        if(s[i] == '?'){
            s[i] = '(';
            cntl++;
        }
        if(cntl == n / 2){
            break;
        }
    }

    for(int i = 0; i < n; i++){
        if(s[i] == '?'){
            s[i] = ')';
            cntr++;
        }
        if(cntr == n / 2){
            break;
        }
    }

    int t = 0;
    bool f = true;
    for(int i = 0; i < n; i++){
        if(s[i] == '('){
            t++;
        }
        if(s[i] == ')'){
            t--;
        }
        if(t <= 0 && i < n - 1){
            f = false;
            break;
        }
        if(t != 0 && i == n - 1){
            f = false;
            break;
        }
    }

    if(n % 2){
        f = false;
    }
    cout << (f ? s : ":(") << endl;
}

D. Serval and Rooted Tree

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 is the last different from vertex on the path from the root to the vertex . Children of vertex are all nodes for which is the parent. A vertex is a leaf if it has no children.

The rooted tree Serval owns has nodes, node 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 or 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 leaves in the tree. Serval wants to put integers to the 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 (), the size of the tree.

The second line contains integers, the -th of them represents the operation in the node . represents and represents . If the node is a leaf, there is still a number of or , but you can ignore it.

The third line contains integers (), where represents the parent of the node .

output

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

Examples

case 1:

input output
6<br>1 0 1 1 0 1<br>1 2 2 2 2 1

case 2:

input output
5<br>1 0 1 0 1<br>1 1 1 1 4

case 3:

input output
8<br>1 0 0 1 0 1 1 0<br>1 1 2 2 3 3 3 4

case 4:

input output
9<br>1 1 0 0 1 0 1 0 1<br>1 1 2 2 3 3 4 4 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 .

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

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

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

Solve

这是一道1800分的动态规划题。
官方标签：binary search dfs and similar dp greedy trees

题意： Serval现在是加帕里中学的一名初中生，和小学一样，他依旧对数学感到兴奋(你是都抖S吧) 这一次，他选择在一棵树的根上玩数学游戏
<接下来一段是树的定义，跳过了>
** Serval拥有一个带n个节点的有根树，其中节点1是根。Serval会将数字写入树的所有节点。但是，除了叶子节点之外的每个节点都有一个属性MAX或MIN，分别等于其所有叶子节点所有数字的最大值或最小值。**
假设有k个叶子节点，Serval希望将整数1.2...k填入到k个叶子节点上（每个数字仅限填写一次），使根获得最大值。求根的最大值。

一道树型DP题。贪心讲道理应该是可以做的（毕竟标签都打上greedy了）

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3 * 100000 + 50;
const int INF = 0x3f3f3f3f;

vector<vector<int>> G(MAXN);
vector<int> stat(MAXN);
vector<int> dp(MAXN, 0);
int n, k = 0;


void dfs(int u){
    if(G[u].size() == 0 && u != 0){
        dp[u] = 1;
        k++;
        return;
    }
    if(stat[u]){
        dp[u] = INF;
    } else {
        dp[u] = 0;
    }
    for(auto e : G[u]){
        dfs(e);
        if(stat[u]){
            dp[u] = min(dp[e], dp[u]);
        } else {
            dp[u] += dp[e];
        }
    }
}

int main(){    
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> stat[i];
    }
    for(int i = 1; i < n; i++){
        int t;
        cin >> t;
        G[--t].push_back(i);
    }


    // ~ for(int i = 0; i < n; i++){
        // ~ cout << i + 1 << ": ";
        // ~ for(auto j : G[i]){
            // ~ cout << j + 1 << " ";
        // ~ }
        // ~ cout << endl;
    // ~ }


    dfs(0);
    cout << k + 1 - dp[0] << endl;
}

E. Serval and Snake

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 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 .

Today Serval got up too late and only have time to make 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 , 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 () — the size of the grid.

output

When you are ready to answer, you should print ! x1 y1 x2 y2, where represents the position of the head and 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 (, ), representing a rectangle consisting of all cells such that and . 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 instead of a valid answer means that you made an invalid query or exceeded the maximum number of queries. Exit immediately after receiving 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 () in the first line, indicating the size of the grid.

Then print an integer () in the second line, indicating the length of the snake.

In the next lines, print pairs of integers (), each pair in a single line, indicating the -th cell of snake, such that the adjacent pairs are adjacent, and all pairs are distinct.

Examples

case 1:

input output
2</br>1</br>0</br>0 ? 1 1 1 1</br>? 1 2 1 2</br>? 2 2 2 2</br>! 1 1 2 1

case 2:

input output
3</br>2</br>0 ? 2 2 2 2</br>? 2 1 2 3</br>! 2 1 2 3

Note

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

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

Solve

这是一道1800分的动态规划题。
官方标签：binary search brute force interactive

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> P;

vector<P> res;
int n;

int query(int x1, int y1, int x2, int y2){
    cout.flush();
    cout << "?" << " " << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
    int t;
    cin >> t;
    return t;
}

void go_row(int row){
    int l = 1, r = n, mid, f;
    while(l <= r){
        mid = (l + r) / 2;
        int t = query(l, row, mid, row);
        if(t & 1){
            r = mid - 1;
            f = mid;
        } else {
            l = mid + 1;
        }
    }
    res.push_back(P(f, row));
}

void go_col(int col){
    int l = 1, r = n, mid, f;
    while(l <= r){
        mid = (l + r) / 2;
        int t = query(col, l, col, mid);
        if(t & 1){
            r = mid - 1;
            f = mid;
        } else {
            l = mid + 1;
        }
    }
    res.push_back(P(col, f));
}

int main(){
    cin >> n;

    vector<int> cnt(n + 1);
    int s = 0;
    for(int i = 1; i < n; i++){
        int t = query(1, i, n, i);
        cnt[i] = t;
        s += t;
    }
    cnt[n] = s;
    vector<int> found;
    for(int i = 1; i <= n; i++){    /// 查询列
        if(cnt[i] & 1){
            found.push_back(i);
        }
    }
    if(found.size() == 2){
        for(auto d : found){
            go_row(d);
        }
    } else {
        s = 0;
        for(int i = 1; i < n; i++){        /// 查询行
            int t = query(i, 1, i, n);
            cnt[i] = t;
            s += t;
        }
        cnt[n] = s;
        found.clear();
        for(int i = 1; i <= n; i++){
            if(cnt[i] & 1){
                found.push_back(i);
            }
        }
        for(auto d : found){
            go_col(d);
        }
    }

    cout << "!" << " ";
    for(auto d : res){
        cout << d.first << " " << d.second << " ";
    }
}