| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 12155 | Cat-Toast Crisis |
|
| 12521 | Break my heart |
|
| 12522 | Thanos' Return |
|
Description
Recently, scientists finally find a way to produce unlimited energy. The scientists call it "Cat-Toast".
In case that someone might not know:
While buttered toast falls onto the ground, it will always land with its buttered side - Falling Toast Theorem(FTT)
While cats fall onto the ground, they will always land with their four feets. - Falling Cat Theorem(FCT)
By FTT, we can assume that if we put butter on both sides of the toast, we might create a perpetual motion machine, because by FTT, we know that the buttered side will land onto the ground. However, there are two buttered sides. If any side of the toast lands, there will be a contradiction, so the toast will never fall and continue spinning around. We can apply the same way on FCT.
However, there is a big problem. if we just put two buttered toasts or two cats together, there will be no momentum, and obviously it won't spin except for any external force, which cannot be a perpetual motion machine. This problem had confused scientists for centuries.
Recently, scientists finally got a breakthrough progress. They combined a cat and a buttered toast and it just spins by itself! Due to the difference mass of a cat and a buttered toast, the machine itself will provide the momentum to spin, and it will never fall onto the ground (due to the contradiction we proved before), the first perpetual motion machine was born!
The original video is here.
Scientists found that if two cat-toasts' distance are equal to or closer than r, there will be a collision which cause a small black hole and soon disappear, which is very dangerous. The cat-toast must be secured separately. Also, if there are multiple cat-toasts that will collide, those cat-toasts will all collide together and spawn exactly one black hole. If there's any problem, you may refer to Sample I/O.
One day in NTHU, a servitor just carries a lot of cat-toasts, each with a secured box. He accidently falls down and all the cat-toasts just drop out of their own boxes.
Now given r and all the coordinates of all cat-toasts, the servitor wants to know how many cat-toasts remains there after some destructive collisions and how many black holes spawned.
Note that the distance of two cat-toasts is sqrt( (x1-x2)^2 + (y1-y2)^2 ), where (x1,y1) and (x2,y2) are the coordinates of this two.
Input
The first line contains two integers n, r, indicate the number of cat-toast, the distance r decribed above.
The next n lines, each line contains two integers xi, yi, indicates the location of the i-th cat-toast.
1 <= n <= 1000, 1 <= r <= 104
1 <= xi, yi <= 104
Output
The first line of the output is the total number of cat-toasts that still remains and the total number of black holes after collisions, separated by a space.
Remember to output a '\n' at the end of the output.
(In fact, except for the problem DO ask you not to output a '\n' at the end of the output, mostly you shoul output a '\n' at the end.)
Take Sample I/O as an example, obviously cat-toast located at (5,15) and (1,15) will collide. (1,7), (1,3), and (5,3) will collide together because (1,7), (1,3) collides, and (1,3), (5,3) collides, just like a chain, or a tree.
There's only one remaining cat-toast located at (500,500) and spawned 2 black holes, so the answer is "1 2" without quotes.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
I have broken many girls' hearts into pieces. But none of them mad at me. None.
~ by anonymous surgeon
You're a surgeon, you need to mend those girls' hearts. Therefore you need a data structure to support some functions.
This question is about maintain a set that contains only integers.
There will be n instructions.
Each instruction will be either:
insert:
Insert a new element ai into the set. Note that if the element has already in the set, do nothing.
print:
print all the element in the set in increasing order.
min:
print the number in the set that is the smallest. If there's no number, do nothing.
range_erase:
You will have two integer l, r.
You need to erase all the elements ai in the set that l <= ai <= r
Hint: You can solve this question very fast by using std::set .
These are some functions you may use in your code:
set.begin(), set.size(), set.erase(), set.lower_bound(), set.upper_bound(), set.insert(). To traverse through your set, you may also need iterator or type auto(only in c++11!)
You can also solve this question in C.
Input
the input will contain several lines.
The first line only contains an integer n (1 <= n <= 5000)
The following are n lines.
Each lines contains a instruction list above.
Note that ai (0 <= ai <= 10^9)
Output
For each print instruction, print all the number in the set in increasing order.
Each number is separated by a single blank.(No blank at the the end!)
Remember to print \n at the end of output
For each min instruction, print the smallest number in the set.
Remember to print \n at the end of output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The Avengers finally gathered all the infinity stones together from different universe, and saved all lives that disappeared five years ago. However, Thanos comes again, from different universe. And this time, he'll eliminate the whole universe and create a new one, a grateful universe.
Thanos needs to compute how many energy he needs to consume to destruct and create a new universe. That is, he has to perform lots of matrix operations, including addition and multiplication. Now he threaten you to calculate these troublesome math, so that he can spend more time to deal with those ants ── those so called "Avengers".
Thanos thinking about this problem
If you click on this picture, something might happen...
You're given and , indicate the row number and column number of matrix .
An operation : + or *, and times will be given.
-
For operation
+, you need to calculate and print the result.Note that:
-
For operation
*, you need to calculate and print the result.Note that:
This problem is partial judge. Note that in this problem, you can and you must use C++ to solve this problem.
in function.h, we have implemented the interfaces and some implementations of the class Matrix for you. What you need to do is to implement the remaining functions.
Functions we have implemented:
-
Matrix()(constructor):Construct an empty Matrix object.
-
const int &getrow():Get the row number of the corresponding matrix.
-
const int &getcol():Get the column number of the corresponding matrix.
-
const int *operator[] (const int &x) const:Implement operator[] for
Matrixclass. Make private membermatcan be viewed using[]only. For example, we can viewM.mat[x][y]by accessingM[x][y]for aMatrixobjectM. -
void print():The function to print the whole matrix.
Functions you have to implement:
-
Matrix(int r, int c)(constructor):Construct an Matrix with row =
rand column =c, and all elements equals to 0. -
int *operator[] (const int &x):Implement operator[] for
Matrixclass. Make private membermatcan be accessed using[]only. For example, we can accessM.mat[x][y]by accessingM[x][y]for aMatrixobjectM. -
Matrix operator+ (const Matrix &x) const:Perform "addition" operation, then return the result.
-
friend Matrix operator* (const Matrix &x, const Matrix &y):Perform "multiplication" operation, then return the result. Note that this function is declared with
friend.
In case of the result might be too large, all numbers should be module by 10007.
UPDATE: All nubmers should be module by 10007, and should output the positive one.(-2395%10007=7612)
Input
The first line contains , , , and , respectively.
There are lines below. Each line contains numbers. These numbers indicate every element in matrix .
, , , where here incidates all elements in matrix .
Output
Output the result of the corresponding operation.
For output format, please refer to print function in function.h and the sample output.