Задачи

Problem A. Memory management.

(A. Klepinin)

Time limit:

Celeron-450 - 6 sec. (30 sec.)

486 DX2-66 - 40 sec. (> 80 sec.)

Don't you know that at a school pupils' programming contest a new computer language has been developed. We call it D++. Generally speaking it doesn't matter if you know about it or not. But to run programs written in D++ we need a new operating system. It should be rather powerful and complex. It should work fast and have a lot of possibilities. But all this should be done in future.

And now you are to... No. You should not devise the name for the operating system. You are to write the first module for this new OS. And of course it's the memory management module. Let's discuss how it is expected to work.

Our operating system is to allocate memory in pieces that we'll call "blocks". The blocks are to be numbered by integers from 1 up to N. When operating system needs more memory it makes a request to the memory management module. To process this request the memory management module should find free memory block with the least number. You may assume that there are enough blocks to process all requests.

Now we should define the meaning of words "free block". At the moment of first request to the memory management module all blocks are considered to be free. Also a block becomes free when there were no requests to it during T minutes.

You may wonder about a notion "request to allocated blocks". What does it mean, "request to allocated block"? The answer is simple: at any time the memory management module may be requested to access a given block. To process this request the memory management module should check if the requested block is really allocated. If it is, the request is considered to be successful and the block remains allocated for T minutes more. Otherwise the request is failed.

That's all about the algorithms of the memory management block. You are to implement them for N = 30 000 and T = 10 minutes.

Input. Each line of input contains a request for memory block allocation or memory block access. Memory allocation request has a form:
<Time> +
where <Time> is a nonnegative integer number not greater than 65000. Time is given in seconds. Memory block access request has a form:
<Time> . <BlockNo>
where <Time> meets conditions mentioned above for the memory allocation request and <BlockNo> is an integer value in range from 1 to N. There are less then 80001 lines in input.

Output. For each line of input you should print exactly one line with a result of request processing. For memory allocation request you are to write an only integer - a number of allocated block. As it was mentioned above you may assume that every request can be satisfied, there will be no more than N simultaneously allocated blocks. For memory block access request you should print the only character:

'+' - if the request is successful (i.e. the block is really allocated)

'-' - if the request fails (i.e. the block with number given is free, so it can't be accessed)

Requests are arranged by their times in an increasing order. Requests with equal times should be processed as they appear in input.

Problem B. Spell checker.

The boss of a firm that you are employed with is dissatisfied with the text processor Word. He wants you to write a better text processor by tomorrow. The interface of the new processor should be clearer, there should be more options, and the resulting text should be more beautiful. You told the boss that this work would take not less than four days. Then your boss asked you to begin with a spell checking program. This program should check capital and small letters. It should detect a mistake in each of the following cases.

1. The first letter in a sentence is small.
2. A capital letter is not the first letter in a word.

A word is a sequence of letters not containing any other symbols or ends of line.

The end of a sentence is defined a full stop, a question-mark or an exclamation mark.

Input contains a text that consists of capital and small letters of the Latin alphabet (A - Z, a - z), punctuation marks (.,;:-!?) and spaces.

Output should contain a number of mistakes in the input text.

Sample input.

This sentence iz correkt! -It Has,No mista;.Kes et oll.
But there are two BIG mistakes in this one!
      and here is one more.

Sample output.

3

Problem C. Anniversary party.

There is going to be a party to celebrate the 80-th Anniversary of the Ural State University. The University has a hierarchical structure of employees. It means that the supervisor relation forms a tree rooted at the rector V. E. Tretyakov. In order to make the party funny for every one, the rector does not want both an employee and his or her immediate supervisor to be present. The personnel office has evaluated conviviality of each employee, so everyone has some number (rating) attached to him or her. Your task is to make a list of guests with the maximal possible sum of guests' conviviality ratings. V. E. Tretyakov doesn't have to be present at party. The list of guests can be empty, in this case the sum of ratings equals to 0.

Input. Employees are numbered from 1 to N. A first line of input contains a number N. 1 <= N <= 6000. Each of the subsequent N lines contains the conviviality rating of the corresponding employee. Conviviality rating is an integer number in a range from -128 to 127. After that go N - 1 lines that describe a supervisor relation tree. Each line of the tree specification has the form:
<L> <K>

It means that the K-th employee is an immediate supervisor of the L-th employee. Input is ended with the line
0 0

Output should contain the maximal sum of guests' ratings.

Sample input.

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0

5

Problem D. Airline company.

(D. O. Filimonenkov)

An airline company is a sponsor of the 80-th Anniversary celebration at the Ural State University. In return for it the company wants the University to help it. The company serves n airports and carries out flights between some of them. In order to simplify the work the flights are numbered with integers from 1 up to m. If there is a flight between two airports a plane flies in the both directions with the same flight number. There may be only one flight between any two airports.

The airline company understands that its planes may attract terrorists. In order to create difficulties for terrorists the company wants to number the flights in some special manner. If there are several flights that depart from one airport then the greatest common divisor of their flight numbers should be equal to 1. The company turns to you for help (remember, this is a sponsor; you are to work properly).

You should write a program that finds a required numbering or informs that it is impossible to satisfy the requirements. If several numberings are possible, it is sufficient to find any one of them.

Input. The first line of input contains numbers n and m separated with a space (2 <= n <= 50). The next m lines contain information on flights. Each flight is determined by the numbers of the airports that it connects. The numbers of the airports are separated with a space.

Output. The first line of an output should contain YES, if it is possible to find a required numbering, and NO otherwise. If the answer is YES, the second line should contain a possible numbering of flights. The numbers are to be ordered as it is done in the input. Flight numbers are to be separated with a space.

Sample input.

6 5
1 2
2 3
2 4
4 3
5 6

YES
4 2 3 1 5

Problem E. Nikifor.

(D. O. Filimonenkov)

Nikifor has decided to present the dean of the Department of Mathematics and Mechanics with a linearly independent vector system (you know, that we've just celebrated jubilees of the University and of the Department). A store sells m items of n-dimensional vectors, m <= 2000, 3 <= n <= 50. For each vector its price c_i is known, 0 < i <= m. Nikifor wants to buy n linearly independent vectors paying for them minimal sum of money. Write a program that would determine which vectors Nikifor should buy or would inform that it is impossible to satisfy his requirements.

Input. The first line of an input contains numbers m and n separated with a space. The next m lines contain the vectors on sale. All of the coordinates are integers with an absolute value not exceeding 2000. The numbers are separated from each other with a space. The next m lines contain prices c_i, one number in each line. The prices are positive integers not exceeding 15000.

Output. The first line of an output should contain the minimal amount of money that Nikifor is to pay or the number 0, if Nikifor's requirements cannot be satisfied in this store. If it is possible to make a purchase, then the next n lines should contain the numbers of the vectors that Nikifor should buy. If several sets of such numbers are possible, then you should write one of them which is minimal according to the lexicographic order.

5 3
1 0 0
0 1 0
0 0 1
0 0 2
0 0 3
10
20
30
10
10

40
1
2
4

Problem F. Central heating.

(E. Shtykov)

Time limit: 20 sec.

Winter has come, but at the Ural State University heating is not turned on yet. There's one little problem: the University is heated only if all of the valves are opened. There are some technicians at the University. Each of them is responsible for one or more valves. There may be several technicians responsible for the same valve. When a technician gets an instruction to turn on the heating he goes round all of his valves and turns them. It means that if a valve was opened then he closes it, and if it was closed then he opens it. It is well known that every technician earns his money not in vain so it's impossible to replace any technician by any combination of other technicians.

Your task is to determine who of the technicians is to get an instruction "to turn on the heating" in order to heat all the Ural State University. Note that there are N technicians and N valves at the University (1 <= N <= 250).

Input. The first line of an input contains the number N. The next N lines contain lists of the valves in charge of each of the technicians. It means that a line number i + 1 contains numbers of the valves that the i-th technician is responsible for. Each list of valves is followed by -1.

Output. An output should contain a list of technicians' numbers sorted in ascending order. If several lists are possible, you should send to an output the shortest one. If it's impossible to turn on the heating at the University, you should write "No solution".

Sample input.

4
1 2 -1
2 3 4 -1
2 -1
4 -1

1 2 3

Problem G. Cover an Arc.

(A. Mironenko)

A huge dancing-hall was constructed for the Ural State University's 80-th anniversary celebration. The size of the hall is 2000 x 2000 metres! The floor was made of square mirror plates with side equal to 1 metre. Then the walls were painted with an indelible paint. Unfortunately, in the end the painter flapped the brush and the beautiful mirror floor was stained with the paint. But not everything is lost yet! The stains can be covered with a carpet.

Nobody knows why, but the paint on the floor formed an arc of a circle (a centre of the circle and whole arc lie inside the hall). The dean of the Department of Mathematics and Mechanics M. O. Asanov measured the coordinates of the arc's ends and of some other point of the arc (he is sure that this information is quite enough for any student of the Ural State University). The dean wants to cover the arc with a rectangular carpet. The sides of a carpet must go along the sides of the mirror plates (so, the corners of the carpet must have integer coordinates). You should find the minimal square of such a carpet.

Input consists of six integers, each in [-1000,1000]. They are coordinates of three points not belonging to a straight line. At first the coordinates of the arc's ends are given. The coordinates of an inner point of the arc follow them.

Output. You should write to an output file the minimal square of the carpet covering this arc.

Sample input.

476 612
487 615
478 616

66

Problem H. Lucky tickets.

(S. Vasilyev)

The public transport administration of Ekaterinburg is anxious about the fact that passengers don't like to pay for passage doing their best to avoid the fee. All the measures that had been taken (hard currency premiums for all of the chiefs, increase in conductors' salaries, reduction of number of buses) were in vain. An advisor especially invited from the Ural State University says that personally he doesn't buy tickets because he rarely comes across the lucky ones (a ticket is lucky if the sum of the first three digits in its number equals to the sum of the last three ones). So, the way out is found - of course, tickets must be numbered in sequence, but the number of digits on a ticket may be changed. Say, if there were only two digits, there would have been ten lucky tickets (with numbers 00, 11, …, 99). Maybe under the circumstances the ratio of the lucky tickets to the common ones is greater? And what if we take four digits? A huge work has brought the long-awaited result: in this case there will be 670 lucky tickets. But what to do if there are six or more digits?

So you are to save public transport of our city. Write a program that determines a number of lucky tickets for the given number of digits. By the way, there can't be more than nine digits on one ticket.

Input contains a positive even integer not greater than 9.

Output should contain a number of tickets such that the sum of the first half of digits is equal to the sum of the second half of digits.

Sample input.

4

Sample output.

670