Untitled
unknown
plain_text
a year ago
8.5 kB
3
Indexable
[Problem Description]
You are required to implement a notepad program.
Only lowercase English letters can be inserted in the program and the width and height of each character is 1.
The height of the notepad is H and the width is W.
Since W number of characters can be inserted in one line, the rest of words exceeding the number are moved to the next line.
[Fig. 1]
[Fig. 1] shows an example of inserting 26 characters from a to z in a notepad with H = 5 and W = 7.
In the above picture, the cursor is placed between j and k.
Implement a notepad with the following features:
1. Insert a character in the position where the cursor is placed
2. Move the cursor
3. Return the number of particular characters following the cursor
Implement each required function by referring to the following API description.
※ The function signature below is based on C/C++. As for Java, refer to the provided Solution.java and UserSolution.java.
The following is the description of API to be written in the User Code.
void init(int H, int W, char mStr[])
This function is called in the beginning of each test case.
The height and width of the notepad are H and W.
A string mStr is inserted in the initial status of the notepad.
The string mStr consists of only lowercase English letters, ending with ‘＼0.’
The length of mStr is minimum 1, but no larger than H * W.
The cursor is placed on the left of the 1st character.
Parameters
H : Height of the notepad (1 ≤ H ≤ 300)
W : Width of the notepad (1 ≤ W ≤ 300)
mStr: String inserted in the initial status of the notepad (1 ≤ |mStr| ≤ H * W; |a| represents the length of a string “a.”)
void insert(char mChar)
This function inserts a character mChar in the position where the cursor is placed.
After the insertion, the cursor is placed on the right of the newly inserted character.
mChar is a lowercase English letter.
There is no case where the length of the string exceeds H * W when the character is inserted.
Parameters
mChar : Character to be inserted
char moveCursor(int mRow, int mCol)
This function moves the cursor to the left of the character in the mRowth row, mColth column.
If the mRowth row, mColth column is empty, the cursor is moved to the right of the last character of the string.
The character on the right of the cursor is returned.
If the cursor is at the end of the string and therefore followed by no character, ‘$’ is returned.
Parameters
mRow : Number of the row to which the cursor is moved (1 ≤ mRow ≤ H)
mCol : Number of the column to which the cursor is moved (1 ≤ mCol ≤ W)
Returns
The character following the cursor (or ‘$’) is returned.
int countCharacter(char mChar)
This function counts and returns the number of mChar following the cursor.
[Fig. 2]
In [Fig. 2], the string following the cursor is “bcdefgeb.”
If mChar is ‘b’ in the above example, 2 is returned, which is the number of times ‘b’ appears in this string.
It is guaranteed that mChar is a lowercase English letter.
Parameters
mChar : Character whose number of times appearing is to be counted
Returns
The number of times is returned that mChar appears after the cursor.
[Example]
Let’s look into the below case of functions and return values in order in the first test case.
Order
Function
Figure
Note
Return
1
init(3, 4, “bcdeg”)
The height and width of the notepad are 3 and 4.
“bcdeg” has been inserted.
The cursor is placed on the left of the 1st character.
2
countCharacter(‘b’)
The string following the cursor is “bcdeg.” Since ‘b’ appears once in “bcdeg,” return 1.
1
3
moveCursor(2, 1)
Move the cursor to the left of the character in the 2nd row, 1st column.
Return ‘g,’ which is the character on the right of the cursor.
g
4
insert(‘f’)
Insert ‘f’ in the position where the cursor is. The cursor is placed on the right of the newly inserted character.
5
moveCursor(1, 4)
Move the cursor to the left of the character in the 1st row, 4th column.
Return ‘e,’ which is the character on the right of the cursor.
e
6
countCharacter(‘f’)
The string following the cursor is “efg.”
Return 1 since ‘f’ appears once in “efg.”
1
7
moveCursor(2, 4)
There is no character in the 2nd row, 4th column. In this case, move the cursor to the end of the string and then return ‘$.’
$
8
insert(‘e’)
Insert ‘e’ in the position where the cursor is.
9
insert(‘b’)
Insert ‘b’ in the position where the cursor is.
10
countCharacter(‘b’)
The string following the cursor is empty.
Since ‘b’ does not appear in the empty string, return 0.
0
11
moveCursor(3, 1)
There is no character in the 3rd row, 1st column. Move the cursor to the end of the string and return ‘$.’
$
12
moveCursor(1, 1)
Move the cursor to the left of the character in the 1st row, 1st column.
Return ‘b,’ which is the character on the right of the cursor.
b
13
insert(‘a’)
Insert ‘a’ in the positon where the cursor is.
14
insert(‘b’)
Insert ‘b’ in the position where the cursor is.
15
insert(‘a’)
Insert ‘a’ in the positon where the cursor is.
16
countCharacter(‘b’)
The string following the cursor is “bcdefgeb.”
Since ‘b’ appears twice in this string, return 2.
2
17
moveCursor(1, 1)
Move the cursor to the left of the character in the 1st row, 1st column.
Return ‘a,’ which is the character on the right of the cursor.
a
18
countCharacter(‘b’)
The string following the cursor is “ababcdefgeb.”
Since ‘b’ appears three times in this string, return 3.
3
19
countCharacter(‘a’)
Return 2 since ‘a’ appears twice in “ababcdefgeb.”
2
[Constraints]
1. init() is called in the beginning of each test case.
2. For each test case, insert() and moveCursor() can be called less or equal to 30,000 times, respectively.
3. For each test case, countCharacter() can be called less or equal to 40,000 times.
[Input and Output]
As the input and output are processed in the provided code in the Main, they are not processed separately in the User Code.
The output result for the sample input is in the format of “#TC number result.” It is the correct answer if the result is 100; it is the wrong answer if it is 0.
#define opt __attribute((optimize("Ofast")))
#include <string>
#define MAX_AZ 26
#define MAX_HW 300
using namespace std;
int h, w, consorPos, ket_thuc;
string s;
int countS[MAX_HW][MAX_AZ];
opt void init(int H, int W, char mStr[]){
s = "";
consorPos = 0;
for (int i = 0; i < MAX_HW; i++)
for (int j = 0; j < MAX_AZ; j++)
countS[i][j] = 0;
h = H;
w = W;
for (ket_thuc = 0; mStr[ket_thuc]; ket_thuc++){
s.push_back(mStr[ket_thuc]);
countS[ket_thuc / w][mStr[ket_thuc] - 'a']++;
}
}
opt void insert(char mChar){
s.insert(s.begin() + consorPos, mChar);
int row = consorPos / w;
int hl = ket_thuc/ w;
for (int r = row; r < hl; r++){
countS[r][s[r * w + w] - 'a']--;
countS[r + 1][s[r * w + w] - 'a']++;
}
ket_thuc++;
consorPos++;
countS[row][mChar - 'a']++;
}
opt char moveCursor(int mRow, int mCol){
consorPos = (mRow - 1) * w + (mCol - 1);
if (consorPos >= ket_thuc){
consorPos = ket_thuc;
return '$';
}
return s[consorPos];
}
opt int countCharacter(char mChar){
int sum = 0;
int row = consorPos / w;
int hl = ket_thuc / w;
if (consorPos == ket_thuc) return 0;
for (int j = row; j <= hl; j++)
sum = sum + countS[j][mChar - 'a'];
for (int i = (row * w); i <= consorPos-1; i++)
if (s[i] == mChar) sum--;
return sum;
}