| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 13248 | I2P(II) Final-Exam Cheat Sheet |
|
| 13538 | Find the pairs 2 |
|
| 13545 | NPK-group (1/3) |
|
| 13546 | NPK-group (2/3) |
|
| 13547 | NPK-group (3/3) |
|
| 13548 | Sokoban (1/3) |
|
| 13549 | Sokoban (2/3) |
|
| 13550 | Sokoban (3/3) |
|
Description
set:
Sets are containers that store unique elements following a specific order.
#include <set>
begin: Return iterator to beginning
end: Return iterator to end
rbegin: Return reverse iterator to reverse beginning
rend: Return reverse iterator to reverse end
empty: Test whether container is empty
clear: Clear content
size: Return container size
insert: Insert element
erase: Erase elements
find: Get iterator to element
lower_bound(val): Return an iterator pointing to the first element in the container which is not considered to go before val (i.e., either it's equivalent or goes after).
list:
Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions.
#include <list>
begin: Return iterator to beginning
end: Return iterator to end
rbegin: Return reverse iterator to reverse beginning
rend: Return reverse iterator to reverse end
empty: Test whether container is empty
clear: Clear content
size: Return container size
front: Access first element
back: Access last element
emplace_front: Construct and insert element at beginning
emplace_back: Construct and insert element at the end
push_front: Insert element at beginning
push_back: Insert element at the end
pop_front: Delete first element
pop_back: Delete last element
erase: Erase elements
remove: Remove elements with specific value
vector:
Vectors are sequence containers representing arrays that can change in size.
#include <vector>
begin: Return iterator to beginning
end: Return iterator to end
rbegin: Return reverse iterator to reverse beginning
rend: Return reverse iterator to reverse end
empty: Test whether container is empty
clear: Clear content
size: Return container size
front: Access first element
back: Access last element
emplace_back: Construct and insert element at the end
push_back: Add element at the end
pop_back: Delete last element
queue:
#include <queue>
empty: Test whether container is empty
size: Return container size
push: Insert element
pop: Remove next element
front: Access next element
priority_queue:
#include <queue>
empty: Test whether container is empty
size: Return container size
push: Insert element
pop: Remove top element
top: Access top element
stack:
#include <stack>
empty: Test whether container is empty
size: Return container size
top: Access next element
push: Insert element
pop: Remove top element
map:
#include <map>
begin: Return iterator to beginning
end: Return iterator to end
rbegin: Return reverse iterator to reverse beginning
rend: Return reverse iterator to reverse end
empty: Test whether container is empty
clear: Clear content
insert: Insert Element
erase: Erase element
count : Count elements with a specific key
find: Get iterator to element
operator[]: Access element
deque:
#include <deque>
push_front: Insert element at beginning
push_back: Insert element at the end
pop_front: Delete first element
pop_back: Delete last element
empty: Test whether container is empty
size: Return container size
insert: Insert element
erase: Erase element
operator []: Access element
front: Access first element
back: Access last element
clear: Clear the container
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Several men and women are going to attend the singles mixer (聯誼會) tonight. As the organizer, you have collected the personal score of each participant. Several independent events will occur during the party. Each event has a random lucky value ei. If the sum of the scores of a man and a woman equals ei, they will form a perfect pair and dance together. However, since this is a singles mixer and the events are independent, a specific man/woman may dance with a different woman/man in a different event.
Your staff has shown you the lucky value of each event. To gain more control over the party, you want to calculate the number of perfect pairs in each event before the singles mixer.
Input
The first line contains 3 positive integers M, W and E, where there're M men, W women and E events.
The second line contains M integers, denoting the personal score of each man.
The third line contains W integers, denoting the personal score of each woman.
Next, followed by E lines, each line has the lucky score ei.
Testcases:
Cases 1~3: the score of every man or woman is different, 0 < M + W <= 200000, min(M, W) * log2(max(M, W)) * E <= 108
Case 4: 0 <= score, ei <= 100000, 0 < M + W <= 200000, min(M, W) * log2(max(M, W)) * E <= 108
Case 5: 0 < M + W <= 200000, min(M, W) * log2(max(M, W)) * E <= 108
The absolute values of all scores range in [0, 107).
Output
For each event, print the number of perfect pairs. Remember to add a '\n' at the end.
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 are lining up in a queue to buy Jinkela. Each person is given a unique id x. Lining up is tedious, so everyone wants to cut in line! These people follow some rule when they cut in line:
when a person enters the queue,
- if the queue is empty, he becomes the first person in the queue;
- if there is a friend in line, he will queue after the last person among the friends;
- otherwise, he becomes the last person in the queue.
Some people may leave the queue without buying Jinkela, and these people may join the queue again.
You are curious about the order people get their Jinkela. Given the status of the queue, whenever someone gets his Jinkela, output his id.
Refer to the sample IO for example if you don't understand the rule.
Input
The first line contains two integers n m: the number of commands and the number of friend groups.
The following m lines are the friend groups, where, in each line, the first integer k is the number of the group members, and the next k integers are the id's of the group members. (Each person belongs to at most one group of friends.)
The following n lines are the commands, which can be:
- ENQUEUE x: the person with id x enters the queue;
- LEAVE x: the person with id x leaves the queue;
- DEQUEUE: the first person in the queue buys his Jinkela and leaves the queue.
Testcases:
- Cases 1~3: Without LEAVE commands; 1 <= n, x, k <= 1000, m = 3; everyone belongs to a group, and two persons are in the same group if the remainders are the same when their id's are divided by m.
- Cases 4~6: Without LEAVE commands; 1 <= n, x, m <= 100000, 1 <= k <= 100.
- Cases 7~9: Without LEAVE commands; 1 <= n, m <= 100000, 1 <= x <= 2147483647, 1 <= k <= 100.
- Cases 10~12: With LEAVE commands; 1 <= n, m, k <= 1000, 1 <= x <= 100000; having LEAVEed the queue, a person will not enter the queue again.
- Case 13: With LEAVE commands; 1 <= n, x, m <= 100000, 1 <= k <= 100; having LEAVEed the queue, a person will not enter the queue again.
- Case 14: With LEAVE commands; 1 <= n, m <= 100000, 1 <= x <= 2147483647, 1 <= k <= 100.
In addition, for each "LEAVE x" command, it is guaranteed that the person with id x must be in the queue.
Hint:
The 13rd & 14th testcases are more challenging. For the LEAVE commands, find some way to avoid "leaving the queue immediately".
Output
For each DEQUEUE command, please output the id of the person who buys his Jinkela and leaves the queue. If the queue is empty, output "The queue is empty".
Each output occupies a single line. Remember to add a '\n' at the end.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Sokoban (倉庫番, Sōko-ban, “warehouse keeper”) is a puzzle video game genre in which the player pushes crates or boxes around in a warehouse, trying to get them to storage locations.
- The player may move horizontally or vertically onto empty squares (never through walls or boxes).
- The player can move a box by walking up to it and push it to the square beyond. Boxes cannot be pulled, and they cannot be pushed to squares with walls or other boxes.
- From Wikipedia, the free encyclopedia.
Your goal is to find the actions required to solve the problem.
The possible tiles are listed as follows:
'o': The player stepping on a regular tile
'O': The player stepping on a target tile
'x': A box on a regular tile
'X': A box on a target tile
' ': Nothing on a regular tile
'.': Nothing on a target tile
'#': Wall
Your program should output a sequence of actions that push all the boxes to the target tiles, where the actions are represented by the uppercase WASD characters:
W: move the player upA: move the player leftS: move the player downD: move the player right
Example 1:
Input:
1
4 9
#########
# xox..#
# #####
#########
Output:
DDAAASAAWDDDD
Note:
- Your solution is not required to have the least number of moves. Any sequence that solves the problem is valid.
- Your program only needs to deal with valid inputs. It is guaranteed that:
- there is only one player, stepping on either a regular tile or a target tile;
- the number of target tiles is equal to the number of boxes;
- all tiles other than wall tiles are within an enclosed area formed by wall tiles;
- no more than 5 boxes;
- there is at least one solution.
- If you get Runtime Error, maybe you should use a more efficient state representation to reduce memory usage.
Input
The first line contains a single integer T (1 ≤ T ≤ 100). Then T test cases follow.
For each test case:
- the first line gives two integers N and M (1 ≤ N*M ≤ 256);
- each of the next N lines consists of M characters, representing the tiles of each row.
Output
For each test, output a sequence of actions, represented by the uppercase WASD characters, that push all the boxes to the target tiles. Remember to add a '\n' at the end.