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

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

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

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, which can be one of three types:

1. A car of size x wants to park.
2. A car in space y leaves.
3. Query how many parking spaces of size z are still available.

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

1. Choose the smallest space that is >= x.
2. If multiple spaces meet rule 1, follow the driver’s preference: if they prefer "small," assign the space with the smallest number; if they prefer "big," assign the space with the largest number.
3. If no space meets rule 1, skip the operation and don’t assign a space.

For each car entering operation, output the assigned parking space number. If no space can be assigned, output -1.

Input

The first line contains two positive integers n and m, representing the number of parking spaces and the number of events, respectively.
The second line contains n positive integers s₁ ~ s_n, representing the size of each parking space.
The next m lines each describe an event in one of three formats:
1 x small/big: A car of size x with a preference for small (smallest numbered space) or big (largest numbered space) wants to park.
2 y: The car in parking space y leaves the parking lot.
3 z: Query how many parking spaces of size z are still available.

Constraints

• 1 <= n, m <= 200000
• 1 <= x <= 10⁹
• 1 <= y <= n

Subtasks

• Testcases 1, 2: There will only be type 1 events (cars entering).
• Testcases 3, 4: Each car's preference will only be "small" (choosing the smallest numbered parking space).
• Testcases 5, 6: Each car's preference will only be "big" (choosing the largest numbered parking space).
• Testcases 7, 8 No additional constraints.

Output

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

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You had barely escaped the original Pacman world, your heart still pounding, when suddenly the monitors in the National Tsing Hua University CS lab flickered once again, pulling you into a new maze!

As a Computer Science student at NTHU, you had stayed up late testing your friends' AI-driven Pacman simulator. One moment you were celebrating your narrow escape, the next—the desks and lights of the lab melted away, replaced by a strange maze filled with dots and a lone ghost. You looked down and realized: you had become Pacman!

In this parallel campus:

• The maze is an N × M grid, representing the layout of the CS building. It wraps around both horizontally and vertically on the left and right edges, as well as the top and bottom edges, are considered adjacent if neither is a wall—forming a toroidal structure.

• Walls (#) are packed bookshelves or locked lab doors; open spaces (.) are clear hallways; dots (O) float where projectors once shone.

• Your starting position (P) is the console where you appeared. A single ghost (G)—an AI debug-bot—chases you relentlessly, always using BFS to determine the shortest path and moving exactly one step each round.

Your mission remains clear: Eat every dot without being caught by the ghost. Once you successfully collect all dots, the simulation will finally end, returning you safely to your own world—and tomorrow's lecture on Introduction to Programming (II).

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

• Ghost never remain stationary.

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

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 ~ 3: Ensures that ghost cannot touch pacman.
• Testcases 4 ~ 6: There is exactly one dot.
• Testcases 7 ~ 8: N, M ≤ 5
• Testcases 9 ~ 10: 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) ? (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;

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

class Ghost : public Entity {
    public:
        Ghost(Position pos): Entity(pos){}
    
        void setPacmanPos(const Position& pos) {
            pacmanPosition = pos;
        }
    
        void move() override {
            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] != '#') {
                    nbrs.push_back(nbr);
                }
            }
            int now_dis = INT_MAX;
            Position chosen = pos;
            double p = (double)rand() / RAND_MAX;
            if (p < 0.9) {
                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];
            }
            pos = chosen;
        }
    private:
        Position pacmanPosition;
};

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});
                    }
                }
            }
        }
        void eatDot(const Position& p) {
            if (dots.find(p) != dots.end()) {
                dots.erase(p);
            }
        }
};

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.eatDot(pacman.getPosition());
        ghost.setPacmanPos(pacman.getPosition());
        ghost.move();
        ghost.fixedPos();
        cout << pacman << ' ' << ghost << '\n';
    }
    cout << GHOST_SEED <<'\n';
    return 0;
}

Pacman Simulation Visualizer

A visualization tool is provided to help you debug your solution.

Paste your program's input and output into the provided text fields, then click "Load Data" and "Play".

You'll see Pacman and the ghost move according to your data, along with the current game state (win/lose/invalid).

You can also generate custom test cases by entering a seed number and clicking "Generate Input."

Pacman Simulation Visualizer

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