| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 4068 | Squares |
|
| 4069 | The Swallowing Ground |
|
| 4070 | Mapmaker |
|
| 4071 | Cantor Fractions |
|
| 4072 | Hotel booking |
|
Description
For any positive integer N , N = a1
2 + a22 +...+ an2 that is, any positive integer can be represented as sum of squares of other numbers.
Your task is to print the smallest `n ' such that N = a12 + a22 +...+ an2 .
Input
The first line of the input will contain an integer `t ' which indicates the number of test cases to follow.
Each test case will contain a single integer `N ' (1
N10000) on a line by itself.
Output
Print an integer which represents the smallest `n ' such that
N = a12 + a22 +...+ an2 .
Explanation for sample test cases:
5 - > number of test cases
1 = 12 (1 term)
2 = 12 + 12 (2 terms)
3 = 12 + 12 + 12 (3 terms)
1 = 22 (1 term)
2 = 52 + 52 (2 terms)
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Now that the wicked is punished, there is still work to do. For example, the ground needs to seal itself up. (Otherwise, good people will accidentally fall into Hell, which is not good.)
The ground swallowed Don Giovanni by collapsing: Part of the ground collapsed--fell off to Hell--and this created a gap that swallowed Don Giovanni. The only way the ground can be fixed is by sliding landmasses to close up the gap. Here is an example. The left diagram shows the ground with a ravine. Assume that the ground extends infinitely to the north and to the south, and there are seams on the east and west ends; so the northern block can slide southward, and the southern block can slide northward. The right diagram shows the gap closed.
Here is another example. The ravine in the left diagram cannot be closed perfectly by sliding the ground northward and southward. The right diagram shows the result of the best effort: there is still a hole.
Write a program to determine if the gap can be closed. The ground is a grid with rows (a row runs east-west) and columns (a column runs north-south). Holes are cells on the grid, and the gap consists of holes.
Input
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
The first line contains the number of columns W of the ground to be considered. Then W lines follow, specifying the boundary of the gap by columns: a line represents a column, and the order of the lines follows the east-to-west order. Each line contains 
, the north-most row of the gap in this column, and 
, the south-most row of the gap in this column. Row numbers are integers between -100 and 100 inclusive.
The input specifies a valid gap: the holes separate the ground into exactly a northern block and a southern block. There are no holes embedded inside a block. There are no islands.
Note:The sample input below corresponds to the first diagram.
Output
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
Output the line
yes
if the gap can be closed by sliding blocks north and south; and
no
otherwise.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The Cybersoft Computer Company (a leader in programming languages) has hired you to work on a new programming language named A--. Your task is to work on the array mapping tasks of the language. You will take an array reference such as x[5,6] and map it to an actual physical address. In preparation for doing this, you will write a program that will read in several array declarations and references and give the physical address of each reference. The physical address output by the program should be an integer number in base 10.
The physical address of an array reference 
is calculated from the formula 
, where the constants 
are calculated as specified below.
Input
The first line of the input file contains two positive integers. The first integer specifies N, the number of arrays defined in the data file, and the second integer specifies R, the number of array references for which addresses should be calculated. The next N lines each define an array, one per line, and the following R lines contain one array reference per line for which an address should be calculated.
Each line which defines an array contains, in the following order, the name of the array (which is limited to 10 characters), a positive integer which specifies the base address of the array, a positive integer which specifies the size in bytes of each array element, and D, the number of dimensions in the array (no array will have fewer than 1 or more than 10 dimensions). This is followed on the same line by D pairs of integers which represent the lower and upper bounds, respectively, of dimensions 
of the array.
Each line which specifies an array reference contains the name of the array followed by the integer indexes 
where D is the dimension of the array.
Output
The output file should contain the array references and the physical addresses. There should be one array reference and physical address per line. The formatting guidelines below must be adhered to.
For each line of output:
- Output the name of the array
- Output a left square bracket
- Output each index value (each pair of indexes should have a single comma and space between them)
- Output a right square bracket, a space, an equal sign, and another space
- Output the physical address
Sample Input Download
Sample Output Download
Tags
Discuss
Description
In the late XIXth century the German mathematician George Cantor argued that the set of positive fractions Q+ is equipotent to the set of positive integers N, meaning that they are both infinite, but of the same class. To justify this, he exhibited a mapping from N to Q+ that is onto. This mapping is just traversal of the N x N plane that covers all the pairs:
The first fractions in the Cantor mapping are:
Write a program that finds the i-th Cantor fraction following the mapping outlined above.
Input
The inputs consists of several lines with a positive integer number i each one.
Output
The output consists of a line per input case, that contains the i-th fraction, with numerator and denominator separed by a slash (/). The fraction should not be in the most simple form.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A transport company often needs to deliver goods from one city to another city. The transport company has made a special deal with a hotel chain which allows its drivers to stay in the hotels of this chain for free. Drivers are only allowed to drive up to 10 hours a day. The transport company wants to find a route from the starting city to the destination city such that a driver can always spend the night in one of the hotels of the hotel chain, and that he needs to drive at most 10 hours from one hotel to the next hotel (or the destination). Of course, the number of days needed to deliver the goods should also be minimized.
Input
The input file contains several test cases. Each test case starts with a line containing an integer n, (2 ≤ n ≤ 10000), the number of cities to be considered when planning the route. For simplicity, cities are numbered from 1 to n, where 1 is the starting city, and n is the destination city. The next line contains an integer h followed by the numbers c1, c2, ..., ch indicating the numbers of the cities where hotels of the hotel chain are located. You may assume that 0 ≤ h ≤ min(n, 100). The third line of each test case contains an integer m (1 ≤ m ≤ 105), the number of roads to be considered for planning the route. The following m lines describe the roads. Each road is described by a line containing 3 integers a, b, t (1 ≤ a, b ≤ n and 1 ≤ t ≤ 600), where a, b are the two cities connected by the road, and t is the time in minutes needed by the driver to drive from one end of the road to the other. Input is terminated by n = 0.
Output
For each test case, print one line containing the minimum number of hotels the transport company has to book for a delivery from city 1 to city n. If it is impossible to find a route such that the driver has to drive at most 10 hours per day, print -1 instead.