| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11462 | cppreference |
|
| 11965 | Queueing |
|
| 11966 | Parentheses Matching |
|
| 11967 | Count the Leaves |
|
| 11968 | Swapsort_Extend |
|
| 11970 | AI Chatbot (Bonus) |
|
| 11971 | Turn left! (Bonus) |
|
Description
You need to write a program to simulate a queue of names. Each name is a string consisting of English letters only. There are three operations:
1. “Push [name]”, which means to enque name in the queue.
2. “Pop”, which means to deque. If the queue is empty, this operation takes no effect.
3. “Front”, which means to print out the name in the front of queue. If the queue is empty, print "empty" (without quotes).
Case1 : #operation <= 10^2, There will be no "Pop" and "Front" command when queue is empty.
Case2 : #operation <= 10^3. There will be no "Pop" and "Front" command when queue is empty.
Case3 : #operation <= 10^4.
Case4 : #operation <= 10^6.
Input
Each line contains one of the following operations. “Push [name]” (without quotes), “Pop” (without quotes), “Front”(without quotes). The length of each name is at most 10.
Output
For each “Front” operation, print out the name in the front of the queue.
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
Given a tree, count the number of leaves in this tree. Each node has unique integer identification (ID), but all IDs may not be consecutive.
Input
There are multiple test cases. Each test case begins with an integer N (1 <= N <=1000). In the following N lines, each line has two integer a and b (1 <= a,b <= 1000), indicating node a is node b’s parent. The next line contains an integer R, which represents the root of the Tree. You can assume that all the nodes will be on the same tree. The input is terminated by N = 0.
Output
Print the number of the leaves for each test case.
Hint: All leaves have no children!
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given an integer sequence, say {6, 1, 3, 4, 5, 2}, can we sort the sequence by keeping swapping the first number with its two neighbors: the second number and the last number ?
For example, Swap the first number 6 and with the last number 2 to get {2, 1, 3, 4, 5, 6}, and then swap the first number 2 and the second number 1 to get {1, 2, 3, 4, 5, 6}, and we get the sequence sorted.
In function.h we define a class called SwapSort. A constructor and member functions show_solutions, solve, isSorted are implemented. Your task is to complete the implementation of extend function:
1. set<State> extend(State s);
A State is defined as using State = vector<int>;
For some State s, we may extend it by swapping the first number with the second one, or swapping the first number with the last one. Therefore, from State s we may generate two new states, and insert them into a set.
Note:
1. no duplicate states are allowed in a solution.
2. For OJ submission, you may choose c++ 11 as your compiler.
You need to implement the function in function.cpp
Input
An integer sequence, separated by spaces. End by EOF.
Output
The output will be generated by function.h
Sample Input Download
Sample Output Download
Partial Judge Code
11968.cppPartial Judge Header
11968.hTags
Discuss
Description
Niflheimr wants to build a chatbot on his facebook. So that, everytime when he becomes offline, the chatbot will automatically chat with other people.
This chatbot's data bases on chatlog, in the beginning, the log is empty.
Here's the rule of the chatbot: upon reception of a "sentence" from a person,
1. If the chatbot has logged a "comment" for the sentence before, it will reply the "comment" he logged before.
2. If the chatbot hasn't seen the "sentence" before, it will simply reply "what's that means?" and then log the following reply of the person as the corresponding "comment" for the "sentence".
Here's an example:
Person: Hi
Chatbot: what's that means?
Person: Hi
(chatbot now logs 'Hi' -> 'Hi')
Person: Hi
Chatbot: Hi
Oh, here's an another example.
Person: Hello
Chatbot: what's that means?
Person: gtg
(chatbot now logs 'Hello' -> 'gtg')
Person: Hello
Chatbot: gtg
There are 4 testcases
for testcase 1: all input sentences will be only one word , and the chatbot have never seen it before.
for testcase 2: all input sentences the chatbot have never seen before.
for testcase 3: all input setences will be only one word.
Hint:
1. You can use std::map to store the chatog.
2. You can use std::getline (std::cin,string) to get from stream into string.
How to use getline:
// how to use getline
#include <iostream>
#include <string>
int main ()
{
std::string name;
std::cout << "Please, enter your full name: ";
std::getline (std::cin,name);
std::cout << "Hello, " << name << "!\n";
return 0;
}
Input
There are a lot of sentences. and each line contains one sentence.
"_END" means the END.
Don't output anything with _END
Output
1. If the chatbot has logged a "comment" for the sentence before, it will reply the "comment" he logged before.
2. If the chatbot hasn't seen the "sentence" before, it will simply reply "what's that means?" and then log the following reply of the person as the corresponding "comment" for the "sentence".
The output will be the chatbot's reply for each input sentence.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Niflheimr is playing a game call "Maze", he can control the robot.
Available controls are as below:
key up: move forward
key left: turn left
key right: turn right
But the right key of his keyboard is broken, he has to turn left 3 times to turn right. (-270º is equal to +90º)
Maze will be a rectangle surrounded by walls, with 'start' and 'end' points.
Note that the robot is initially at 'start', and the initial facing direction is not determined (this will affect the answer to our question)!
Figure out the minimum times he should type his left key to reach the 'end'.
HINT:
here's some code for you to understand this problem. you can use it and implement the solve or rewrite all the code by yourself.
#include <queue>
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
/// TypeDef
typedef pair<int, int> cor;
typedef int Direction;
/// ClassDef
class CorData {
public:
int x, y, dir;
CorData(int _x, int _y, int _dir) {
x = _x;
y = _y;
dir = _dir;
}
};
/// ConstDef
const int mazeMaxSize = 100;
const int dirSize = 4;
/// GlobalDef
int Maze[mazeMaxSize][mazeMaxSize];
int MazeBeen[mazeMaxSize][mazeMaxSize][dirSize]; /// 儲存走到該位置 , 面向
/// 的最小轉彎次數 , INF =1e9
queue<CorData> que, nextQue; /// the queue for BFS .
int movex[4] = {-1, 0, 1, 0}; /// 記錄DIR對應到的X移動方向 {上,左,下,右}
int movey[4] = {0, -1, 0, 1}; /// 記錄DIR對應到的Y移動方向 {上,左,下,右}
int x, y;
/// FunctionDef
inline int Turn(int i);
inline void printMazeBeen();
inline void printMaze();
inline void initMaze(); /// x ,y is global variable.
inline void loadMaze();
int solve();
/// MAIN Function
int main() {
int T;
int ans;
cin >> T;
while (T--) {
loadMaze();
// printMaze();
ans = solve();
cout << ans << "\n";
}
}
/// Inline function
inline int Turn(int i) { return (i + 1) % 4; }
/// for debugging
inline void printMazeBeen() {
for (int i = 0; i < 4; i++) {
cout << "============printMazeBeen==========\n";
for (int j = 0; j < x; j++) {
for (int k = 0; k < y; k++) {
if (MazeBeen[j][k][i] == int(1e9)) cout << "N ";
else cout << MazeBeen[j][k][i] << " ";
}
cout << "\n";
}
}
}
/// for debugging
inline void printMaze() {
cout << "=========printMaze===========\n";
for (int j = 0; j < x; j++) {
for (int k = 0; k < y; k++) cout << Maze[j][k] << " ";
cout << "\n";
}
}
inline void initMaze() { /// x ,y is global variable.
for (int i = 0; i < x; i++) {
for (int j = 0; j < y; j++) {
MazeBeen[i][j][0] = MazeBeen[i][j][1] = MazeBeen[i][j][2] = MazeBeen[i][j][3] = int(1e9); // let never been equal to 1e9(INF)
}
}
while (!que.empty()) que.pop();
while (!nextQue.empty()) nextQue.pop();
return;
}
inline void loadMaze() {
string str;
cin >> x >> y; /// input Maze x, y .
initMaze();
getline(cin, str);
for (int i = 0; i < x; i++) {
getline(cin, str);
for (int j = 0; j < y; j++) {
if (str[j] == '*') {
Maze[i][j] = -1;
} else if (str[j] == '.') {
Maze[i][j] = 0;
} else if (str[j] == 'S') {
Maze[i][j] = 1;
for (int d = 0; d < 4; d++) que.push(CorData(i, j, d));
} else if (str[j] == 'E') {
Maze[i][j] = 2;
}
}
}
}
int solve() {
/// TODO: implement this function so that the BFS will work.
}
Input
first line will be an integer T means T cases below.
each testcase will have two integer X Y shows the size of Maze
there will be X lines , Y character each line.
for all testcases : 0 < X , Y < 31
for '*' means wall , barrier.
for '.' means path.
for 'S' means start.
for 'E' means end.
Output
output should be one integer to show the minimal left button to finish the game.