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

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

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

Tags

Discuss

Description

A parking lot has n parking spaces, each with a size s_i. There are m events, and each event j is one of two types:

1. At time t_j, a car of size x arrives, preferring parking space l_j, and will leave at time t_j + a_j.
2. At time t_j, check how many parking spaces of size y are available. If a car leaves the parking lot at the moment of a query, the query result reflects the state after the car has left.

For each event of type 1, assign a parking space based on these rules:

1. Choose the smallest parking space that is >= x.
2. If multiple spaces meet rule 1, pick the one closest to the preferred space l_j.
3. If multiple spaces meet rule 2, choose the one with the smallest index.
4. If no space meets rule 1, output -1 and skip the operation.

Input

The first line contains two positive integers n and m, representing the number of parking spaces and the number of events.

The second line contains n positive integers s₁ to s_n, representing the size of each parking space.

The next m lines each describe an event, with event i presented in one of two formats:

1. 1 ti x li ai: At time t_i, a car of size x arrives, preferring to park as close as possible to space l_i, and will stay for a_i time units.
2. 2 ti y: At time t_i, query how many parking spaces of size y are available.

Output

For each car arrival event, output the assigned parking space number, or -1 if no space can be assigned. For each parking space query event, output the corresponding result.

Constraints

• 1 <= n, m <= 2 * 10⁵
• 1 <= s_i, t_i, x, a_i, y <= 10⁹
• t_{i - 1} < t_i
• 1 <= l_i <= n

Subtasks

• Testcase 1: Each parking space has a unique size, and whenever a vehicle arrives, there is always a parking space of size = x available, a_i = 10⁹
• Testcase 2: a_i = 10⁹, l_i = 1
• Testcases 3, 4: l_i = 1
• Testcase 5: a_i = 10⁹
• Testcases 6, 7: No additional constraints.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You thought you had vanquished every maze’s challenge: first outwitting the AI debug-bot in Polymorphic Pacman: Parallel Pursuit, then mastering the power-dot frightened mode in Polymorphic Pacman II. Yet the simulators will not let you go so easily. The monitors in the NTHU CS lab flicker once more, and you find yourself hurled into a new, even more twisted world.

In this "final stage" of your nightmarish odyssey:

• The maze is still an N × M grid, representing an expanded section of the CS building. It wraps around both horizontally and vertically— cells at (i,0) and (i,M−1) are adjacent if neither is a wall; similarly for rows 0 and N−1.
• Walls (#) remain impenetrable barriers (packed bookshelves, locked lab doors).

• It still contains ordinary dots O, but now ten power‑dots X are spread across the map.
  Whenever Pacman eats a power‑dot:

  • The ghost immediately turns blue ( “frightened mode” ) for 10 rounds;
  • During those 10 rounds it runs away from Pacman;
  • If Pacman meets the blue ghost, the ghost is eaten, and the ghost will re‑spawn 10 rounds later on its initial square.

Succeeding in these tasks will finally tear you out of the simulation and return you to your world—just in time to welcome summer vacation.

Task Implementation

You must modify the provided code at each part marked "TODO" to help Pacman evade the ghost and clear all the dots.
Every round, your Pacman can:

• Move to any of the four adjacent cells (up, down, left, right) that aren't walls.

• Choose to stay still and not move this round.

• Note that the maze wraps around both horizontally and vertically: moving off the right edge into column M is treated as moving into column 0, and moving off the left edge into column −1 is treated as moving into column M − 1, provided the destination cell is not a wall. The same applies vertically for rows.

Ghost Movement Logic

(Already implemented; modifying it is not recommended)

• Ghost has 10% chance to move randomly to an adjacent non-wall cell.

• Ghost has 90% performs a breadth‐first search (BFS) from its current position to Pacman’s current position, and then moves exactly one step along the resulting shortest path—moving toward Pacman if in normal mode, or away from Pacman if in frightened mode.

• Ghost never remain stationary.

• Ghost will never move onto a power-dot cell (X).

Important Notes

• Avoid changing parts of the code not marked by "TODO" unless you're absolutely sure what you're doing.

• Modifying ghost movement logic to avoid capture is strongly discouraged. The judge system will recreate ghost paths based on your provided random seed. If your output differs from the judge's expected ghost path, you will receive a "Wrong Answer."

Power Dot & Frightened Mode Rules

When pacman moves and may eat O/X :

• O(Normal dot) : disappears.
• X(Power dot) : disappears, and if no frightened mode is active, sets the frightened timer to 10 and counts as one frightened-mode trigger.
  • ​If Pacman eats additional X while the timer > 0​ or the ghost is not alive, the timer will not reset and no additional trigger will be counted.

While the frightened timer > 0:

1. Ghost moves away from Pacman.

2. If Pacman lands on the blue ghost, ghost disappears and re-spawns after 10 rounds.

3. At end of each round:

   1.  if timer = 0, the surviving blue ghost reverts to normal.

   2. timer--; 

There are exactly 10 power-dots in each test case.

Scoring

To pass each testcase, you should:

• Testcases 1 ~ 4: Clear all normal dot O.(This solution for the final practice problem will work)
• Testcases 5 ~ 8: Clear all normal dot O and trigger frightened mode at least 4 times. 
• Testcases 9 ~ 12: Clear all normal dot O​, trigger frightened mode at least 4 times, and eat at least two blue ghost.

Constraints

• 1 ≤ N, M ≤ 40

• 5 × N × M ≤ T ≤ 10 × N × M

• It is guaranteed that no cell in the map is enclosed by walls on three sides (meaning every cell has at least two accessible paths).

• It is guaranteed that Pacman can always clear all dots.

Subtasks

• Testcases 1 ~ 2: There is exactly one dot.
• Testcases 3 ~ 4: N, M ≤ 5
• Testcases 5 ~ 12: No additional restrictions

Testing on Your Computer

• Uncomment the following two lines inside int main() in the provided code:

  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);

• Place your input data into a file named input.txt (make sure it’s in the same directory as your program).

• After execution, your program's output will be stored in output.txt.

Code

#include <bits/stdc++.h>
using namespace std;

int T, N, M;
vector<string> grid;

struct Position {
    int x, y;

    bool operator==(const Position& other) const {
        return x == other.x && y == other.y;
    }

    bool operator<(const Position& other) const {
        return (x != other.x) ? (x < other.x) : (y < other.y);
    }

    int operator-(const Position& other) const {
        /// TODO-01:
        // Implement the BFS algorithm to find the distance between two positions.
    }
   
    void fixedPos() {
        x = (x + N) % N;
        y = (y + M) % M;
    }
};

set<Position> dots;
set<Position> power_dots;

class Entity {
    public:
        Entity(Position pos): pos(pos) {}
        virtual ~Entity() = default;
        virtual void move() = 0;
        Position getPosition() const { 
            return pos;
        }
        void fixedPos() {
            pos.fixedPos();
        }
    protected:
        Position pos;
};

class Pacman : public Entity {
    public:
        Pacman(Position pos): Entity(pos) {}        

        void setGhostPos(const Position& pos) { 
            ghostPosition = pos;
        }

        void move() override {
            // TODO-02:
            // Implement how Pacman moves in each round.
        }        

    private:
        // TODO (optional):
        // You may want to add some extra variables here.
        Position ghostPosition;
        int scaredTimer = 0;
};

class Ghost : public Entity {
    public:
        Ghost(Position p): Entity(p), startPosition(p) {}
    
        void setPacmanPos(const Position& pos) {
            pacmanPosition = pos;
        }

        void setFrightened(bool f) { 
            frightened = f; 
        }

        void stateUpdate() {
            if (!alive) {
                if (timer == 0) {
                    revive();
                }
                timer--;
                return;
            }
        }
    
        bool isAlive() const { 
            return alive; 
        }

        bool isFrightened() const { 
            return frightened && alive; 
        }
    
        void eaten() {
            alive = false;
            frightened = false;
            pos = startPosition;
            timer = 10;
        }

        void revive() {
            alive = true;
            frightened = false;
            pos = startPosition;
        }
    
        void move() override {
            if (!alive) return;
            vector<Position> nbrs;
            static const int dxs[4] = {-1, 1, 0, 0};
            static const int dys[4] = {0, 0, -1, 1};
            for (int i = 0; i < 4; i++) {
                Position nbr = pos;
                nbr.x += dxs[i];
                nbr.y += dys[i];
                nbr.fixedPos();
                if (grid[nbr.x][nbr.y] != '#' && grid[nbr.x][nbr.y] != 'X') {
                    nbrs.push_back(nbr);
                }
            }
            for(auto i:power_dots) {
                grid[i.x][i.y] = '#';
            }
            int now_dis;
            Position chosen = pos;
            double p = (double)rand() / RAND_MAX;
            if (p < 0.9) {
                if(frightened) {
                    now_dis = 0;
                    if (!nbrs.empty()) {
                        for (Position& c : nbrs) {
                            int d = c - pacmanPosition;
                            if (d >= now_dis) {
                                chosen = c;
                                now_dis = d;
                            }
                        }
                    }
                }
                else{
                    now_dis = INT_MAX;
                    if (!nbrs.empty()) {
                        for (Position& c : nbrs) {
                            int d = c - pacmanPosition;
                            if (d <= now_dis) {
                                chosen = c;
                                now_dis = d;
                            }
                        }
                    }
                }
            }
            else {
                int idx = rand() % nbrs.size();
                chosen = nbrs[idx];
            }
            for(auto i:power_dots) {
                grid[i.x][i.y] = 'X';
            }
            pos = chosen;
        }
    private:
        Position startPosition, pacmanPosition;
        bool alive = 1, frightened = 0;
        int timer = 0;
};

ostream& operator<<(ostream& os, const Position& p) {
    os << p.x << ' ' << p.y;
    return os;
}

ostream& operator<<(ostream& os, const Entity& e) {
    os << e.getPosition();
    return os;
}

class GameMap {
    public:
        GameMap(const vector<string>& g) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (grid[i][j] == 'O'){
                        dots.insert({i, j});
                    }
                    else if (grid[i][j] == 'X') {
                        power_dots.insert({i, j});
                    }
                }
            }
        }

        void handlePacmanCell(const Position& pacman, Ghost& ghost) {
            if (grid[pacman.x][pacman.y] == 'O'){
                grid[pacman.x][pacman.y] = '.';
                dots.erase(pacman);
            }
            else if (grid[pacman.x][pacman.y] == 'X'){
                grid[pacman.x][pacman.y] = '.';
                if(ghost.isAlive()){
                    frightenedTimer = 10;
                    ghost.setFrightened(true);
                }
                power_dots.erase(pacman);
            }
        }

        void updateTimer(Ghost& ghost) {
            if (frightenedTimer > 0) frightenedTimer--;
            if (frightenedTimer == 0) {
                ghost.setFrightened(false);
            }
        }

        void resolveCollision(Pacman& pacman, Ghost& ghost) {
            if (!ghost.isAlive()) return;
            if (pacman.getPosition() == ghost.getPosition()) {
                if (ghost.isFrightened()) {
                    ghost.eaten();
                }
            }
        }
    private:
        int frightenedTimer;
};

int main() {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    cin >> T >> N >> M;
    grid.resize(N);
    for (int i=0;i<N;i++) cin >> grid[i];
    Position pacman_start, ghost_start;
    for (int i=0;i<N;i++) for (int j=0;j<M;j++) {
        if (grid[i][j]=='P') pacman_start = {i,j};
        if (grid[i][j]=='G') ghost_start = {i,j};
    }

    unsigned GHOST_SEED = /* TODO-03: */ ;
    // Choose any integer you like as a random seed! It will affect how the ghosts move.
    // Note: make sure the number you pick fits within the range of an unsigned integer (0 to 4,294,967,295),or unexpected results may happen.

    srand((unsigned)GHOST_SEED);

    GameMap gameMap(grid);
    Pacman pacman(pacman_start);
    Ghost ghost(ghost_start);
    
    for (int t=0; t<T; t++) {
        pacman.setGhostPos(ghost.getPosition());
        pacman.move();
        pacman.fixedPos();
        gameMap.handlePacmanCell(pacman.getPosition(), ghost);
        gameMap.resolveCollision(pacman, ghost);
        ghost.setPacmanPos(pacman.getPosition());
        ghost.move();
        ghost.fixedPos();
        gameMap.resolveCollision(pacman, ghost);
        ghost.stateUpdate();
        gameMap.updateTimer(ghost);
        cout << pacman << ' ';
        if(ghost.isAlive()) cout << ghost << '\n';
        else cout << "-1 -1" << '\n';
    }
    cout << GHOST_SEED <<'\n';
    return 0;
}

 

Pacman Simulation Visualizer

Input: Output:

Input

(Input handling is already implemented in the provided code.)

The first line contains three integers T, N and M, representing the number of rounds T and the dimensions of the maze ( N × M ) .
The next N lines each contain M characters c_i,j, where:

• c_i,j = '#' represents a wall.

• c_i,j = '.' represents an empty space.

• c_i,j = 'O' represents a dot.

• c_i,j = 'X' represents a power dot.

• c_i,j = 'P' represents Pacman's initial position.

• c_i,j = 'G' represents a ghost's initial position.

Output

(Output handling is already implemented in the provided code.)

Output ( T + 1 ) lines:

• For the first T lines, each line should contain four integers P_x, P_y, G_x, G_y, representing Pacman's position (P_x, P_y) and the ghost's position (G_x, G_y) at each round from 1 to T.

• The ( T + 1 ) th line should output your chosen random seed.

If multiple valid solutions exist, outputting any one of them will be accepted.

Sample Input  Download

Sample Output  Download

Tags

Discuss