| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 1610 | Problem A. NTHU |
|
| 1611 | Problem B. Game |
|
| 1612 | Problem C. Land |
|
| 1613 | Problem D. Daily Walk |
|
| 1614 | Problem E. Mahjong |
|
| 1615 | Problem F. Party |
|
| 1616 | Problem G. Magic Box |
|
| 1617 | Problem H. Give Me Five |
|
| 1618 | Problem I. Lazy Typing |
|
| 1619 | Problem J. Table |
|
Description
ATP is a cute caterpillar living in the SK (Shik Kingdom). To prove that she's the bravest caterpillar in the world, she's going to participate a dangerous game. The rule is pretty easy: First, the participant should choose a grid of the NxM board. The game has K+1 stages and some of the rows and columns will become red each stage (It may turn back black at the next stage). The participant can either stay at current grid or move to one of the adjacent grids (eight-direction) between each stage. If the participant stands on a row or a column that was red at the previous stage, she'll be squashed. (Note that no rows or columns will become red at the (K + 1)-th stage.)
What a mad game! It's impossible to survive! Well, it's not the case for ATP, a brilliant hacker. ATP has hacked into the system and pulled out all the data about the game, hence she's able to predict what rows and columns will become red at each stage. Now, the problem is to find out a safe path.
Input
There is an integer T in the first line, representing the number of test cases. The first line of each test case contains three numbers N, M, K. The (3xi-2)-th to (3xi)-th lines in the next 3xK lines describe the rows and columns that become red at the i-th stage. The first line of the three lines contains two integers X, Y. The stage contains X integers, representing the rows that become red. The third line contains Y integers, representing the columns that become red. Index begins from one.
1<=T<=10
1<=N, M, K<=1000
1<=X<=N
1<=Y<=M
Output
You should output one line for each test case. Note that ATP will be angry if you tell her the path, hence you should only output a number representing the number of initial position that can survive.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
ADP is a cute caterpillar living in the SK (Shik Kingdom). According to the tradition, every caterpillar in SK must go to the LAND once in the lifetime, hence ADP has just decided to make a journey. However, it's not that easy to go to the LAND, ADP will encounter birds, which will eat caterpillars, during the trip. Luckily, birds will only appear on roads between cities, so ADP can just stay in city for a while to wait for birds to fly away. ADP wrote a program to analyze the behavior of birds and find out when those birds will show up. Unfortunately, ADP is not familiar with Dijkstra
hence just can't write a program to figure out how much time this trip will takes. In order to accomplish her dream, she asks her smartest friend, you, to write the program. Can you help her?
Input
There's only one integer T in the first line, representing the number of test cases. The first line of each test case contains two integers N, M, the number of cities and the number of roads. city0 is ADP's hometown and cityn-1 is the LAND. Each of the next M lines describes one road. There're at least four integers in each line, V1, V2, C, D, indicating that it's a bidirectional road between cityv1 , cityv2 and ADP will need C units of time to crawl through it. The next D integers T1, T2… TD in the line represents that birds will show up at this road at time T1, T2… TD. ADP will be eaten if she's still crawling on this road while birds show up. We guarantee that there's a path to get to the LAND.
1<=T<=10
1<=N, M, ΣD<=2*10^5
1<=C<=2000
0<=Ti<=2^31-1
Output
Output the minimum units of time that ADP needs to get to the LAND for each test case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Welcome to Summer Rift! Summer Rift is a modern city. Its roads run either north-south or east-west and therefore the whole city looks like a grid table. As a result, every intersection in Summer Rift can be identified by a pair of integer (x, y), 0<=x<=n, 0<=y<=m.
Garen is a Summer Rift citizen and lives at intersection (0, 0). Every day he is going to visit Lux, who is living at intersection (n, m), and fight with her. Garen don't want to waste time, so he needs to follow a shortest route from (0, 0) to (n, m). In other words, if Garen is at intersection (x, y) on his way to Lux's place, he can only go to (x+1, y) or (x, y +1) in the next step. Now Garen wonders that how many routes he can choose.
Oh, that's too easy, right?
Summer Rift is also a dangerous city. There're many rampage enemies that slay, double-kill or triple-kill other citizens. So every day the police will block a rectangle region which is represented as (x1, y1, x2, y2). All intersections (x, y) that satisfy x1<=x <=x2 and y1<=y<=y2 are dangerous this day.
Every day Garen receives the blocked region (x1, y1, x2, y2) of that day before he visits Lux. Now Garen wonders how many routes he can choose to visit Lux without passing through any dangerous intersection during the tour?
Input
The first line of input contains an integer T, the number of test cases in total.
The first line of each test case contains three integers n; m; d, the size of Summer Rift and the number of considered days. Each of following d lines contains four integers (x1, y1, x2, y2) which is the representation of the blocked region of that day.
1<=T<=25
1<=n,m<=2000
1<=d<=2*10^5
0<=x1<=x2<=n, 0<=y1<=y2<=m
Output
Print the number of routes module 10007 for each day, one day per line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There are many variations of mahjong. In many places, players often observe one version and are either unaware of other variations or claim that different versions are incorrect. In order to simplify this problem, we consider 13 tiles with only one suit.
We use a single integer (1 to 9) to represent a tile in this simplified problem, and consider below melds only:
Pong A set of three identical tiles, like 7 7 7.
Chow A meld of three tiles in sequence, like 1 2 3.
Eye A pair, like 9 9.
A player wins by creating a hand which can be decompose into four of Pong and/or Chow, with a single Eye.
Input
The first line of the input will be an integer T (1<=T<=1000), denoting the number of test cases.
Each case has a single line containing 13 integers, which are the tiles you have already had.
Output
For each case, output all the tiles that can make you win in one line in ascending order, separated by one space.
If there are no solution, please output “0” in a single line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
It's the last day of summer camp for the freshmen of NTHU, so the organizer held a big party. There were in total 2n freshmen - n boys and n girls - who participated the party.
You, as a member of organizer, found an interesting fact: These freshmen tended to stand closer to the one he/she like. That is, during the party, every boy always moved himself to keep the girl he likes being closest to him(among these n girls); Similarly, every girls always moved herself to keep the boy she likes being closest to her(among these n boys).
There were another interesting fact that you'd already known: Due to the the romantic atmosphere of the party, a boy and a girl must become a couple when the camp was over if they liked each other.
You were very, very willing to know every gossip of these young schoolmates, so you took a snapshot of the party to record the positions of these freshmen. Can you _gure out how many couple there will be after the camp?
Input
The first line of input contains an integer T, the number of test cases in total.
There are three lines in each test case. The first line contains an integer n, the number of boys and girls in the party; The second line contains 2n integers (x1, y1), (x2, y2)… (xn, yn), where (xi, yi) is the coordination of i-th boy; The third line contains 2n integers (X1, Y1), (X2, Y2),…, (Xn, Yn), where (Xi; Yi) is the coordination of i-th girl.
It's ensured that no two people stood at same position. It's also ensured that every boy/girl liked exactly one girl/boy in the group, and there's no ambiguity - that is, for every boy/girl, there's only one girl/boy who was closest to him/her.
1<=T<=25
1<=N<=1000
-10000<=xi, yi, Xi, Yi<=10000
Output
You should output the answer (number of couples) in one line for each test case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
One day, you found a magic box on the road with its manual.
This box is an nxnxn cube, and you can fill one energy crystal in each 1x1x1 cell. There are two types of energy crystal: positive and negative.
When two adjacent cells(shared by a face) are filled by different types of crystals, they will produce one unit of energy! MAGIC!
Now, some cells of the box have been filled, while others are empty. You want to know the maximum energy it can produce, if you fill the remaining cells in an optimal way.
Input
The first line of the input will be an integer T (1<=T<=200), denoting the number of test cases.
For each test case, the first line contains an integer n (1<=n<=10), followed by n2 lines, each line contains n characters describe the magic box, `P' for positive, `N' for negative, and `?' for empty.
Output
Output the answer in one line per test case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Miruka: 1, 33, 276, 1300…?
Input
The first line of the input will be an integer T (1<=T<=10000), denoting the number of test cases.
The only line of each input will be two integers N (1 <=N<=10^8) and M (1<=M<=10^8).
Output
One line per test case, an integer equals to (Σk=1~N k5) modulo M.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Due to my work, I have to type several words every day. But the problem is that I'm too lazy to lift my finger up from keyboard, so I come up with a clever method: When I am going to type a word w, I first press on a key of lowercase alphabet on keyboard, then moving my finger along keys, and lift up my finger from keyboard. All keys my finger has passed through are pressed and corresponding letters are typed in order.
I can move my finger from a button to another only if they are adjacency" on keyboard. That is, they contain a common point on keyboard. A button is also adjacent to itself. For example, the button `p' is adjacent to `o', `l', `p', while the button `j' is adjacent to `u', `h', `n', `m', `k', `i', and `j'.
But not all the words can be typed by this way. So after surfing my finger on keyboard, I will get a string s that may be different to w. So in the end I will delete some redundant letters in s to form the word.
This method works well. Believe it or not, I type this problem by this method!
Nevertheless, I still want to optimize the method. Please help me to minimize the number of letters I should delete (It's also a hard work!).
Input
The first line of input contains an integer T, the number of test cases in total. Following are T test cases, each in a line. Each test case contains a number l and a string s. l is the length of s, and the string s contains l lowercase alphabets (i.e. `a' to `z'). Similarly, I can only press the key `a' to `z' during the process. Other keys, for example, space bar, numbers (`1'), signals(`?'), and special keys(`alt'), are forbidden.
1<=T<=100
1<=l<=1000
Output
You should output the minimum number of letters I should delete for each word.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
AMP is a cute caterpillar living in the SK (Shik Kingdom). As a result of her addiction on placing sticks on the table, she plans to buy a looooooong table to place sticks on. However, instead of buying the looooooongest table, AMP would like to buy a table that has most “shiky" ways to place sticks on.
A placement of sticks is valid if and only if the sum of length of sticks on the table is not greater than the length of table. It's “shiky" if and only if it's valid and it will become invalid if we add any of the remaining sticks. It's quite complicate, right? Well, it's “shiky"! Note that AMP never cares about the order of sticks.
Input
The first line contains an integer T, the number of test cases. There're two integers N; L in first line of each test case. The next line contains N integers, representing the length of each stick.
1<=T<=10
1<=N<=200
<=1<=L<=20000
Output
AMP is such a kind caterpillar that she won't ask you to buy the table. What you need to do is printing out L integers for each test case where the k-th integer represents the number of "shiky" ways to place sticks on a k unit long table.
Since the number maybe very LARGE, please output that number modulo 514514514.