Category Archives: URI Online Judge Problems

[URI Online Judge] – 1717 – Cut


Every convex polygon, with 2N vertices, can be decomposed into N − 1 quadrilaterals, by making N − 2 straight line cuts between certain pairs of vertices. The figure below shows three different decompositions of the same polygon with N = 5. The weight of the decomposition is the sum of the lengths of its N −2 cuts. Your program should compute the weight of a minimum weight decomposition!


The input contains several test cases. The first line of a test case contains one integer N (2 ≤ N ≤ 100). The following 2N lines contain, each one, two real numbers X and Y (0 ≤ X, Y ≤ 10000), with precision of 4 decimal digits: the coordinates of the 2N points, in counterclockwise order, of the convex polygon.


    For each test case in the input your program must output one line containing a real number, with 4 decimal digits precision. The number should be the weight of a minimum weight decomposition of the given polygon.

Sample InputSample Output

5715.7584 3278.6962

3870.5535 4086.7950

3823.2140 4080.7543

3574.4323 170.2905

4521.4796 144.9156

4984.6486 306.2896

5063.1061 347.1661

6099.9959 2095.9358





[URI Online Judge] – 1699 – Very Boring Game

Annie and Garen love playing computer games but they are not very good on counting. So they need your help in this new game. The game consists of n boxes, each one has a label x. In each box are placed d balls, where d is the number of positive divisors of x, the label of the box. In each turn, a player chooses one ball of any box and removes it from the game. The player who makes the last move is the winner. Given n and x for all boxes, they want to know who will win. Annie is always the first player to act.


The input consists of several test cases. Each test case is described using two lines. The first line contains the integer n (1 ≤ n ≤ 105), representing the number of boxes. The second line contains n integers, the i-th integer represents the label x (1 ≤ x ≤ 1012) of the i-th box. The last test case is followed by a line containing a zero.


For each test case output, in a single line, Annie or Garen, the winner of the game.

Sample InputSample Output

1 2 3 4


1 1 1 1 1








[URI Online Judge] – 2516 – Running


To get fit until next summer, you and your friend decided to run on the streets in the campus every morning. Usually, you run together. However, today your friend started running early and, hence, he is a little ahead of you now.

Right now, your friend is S meters away from you. You are running at a constant speed of va meters per second, and your friend is running at a constant speed of vb meters per second. The following figure shows the situation:

Your task is to determine whether you will reach your friend, and, if so, how many seconds it will take.


The input contains several test cases. The only line in each test case contains three integers S, va and vb (1 ≤ S, va, vb ≤ 103), the current distance between you and your friend (in meters), your speed (in meters per second) and your friend’s speed (in meters per second), respectively.

The input ends with end-of-file (EOF).


For each test case, if you cannot reach your friend, print a line containing “impossivel” (without quotes). Otherwise, print a line containing the time it takes, in seconds, for you to reach your friend. Round and print the answer with exactly two decimal places.

Input SampleOutput Sample
1 2 1
2 3 4




[URI Online Judge] – 2483 – Merry Christmaaas!


You get so happy at Christmas that you want to scream at everyone: “Merry Christmas!!”. To put all this happiness out, you’ve wrote a program that, given an I index of happiness, your Christmas scream is more lively.


The input consists of an integer I (1 < I ≤ 104) that represents that happiness index.


The output consists of the phrase “Feliz natal!” (“Merry Christmas” in Portuguese), and the last a of the sentence is repeated I times. A line break is necessary after printing the sentence.

Input SampleOutput Sample
5Feliz nataaaaal!


[URI ONLINE JUDGE] – 1714 – Letters


The parks in the City of Logic are always a grid of N ×N squares (2 ≤ N ≤ 100), where each square has one of the first 10 ASCII letters, abcdefghijABCDEFGHIJ, in either lowercase or uppercase format. People from the City of Logic proudly follow only consistent paths when crossing parks. For example, if they step over a lowercase c, they will not allow themselves stepping over an uppercase C afterwards. To define this more precisely, a consistent path is a sequence of squares satisfying: consecutive squares are orthogonally adjacent; no letter occurs in both lowercase and uppercase format. That is to say, either a letter is not in the sequence at all, or it occurs only in lowercase, or only in uppercase format.

You have to write a program to help the people from the City of Logic to find the length a shortest consistent path between the square with coordinates (1, 1), in the upper left corner, and the square with coordinates (N, N ), in the lower right corner. For the example park above, the shortest consistent path has length 13.


The input contains several test cases. The first line of a test case has a integer N (2 ≤ N ≤ 100), the size of the park. The next N lines contain, each one, a sequence of N letters, defining the park.


For each test case in the input your program must output one line containing one integer, the length of a shortest consistent path. If there is no consistent path, output -1.

Sample InputSample Output