Problem A. Factoring a Polynomial ≡

Author:NEERC-2003 Northern
Input file: factor.in   Time limit:2 sec
Output file: factor.out   Memory limit:16 Mb

Statement

Recently Georgie has learned about polynomials. A polynomial in one variable can be viewed as a formal sum anxn + an-1xn-1 + … + a1x + a0, where x is the formal variable and ai are the coefficients of the polynomial. The greatest i such that ai ≠ 0 is called the degree of the polynomial. If ai = 0 for all i, the degree of the polynomial is considered to be −∞. If the degree of the polynomial is zero or −∞, it is called trivial, otherwise it is called non-trivial. What really impressed Georgie while studying polynomials was the fact that in some cases one can apply different algorithms and techniques developed for integer numbers to polynomials. For example, given two polynomials, one may sum them up, multiply them, or even divide one of them by the other. The most interesting property of polynomials, at Georgie's point of view, was the fact that a polynomial, just like an integer number, can be factorized. We say that the polynomial is irreducible if it cannot be represented as the product of two or more non-trivial polynomials with real coefficients. Otherwise the polynomial is called reducible. For example, the polynomial x2-2x+1 is reducible because it can be represented as (x - 1) (x - 1), while the polynomial x2+1 is not. It is well known that any polynomial can be represented as the product of one or more irreducible polynomials. Given a polynomial with integer coefficients, Georgie would like to know whether it is irreducible. Of course, he would also like to know its factorization, but such problem seems to be too difficult for him now, so he just wants to know about reducibility.

Input file format

The first line of the input file contains n — the degree of the polynomial. Next line contains n + 1 integer numbers, an, an-1, …, a1, a0 — polynomial coefficients (an ≠ 0).

Output file format

Output YES if the polynomial given in the input file is irreducible and NO in the other case.

Constraints

0 ≤ n ≤ 20, -1000 ≤ ai ≤ 1000

Sample tests

No. Input file (factor.in) Output file (factor.out)
1 
2
1 -2 1
 
NO
2 
2
1 0 1
 
YES

Problem B. Highways ≡

Author:NEERC-2003 Northern
Input file: highways.in   Time limit:2 sec
Output file: highways.out   Memory limit:16 Mb

Statement

In a distant country Lineland there are N cities and they are all located along the highway. The highway is a straight line; it starts from the first city and runs through the second, third city and so on, ending in the N-th city. The i-th city is located at the distance of Xi miles from the first one.

The highway is wide and smooth, so it is a pleasure for all people to drive along it. But there is one problem — all roads in Lineland, including the highway, are one-way. So people are only allowed to drive along the highway from the city with smaller number to the city with greater number and they have to use country roads to get back, and that is not such a great pleasure indeed.

After the new president Mr. Pathwayson was elected in Lineland, he has decided that he would like to make it easier for people to get from one town to another. But he does not dare to change the traditions, and make the highway two-way. Therefore he has decided to build new highways to connect the cities, so that it would be possible to get from any city to any other one by highways. Traditionally, the new highways must be one-way.

Of course, Mr. Pathwayson is a great president, and he wants people to remember him in years. After a thought he has decided that building just one highway would not be enough for that. Therefore he has decided that he must build two new highways. Each highway would connect two different cities. Since people are anxious about their health, and cars running along the highway produce dangerous wastes, each new highway must not pass through any cities, except the cities it connects. Also building two new highways in one city would disturb people too much, so all the cities that would be the ends of the new highways must be different.

You are the assistant of the minister of transportation of Lineland, so you are asked to choose the cities to be connected by the new highways. Since the cost of building a highway is proportional to its length, the total length of the highways must be minimal possible. Write a program to solve this problem. You may assume that the distance between two cities along the new highway is equal to the distance between those cities along the main highway.

Input file format

The first line of the input file contains N.

Next line contains N-1 integer numbers: X2, X3, …, XN

Output file format

If it is impossible to build the highways satisfying all requirements, print number 0 on the first line of the output file.

In the other case on the first line of the output file print the minimal possible total length of the highways to be built. On the second line print S1, E1, S2 and E2 — the numbers of the cities to connect by the first and the second highway, respectively. Note that highways are one-way and must run from S1 to E1 and from S2 to E2.

Внимание! Выводить надо только длину!

Constraints

2 ≤ N ≤ 50000, 1 ≤ X2 < X3 < … < XN ≤ 109

Sample tests

No. Input file (highways.in) Output file (highways.out)
1 
4
3 5 10
 
12
3 1  4 2

Задача Z. Лабиринт ≡

Автор:Кленин А.
Входной файл: input.txt   Ограничение времени:4 сек
Выходной файл: output.txt   Ограничение памяти:16 Мб

Условие

Лабиринт размером N x N клеток задан массивом символов. Символ '#' обозначеет стену, символ '.' — проход. Передвигаться по лабиринту можно шагами по горизонтали или вертикали, но не по диагонали.

Требуется найти длину кратчайшего пути между левым верхним и правым нижнем углами или определить, что пути не существует.

Формат входного файла

Первая строка входного файла содержит размер лабиринта N.

Следующие N строк содержат по N символов — описание лабиринта.

Формат выходного файла

Выходной файл должен содержать единственное целое число — длину кратчайшего пути, либо −1, если пути не существует

Ограничения

1 ≤ N ≤ 1500, левый верхний угол лабиринта всегда свободен.

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
2
.#
..
 
2
2 
2
.#
#.
 
-1
0.038s 0.007s 11