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

Tags

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

Tags

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
• '+': food 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.

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

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

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.

When the cat moves onto a cell with food, the food is eaten and the cell becomes empty immediately. 

When the mouse moves onto a cell with food, nothing happens and the cell remains a food cell.

Your goal is to make the cat eat all the food and then reach the exit cell within 9000 turns. This is guaranteed to be possible for all given test cases.

HINT

The following strategy works for the case that there is no food.

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 = 9000;
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.
    // Cells not reachable from start should have distance INF (1000000000).
    void computeDistance(Pos start, int distance[SIZE][SIZE]) const;

    // Finds a known open cell whose removal does not block the path from start to dest.
    Pos findUnblocked(Pos start, Pos dest) {
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                Pos p{i, j};
                if (not knownOpen(p) or p == start or p == dest) {
                    continue;
                }

                char old_cell = memory[i][j];
                memory[i][j] = '#';
                int distance[SIZE][SIZE];
                computeDistance(start, distance);
                memory[i][j] = old_cell;
                if (distance[dest.r][dest.c] != INF) {
                    return p;
                }
            }
        }

        return {-1, -1};
    }

    // Finds the farthest reachable cell from start.
    Pos findFarthest(Pos start) const {
        int distance[SIZE][SIZE];
        computeDistance(start, distance);

        Pos farthest = start;
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                if (distance[i][j] != INF and distance[farthest.r][farthest.c] < distance[i][j]) {
                    farthest = Pos{i, j};
                }
            }
        }

        return farthest;
    }
};

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:
    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];
    }

    void eatFood() {
        if (getCell(catPos) == '+') {
            maze[catPos.r][catPos.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 findCell('+') == Pos{-1, -1} && catPos == exitPos;
    }

    char stepChar(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';
    }

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 += stepChar(catDir);
            catPos = catPos + catDir;

            if (catPos == mousePos or getCell(catPos) == '#') {
                return;
            }

            eatFood();

            if (success()) {
                return;
            }

            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 += stepChar(mouseDir);
            mousePos = mousePos + mouseDir;

            if (mousePos == catPos or getCell(mousePos) == '#') {
                return;
            }
        }
    }

    string getCatSteps() const {
        return catSteps;
    }

    string getMouseSteps() const {
        return mouseSteps;
    }
};

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

    while (cin >> inputMaze[0]) {
        for (int i = 1; i < SIZE; i++) {
            cin >> inputMaze[i];
        }

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

        cout << game.getCatSteps() << '\n';
        cout << game.getMouseSteps() << '\n';
    }

    return 0;
}

Input

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

There may be multiple testcases in a single test.

Each testcase contains exactly 20 lines.

Each line of each testcase 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

• Test 1 has no food and no wall other than the outer border.
• Test 2 has no food and the exit cell is adjacent to at least two empty cells.
• Test 3 has no food.
• Test 4 has the exit cell adjacent to at least two non-wall cells, and one of them is an empty cell and is adjacent to the exit cell only.
• Test 5 has no extra constraints.

Output

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

For each testcase, output two strings:

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

Each character must be one of:

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

Each string must contain at most 9000 characters.

The special judge will simulate the game. You will receive AC if, for every testcase, the cat eats all food and then reaches 'E' within 9000 turns without either player moving into a wall or both players occupying the same cell.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

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

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

It is guaranteed for each i = 1, ..., Q - 1, L_i - 3 ≤ L_i+1 and R_i - 3 ≤ 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 three integers L_i, R_i, and K_i, the range and the order of the mode to report for the i-th query.

Constraints

There are five subtasks. For each subtask,

1. N ≤ 2000, Q ≤ 1000.
2. N ≤ 200000, Q ≤ 100000, K_i = 1 for every query, and L_i ≤ L_i+1 and R_i ≤ R_i+1 for each i = 1, ..., Q - 1.
3. N ≤ 200000, Q ≤ 100000, and L_i ≤ L_i+1 and R_i ≤ R_i+1 for each i = 1, ..., Q - 1.
4. N ≤ 200000, Q ≤ 100000, and K_i = 1 for every query.
5. N ≤ 200000, Q ≤ 100000.

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

Output

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

If such value does not exist, print -1 instead.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

1. Class Array Operator Overloading

const Array &Array::operator=( const Array &right )
{
   if ( &right != this ) // avoid self-assignment
   {
      // for Arrays of different sizes, deallocate original
      // left-side Array, then allocate new left-side Array
      if ( size != right.size )
      {
         delete [] ptr; // release space
         size = right.size; // resize this object
         ptr = new int[ size ]; // create space for Array copy
      } // end inner if

      for ( size_t i = 0; i < size; ++i )
         ptr[ i ] = right.ptr[ i ]; // copy array into object
   } // end outer if

   return *this; // enables x = y = z, for example
} // end function operator=

bool Array::operator==( const Array &right ) const
{
   if ( size != right.size )
      return false; // arrays of different number of elements

   for ( size_t i = 0; i < size; ++i )
      if ( ptr[ i ] != right.ptr[ i ] )
         return false; // Array contents are not equal

   return true; // Arrays are equal
} // end function operator==

int &Array::operator[]( int subscript )
{
   // check for subscript out-of-range error
   if ( subscript < 0 || subscript >= size )
      throw out_of_range( "Subscript out of range" );

   return ptr[ subscript ]; // reference return
} // end function operator[]

int Array::operator[]( int subscript ) const
{
   // check for subscript out-of-range error
   if ( subscript < 0 || subscript >= size )
      throw out_of_range( "Subscript out of range" );

   return ptr[ subscript ]; // returns copy of this element
} // end function operator[]

istream &operator>>( istream &input, Array &a )
{
   for ( size_t i = 0; i < a.size; ++i )
      input >> a.ptr[ i ];

   return input; // enables cin >> x >> y;
} // end function

ostream &operator<<( ostream &output, const Array &a )
{
   // output private ptr-based array
   for ( size_t i = 0; i < a.size; ++i )
   {
      output << setw( 12 ) << a.ptr[ i ];

      if ( ( i + 1 ) % 4 == 0 ) // 4 numbers per row of output
         output << endl;
   } // end for

   if ( a.size % 4 != 0 ) // end last line of output
      output << endl;

   return output; // enables cout << x << y;
} // end function operator<<

2. Inheritance Access Control

3. Operator Overloading

/* 1. non-static member function */
complex operator+ ( const complex& );

/* 2. non-member function */
friend complex operator* ( const complex&, const complex& );

/* 1. non-static member function */
complex operator-();

/* 2. non-member function */
friend complex operator~( const complex& );

4. Inheritance

class A {
// A is a base class
};

class B: public A {
// B inherits A.
// B is a derived class
};

5. Dynamic Allocation

int *ptr = new int;
delete ptr;

int *ptr = new int[100];
delete [] ptr;

6. String Object

#include <string>
using namespace std;
...
string str1 = "Hello";
string str2 = "World";

7. Standard C++ Library - <string>

8. Standard C++ Library - <sstream>

stringstream ss{"Hello"};    // constructor
string str = ss.str();    // a = "Hello"

stringstream ss;
ss<<"75";
ss<<"76";
int num;
ss>>num;    // num = 7576

9. Reverse Iterator in std::vector

vector<int> v = {10, 20, 30, 40, 50};

for ( auto it = v.rbegin(); it != v.rend(); ++it ) {
    cout << *it << " ";
}

// Output:
// 50 40 30 20 10

vector<int> v = {10, 20, 30, 40, 50};

auto it = v.rbegin();

cout << *it << endl;       // 50

++it;
cout << *it << endl;       // 40

--it;
cout << *it << endl;       // 50

cout << *next(it) << endl; // 40

auto it2 = next(v.rbegin(), 2);
cout << *it2 << endl;      // 30

cout << *prev(it2) << endl; // 40

10. Offline cppreference.com

更改副檔名教學：

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

解壓縮
>> 點進 reference 目錄
>> 點進 en 目錄
>> 打開 Main_Page.html

就可以看到完整的 cppreference.com 離線版。

How to change the file extension:

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