On 25-26 April The Bulgarian National Olympiad in Informatics took place. Here are the tasks:

Junior Task 1:

There is a sequence of stones numbered 0,1,...,10^9 from left to right respectively. A chameleon is placed on the stone with number 0. There are N (1<=N<=10^5) flies on the other stones and more than one fly can share the same stone. To reach the i-th stone with his tongue, the chameleon loses i unities of energy. When he reach the i-th stone, he eats one of the flies on the stone. The flies on stones 1,2,...,i-1 moves one stone to the left, the flies on stones, i+1,... moves one stone to the right and the remaining flies on the i-th stone don't move. Given the number of flies N and their positions on the stones 1<=a1,a2,...,aN<=10^9, you are to find the minimum energy the chameleon will lose in order to eat all flies.

Junior Task 2:

Given a dictionary of consisting of N (1<=N<=2000) words with length up to 20 lowercase letters and a string with up to 100 lowercase letters. It's known that the string is a sentence consisting of words from the dictionary written without spaces, you are to find the minimum number of words we need to use in a sentence so that writing it without spaces results in the given string. You need to print the actual sentence. If there are multiple solutions, print the one where the first word have minimum length. If there are still multiple solutions, print the one where the second word have the minimum length and so on and so on.

Junior Task 3:

Just a short description of it. You need to write a compiler for a programming language called "EASY". The language uses 10 variables R0,R1,...,R9 and integer numbers from 0 to 999 inclusively. R0 is the value that the main function is called with and R9 contains the returning value. There are operations like MOV, ADD, SUB, MUL, DIV, MOD that you need to implement with the given variables or integer numbers from 0 to 999 inclusively. There are operators IFEQ(if equal), IFNEQ(if not equal), IFG(if greater), IFL(if less), IFGE(if greater or equal), IFLE(if less or equal) and an ENDIF operator for each of them. There are operators CALL and RET. CALL calls the main function recursively with a new value and RET returns a value. All R0,...,R8 are local, only R9 isn't since it stores the answer(the returned value). So it is all about coding and having strong nerves.

Senior Task 1:

In this task you are given a string. You can mark a prefix of it and then by clicking a button your mark moves to the next occurence of the marked substring that does not overlap the current marked part. If there is no such an occurence, the mark stays at its place.

Some examples:

1 2312312312 -------> 123 1 2312312

12 312312312 -------> 123 12 312312

123 12312312 -------> 123 123 12312

1231 2312312 -------> 123123 1231 2

12312 312312 -------> 123123 12312

123123 12312 -------> 123123 12312

Your task is to find the length and the starting position of the longest substring such that after pressing that button the marked part to move.

In 15% of the tests 0 < n < 1000

In 25% of the tests 999 < n < 10000

In 60% of the tests 9999 < n < 1000000

Where n is the length of the string.

Senior Task 2

You are given a numeric system in base N where the first digits are: 1, 2, 3, ... N. Let them be c1, c2, c3, ... cN. You can write only 2-digit numbers. The task is to find the number of strictly increasing sequences in witch every digit is written twice and every number's first digit is less than its second. For example if N = 3 there is only 1 sequences of this type: c1c2, c1c3, c2,c3. Find the answer modulo 987654321.

Senior Task 3

You are given a matrix NxM. You need to delete all elements in the table. You can delete any side of the matrix. This operation will cost you the maximum number in the row/column. You need to find the minimum cost to delete the matrix. Example:

Input:

3 4
6 8 7 2
3 0 9 1
4 2 9 1

Output:

24

Explanation: One way you can delete the matrix for minimal cost: up, right, right, left, down

8 + 1 + 9 + 4 + 2 = 24