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

Given an integer sequence, say {6, 1, 3, 4, 5, 2}, can we sort the sequence by keeping swapping the first number with its two neighbors: the second number and the last number ? 

For example, Swap the first number 6 and with the last number 2 to get {2, 1, 3, 4, 5, 6}, and then swap the first number 2 and the second number 1 to get {1, 2, 3, 4, 5, 6}, and we get the sequence sorted.

In function.h we define a class called SwapSort. A constructor and a member function show_solutions are implemented. Your task is to complete the implementation of the following two functions:

1. set<State> extend(State s);
A State is defined as using State = vector<int>;
For some State s, we may extend it by swapping the first number with the second one, or swapping the first number with the last one. Therefore, from State s we may generate two new states, and insert them into a set.

2. void solve(int steps);
This function tries to solve the problem in a number of swaps specified by steps. The found solutions are stored in the class member set<list<State>> _solutions;

Notice that, no duplicate states are allowed in a solution.

You need to implement the two functions in function.cpp

main.cpp

#include "function.h" int main() { State s;// = {2, 1, 3}; int e; while (cin >> e) { // press Ctrl + Z to end the input s.push_back(e); } SwapSort prob1(s); prob1.solve(4); prob1.show_solutions(); cout << "\n"; }

function.h

#ifndef _SWAPSORT_ #define _SWAPSORT_ #include <iostream> #include <vector> #include <set> #include <list> #include <algorithm> using namespace std; using State = vector<int>; class SwapSort { private: set<list<State>> _paths; set<list<State>> _solutions; set<State> _explored; public: SwapSort(State init) { list<State> ls; ls.push_back(init); _paths.insert(ls); } void show_solutions() { if (_solutions.size()==0) { cout << "No solution.\n"; } else { for (auto p : _solutions) { for (auto s : p) { for (auto i : s) { cout << i << " "; } cout << "-> "; } cout << ".\n"; } } } set<State> extend(State s); void solve(int steps); }; #endif

function.cpp

#include "function.h" set<State> SwapSort::extend(State s) { set<State> SS; // your code here return SS; } void SwapSort::solve(int steps) { while (steps>0) { set<list<State>> oldPaths; set<list<State>> newPaths; for (auto p : _paths) { // your code here } for (auto p : oldPaths) { _paths.erase(p); } for (auto p : newPaths) { _paths.insert(p); } --steps; } }

Input

An integer sequence, separated by spaces. End by EOF.

Output

The output will be generated by function.h

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

This problem will help you understand how to use std::map.

http://en.cppreference.com/w/cpp/container/map

Notice, this time, first and last is [first, last].

目前有五個測資，第三筆測資不算，答題測資看另外四筆

Input

The input consist of series of command. Each commands is insert, range output or range erase.

insert: inserts a string (cmd) with the key (key) to map. If the key has already existed, insert the cmd at the begining of string (the string which the key belongs).

For example,

insert 0 "abc"

insert 1 "def"

the map should contain "abc", "def".

insert 0 "xyz"

the map should contain "xyzabc", "def".

range output: outputs the string from key (first) to key (last). Output a space character (' ') after printing an element.

range erase: erase the string from key (first) to key (last).

operator<<: outputs all strings in map. From the smallest key to biggest key. Output a space character (' ') after printing an element.

Output

Complete insert, output, erase and operator<<.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

This problem will help you understand how to use std::set and comparator.

e.g., std::set<std::vector<int>>

http://en.cppreference.com/w/cpp/container/set

Input

How to compare the integer sequence (calculate the key of an integer sequence):

• get the length of integer sequence (size)
• key value=[first element]*(size)+[second element]*(size-1)+[third element]*(size-2)+...+[last element]*1
• compare the key value. Small key value is smaller.
• if the length of a integer sequence is 0, the key value is 0.
• e.g., the key of an integer sequence "3 9 -1 3 -6" is 48 (3*5+9*4+(-1)*3+3*2+(-6)*1)

The input consist of series of command. Each commands is insert, range_out or output.

​insert: inserts an integer sequence (each value is greater than -6 and smaller than 11, stop reading from cin when value is 0). If the key has already existed, then

• output "exist\n"
• erase the integer sequence from set
• reverse the integer sequence (from input)
• insert the reversed integer sequence

For example,

insert 3 9 -1 3 -6 0

The set should contain 3 9 -1 3 -6.

insert 9 -2 6 6 0

The set should contain 6 6 -2 9.

range_out: outputs all integer sequences from the integer sequence (first key) to the integer sequence (second key) of set (including the second key). First key and second key are read from input (each value is greater than -6 and smaller than 11, stop reading from cin when value is 0).

For example,

insert 2 -5 -5 0

insert 3 9 -1 3 -6 0

insert 7 6 1 2 0

insert 10 10 10 2 0

range_out -5 0 10 9 2 0

It should output

3 9 -1 3 -6

7 6 1 2

For example,

insert 2 -5 -5 0

insert 3 9 -1 3 -6 0

insert 7 6 1 2 0

insert 10 10 10 2 0

range_out -5 0 10 10 10 0

It should output

3 9 -1 3 -6

7 6 1 2

output: outputs all integer sequences from the smallest key to the biggest key of set. Output a space character (' ') after printing an integer. Output a newline character ('\n') after printing all elements of a key.

Output

Complete insert, range output and output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a tree, count the number of leaves in this tree. Each node has unique integer identification (ID), but all IDs may not be consecutive.

Input

There are multiple test cases. Each test case begins with an integer N (1 <= N <=1000). In the following N lines, each line has two integer a and b (1 <= a,b <= 1000), indicating node a is node b’s parent. The next line contains an integer R, which represents the root of the Tree. You can assume that all the nodes will be on the same tree. The input is terminated by N = 0.

Output

Print the number of the leaves for each test case.

Hint: All leaves have no children!

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

Price of fertilizers in the world are raising! Adding Jinkela in fertilizer, one bag can cover two bags!!

People from America, Africa, Japan are lining up in a queue to buy Jinkela. Each person is given a unique id x. The country of each person can be identified by the remainder of his id divided by 3. If x mod 3 = 0, he is from America; if x mod 3 = 1, he is from Africa; if x mod 3=2, he is from Japan. Lining up is tedious, everyone wants to cut in line! These American, African, and Japanese follow some rule when they cut in line:

When a person enters the queue,

1. If the queue is empty, he becomes the first person in the queue.
2. If there isn't anyone who comes from the same country in the queue, he becomes the last person in the queue.
3. Otherwise, of all people coming from the same country in the queue, he finds the last of them and lines up after him ( and possibly cuts in line ).

After a person buys Jinkela, he leaves the queue immediately and will not enter the queue again.

You are curious about the order people get their Jinkela. Given the status of the queue. Whenever someone leaves the queue, output his id.

Refer to the sample IO for example if you don't understand the rule.

For example, assume the queue is empty initially.

• ENQUEUE 0: An American with id 0 enters the queue. Since the queue is empty, he becomes the first person in the queue

queue: 0

• ENQUEUE 1: An African with id 1 enters the queue. Since there isn't any other African in the queue, he becomes the last person in the queue.

queue: 0 1

• ENQUEUE 3: An American with id 3 enters the queue. Since he finds an American (id=0) in the line, he lines up right after him.

queue: 0 3 1

• ENQUEUE 6: An American with id 6 enters the line. He finds two American (id=0, id=3) in the line, where American with id 3 is the last one, he lines up after American with id 3.

queue: 0 3 6 1

• DEQUEUE: The first person leaves the line. Output his id(0).

queue: 3 6 1 output: 0

Input

The status of queue is represented as several commands.

The first line of Input consists of a single integer n (n ≦ 10^6), indicating there are n commands in total.

The following n lines are the commands. There are two kinds of commands:

• ENQUEUE x: person with id x enters the queue. x is an integer, 0 ≦ x ≦ 10^6
• DEQUEUE: the first person in the queue buys his Jinkela and leaves the queue

Output

For each DEQUEUE command, please output the id of person who leaves the queue.

Each output occupies a single line.

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

You are playing a game. The goal of this game is to kill the monster when you are still alive (HP > 0, HP = health point). The monster is dead if and only if its HP <= 0.

This game consists of rounds, and you go first in each round.

You have 3 options in each round:

1. ATTACK. This will deduct the monster's HP. If your damage point is p, then you can deduct p monster's HP.
2. HEAL. You can recover some of your HP, but it can't exceed your max HP.
3. Level-up. Level-up might enhance the effect of attacking or healing, but if you are not lucky enough, sometimes it will deduct the effect of attacking and healing. Thus, choosing to level-up is not always a good choice. If you have reached max level, taking this action makes no effect.

In each round, the monster will attack you once with a fixed damage point.

You start the game with full HP and level 1. What is the minimun number of rounds you need to kill the monster?

Input

First line contains 4 numbers L, HP, MHP, MDMG.

• L = max level
• HP = your max HP
• MHP = monster's HP in the beginning of game
• MDMG = monster's damage point

The next L lines describes each level, i-th line of them describes level i. Each of them consists of two numbers, DMG and HL.

• DMG = your damage point when you use ATTACK at level i
• HL = amount of HP you can recover when you use HEAL at level i

Limits:

• L <= 15
• HP <= 300
• MHP <= 400
• MDMG <= 10000
• DMG <= 10000
• HL <= 50

Output

Print a single integer, denoting the mininum number of steps you need to kill the monster.

If you are unable to beat the monster, print -1.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Give N words 

List words that cannot be the anagram to other words (unique words).

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once. By Wikipedia.

Example:

"earth" <=> "heart"

"Silent" <=> "listen"

And those unique words are the words that cannot be any word's anagrams in the given words.

Hint: sort, map, set, ...

Input

Give a number N means N string.

Next N line be the words.  

N <= 10⁶

Input would be mixed with uppercase and lowercase  ( But:  "Input" = "input" = "iNPuT" for anagram) 

Output

Output those unique words in alphabetical order.

Sample Input  Download

Sample Output  Download

Tags

Discuss