Description

You are going to maintain a data structure that each element is a person described by a string of name and int of age.

Give you n orders. There're four types of order

born:

The order will followed by a string and a int represented a person's name and age. Insert the new person into the set.

find:

The order will followed by a string and a int. Find out if the person exist in the set or not. If the person exist, print YES, else print NO.

kill

The order will followed by a string and a int. Erase the person from the set.

If you can't find the person, do nothing.

young:

Print the youngest person in the set. If multiple people has the same age, print the person whose name is the smallest lexicographical order.

If you can't find the person, do nothing.

Download the C++ reference.
You will see the file named "12534.cpp" but that's OK.
Just download the file and change the filename extension(副檔名) into "zip" then you can upzip the file and use the reference.
The link is below.

reference.zip

Input

The first line contains only one integer n(1 <= n <= 200000)

The following n lines each lines contains order as the description described.

Each name's length will not exceed 10000.

Each age is in rage of  int

Output

For each order print as demand.

Remember to print \n at the end of each output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

I/O optimization

If you encounter a TLE, you may try to use this optimization for C++ I/O functions:

std::ios_base::sync_with_stdio(false);
cin.tie(0);

And replace all std::endl with '\n'.

Do note that you must not use any of C I/O functions such as scanf, printf, fgets if you use this optimization.

<vector>

#include <iostream>
#include <vector>
#include <algorithm> // sort
int main () {
    std::vector<int> V;
    int x;
    while (std::cin >> x) {
        V.push_back(x);
    }
    for (auto t : V) std::cout << " " << t;
    std::cout << "\n";
    std::sort(V.begin(), V.end());
    for (auto t : V) std::cout<<" "<< t;
    std::cout << "\n";
}

<queue>

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;
int main() {
    string s;
    queue<string> q;
    while (cin >> s) {
        if (s == "Push") {
            cin >> s;
            q.push(s);
        }
        else if (s == "Pop") {
            if (q.size()>0)
                q.pop();
        }
        else if (s == "Front") {
            if (q.size() == 0)
                cout << "empty\n";
            else
                cout << q.front() << "\n";
        }
    }
}

<stringstream>

#include <string>
#include <iostream>
#include <sstream> // std::stringstream
int main () {

     std::stringstream ss;
     ss << "Hello " << 123;
     std::string s = ss.str();
     std::cout << s << '\n';
}

<set>

#include <iostream>
#include <set>
int main()
{
     std::set<int> S = {1, 2, 3, 4};
     auto search = S.find(2);
     if(search != S.end()) {
          std::cout << (*search) << '\n';
     }
     else {
          std::cout << "Not found\n";
     }
}

<stack>

#include <stack>
#include <iostream>
int main()
{
     std::stack<int> s;
     s.push( 3 ); s.push( 6 );
     s.push( 18 );
     std::cout<<s.size()<<" elements\n";
     std::cout<<"Top: "<< s.top()<< "\n";
     s.pop();
     std::cout<<s.size()<<" elements\n";
}

getline()

#include <string>
#include <iostream>
int main()
{
     std::string name;
     std::cout << "What is your name? ";
     std::getline(std::cin, name);
     std::cout << "Hello "<< name<< "\n";
}

<map>

#include <iostream>
#include <string>
#include <map>
#include <utility> // make_pair
int main()
{
     std::map<std::string, int> ID;
     ID.insert(std::make_pair("Tom", 123));
     std::cout << ID["Tom"] << "\n";
}

<string>

#include <iostream>
#include <string>
int main() {
    std::string str1, str2, out;
    while (std::cin >> str1 >> str2) {
        out.clear();
        for(auto t : str1) out.push_back(t);
        std::cout << out << '\n';
        out += str2;
        std::cout << out << '\n';
        out.pop_back();
        std::cout << out << '\n';
        for(size_t i = 0; i < out.size(); i++)
            std::cout << out[i];
        std::cout << '\n';
    }
}

Miscellaneous

For more standard library or C++ reference, please refer to this file and rename the downloaded file(12534.cpp) to reference.zip, then unzip it. There's a readme inside the zip.

If you have difficulty renaming file, try the following command on terminal (Windows)

move 12534.cpp reference.zip

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

And now my watch begins.

~by a binge watching man

Your a lord commander of the night's watch. You wants to choose some men to be your soldiers while other lords also needs to choose some men. There're n lords and n soldiers and there're k lords who are your friends therefore they will follow your order. And each soldier's ability is represented by a number ai. Since the lords stand in a line and wait for their turn to choose, you are standing in the m-th position.

Given a sequence of numbers a1 ~ an. n people standing in a line to choose one number from the sequence.

Each person can only choose a number from the head or the tail of the sequence.

Once a number is chosen, it will be remove from the sequence.

You are at m-th position of the line.

You want to get the number as big as possible.

You can command at most k people to choose what you want them to choose(head or tail).

But you can not change your command during the choosing process.

And those who you don't give a command will choose arbitrarily.

Your task is to find out what is the greatest integer x such that, no matter what are the choices of the others you didn't choose to control, the element you will take from the array will be at least x?

Example:

If there are n=6 numbers 2, 9, 2, 3, 8, 5.

You are at m=4 position.

And you can control k=2 people.

If the first person ordered by you choose tail 5.

The second person ordered by you choose head 2.

Then the third person can choose either 9 or 8.

No matter what the third person choose, you can get at least 8.

Therefore the answer is 8.

Input

The first line of input will be t(1 <= t <= 10) means number of testcases.

Each testcases contains two lines.

First line contains three integers n( 1 <= n <= 5000), m(1 <= m <= n), k(0 <= k <= n-1).

Second line contains n integers ai(1 <= ai <= 10^9).

Output

For each testcases, print a single integer x.

Each output is ended by \n.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Help! Help! We're all gonna be flunked by these devil-like TAs!

── Students

It's said that there's a course that every student who take that course will be flunked...

The course might be Advanced Calculus, Complex Analysis ... it could be Introduction to Programming! Who knows?

The only thing you know is that the professor of this course is Professor Chen-Tzong Hwann(煥陳宗), a.k.a. CTH. His TAs keep producing extremely hard problems, leads that every student are going to be flunked.

However, flunking every student means that CTH needs to submit a report to the administration of the university, and CTH is too lazy to write that report, so he decide to let exactly one student pass.

The class have $n$ students, CTH will organize a tournament. The tournament is going to be held with the following format:

1. If there's only one student remaining, then the student is the winner, the tournament ends.

2. If the number of remaining students is even, they split in pairs and compete for each pair. The loser of each pair will be eliminated(no draws for this competition).

3. Otherwise, if the number of remaining students is odd, they'll compete each other once in round robin tournament and decide the final winner, then the tournament ends.

   • For the round robin tournament part, if there are $x$ students remaining, there will be $\frac{x(x-1)}2$ competitions since they compete with everyone once.

For example, if there are 20 students initially, they would have 10 competitions, then 10 students are eliminated. The remaining 10 students would have 5 competitions and remain 5 students, then have 10 competitions for round robin tournament. Totally there are 10+5+10=25 competitions.

CTH's TA want to see exactly $n$ competitions in order to see them suffer. He asks you to calculate the minimum number of students that the course need to have.

Hint:

This problem involves brute force(暴力搜尋) and binary search(二分搜尋). One of the solutions is to combine the two techniques. You may try to think what we can enumerate, and what we can do a binary search.

Brute Force: usually applied when the number is small.

Binary Search: If the sequence is in increasing / decreasing order, the binary search technique can be applied.

Input

The first line contains an integer $T$. There are $T$ testcases below. $1\le T\le 64$.

There are $T$ lines below. Each line contains exactly one integer $n$, the number of competitions.

$1\le n\le 10^{18}$.

Output

For each testcase, output its minimum number of students that the course need to have with newline.

If there's no such answer, print -1 instead.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Recently, Gilgamesh found that he's almost lack of swords in his vault, so he wants to forge a lot of swords with different shapes. He command you to forge for him!

Gilgamesh's sword can only be forged by triangle. Different triangle can be forged into a unique sword. He will give you the intervals of the edges of triangles, you have to calculate how many swords with different shape can he get?

Gilgamesh threats you with his "Gate of Babylon".

You are given four positive integer $A\le B\le C\le D$, you're going to count how many triangle that can be build by edges with length $x,\ y,\ z$, where $A\le x\le B,\ B\le y\le C,\ C\le z\le D$.

For example: $A=1,\ B=2,\ C=3,\ D=4$

You can build triangles with edges : $(x,y,z)\in \{(1,3,3),\ (2,2,3),\ (2,3,3),\ (2,3,4)\}$.

So the answer is 4.

Input

The first line contains one integer $T$, there are $T$ testcases below.

For each testcase, the four integer $A,\ B,\ C,\ D$ is given respectively.

$1\le T\le 100$.

$1\le A\le B\le C\le D\le 5\times 10^4$.

Output

For each testcase, output its answer, followed by a newline character.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

1. Both C and C++ are allowed. Solving problems with other languages (e.g. python, java) are forbidden, otherwise you'll get zero point.

2. Paper references, electronic devices, or other items that may contain any information relative to this exam are not allowed.

3. Before leaving, please tell TAs, we'll check if your accepted / partially accepted submissions are all written in C or C++. After you pass the check, you may sign your name as a record and leave.

4. The score of each problem is shown below:

   • 12536: 5 points

   • 12661: 5 points

   • 12797: 6.5 points

   • 12712: 5 points

If you get partially correct in a problem, your score of the problem will be

• score of the problem * number of testcases you passed / number of testcases

For example, if score of a problem is 10 points and the problem contains 6 testcases. If you pass the 3 testcases, you'll get 10*3/6=5 points on this problem.

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss