| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 1052 | Longest Paths |
|
| 3100 | (*) Goldbach's Conjecture |
|
| 3101 | (*) Primed Subsequence |
|
| 3102 | (*) Hangover |
|
| 3103 | (*) Humidex |
|
| 3104 | (*) Ugly Numbers |
|
| 3105 | (*) Self Numbers |
|
| 3106 | (*) Summation of Four Primes |
|
| 3107 | (*) Digit Primes |
|
| 3108 | (*) Prime Gap |
|
| 3280 | Who Gets the Most Candies? |
|
| 3281 | Help with Intervals |
|
| 3282 | Mayor's posters |
|
| 3283 | Count Color |
|
| 7315 | Frogger |
|
| 7371 | Hotel |
|
| 7373 | A Simple Problem with Integers |
|
| 7393 | Buy Tickets |
|
| 7414 | Arbitrage |
|
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
http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=484
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1812
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
http://poj.org/problem?id=3299
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=72
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
http://poj.org/problem?id=1316
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1109
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1474
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
http://poj.org/problem?id=3518
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
http://poj.org/problem?id=2886
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
http://poj.org/problem?id=3225
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
http://poj.org/problem?id=2528
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
http://poj.org/problem?id=2777
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but since the water is dirty and full of tourists' sunscreen, he wants to avoid swimming and instead reach her by jumping.
Unfortunately Fiona's stone is out of his jump range. Therefore Freddy considers to use other stones as intermediate stops and reach her by a sequence of several small jumps.
To execute a given sequence of jumps, a frog's jump range obviously must be at least as long as the longest jump occuring in the sequence.
The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones.
You are given the coordinates of Freddy's stone, Fiona's stone and all other stones in the lake. Your job is to compute the frog distance between Freddy's and Fiona's stone.
Input
The input file will contain one or more test cases. The first line of each test case will contain the number of stones n ( 2<=n<=200). The next n lines each contain two integers xi, yi (0<=xi,yi<=1000) representing the coordinates of stone #i. Stone #1 is Freddy's stone, stone #2 is Fiona's stone, the other n-2 stones are unoccupied. There's a blank line following each test case. Input is terminated by a value of zero (0) for n.
Output
For each test case, print a line saying ``Scenario #x" and a line saying ``Frog Distance = y" where x is replaced by the test case number (they are numbered from 1) and y is replaced by the appropriate real number, printed to three decimals. Put a blank line after each test case, even after the last one.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The cows are journeying north to Thunder Bay in Canada to gain cultural enrichment and enjoy a vacation on the sunny shores of Lake Superior. Bessie, ever the competent travel agent, has named the Bullmoose Hotel on famed Cumberland Street as their vacation residence. This immense hotel has N (1 <= N <= 50,000) rooms all located on the same side of an extremely long hallway (all the better to see the lake, of course).
The cows and other visitors arrive in groups of size D_i (1 <= D_i <= N) and approach the front desk to check in. Each group i requests a set of D_i contiguous rooms from Canmuu, the moose staffing the counter. He assigns them some set of consecutive room numbers r..r+D_i-1 if they are available or, if no contiguous set of rooms is available, politely suggests alternate lodging. Canmuu always chooses the value of r to be the smallest possible.
Visitors also depart the hotel from groups of contiguous rooms. Checkout i has the parameters X_i and D_i which specify the vacating of rooms X_i..X_i+D_i-1 (1 <= X_i <= N-D_i+1). Some (or all) of those rooms might be empty before the checkout.
Your job is to assist Canmuu by processing M (1 <= M < 50,000) checkin/checkout requests. The hotel is initially unoccupied.
Input
* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Line i+1 contains request expressed as one of two possible formats: (a) Two space separated integers representing a check-in request: 1 and D_i (b) Three space-separated integers representing a check-out: 2, X_i, and D_i
Output
* Lines 1.....: For each check-in request, output a single line with a single integer r, the first room in the contiguous sequence of rooms to be occupied. If the request cannot be satisfied, output 0.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.
Input
The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.
Output
You need to answer all Q commands in order. One answer in a line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Railway tickets were difficult to buy around the Lunar New Year in China, so we must get up early and join a long queue…
The Lunar New Year was approaching, but unluckily the Little Cat still had schedules going here and there. Now, he had to travel by train to Mianyang, Sichuan Province for the winter camp selection of the national team of Olympiad in Informatics.
It was one o’clock a.m. and dark outside. Chill wind from the northwest did not scare off the people in the queue. The cold night gave the Little Cat a shiver. Why not find a problem to think about? That was none the less better than freezing to death!
People kept jumping the queue. Since it was too dark around, such moves would not be discovered even by the people adjacent to the queue-jumpers. “If every person in the queue is assigned an integral value and all the information about those who have jumped the queue and where they stand after queue-jumping is given, can I find out the final order of people in the queue?” Thought the Little Cat.
Input
There will be several test cases in the input. Each test case consists of N + 1 lines where N (1 ≤ N ≤ 200,000) is given in the first line of the test case. The next N lines contain the pairs of values Posi and Vali in the increasing order of i (1 ≤ i ≤ N). For each i, the ranges and meanings of Posi and Vali are as follows:
- Posi ∈ [0, i − 1] — The i-th person came to the queue and stood right behind the Posi-th person in the queue. The booking office was considered the 0th person and the person at the front of the queue was considered the first person in the queue.
- Vali ∈ [0, 32767] — The i-th person was assigned the value Vali.
There no blank lines between test cases. Proceed to the end of input.
Output
For each test cases, output a single line of space-separated integers which are the values of people in the order they stand in the queue.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 US Dollar buys 0.5 British pound, 1 British pound buys 10.0 French francs, and 1 French franc buys 0.21 US dollar. Then, by converting currencies, a clever trader can start with 1 US dollar and buy 0.5 × 10.0 × 0.21 = 1.05 US dollars, making a profit of 5 percent.
Your job is to write a program that takes a list of currency exchange rates as input and then determines whether arbitrage is possible or not.
Input
The input file will contain one or more test cases. On the first line of each test case there is an integer n (1 ≤ n ≤ 30), representing the number of different currencies. The next n lines each contain the name of one currency. Within a name no spaces will appear. The next line contains one integer m, representing the length of the table to follow. The last m lines each contain the name ci of a source currency, a real number rij which represents the exchange rate from ci to cj and a name cj of the destination currency. Exchanges which do not appear in the table are impossible. Test cases are separated from each other by a blank line. Input is terminated by a value of zero (0) for n.
Output
For each test case, print one line telling whether arbitrage is possible or not in the format "Case case: Yes" respectively "Case case: No".