Problem A. Sudoku Checker

Author:A. Klenin   Time limit:2 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

The puzzle game of Sudoku is played on a board of N2 × N2 cells. The cells are grouped in N × N squares of N × N cells each. Each cell is either empty or contains a number between 1 and N2.

The sudoku position is correct when numbers in each row, each column and each square are different. The goal of the game is, starting from some correct position, fill all empty cells so that the final position is still correct.

This game is fairly popular in the Internet, and there are many sites which allow visitors to solve puzzles online. Such sites always have a subroutine to determine a correctness of a given position.

You are to write such a routine.

Input file format

Input file contains integer N, followed by N4 integers — sudoku position. Empty cells are denoted by zeroes.

Output file format

Output file must contain a single string 'CORRECT' or 'INCORRECT'.

Constraints

1 ≤ N ≤ 10.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2
0 0 0 0
0 0 0 0
0 0 2 0
0 0 0 1
CORRECT
2
2
2 1 3 0
3 2 4 0
1 3 2 4
0 0 0 1
INCORRECT

Problem B. Going to be a programmer?

Author:A. Klenin   Time limit:2 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

Igor is a computer science freshman student. As opposed to most of his classmates, he actually knows a little about computer programming. Because of this, other students often ask him to write their homework assignments for the "Introductory Programming" course.

He noticed that, although each assignment is unique, they usually follow a simple pattern. In particular, one assignment states:

"Count the number of integers in the array which are [greater than|less than|equal to|not equal to] [value]",

where parts in brackets differ from student to student. Assignments also contain sample input and output to encourage students to test their programs before submission.

Igor have many classmates, so to save time he decided to write a homework generator. He started with the following template:


  count := 0;
  for i := 1 to N do
    if a[i] #cond# #value# then
      Inc(count);

And now he wants to substitute #cond# and #value# based on the sample input from the assignment. Of course, generated program might be different from what was required in the assignment, but at least it would pass the sample test — his classmates are grateful to have even that. Do you know enough Introductory Programming to help Igor?

Your program will be given sample input — an array of N integer values, and the corresponding output R. It must find such substitution strings for #cond# and #value# that after execution of the code snippet above count will be equal to R, or determine that it is impossible.

Input file format

Input file contains integer N followed by N integers ai and then by integer R.

Output file format

The first line of output must contain one of the strings '<', '>', '=', '<>' — substitution for #cond#. The second line must contain an integer — substitution for #value#.

If there is no solution, output file must contain a single character '?' (ASCII 63). If there is more then one solution, output any of them.

Constraints

1 ≤ N ≤ 100, 0 ≤ R ≤ N,  − 106 ≤ ai ≤ 106.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3
10 20 30
2
>
15
2
3
1 1 1
2
?

Problem C. How many iterations?

Author:I. Tuphanov   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Young programmer Vasya is learning the beginnings of the algorithm complexity theory. For starters, he wants to be able to quickly estimate the number of iterations of nested loops. As a first example, he wrote the following code:

CPascal
long long f(int n)
{
   long long ans = 0;
   for (int i = 1; i <= n; i++) 
      for (int j = i+1; j <= n; j++)
         for (int k = j+1; k <= n; k++)
            ans++;
   return ans;
}
function f(n: integer): int64;
var i, j, k: integer;
begin
   result := 0;
   for i := 1 to n do 
      for j := i+1 to n do 
         for k := j+1 to n do
            inc(result);
end;

Using your knowledge of the subject, help Vasya calculate f(n) for given n.

Input file format

Input file contains an integer n.

Output file format

Output file must contain a single integer — f(n).

Constraints

1 ≤ n ≤ 106

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
1
0
2
1000
166167000

Problem D. Uncertain Finish

Author:T.Chistyakov, A. Klenin   Time limit:2 sec
Input file:input.txt   Memory limit:32 Mb
Output file:output.txt  

Statement

At the running contest, jury used a new computerized stopwatch system to ensure the most accurate measuring of results. Unfortunately, despite very successfull trials, the system malfunctioned during the actual contest.

Jury was so confident in the new system that it did not use the old mechanical stopwatches. So the only way to determine outcome was to compare visual impressions of the people watching the contest. M such impressions were recorded, each in one of two forms: "runner A finished before runner B" and "runners A and B finished at the same time".

You task is to assign a place pi to each of N runners, such that

  1. If there is a record that A and B finished at the same time, then pA = pB.
  2. If there is a record that A finished before B, then pA < pB.

Additionally, places must be allocated as densely as possible, i.e. 1 ≤ piK for minimum possible value of K.

Input file format

Input file contains integers N M followed by M pairs Ai Bi ci, where ci = 0 means the record "runners Ai and Bi finished at the same time", ci = 1 means the record "runner Ai finished before Bi".

Output file format

Output file must contain either a single number −1, if the places could not be assigned, or a sequence of N numbers pi. If several solutions exist, output any of them.

Constraints

1 ≤ N ≤ 10000, 0 ≤ M ≤ 106, 1 ≤ Ai, BiN

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 2
3 2 1
2 1 0
2 2 1

Problem E. Repeating digit (easy)

Author:T. Chistyakov, A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

For given integers P and N you need to find all such values of x < 10N, that N last digits of xP are non-zero and equal.

Fortunately, there is not so many numbers showing this property. For example, for P = 2 and N = 2 there exist only 4 of them:

12, 38, 62, 88

Input file format

Input file contains P and N.

Output file format

Output the number of existing numbers X, then all these numbers in any order.

Constraints

2 ≤ P ≤ 100

2 ≤ N ≤ 9

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 2
8 
14 42 53 64 77 71 92 99

Problem F. Add one

Author:A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

Your task is the most trivial one: given non-negative integer N, output N + 1.

The only complication is that the integer is given in an unknown base between 2 and 36 inclusive. Because of that, your program should output all possible distinct answers in lexicographically increasing order.

Input file format

Input file contains integer N composed of digits from 0 to 9 and latin capital letters from A to Z, without leading zeroes.

Output file format

Output file must contain all possible distinct answers, one per line. Answers must be output in the same format as input.

Constraints

N contains from 1 to 100 digits

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
32
33
2
9
10
A

Problem G. Second Best

Author:A. Klenin   Time limit:2 sec
Input file:input.txt   Memory limit:4 Mb
Output file:output.txt  

Statement

Given the sequence of integers A1, A2, …, AN, find a number As such that there exists exactly one Am > As, and for all k ≠ m Ak ≤ As.

Input file format

Input contains N followed by A1 A2… AN.

Output file format

Output should contain a single integer — As, or  − 1 if no such number exists.

Constraints

1 ≤ N ≤ 1000000, 0 ≤ Ai ≤ 109,

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3
1 2 3
2
2
4
3 3 2 3
-1

Problem H. Customer support

Author:A. Klenin   Time limit:2 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

Customer support department in an "Incomprehension Amateurs, Ltd" software company has call center for answering users' questions. Support prices are as follows:

1.Answer to a question10 USD
2.Correct answer to a question20 USD
3.Correct answer to a question with explanation40 USD
4. Correct answer to a question which was already correctly answered before +10 USD for each previous correct answer

So, for example, if user asks the same question three times, first receives incorrect answer, then correct one, and the third time correct answer with explanation, it will cost him 10 + 20 + (40 + 1 * 10) = 80 USD.

Customers are billed monthly according to call log. Company engineers review the log and for each question determine:

  1. unique number, so the equivalent questions have same numbers,
  2. whether the answer was correct,
  3. whether the answer was short or included detailed enough explanation.
Given that data, your program must calculate the payment amount.

Input file format

Input file contains number of calls N followed by N triples qi ai xi, where qi is integer question number, ai = 1 if the answer was correct, 0 otherwise, xi = 1 if explanation was given, 0 otherwise.

Output file format

Output file must contain a single number — payment amount.

Constraints

1 ≤ N ≤ 10000, 1 ≤ qi ≤ 106.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
1
9834 0 1
10
2
3
33 1 0
33 0 0
33 1 1
80

Problem I. Shortest Spanning Tree

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:16 Mb
Output file:output.txt  

Statement

You are to write a program that receives a weighted undirected graph and finds length of its shortest spanning tree.

Input file format

Input file contains two integers N, M. Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of next M lines contain three integers describing an edge — numbers of vertices, connected by an edge and its weight respectively. All weights are positive. There is at most one edge connecting two vertices.

Output file format

Output file must contain a signle integer number — length of the SST. If it is impossible to construct spanning tree, output file must contain −1.

Constraints

1 ≤ N ≤ 1000 All weights are less or equal 1000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3
1 2 10
2 3 10
3 1 10
20

Задача J. Табуретки-2 (30 баллов)

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

Условие

Для изготовления качественной табуретки необходимы 4 ножки одинаковой длины. На табуреткоизготовительную фабрику поступило N ножек, имеющих слегка различающиеся длины L1, L2, … LN. Научно-исследовательский отдел фабрики обнаружил, что выпуск табуреток можно увеличить, если укорачивать некоторые ножки. При этом отпиленная часть выбрасывается.

Требуется определить минимальное количество распилов, необходимых для для изготовления N / 4 качественных табуреток.

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

Входной файл содержит число N, за которым следуют N чисел Li — длины ножек. Все числа целые.

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

В выходной файл следует вывести единственное целое число — минимальное количество распилов.

Ограничения

1 ≤ N ≤ 10000, N mod 4 = 0, 1 ≤ Li ≤ 100.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
8
18 16 17 17 16 17 17 19
2

Задача K. Домой на электричках

Автор:X командный чемпионат Санкт-Петербурга по программированию - V Открытая Кировская командная олимпиада   Ограничение времени:2 сек
Входной файл:a.in   Ограничение памяти:8 Мб
Выходной файл:a.out  

Условие

Одна из команд-участниц олимпиады решила вернуться домой на электричках. При этом ребята хотят попасть домой как можно раньше. К сожалению, не все электрички идут от города, где проводится олимпиада, до станции, на которой живут ребята. И, что еще более обидно, не все электрички, которые идут мимо их станции, останавливаются на ней (равно как вообще, электрички останавливаются далеко не на всех станциях, мимо которых они идут).

Все станции на линии пронумерованы числами от 1 до N. При этом станция номер 1 находится в городе, где проводится олимпиада, и в момент времени 0 ребята приходят на станцию. Станция, на которую нужно попасть ребятам, имеет номер E.

Напишите программу, которая по данному расписанию движения электричек вычисляет минимальное время, за которое ребятам удастся добраться домой.

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

Во входном файле записаны сначала числа N и E. Затем записано число M, обозначающее число рейсов электричек. Далее идет описание M рейсов электрички. Описание каждого рейса электрички начинается с числа Ki — количества станций, на которых она останавливается, а далее следует Ki пар чисел, первое число каждой пары задает номер станции, второе — время (время выражается целым числом из диапазона от 0 до 109). Станции внутри одного рейса упорядочены в порядке возрастания времени. В течение одного рейса электричка все время движется в одном направлении — либо от города, либо к городу.

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

В выходной файл выведите одно число - минимальное время, когда ребята смогут оказаться на своей станции. Если существующими рейсами электричек они добраться не смогут, выведите -1.

Ограничения

2 ≤ E ≤ N ≤ 1000, 1 ≤ M ≤ 100, 2 ≤ Ki ≤ N.

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

Входной файл (a.in) Выходной файл (a.out)
1
5 3
4
2 1 5 2 10
2 2 10 4 15
4 5 0 4 17 3 20 2 35
3 1 2 3 40 4 45
20

Задача L. Ближайшее число

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

Условие

Дана последовательность из N целых чисел. Для каждого числа вывести ближайшее к нему справа в этой последовательности, которое будет больше него. Для чисел, которым найти ближайшее большее не удалось, вывести сами эти числа.

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

Входной файл содержит целое число N за которым следует N целых чисел ai - исходная последовательность.

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

В выходной файл необходимо вывести N целых чисел bi, таких что bi является ответом на задачу для числа ai.

Ограничения

1 ≤ N ≤ 106

|ai| ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 1 2 3 4
2 3 4 4
2
1
1
1

Problem M. Altitude and visibility

Author:A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Consider a sequence of numbers a1, …, aN, representing heights. Let's say that element ai has a visibility radius d if ai ≥ aj for all j such that 1 ≤ j ≤ N and |i − j| < d.

You task is to find maximum di for every ai.

Input file format

Input file contains integer N followed by N integers ai.

Output file format

Output file must contain N integers di — maximum visibility for every ai. If maximum visibility radius for element ai is unlimited, output di = 0.

Constraints

1 ≤ N ≤ 106, 0 ≤ ai ≤ 109

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
1
10
0 
2
6
1 5 2 2 1 4
1 0 1 2 1 4 

Problem N. Topological sorting

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that performs a topological sorting of a directed graph. Graph contains N vertices, numbered with integers from 1 to N, and M edges.

In other words, given a partial order on numbers from 1 to N, your program must produce some linear order on these numbers which does not conflict with the given partial order.

Input file format

Input file contains two integers N and M, followed by M pairs of integers. Integers in each pair are different, and represent starting and ending vertex of a graph edge.

These pairs may also be considered comparisons where the first number precedes the second one.

Output file format

Output file must contain a permutation of integers from 1 to N — numbers of vertices sorted in topological order. (That is, representing a linear order.) If ordering is not possible, output file must contain a single number  − 1.

Constraints

0 ≤ N, M ≤ 100000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4 3
1 2
1 3
3 4
1 3 2 4

1.189s 0.019s 39