Description

A string is said to be valid if it matches one of the following rules:

(1) The string is an empty string.

(2) If a string S is valid, then {S}, [S], (S) and <S> are valid.

(3) If strings S1 and S2 are both valid, then S1S2 is valid.

Given a string consisting of parentheses, determine if it is a valid string.

Input

The first line of the input contains an integer N (N ≤ 1000) denoting the number of test cases followed by. Each of the next N lines corresponds to a test case, which contains a string consisting of parentheses, and the maximum string length will be no more than 1000. Note that an empty string (a line which contains the newline character only) may be contained in the input and it should be considered as a valid string according to rule (1).

For case 1,2 : 1<N<100. 0<=length<100

For case 3,4 : 1<N<1000. 0<=length<1000

Output

For each test case, print “Case i:” and then “Yes” or “No” to indicate that the string is valid or not, separated by a space character. i is the test case number starting from 1.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Niflheimr is playing Minecraft recently. He occupies a lot of towns, and there are many diamonds inside some of those towns.

Whenever he runs out of diamond, he has to figure out the nearest town with diamonds from his current location.

Doing this task every time waste a lot of time. He asks you to help him for the calculation. For every town, find the shortest distance to get diamonds from a nearby town which has diamonds. If the town itself has diamonds, the distance would be 0.

Hint: Use BFS (Breadth First Search) and std::queue.

If you are not familiar with BFS, you should take a look at the following article:

http://alrightchiu.github.io/SecondRound/graph-breadth-first-searchbfsguang-du-you-xian-sou-xun.html

[IMPORTANT] For those almost run out of time, maybe this note can help you figure out BFS and solve this problem faster!

You are provided with the following code:

#include <queue>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// G[i] is the neighbor towns of town i
vector<int> diamondTowns;
vector<int> G[100005];
int Dist[100005];

struct node {
    int id;
    int dist;
    node(int id, int l) {
        this->id = id;
        this->dist = l;
    }
};

int main() {
    int N, M, K;
    cin >> N >> M >> K;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for (int i = 0; i < K; i++) {
        int x;
        cin >> x;
        diamondTowns.push_back(x);
    }
    fill(Dist, Dist+100005, -1);

    queue<node> Q;

    // [TODO] complete the task!

    // Output
    for (int i = 1; i <= N; i++) {
        cout << Dist[i] << '\n';
    }
    return 0;
}

 You may take it as reference. You are not required to use this code, though.

Input

First line of input contains three integer N, M, K, denoting the number of towns, the amount of roads between towns and the number of towns which has diamond.

All the towns are numbered from 1 to N.

For the next M lines, each of them contains two integer a, b, meaning there is a road between a and b. All the roads are bidirectional, and the length of these roads are all 1.

The last line of input contains K distinct integers, denoting the towns which has diamonds.

It is guaranteed that:

• 1 <= K <= N <= 10⁵
• 1 <= M <= min(10⁶, N*(N+1)/2)
• All the towns can reach each other, i.e. the graph is connected.

Output

Output consists of N lines.

For i-th line, output the shortest distance Niflheimr has to travel from town i to get a diamond.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Hurry! Hurry! Hurry! Wanted!!!

Rumor has it that students in NTHU and NCTU are very friendly. Whenever someone is looking for a Chinese tutor ( especially when that person is in a hurry ), students will recommend their classmates if they know their classmates are capable of being a nice Chinese tutor. Students will tag their classmates in a special format : "classmate_name the school_name pokemon_name"

For example, "王小明清大小鋸鱷" would be "Wangxiaoming the NTHU Waninoko" in English.

Since students in NTHU and NCTU are well educated, they will choose a suitable water type pokemon based on beginning rhymes. They organized a beginning rhymes list. Students can find what pokemon their classmates should be by checking the list. For classmates who can't find a suitable pokemon in the list, we say that they are not good at Chinese.

For example, since WangXiaoMing starts with "Wa", studnets will find a pokemon whose name starts with "Wa".

You want to recommend some of your classmates. Given the names of your classmates and the schools they study in. Please tag your classmates using the special format mentioned above.

Input

The first line contains a single integer n, meaning that you have n classmates to recommend.

The n following lines. Each consists of two strings : name of your classmate and the school he studies in.

It is guarenteed that ...

• lengths of your classmates' names and schools' names will be more than 1, less than 100.
• Every name of your classmates contains english alphabets only, starting with an upper-case character, followed by lower-case characters.

Output

For each of your classmates,

• If you can find a suitable pokemon based on the list, please output using the special format : "classmate_name the school_name pokemon_name" (without quotation mark)
• If you cannot find a suitable pokemon based on the list, please output "classmate_name is looking for a Chinese tutor, too!" (without quotation mark)

Each output occupies one line.

Notes for Sample IO

• Since "Tanner" doesn't start with "Tapu", so he isn't "Tanner the NCTU Tapu Fini"
• According to the list, names starting with "Pi" or "Pe" can be Pikachu, therefore "Peter" is "Peter the NCTU Pikachu"

Useless Hints

Why is Pikachu in the list? Go google search for "surfing pikachu" XDD.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a sequence of N numbers.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Consecutive means continuous, all elements in the subsequence should be continuous in the original sequence.

For example, if the given sequence is {3, 4, 5},
then all possible consecutive subsequences are {3}, {3, 4}, {3, 4, 5}, {4}, {4, 5}, {5}.

A "Stabled Consecutive Subsequence" is a consecutive subsequence that the "maximum value in the subsequence" minus the "minimum value in the subsequence" is less than or equal to a given number K.

Your goal is to find the number of "Stabled Consecutive Subsequences".

ouo.

Input

There are 2 numbers N, K in the first line, separated by the space character.

There are N numbers A_i in the second line, separated by the space characters.

There are 12 test cases in this problem:

For all test cases, it is guaranteed that:
1 <= N <= 10⁷,
1 <= K <= 10⁹,
1 <= Ai <= 10⁹,
and all numbers in the sequence are unique.

For test cases 1 ~ 3,
1 <= N <= 500, that is, time complexity O(N³) will pass these cases.

For test cases 4 ~ 6,
1 <= N <= 5000, that is, time complexity O(N²) will pass these cases.

For test cases 7 ~ 10,
1 <= N <= 500000, that is, time complexity O(Nlog₂N) will pass these cases.

For test cases 11 ~ 12,
1 <= N <= 10⁷, that is, time complexity O(N) will pass these cases.

Output

Output contains only 1 line.

Output the number of "Stabled Consecutive Subsequences" with the given N, K numbers and sequence, with a newline character.

Note that the answer is in the range of [0, 2⁶²].

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Note: This problem is almost the same as social distance, but there are no walls in this problem.

(Don't forget to keep social distance during lifesaving training ><)

Since we are now undergoing the covid-19 pandemic, the CECC(疫情指揮中心) announce that two people should keep space between themselves at a social distance at s meters.

Inside a classroom, there are n seats numbered from 1 to n in a row and there are no walls. m students numbered from 1 to m are coming to class. The distance between to neighboring seats is 1 meter. Initially there are no people on the seats.

Each student takes a seat and leaves the seat at some time and they will take the seat that is farthest from the other people. If there are multiple seats to choose from, he or she will choose the leftmost one (i.e. the seat with smallest number).

Let D be minimum distance between any two people during the whole class. If D >= s then we say the class is safe, otherwise it is not safe.

Given the time when each student enters and leaves classroom. Your professor wants to know whether he follows the CECC's rules , so he wants you to write a program to calculate the value of D and tells him if the class is safe or not.

Explanation for sample IO

Let d be the minimum distance between any two people at a specific time. The following are the first 6 moments.

0. _ _ _ _ _ _ _ _ _, d = INF

1. 1 _ _ _ _ _ _ _ _, d = INF

2. 1 _ _ _ _ _ _ _ 2, d = 8

3. 1 _ _ _ 3 _ _ _ 2, d = 4

4. 1 _ 4 _ 3 _ _ _ 2, d = 2

5. _ _ 4 _ 3 _ _ _ 2, d = 2

6. 5 _ 4 _ 3 _ _ _ 2, d = 2

During the whole class min d = 2, therefore D = 2 < S = 5, it is not safe.

Input

The first line are three integers n m s (mentioned in problem description).

Then there are 2 x m lines, each line represents the event that one student enters or leaves the classroom. For the k-th line:

• i x means that the student with number x comes in the classroom and takes a seat at time k

• o x means that the student with number x leaves the seat and goes out the classroom at time k

It is guaranteed that:

• A student will never comes back to class after he or she leaves

• When a student leaves, he or she must be in the classroom (i.e. for a student x, i x must appear before o x)

Technical Restrictions:

• For all test cases, m <= n

• Test 1 - 3: Small test cases, can be solved with brute force

  • Test 1: 1 <= n, m, S <= 30

  • Test 2 - 3: 1 <= n, m, S <= 2000

• Test 4 - 7: It is guaranteed that the first two students who enter the classroom are same as the last two student to leave the classroom

  • Test 4: 1 <= n, m, S <= 30

  • Test 5: 1 <= m <= 2000 and 1 <= n, S <= 10^5

  • Test 6-8: 1 <= m <= 10^5 and 1 <= n, S <= 10^9

• Test 8 - 12: Good luck and have fun

  • 1 <= m <= 10^5 and 1 <= n, S <= 10^9

Output

Please output D (If D is infinity, then print "INF").  Please output "YES" if it is safe and "NO" if it is not safe.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

下載後將副檔名改成zip（.cpp和.h為相同檔案，下載一個即可）

更改副檔名教學 : 

打開任意資料夾 >> 點擊上方 "檢視" >> 勾選 "副檔名" >> 將.cpp或.h更改成.zip

解壓縮 >> 點進 reference 目錄 >> 點進 en 目錄 >> Main_Page.html  就可以看到完整的cpprefernce.com離線版

===================================================================================================

Download the partial judge code and change the extension to .zip. (.cpp and .h is the same file. Donwload one of them is enough.)

Open the folder with the file in it >> click "view" >> check "File name extensions" >> change .cpp or .h to .zip
Unzip the file >> click "reference" > click "en" >> open "Main_Page.html". Then you can use the offline version of cppreference.com.

Input

Output

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss