| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 1709 | Problem TEST. TESTaceology |
|
| 1710 | Problem A. Ambrosia |
|
| 1711 | Problem B. Black Dark Witch |
|
| 1712 | Problem C. Cavern |
|
| 1713 | Problem D. Doom |
|
| 1714 | Problem E. Energy Gun |
|
| 1715 | Problem F. Friendly Fire |
|
| 1716 | Problem G. Gate |
|
| 1717 | Problem H. Hyper Portal |
|
| 1718 | Problem I. Information |
|
| 1719 | Problem J. Journey’s End |
|
Description
Little Graphy is fond of testaceology, which is a topic of collecting shells.
One day, Little Graphy found a magic shell which can solve A + B problem.
However, Little Graphy can’t even solve the A + B problem, she want to know whether the answer C is correct.
Now, she need your help. She give you B and C, and want you to calculating the original A, then she can check the answer C is correct or not.
Input
The first line is an integer T indicating that there’re T test cases.
For each test case, there’s only one line cotains two integers C;B.
• T <=100
• C,B will always fit in a 32-bit signed integer.
Output
For each test case, print one line cotains an integer A.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
enough, they find the intruders’ power overwhelming. As a result, Little Graphy retreats from the Gobi secretly with two alpacas. They escape successfully, but three days after they leave Gobi, Little Graphy finds herself with an empty stomach.
“Are there any prone grass?” asks the hungry hare.
“Don’t see anything in sight,” the pink alpaca, Pinky, replies immediately.
But then the blue alpaca, Blues, bouncing up and down, announces with great enthusiasm, “but I know a place where you can find the holy ambrosia!”
“The holy ambrosia?” Little Graphy asks slightly confused.
“Yes, and there’s a whole mountain of prone grass there!” Pinky yells excitedly.
“Asi que bueno, ellos seran!” Blues says in Spanish.
Little Graphy has a weird feeling about this, but she’s too hungry to think. The only thing she can think about is eating.
“Okay, how to get to the place?” “The Holy Candy Mountain!” answers Pinky.
“Umm... then how are we going to get to the Holy Candy Mountain?”
“It’s quite easy,” said Blues. “All you have to do is write a program to print the following magic
spell.”
But Little Graphy knows nothing about programming, since she is too hungry to even think.
Now it’s your show time. Please write a programming to print the magic spell.
Input
Chaka Chaka Chaka Chaka Chu Chu~
You don’t have to read anything from standard input in this problem
Output
You should output the exactly same characters in the following fifteen lines.
There are always one hundred characters per single line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
After the magic spell is printed, they find that they’ve already reach the Holy Candy Mountain, which is so magnificent that Little Graphy can’t even breathe. While Little Graphy is still in shock, a huge banana drops down in front of them out of the blue.
“Hey! It’s Banana King!” Pinky shouts, “What is he doing here?”
“Hummm, I think he’s dead.” Blues bounces on the body of Banana King.
“Wowwwwww, dead banana! Maybe it is time to have some fruit!” Pinky says excitedly, peeling the banana.
“Stop it, Pinky. We had better move on,” Little Graphy says with its trembling sound, “the sky is getting dark.”
They quickly bypass the dead Banana King, going straightly up to the summit. As soon as they cross one of the forests on the hillside, a woman with a black cloak appears.
“I’m Black Dark Witch. What are you guys doing here?” the woman stares at them.
“We’re here for the prone grass, do you have some?” Pinky answers, “Little Graphy is starving.”
“I think Little Graphy is hungry enough to eat a mountain of prone grass,” laughs Blues.
“Prone grass? Oh…okay, follow me.” Black Dark Witch says softly, entering the cottage behind her.
“Bang!” the door is slammed and locked.
“What are you doing, Little Graphy?” Blues asks.
“What? I’ve just entered, didn’t even touch the door yet!” Little Graphy says, confused.
“Hahahaha,” laughs the Black Dark Witch, “Why are there so many silly guys wants to steal my prone grass away just like the stupid banana?”
“Bye, poor animals,” Black Dark Witch smiles evilly, leaving through the Scary Door.
“Wait!” Little Graphy yells, “Oh chaaaka~~ the door is locked! So scary!”
“I know the way to open the Scary Door,” says Blues.
“There’re some magic plates in the room, all of them have the same size and same pattern.”
“You should pile them in a 5*L rectangle in such a way that none of the marks on plates overlap, and L is smallest.”
“Notice that you should never flip or rotate any of them.”
However, as you know, Little Graphy can’t even solve the A+B problem. It’s your show time again!
Input
There’re several test cases, ended with EOF.
There are two integers n;m in the first line of each test case, which means there’re m plates, with a size of 5*n.
The 2nd to 6th line of each test case represents the pattern. ‘.’ means blank. ‘X’ means mark, which can’t overlap.
• There’re no more than fifteen test cases.
• 1<=m<=20
• 5
• nm<=107
Output
For each test case, print a line containing an integer indicating the smallest length.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Stepping into the chamber E, Little Graphy and her friend find the Black Dark Witch packaging up some prone grass.
“Black Witch!” yells Pinky, “I’ m gonna burnnnn youuuu!”
“Impressing, really impressing. Many people have died in this cavern,” says the Black Dark Witch.
“However, can you escape again?” she smiles, and disappears into thin air.
“Wai…, ” a laser shoots through Pinky’s body before she finishes her word.
“Pinkyyyyyyyyyyyyyyyyyyy!” cries Blues, “No one will be willing to go scuba diving wi…wow!!” Not until Little Graphy pulls Blues down does he find that the laser gun has been aimed at him.
“Chuchu! I almost get killed!” Blues cries again, “We have to shut this thing down!”
“Well, I think I’ve find the way to turn off the laser gun,” says Little Graphy.
“There’re n red stones and m blue stones on the floor, and there’re some links between some pairs of red and blue stones.”
“Everytime the laser gun shoots, one of the link shines.”
“I think we should destroy some stones in such a way that at least one stone is destroyed in each pair.”
“However, we don’t have lots of time to destroy them, we should spend as less time as possible!”
Can you help Little Graphy figure out the fastest way of destroying stones?
Input
The first line is an integer T indicating that there’re T test cases.
There’re three integers n, m, k in the first line of each test case, which means there’re n red stones, m blue stones, k pairs of links. The second line contains n integers, the ith integer Ri means red stone i will take Ri seconds to destroy. The third line contains m integers, the ith integer Bi means blue stone i will take Bi seconds to destroy. Each of the next k line contains a pair (a, b) means that there is a link between red stone a and blue stone b.
- T ≤ 15
- 1 ≤ n, m ≤ 150
- 0 ≤ Ri, Bi < 231
- 0 ≤ minimum time Little Graphy needs < 230
Output
Output three lines for each test case. The first line should contains an integer indicating the minimum time Little Graphy needs. The second line contains an integer A and followed by A accending integer represending the number of red stones to be destroyed and which red stones should be destroyed. The third line contains an integer B and followed by B accending integer represending the number of blue stones to be destroyed and which blue stones should be destroyed.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
“Hurray! We finally destroyed the red stone system!” Blues bounces up and down.
Then he sees Pinky’s body going stiff. “Pinky, I will live for you!” He yells, but all that answers him are his own echoes.
“Little Graphy, let’s go!” Blues stands up, wipes his tears, and walks toward the exit.
Little Graphy keeps up with Blues, and soon she finds a chest filled with some potions. “Oh, the splash potion of harming 2! It may be a great weapon!” she thinks.
Outside the cavern, they find a guy going against a lot of monsters.
He says, “My name is Big China Day. Can you please help me defeat the little pets from the Black Dark Witch?”
Little Graphy looks around, and finds that there are N monsters surrounding them. Monster i has a HP (Health point) Hi. If a monster’s HP goes down to 0, it will die.
Little Graphy has M splash potions of harming 2, and each potion can cause 1 HP of damage on one monster. Big China Day has a magic energy gun which can nerf monsters. That is to say, if the monster i is shot, his HP will become Ci (Ci ≤ Hi). Then it will be easily defeated. However, you can’t shoot at the same monster twice!
The magic energy gun can shoot at most K times, and Little Graphy wants to know how many monsters they can kill with the best strategy.
Input
The first line contains an integer T indicating the number of test cases.
Each test case begins with N, K, M.
The following N lines contain two integers Hi, Ci.
- T ≤ 30
- 1 ≤ N ≤ 50000, 0 ≤ K ≤ N and 1 ≤ M ≤ 1014
- 1 ≤ Ci ≤ Hi < 231
Output
For each test case, print a single line containing a non-negative integer which means the maximum number of monsters they can kill.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Being satisfied with Little Graphy’s performance, Big China Day says, “You already have the ability to be a good warrior.”
“I don’t have anything more to teach you. All you need to defeat those evil river crabs is faith.”
“Good luck, hare, maybe we’ll meet again in the future,” Big China Day waves his hand and starts his next journey.
After ten minutes of study, Little Graphy learns all the things Big China Day knows.
“Wow, it’s time to get our kidney…our Gobi back! Let’s roooooock!” Blues cheers.
“Calm down,” Little Graphy pulls Blues, “we still need something to bribe the guard of the Gobi Gate.”
“Ummm, You’re right. I’ll find out where Gobi is…” says Blues, acting as if he were The Thinker.
“Surely, you’re not listening to me…. Well, I might as well find a present myself,” sighs Little Graphy.
Entering a shop, she finds two queues of rabbit dolls. “I can’t imaginate how cute it would be if I combine these dolls!” Little Graphy thinks while pulling Blues, who is still acting The Thinker.
“Those guards will be too shocked to move if they see such a cute thing!” she says, “It’s god-like!!”
As a result, Little Graphy decides to make a tower of rabbit dolls.
Little Graphy can choose one doll from the front of the two queues each time. She may decide to keep or not to keep the doll each time she takes one doll. The dolls she keeps will be stacked onto the rabbit tower by the order she takes. It means that if the doll is the kth doll she keeps, it’ll be the kth doll if you count from the bottom.
Every rabbit doll has two values V, D. Any rabbit doll i in the tower, which has x dolls on top of it, will contributes Vi − x × Di points to the cuteness. In order to bribe the guard, Little Graphy wants to maximize the cuteness of the tower. Can you help her calculate the maximum value of cuteness?
Input
The first line contains an integer T indicating the number of test case.
Each test case starts with two integers n, m. indicating the length of the two queues.
The following line contains n pairs of integers V, D representing the n rabbits in the first queue.
The next line contains m pairs of integers V, D representing the m rabbits in the second queue.
- T ≤ 10
- 1 ≤ n, m ≤ 200
- 0 ≤ Vi, Di ≤ 106
Output
For each test case, print the maximum cuteness of the rabbit tower.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
“Once you get the information, you get victory,” Big China Day says seriously.
After hundreds of battles against each other, neither Little Graphy nor the river crabs are able to defeat the other. One day, when Little Graphy is trying to figure out where the crabs are hidding just like usual, Blues rushes into her tent.
“Graphy! Graphy!” he yells. “How many times did I tell you not to be so rough?” Little Graphy scolds.
“Big China Day said that ‘information is the key to victory,’ right?” Blues says excitedly.
Little Graphy tries to answer, “I’m not sure if h…”
“Guess what? I found some encoded messages in the fortress we destroyed last week!” Blues keeps talking, “Look!”
“My intuition of graph tells me this must be a description of a tree.” Little Graphy says.
“Tree? This is just two sequence of integers and an big number,” he asks, “how can it be a tree?”
Little Graphy smiles to Blues and says, “Obviously, the first sequence is the preorder of the tree.”
“And, the second sequence should be its postorder.”
“The big number k means that the tree’s inorder is the kth possible inorder in lexicographical order.”
“Wow! How do we construct the tree?” Blues asks.
“Hummmmmmnmmmmm…In fact, we need to find out the inorder first…” Little Graphy answers.
Guess what? It’s your show time!
Input
There’re several test cases in the file, ended with EOF.
Every test case starts with two integers n, k.
The following line contains n integers, representing the preorder.
The third line also contains n integers, representing the postorder.
- 1 ≤ n ≤ 200000
- 1 ≤ k ≤ number of possible inorder ≤ 260
- 1 ≤ any element of the tree ≤ 109
- We guarantee that each number in the tree is distinct.
- There are no more than 5 test cases.
- Take a look at Problem C if you don’t know what lexicographical order is.
Output
For each test case, print the inorder traversal of the tree.