| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 13522 | Infinitely Big Integer: Darray Implementation |
|
| 14958 | Cat Teleport Maze |
|
Description
The problem "Infinitely Big Integer" is splitted into two subproblems:
- Darray Implementation (3/10)
- Big Integer Implementation (7/10)
You should solve this subproblem first.
Based on the definition of Dynamic Array in Problem 13520 (nthu.edu.tw), you need to implement a dynamic array with the following functions:
- 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.
- void pushback(int x): append the element x
- void popback(void): pop the last element. Don't do anything if the array is empty.
- 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.
- int length(void): return the current size.
- void resize(void): double the capacity and copy the data.
- ~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. Furthermore, a new function void popback(void) is introduced in this problem.
class Darray {
public:
Darray() {
capacity = 100;
size = 0;
data = new int[capacity];
};
~Darray();
int& operator[](int);
void pushback(int x);
void popback(void);
void clear(void);
int length(void);
private:
void resize(void); // double the capacity
int *data;
int capacity;
int size;
};
Darray arr;
for (int i = 0; i < 5; i++) arr.pushback(i*i);
arr[2] += 100 + arr[3];
for (int i = 0; i < arr.length(); i++)
cout << arr[2] << ' '; // Print: 0 1 113 9 16
cout << endl << arr.length() << endl; // Print: 5
arr.clear();
cout << arr.length() << endl; // Print: 0
arr.pushback(9487); arr.pushback(9487);
arr.popback();
cout << arr.length() << ' ' << arr[0] << endl; // Print: 1 9487
std::vector is prohibited (both subproblems 1 and 2) and will result in 0 score if you use it.
Input
This is handled by the main function.
1/3 of the test cases will not test popback(). If you have problems with it, try writing an empty popback function so that it can be compiled successfully.
void popback() {
}
Output
This is handled by the main function.
Sample Input Download
Sample Output Download
Partial Judge Code
13522.cppPartial Judge Header
13522.hTags
Discuss
Description
A cat is trapped in a 20×20 maze. Each cell is one of the following types:
'S': starting position of the cat'E': exit position'#': wall'_': empty cell'+': food'a'-'z': teleport 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.
Some pairs of cells are connected by teleportation. Each cell belongs to at most one teleport pair.
The cat cannot move onto a wall cell.
Initially, the entire maze is unknown to the cat.
The game proceeds in steps. In each step, the cat does the following:
- sees and memorizes the adjacent cells and the paired teleport cell if the current cell has one;
- moves to either an adjacent cell or the paired teleport cell, if one exists.
When the cat moves onto a cell with food, the food is eaten and the cell becomes empty immediately.
Your goal is to make the cat eat all food and then reach the exit cell within the specified number of steps. This is guaranteed to be possible for all given test cases.
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.
Note
Two cells with the same lowercase letter are paired teleport cells.
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
- Subtask 1 contains no teleport pairs and has the step limit 10000.
- Subtask 2 contains no food cells and has the step limit 10000.
- Subtask 3 has the starting position and the exit cell in adjacent cells and the step limit 10000.
- Subtask 4 has the step limit 10000.
- Subtask 5 has the step limit 1500.
Output
(The output is already handled by the provided C++ code.)
If the cat eats all food and reaches the exit within the specified number of steps, the program outputs SUCCESS.
Otherwise, the program outputs FAIL.
You will receive an AC only if the program outputs SUCCESS.