Description

Array vs. Linked List

Array is a basic and fundamental concept in C/C++. It is a series of data which is arranged continiously in the memory space and can be accessed by index. Array is fast for indexing (using the given index to access the certain data), because the memory address of the destination can be calculated quickly. However, the capacity of the array is fixed after the declaration.

In I2PI (introduction of programming 1), we introduce a data structure called "linked list" which supports appending and deleting elements dynamically. The elements are stored in a series of "nodes", where each node points to the address of the next node. It is fast at appending elements but slow at indexing. To access the item of index i, you need to move i steps from head to obtain it.

Dynamic Array

In this problem, we will introduce a new data structure called "dynamic array" (abbreviated to "Darray" in the following statement) which supports dynamic capacity and indexing. We targeted to a simple Darray which has the following three variables

1. size : the number of elements stored in the array
2. capacity : the maximum number of elements which can be stored in the array
3. *data : the pointer which stores the address of the array

and two operations

1. pushback: append an element to the back
2. indexing : access the data by the given index.

To understand the concept of size and capacity, consider an array declaration:

 At first, the capacity is 5, but the size is 0 because no data is stored inside the array. Next, we push 5 elements to the array:

the capacity is still 5 but the size changes from 0 to 5. Therefore, no element can be appended to the array.

If we still want to append additional elements, we'll allocate a new array space with the double capacity and copy the data from old array to the new one. Note that the old array should be freed to avoid memory leak.

In this case, the capacity becomes 10 and the size is 6.

Implementation

You should implement the following functions based on the description above:

1. int& operator[](int): access data like using array. Users and main.cpp should/will not access the index which is greater or equal to size.
2. void pushback(int x): append the element x
3. void clear(void): clear the array (set size to 0) so that the next pushbacks will place elements in data[0],data[1] and so on.
4. int length(void): return the current size.
5. void resize(void): double the capacity and copy the data.
6. ~Darray(): destructor

Note that main.cpp acts like a functional tester for your Darray. There's no need to understand it. You should test your Darray by yourself.

More Notes: Time Complexity of Dynamic Array

Although it seems that copying the whole array will make dynamic array slow, we will analyze the time complexity to show that dynamic array is fast. Recall what Big-O Notation is where we introduced it in "The Josephus problem". O(2n+100)=O(2n)=O(n) means that the operation takes about n steps while O(2)=O(1) takes "constant" time. For array operations, we wish to have O(1) of indexing and pushback. In the following analysis, we will evaluate the amortized time complexity, which can be comprehended as calculating the average time complexity instead of the complexity of total operations.  Amortized time complexity = (complexity of total operations) / (number of operations).

Suppose that C₀ is the initial capacity and n is the number of operation of pushback. We discuss the time complexity in several cases:

1. Expand 0 time, n <= C₀.
   Since there's no expand operation, the total time complexity is O(1)*n=O(n). The amortized time complexity is O(n)/n=O(1).
2. Expand 1 time, C₀ < n <= C₁, C₁ = 2*C₀.
   Push C₀ items to array: O(C₀)
   Expand and copy: O(C₀), since there're C₀ elements to be copied.
   Push n-C₀ items to array: O(n-C₀)
   The total time complexity is O(C₀)+O(C₀)+O(n-C₀) = O(n+C₀). Since C₀ < n <= C₁, O(2C₀) < total time complexity <= O(3C₀). The amortized time complexity ranges in [O(3/2), O(2)). We identify it by the upper bound : O(2).
3. Expand 2 times, C1 < n <= C2, C2 = 2*C1.
   The amortized time complexity should be O(3). You can verify it by your own.

From the above analysis, if it expand i times, the amortized time complexity for appending an element is O(i+1). However, i won't be very large because the capacity grows exponentially so that we often regard the complexity as O(1), or, constant time. For instance, C₀=100, after expanding 20 times, the capacity will be 100*2²⁰≈10⁸.

---

 

Input

This is handled by the main function.

Output

This is handled by the main function.

Sample Input  Download

Sample Output  Download

Partial Judge Code

13520.cpp

Partial Judge Header

13520.h

Tags

Discuss

Description

Caillou has designed a Run-Length Encoding (RLE) challenge for you.

The task is to define the class ‘RLECodec’ for run-length encoding:

The rule of run-length encoding is simple: Count the number of consecutive repeated characters in a string, and replace the repeated characters by the count and a single instance of the character. For example, if the input string is ‘AAADDDDDDDBBGGGGGCEEEE’, its run-length encoding will be ‘3A7DBB5GC4E’, because there are three A’s, seven D’s, … etc. Note that we do not need to encode runs of length one or two, since ‘2B’ and ‘1C’ are not shorter than ‘BB’ and ‘C’.

 

You need to perform T queries on an encoded string, where each query returns the positions (1-based indexes) of a character C in the decoded string.

 

This problem is a partial judge.
Please implement functions defined in the header file.

• decode: Decode the string.

• getPos: Return an array of 1-based positions for character C, terminated by 0.

Input

The first line contains an encoded string S. In every <count><character> pair, the count is guaranteed to be less than or equal to 15.

The second line contains an integer T, indicating the number of queries.

Each of the next T lines contains a character C, querying for all positions of C in the decoded string. C is guaranteed to be an uppercase letter.

Constraints

• 1 ≤ |S| ≤ 150

Subtask

• testcase 1 ~ 3: T = 0
• testcase 4 ~ 6: No additional restrictions

Output

The first line outputs the decoded string of S.

Each of the next T lines outputs all positions of the corresponding C in the decoded string.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14625.cpp

Partial Judge Header

14625.h

Tags

Discuss

Description

After clearing every dot and escaping the ghost, you thought the nightmare was over.
A strange voice echoes: “Nice try … now beat this.”
You are teleported into a fresh maze.
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.

Survive all T rounds and reach the required score to escape safely back to your own world.

Task Implementation

You must modify the provided code at the two parts marked "TODO-01" and "TODO-02" to help Pacman evade the ghosts 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.

Ghost Movement Logic

(Already implemented; modifying it is not recommended)

In normal mode:

• Ghost has a 50% chance to move randomly to an adjacent cell.

• Ghost also has a 50% chance to move one step towards Pacman(Normal mode).

In Frightened mode:

• Move one step away from Pacman.

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

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, the timer will not be reset and no new triggers 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 timer--; when timer reaches 0 the surviving blue ghost reverts to normal.

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

Scoring

To pass each testcase , you should:

• Testcases 1 ~ 6: Clear all normal dot O. (The solution for the mid-2 practice problem will work)
• Testcases 7 ~ 8: Clear all normal dot O and trigger frightened mode at least 7 times. (see Hint)
• Testcases 9 ~ 10: Clear all normal dot O​, trigger frightened mode at least 7 times, and eat at least one blue ghost. (see Hint)

Constraints

• 1 ≤ N, M ≤ 25

• 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: Except for the surrounding walls, no other grids are walls.
• Testcases 4 ~ 6: There is exactly one dot.
• Testcases 7 ~ 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, R, C;
vector<string> grid;
int vis[100][100];

struct Position {
    int x, y;
    int operator-(const Position& other) const {
        return abs(x - other.x) + abs(y - other.y);
    }
    bool operator==(const Position& other) const {
        return x == other.x && y == other.y;
    }
};

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

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

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

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

    private:
        Position ghostPosition;
};

class Ghost : public Entity {
    public:
        Ghost(Position p): Entity(p), startPosition(p) {}

        void setPacmanPos(const Position& p) { 
            pacmanPosition = p; 
        }

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

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

        bool isAlive() const { 
            return alive; 
        }

        bool isFrightened() const { 
            return frightened && alive; 
        }

        void eaten() {
            alive = false;
            frightened = false;
            pos = {-1, -1};
            timer = 10;
        }

        void revive() {
            alive = true;
            frightened = false;
            pos = startPosition;
        }

        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++) {
                int nx = pos.x + dxs[i];
                int ny = pos.y + dys[i];
                if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
                if (grid[nx][ny] == '#') continue;
                nbrs.push_back({nx, ny});
            }
            if (nbrs.empty()) return;

            Position chosen = pos;
            double p = (double)rand() / RAND_MAX;
            if (p < 0.5) {
                int best = INT_MAX;
                for (auto &c : nbrs) {
                    int d = c - pacmanPosition;
                    if (d < best) {
                        best = d;
                        chosen = c;
                    }
                }
            } else {
                chosen = nbrs[rand() % nbrs.size()];
            }

            if (frightened) {
                int best = -1;
                for (auto &c : nbrs)
                    best = max(best, c - pacmanPosition);
                vector<Position> far;
                for (auto &c : nbrs)
                    if ((c - pacmanPosition) == best) far.push_back(c);
                chosen = far[rand() % far.size()];
            }

            pos = chosen;
        }

    private:
        Position startPosition, pacmanPosition;
        bool alive = true, frightened = false;
        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): frightenedTimer(0) {}

        void handlePacmanCell(const Position& pacman, Ghost& ghost) {
            if(!vis[pacman.x][pacman.y]) {
                if (grid[pacman.x][pacman.y] == 'O'){
                    vis[pacman.x][pacman.y] = 1;
                }
                else if (grid[pacman.x][pacman.y] == 'X'){
                    vis[pacman.x][pacman.y] = 1;
                    if(!ghost.isFrightened()) {
                        frightenedTimer = 10;
                        ghost.setFrightened(true);
                    }
                }
            }
        }

        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() && ghost.isFrightened()) {
                ghost.eaten();
            }
        }

    private:
        int frightenedTimer;
};

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

    cin >> T >> R >> C;
    grid.resize(R);
    for (int i = 0; i < R; i++) cin >> grid[i];

    Position pacman_start, ghost_start;
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++) {
            if (grid[i][j] == 'P') pacman_start = {i, j};
            if (grid[i][j] == 'G') ghost_start   = {i, j};
        }

    unsigned GHOST_SEED = /* TODO-02 */;
    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();
        gameMap.handlePacmanCell(pacman.getPosition(), ghost);
        gameMap.resolveCollision(pacman, ghost);

        ghost.setPacmanPos(pacman.getPosition());
        ghost.move();
        gameMap.resolveCollision(pacman, ghost);
        ghost.stateUpdate();
        gameMap.updateTimer(ghost);

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

Note! The "invalid" status in the Pacman Simulation Visualizer does not check whether the ghost's movement path is valid.

 

Input: Output:

Input

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

The first line contains three integers N, M, and T, representing the dimensions of the maze ( N × M ) and the number of rounds T

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