| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 1051 | Twin Primes |
|
| 1052 | Longest Paths |
|
| 1053 | Dominos II |
|
| 1197 | Stepmania |
|
| 4061 | My T-shirt suits me |
|
Description
Twin primes are pairs of primes of the form (p, p+2). The term "twin prime" was coined by Paul Stäckel (1892-1919). The first few twin primes are (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43). In this problem you are asked to find out the S-th twin prime pair where S is an integer that will be given in the input.
Input
The input will contain less than 10001 lines of input. Each line contains an integers S (1<=S<=100000), which is the serial number of a twin prime pair. Input file is terminated by end of file.
Output
For each line of input you will have to produce one line of output which contains the S-th twin prime pair. The pair is printed in the form (p1,
Sample Input Download
Sample Output Download
Tags
Discuss
Description
It is a well known fact that some people do not have their social abilities completely enabled. One example is the lack of talent for calculating distances and intervals of time. This causes some people to always choose the longest way to go from one place to another, with the consequence that they are late to whatever appointments they have, including weddings and programming contests. This can be highly annoying for their friends.
César has this kind of problem. When he has to go from one point to another he realizes that he has to visit many people, and thus always chooses the longest path. One of César's friends, Felipe, has understood the nature of the problem. Felipe thinks that with the help of a computer he might be able to calculate the time that César is going to need to arrive to his destination. That way he could spend his time in something more enjoyable than waiting for César.
Your goal is to help Felipe developing a program that computes the length of the longest path that can be constructed in a given graph from a given starting point (César's residence). You can assume that the graph has no cycles (there is no path from any node to itself), so César will reach his destination in a finite time. In the same line of reasoning, nodes are not considered directly connected to themselves.
Input
The input consists of a number of cases. The first line on each case contains a positive number n (1<=n<=100) that specifies the number of points that César might visit (i.e., the number of nodes in the graph).
A value of n = 0 indicates the end of the input.
After this, a second number s is provided, indicating the starting point in César's journey (1<=s<=n). Then, you are given a list of pairs of places p and q, one pair per line, with the places on each line separated by white-space. The pair ``p q" indicates that César can visit q after p.
A pair of zeros (``0 0") indicates the end of the case.
As mentioned before, you can assume that the graphs provided will not be cyclic.
Output
For each test case you have to find the length of the longest path that begins at the starting place. You also have to print the number of the final place of such longest path. If there are several paths of maximum length, print the final place with smallest number.
Print a new line after each test case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Dominos are lots of fun. Children like to stand the tiles on their side in long lines. When one domino falls, it knocks down the next one, which knocks down the one after that, all the way down the line. However, sometimes a domino fails to knock the next one down. In that case, we have to knock it down by hand to get the dominos falling again.
Given a set of dominos that are knocked down by hand, your task is to determine the total number of dominos that fall.
Input
The first line of input contains one integer specifying the number of test cases to follow. Each test case begins with a line containing three integers n, m, l no larger than 10 000, followed by m+l additional lines. The first integer n is the number of domino tiles. The domino tiles are numbered from 1 to n. Each of the m lines after the first line contains two integers x and y indicating that if domino number x falls, it will cause domino number y to fall as well. Each of the following l lines contains a single integer z indicating that the domino numbered z is knocked over by hand.
Output
For each test case, output a line containing one integer, the total number of dominos that fall over.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Stepmania is a widely played game among otakus. Mr. SuBaRaSi has always wanted to become an otaku.
So he wanted to be a maestro in Stepmania. However, it would take a lot of time to practice.
For each song, some parts are difficult while other parts are easy. For example, the chorus at the middle part of the song
might be hard that he need to practice 25 times in order to get familiar. On the other hand, the intro part might be easy that he
only need to practice 5 times.
He found it is NOT efficient to always practice from the start all the way to the end of the song. As in the previous example,
he can start at the chorus part till the end for 20 times, and from intro to the end 5 times, which might be more efficient.
However, since is not good for him to interrupt at too many different parts, he can ONLY start or stop at the breakpoints settled.
Given a song that contain n parts that numbered from 1 to n, and the difficulty of every part (number of times
needed to practice). Now he has inserted k breakpoints on k different points between two adjacent parts of the song.
Then for each practice, he can start at the beginning or any of the breakpoints, and stop at the end
or any of the breakpoints. The time needed for each practice is exactly the number of parts practiced.
For example, if he started at part 3 and ended at part 7, then the time needed is (7-3+1) = 5.
You are to write a program that help SuBaRaSi to arrange his practice so that the total sum of his
practice time is minimum. In this way, he will thank you because he can then achieve his otaku's dream
more quickly.
Input
The input may contain many cases. In each case, the first line contain
two integers n, k (0<=k<n<=500) representing the number of parts in the song
and the number of breakpoints SuBaRaSi has set. In the following n lines, the i'th line
contain exactly one integer di (0<=di<=1000) denoting the difficulty of part i.
Then, in each of the following k lines contains an integer pi (1<=pi<n) representing the breakpoint
has been inserted between part pi and part pi+1. Note that these k integers are all distinct.
Output
For each case, print exactly one integer on a line representing the minimum time needed for SuBaRaSi to
become proficient in this song.
In the first case of the sample input, he can practice from beginning to the end once.
Then he practices part 2 to part 5 twice. Finally, he practices from part 2 to part 3 twice.
Therefore, the total time used is 18.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Our friend Victor participates as an instructor in an environmental volunteer program. His boss asked Victor to distribute N T-shirts to M volunteers, one T-shirt each volunteer, where N is multiple of six, and N>=M. There are the same number of T-shirts of each one of the six available sizes: XXL, XL, L, M , S, and XS. Victor has a little problem because only two sizes of the T-shirts suit each volunteer.
You must write a program to decide if Victor can distribute T-shirts in such a way that all volunteers get a T-shirt that suit them. If N != M, there can be some remaining T-shirts.
Input
The first line of the input contains the number of test cases. For each test case, there is a line with two numbers N and M. N is multiple of 6, 1<=N<=36, and indicates the number of T-shirts. Number M, 1<=M<=30, indicates the number of volunteers, with N>=M. Subsequently, M lines are listed where each line contains, separated by one space, the two sizes that suit each volunteer (XXL, XL, L, M , S, or XS).
Output
For each test case you are to print a line containing YES if there is, at least, one distribution where T-shirts suit all volunteers, or NO, in other case.