Description

Wild cats take care of each other in the wild. However, when winter comes, the preys are not enough to feed all the cats. Therefore, the cats dine according to the order of their occupations. The order is as follows:
1. elder
2. nursy
3. kitty
4. warrior
5. apprentice
6. medicent
7. deputy
8. leader

In the tradition of the cat society, three different cats serve as the medicent, the deputy, and the leader respectively.
As for the other cats, except that the apprentices have the dining priority of the young over the old, for the other occupations, the old have higher priority. If the occupations and the ages of two or more cats are the same, they will dine in lexicographic order according to their names.

Input

There are multiple test cases.

The first line of each test case contains two integers N and M, indicating the number of cats and the portions of food respectively, where 0<N,M<=10000.

The next N lines are the information of each cat, including name, occupation, and age.
The length of the names will not exceed 30 letters and will contain no spaces.

Output

Please output the cats that could eat the food in order, each name a line.

Sample Input  Download

Sample Output  Download

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

Discuss

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

Discuss

Description

The 15-puzzle is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. The goal of this problem is to transform the arrangement of tiles from the initial arrangement to a goal arrangement.

The legal moves are the moves in which the tiles adjacent to the empty tile are moved to either left, right, up, or down.

Your goal is to find the minimum move to solve the problem.

ouo.

hint

Using BFS/DFS to find answer may exceed memory limit and time limit of some test cases, so we recommend using A* algorithm,  which is more efficient. In A* algorithm, it determine the direction of searching by “steps until now + heuristic value”.

A* algorithm: https://en.wikipedia.org/wiki/A*_search_algorithm

To improve heuristic function, you can adopt manhattan distance with Linear Conflict.

Manhattan distance: https://en.wikipedia.org/wiki/Taxicab_geometry

Linear Conflict: The tile set(t1, t2) is linear conflict if they have same goal row(column), and they are now in that row(column), but they are blocked by each other. A set of lenear conflict will cause at least two extra steps.

Input

Input contains 4 lines, each line has 4 numbers.

The given puzzle is guaranteed to contain numbers from 0 ~ 15.

The zero denotes the empty tile.

It is guaranteed that the given puzzle is solvable.

Output

Output the minimum move to solve the puzzle.

Sample Input  Download

Sample Output  Download

Discuss

Description

There’s a numberline. Initially, no point is lying on it.
Given N queries, each is one of the following two types:
1 x: Add a point x on the numberline. If x is already lying on the numberline, remove it instead.

2 x: There are a lot of segments, separated by the points on the numberline. You have to answer the length of the segments that x is lying on. If x is the endpoints of two segments, x is considered lying on the right one. Furthermore, if the length of the segment is infinite, output −1.

Constraints

• 1 ≤ N ≤ 100000
• 1 ≤ x ≤ 1000000000

Input

The first line contains a integer N represents the number of queries.
In the following N lines, each contains two integers, represents the query.

Output

For each query of type 2, outputs its answer line by line.

Sample Input  Download

Sample Output  Download

Discuss

Description

Given a sequence A = a₁, ..., a_N, answer Q queries.

In the i-th query, you are given two integers L_i and R_i, and have to find the maximum mode of A[L_i...R_i].

It is guaranteed for each i = 1, ..., Q - 1, L_i ≤ L_i+1 and R_i ≤ R_i+1.

scanf and printf are recommended over cin and cout to speed up input and output.

Input

The first line of the input contains an integer T, the number of testcases.

The first line of each testcase contains two integers N and Q, the length of A and the number of queries.

The second line of each testcase contains N integers, a₁, ..., a_N, the sequence A.

Each of the next Q lines contains two integers L_i and R_i, the range of the subsequence in the i-th query.

Constraints

There are six subtasks. For each subtask,

1. N ≤ 20, Q ≤ 10
2. N ≤ 20, Q ≤ 10
3. N ≤ 2000, Q ≤ 1000
4. N ≤ 2000, Q ≤ 1000
5. N ≤ 200000, Q ≤ 100000
6. N ≤ 200000, Q ≤ 100000

In every subtask, 1 ≤ T ≤ 10, 1 ≤ a_i ≤ 10⁹, 1 ≤ L_i ≤ R_i ≤ N.

Output

For each query in each testcase, please print the maximum mode of A[L_i...R_i] followed by a newline.

Sample Input  Download

Sample Output  Download

Discuss

Description

A cat and a mouse are trapped in a 20x20 maze. Each cell is one of the following types:

• 'S': starting position
• 'E': exit position
• '#': wall
• '.': empty cell

Two cells are adjacent if they share a side, that is, if one is directly above, below, to the left of, or to the right of the other.

The cat and the mouse are not allowed to be in the same cell at any time.

The cat starts at 'S' and the mouse starts at 'E'.

Initially, the entire maze is unknown to both the cat and the mouse.

The game proceeds in turns. In each turn, the cat and the mouse act in the following order:

1. The cat sees and memorizes the adjacent cells.
2. The cat moves to a non-wall adjacent cell, or stays in the same cell.
3. The mouse sees and memorizes the adjacent cells.
4. The mouse moves to a non-wall adjacent cell, or stays in the same cell.

They know the current turn number (step), the position of the other, and the position of the exit.

Your goal is to make the cat reach the exit cell within 4000 turns. This is guaranteed to be possible for all given test cases.

HINT

The following strategy works.

Steps 0–799: The cat explores all reachable cells without entering the mouse’s cell. (The mouse stays still.)

Steps 800–1599: The cat moves to a discovered reachable that is farthest from 'E'.

Steps 1600–2399: The mouse explores all reachable cells without entering the cat’s cell.

Steps 2400–3199: The mouse moves to a discovered reachable cell that does not block the cat from reaching 'E'.

• To find such a cell, temporarily treat each candidate cell as a wall and check whether the cat can still reach 'E'.

Steps 3200–3999: The cat moves to 'E'.

Code

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

const int SIZE = 20;
const int MAX_STEPS = 4000;
const int INF = 1000000000;

enum class Direction {
    Up,
    Down,
    Left,
    Right,
    Stay
};

struct Pos {
    int r, c;

    Pos operator+(Direction dir) const {
        switch (dir) {
            case Direction::Up:
                return {r - 1, c};
            case Direction::Down:
                return {r + 1, c};
            case Direction::Left:
                return {r, c - 1};
            case Direction::Right:
                return {r, c + 1};
        }

        return {r, c}; // Direction::Stay
    }

    bool operator==(const Pos& other) const {
        return r == other.r and c == other.c;
    }

    bool operator!=(const Pos& other) const {
        return r != other.r or c != other.c;
    }
};

class MemoryMap {
private:
    char memory[SIZE][SIZE];
    int visited[SIZE][SIZE];

public:
    MemoryMap(Pos startPos, char startCell) {
        fill(memory[0], memory[0] + SIZE * SIZE, '?');
        memory[startPos.r][startPos.c] = startCell;

        resetVisited(startPos);
    }

    char getCell(Pos p) const {
        return memory[p.r][p.c];
    }

    void setCell(Pos p, char cell) {
        memory[p.r][p.c] = cell;
    }

    bool knownOpen(Pos p) const {
        return memory[p.r][p.c] != '#' and memory[p.r][p.c] != '?';
    }

    void resetVisited(Pos pos) {
        fill(visited[0], visited[0] + SIZE * SIZE, 0);
        visited[pos.r][pos.c] = 2;
    }

    // Performs one step of a DFS walk and returns the chosen direction.
    // Remember to call resetVisited(pos) before starting a new DFS search.
    Direction dfsNextDirection(Pos& pos, Pos target, Pos untouchable) {
        /*
            This method performs one step of a DFS walk from pos through known open cells.
            It avoids untouchable when visiting new cells, and stops when it reaches target.

            The parameter pos is the current position of the player. This method updates
            pos to the next position chosen by DFS, and returns the direction of that move.

            The parameter untouchable is usually the position of the other player
            (cat / mouse).

            To use this method:
            1. Call resetVisited(pos) before starting a new DFS search.
            2. Repeatedly call dfsNextDirection(pos, target, untouchable).
            3. If target or untouchable changes, call resetVisited(pos) before continuing.
            4. If target is reached, this method returns Direction::Stay.
            5. To explore all reachable known cells, use an impossible target such as {-1, -1}.
        */

        Direction dirs[4] = {
            Direction::Up,
            Direction::Down,
            Direction::Left,
            Direction::Right
        };

        if (pos == target) {
            return Direction::Stay;
        }

        for (int i = 0; i < 4; i++) {
            Pos p = pos + dirs[i];

            if (knownOpen(p) and visited[p.r][p.c] == 0 and p != untouchable) {
                visited[p.r][p.c] = visited[pos.r][pos.c] + 1;
                pos = p;
                return dirs[i];
            }
        }

        for (int i = 0; i < 4; i++) {
            Pos p = pos + dirs[i];

            if (visited[p.r][p.c] == visited[pos.r][pos.c] - 1) {
                visited[pos.r][pos.c] = -1;
                pos = p;
                return dirs[i];
            }
        }

        return Direction::Stay;
    }

    // TODO: Use BFS to compute shortest distances from start to all known open cells.
    void computeDistance(Pos start, int distance[SIZE][SIZE]) const;
};

class Cat {
private:
    MemoryMap memory_map;
    Pos pos;
    Pos target;

    // HINT(optional): You may use these variables if you need them.
    int phase;
    int direction;
    int state[SIZE];

public:
    // TODO: Initialize the cat.
    Cat(Pos startPos);
    // TODO: Update the cat's memory using the visible neighboring cells.
    void see(char up, char down, char left, char right);
    // TODO: Move the cat and return the chosen direction.
    Direction move(int step, Pos mousePos, Pos exitPos);
};

class Mouse {
private:
    MemoryMap memory_map;
    Pos pos;
    Pos target;

    // HINT(optional): You may use these variables if you need them.
    int phase;
    int direction;
    int state[SIZE];

public:
    // TODO: Initialize the mouse.
    Mouse(Pos startPos);
    // TODO: Update the mouse's memory using the visible neighboring cells.
    void see(char up, char down, char left, char right);
    // TODO: Move the mouse and return the chosen direction.
    Direction move(int step, Pos catPos, Pos exitPos);
};

class Game {
private:
    const vector<string> maze;
    Pos catPos;
    Cat cat;
    Pos exitPos;
    Pos mousePos;
    Mouse mouse;
    string catSteps;
    string mouseSteps;

    char getCell(Pos p) const {
        return maze[p.r][p.c];
    }

    Pos findCell(char cell) const {
        for (int i = 0; i < SIZE; i++) {
            if (auto it = maze[i].find(cell); it != string::npos) {
                return {i, int(it)};
            }
        }

        return {-1, -1};
    }

    bool success() const {
        return catPos == exitPos;
    }

    char directionToChar(Direction dir) const {
        switch (dir) {
            case Direction::Up:
                return 'U';
            case Direction::Down:
                return 'D';
            case Direction::Left:
                return 'L';
            case Direction::Right:
                return 'R';
            case Direction::Stay:
                return 'S';
        }

        return 'S';
    }

    bool illegal(Pos p) const {
        return p.r < 0 or p.r >= SIZE or p.c < 0 or p.c >= SIZE or getCell(p) == '#';
    }

public:
    Game(const vector<string>& inputMaze)
        : maze(inputMaze),
          catPos(findCell('S')),
          cat(catPos),
          exitPos(findCell('E')),
          mousePos(exitPos),
          mouse(mousePos)
    {}

    void play() {
        for (int step = 0; step < MAX_STEPS; step++) {
            cat.see(
                getCell(catPos + Direction::Up),
                getCell(catPos + Direction::Down),
                getCell(catPos + Direction::Left),
                getCell(catPos + Direction::Right)
            );

            Direction catDir = cat.move(step, mousePos, exitPos);
            catSteps += directionToChar(catDir);
            catPos = catPos + catDir;

            if (catPos == mousePos or illegal(catPos) or success()) {
                break;
            }

            mouse.see(
                getCell(mousePos + Direction::Up),
                getCell(mousePos + Direction::Down),
                getCell(mousePos + Direction::Left),
                getCell(mousePos + Direction::Right)
            );

            Direction mouseDir = mouse.move(step, catPos, exitPos);
            mouseSteps += directionToChar(mouseDir);
            mousePos = mousePos + mouseDir;

            if (mousePos == catPos or illegal(mousePos)) {
                break;
            }
        }

        cout << catSteps << '\n' << mouseSteps << '\n';
    }
};

int main() {
    vector<string> inputMaze(SIZE);

    for (string& row : inputMaze) {
        cin >> row;
    }

    Game game(inputMaze);
    game.play();

    return 0;
}

Input

(The input is already handled by the provided C++ code.)

The input contains exactly 20 lines.

Each line contains exactly 20 characters, representing the maze.

The maze contains exactly one 'S' and exactly one 'E'.

The outer boundary of the maze is guaranteed to be '#'. (See the sample input for an example.)

Subtasks

• Testcase 1 is the sample input.
• Testcase 2, 3, and 4 have the exit cell adjacent to at least two empty cells.
• Testcase 5, 6, 7, and 8 have no extra constraints.

Output

(The output is already handled by the provided C++ code.)

The provided main function prints two lines:

1. The cat's moves.
2. The mouse's moves.

Each move is represented by one character:

• 'U': move up
• 'D': move down
• 'L': move left
• 'R': move right
• 'S': stay in the same cell

The special judge accepts the output if, after simulating the two strings, all moves are legal, the cat and mouse are never in the same cell, and the cat reaches 'E' within 4000 steps. Otherwise, the special judge rejects the output.

Sample Input  Download

Sample Output  Download

Discuss