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

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.

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

It is highly recommended to use IO optimization to avoid TLE in this problems.

The status of queue is represented as several commands.

Each line contains one of the following commands:

• ENQUEUE x: person with id x enters the queue. x is an integer, 0 ≦ x ≦ 3*10^8
• DEQUEUE: the first person in the queue buys his Jinkela and leaves the queue
• POLICEWATCHING: The police is watching, no one can cut in line now!
• DONUTSTIME: The police is gone. 

Please keep reading input until reach EOF.

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

A Neo-Stack (Neo Armstrong Cyclone Jet Armstrong Stack) supports the following functions. Your goal is to Implement a Neo-Stack.

• push(x): push an integer x into the Neo-Stack.

• top(): return the top-most (the most recent element that is pushed) in the Neo-Stack.

• pop(): remove the top-most element in the Neo-Stack.

• maxElement(): return the maximum element currently in the Neo-Stack.

• popMax(): remove the maximum element currently in the Neo-Stack. If there are multiple maximum elements, remove only the top-most maximum element.

• minElement(): return the minimum element currently in the Neo-Stack.

• popMin(): remove the minimum element currently in the Neo-Stack. If there are multiple minimum elements, remove only the top-most minimum element.

(↑ Maybe useful PPAP meme on how to implement Neo-Stack. Ignore this meme if you can't get any idea from Mr. PPAP.)

(APOLOGIZE: Sorry I(Problem setter) don't have enough time to draw a nice Neo Armstrong Cyclone Jet Armstrong Stack. QAQ)

You are encouraged to implement Neo-Stack as a class, for example:

 class NeoStack
 {
 private:
     /* anything you need */
     /* using STL is welcome */
     
 public:
     NeoStack() {/* ... */}
     ~NeoStack() {/* ... */}
     void push(int x) {/* ... */}
     void pop() {/* ... */}
     int top() {/* ... */}
     int maxElement() {/* ... */}
     void popMax() {/* ... */}
     int minElement() {/* ... */}
     void popMin() {/* ... */}
 };

Given a sequence of functions mentioned above, please output the result when top() or maxElement() or minElement() is called.

Note : If your algorithm is O(lgn) but get TLE, you can use IO optimization

Input

The first line contains an integer T (1 ≦ T ≦ 10), indicating that there will be T test case in total.

The first line of each test case contains a integer n (1 ≦ n ≦ 1000000), indicating that there will be n functions to be called in this test case.

The next n lines will be the functions. The functions are presented in the following format:

• push x : push integer x into Neo-Stack, 1 ≦ x ≦ 10^6

• top : print the top-most element in Neo-Stack in a line

• pop : remove the top-most element in Neo-Stack

• maxElement : print the maximum element in Neo-Stack in a line

• popMax : remove the maximum element in Neo-Stack. If there are multiple maximum elements, please remove the top-most one.

• minElement : print the minimum element in Neo-Stack in a line

• popMin : remove the minimum element in Neo-Stack. If there are multiple minimum elements, please remove the top-most one.

It is guaranteed that functions EXCEPT push will not be called when the Neo-Stack is empty.

Important Notes (on how to get AC on more test cases )

There are five test cases in this problem.

In terms of test case size :

• The first test case is small ( n ≦ 100 ). Mr. PPAP said it is possible to AC this test case using brute force.

• The second to fifth test case are big ( it is guaranteed that T x n ≦ 4000000 ). Mr. PPAP suggested that the complexity of your solution should be O(lg n).

In terms of test case design :

• In the first test case : Every function will appear in the first test case. Mr. PPAP said that the test case is very small, why not try brute force? (e.g. O(n) for each function)

• In the 2nd test case : Only push, pop, top, maxElement, will appear in the 2nd test case. However, the test case is big, Mr. PPAP said that complexity of each function should be less or equal to O(lg n).

• In the 3rd test case : Only push, pop, top, maxElement, popMax will appear in the 3rd test case. However the test case is still big.

• In the 4th test case : Only push, pop, top, maxElement, popMax, minElement will appear in the 4th test case. The test case is still big.

• In the 5th test case : It is a big test case with all kinds of function.

Output

For each test case:

• Please output "Case #i :"(without quotation mark) in the beginning for each test case, occupying a line, where i is the number of the test case. Notice that there is space before #i and no space after the colon(冒號).

• For top, maxElement, minElement, please output the required element in a line.

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