- Final
- Elimination
**Third qual**- Second qual
- First qual
- Warm-up

# Third qualification round completed

## Tasks

Show one task per page / all tasks on one page

Time limit | 1 second |
---|---|

Memory limit | 256 megabytes |

Petya is developing his own spreadsheet editor. His editor will use the following naiming for columns: the first 26 columns will be named by the letters of the alphabet: A, B, C, ..., Z. The following columns, starting from column 27, will be named using pairs of letters: AA, AB, ..., AZ, BA, BB, ..., BZ, ..., ZZ. Then triples of letters will be used: AAA, AAB, AAC, ..., then strings of four letters, and so on.

Now Petya needs to get the name of the column by its number. Help him to create the corresponding piece of code.

Input format |
Input data contains several test cases. The first line of input contains an integer The following |
---|---|

Output format |
For each test case output the name of the |

Examples |
Input data
4 1 10 100 1000
Output data
A J CV ALL |

Time limit | 1 second |
---|---|

Memory limit | 256 megabytes |

Vasya has started playing a new video game. In the end of the first level he is taking a combat with the level boss. He needs to win the combat to continue playing. Vasya has a squad of *n* heroes, the *i*-th of them has *h*_{i} hit points and *a*_{i} attack points. The boss has *H* hit points and *A* attack points.

The combat goes as follows.

- If Vasya has no more heroes, he loses the game.
- If he still has at least one hero, he can choose any one and send it to fight against the boss;
- If Vasya has chosen the
*i*-th hero, the combat proceeds as follows:- The hero attacks the boss and reduces its hit points by
*a*_{i}; - If the boss is still alive — has strictly positive hit points — it attacks the hero and reduces its hit points by
*A*; - While the hero and the boss are both still alive, the attacks are repeated.

- The hero attacks the boss and reduces its hit points by
- If the boss is dead, the combat is over, Vasya wins. In the other case all of the actions are repeated.

Vasya doesn't want to lose many heroes at the very first level of the game. So he wants to plan the combat to lose the minimum possible number of heroes. Help him to find what is the minimal number of heroes that he can lose but still defeat the boss. If Vasya cannot defeat the boss even losing all of his heroes, output - 1.

Let us consider sample test cases.

In the first test case the optimal plan is the following: first send hero 2 to the combat. It attacks the boss three times, reduce its hit points by 12, and then dies. After that Vasya must send hero 3 to the combat, it immediately reduces the hit points of the boss by 6, and the boss dies. Therefore Vasya loses one hero only.

In the second test case Vasya cannot kill the boss, no matter in which order he sends his heroes to the combat.

Input format |
Input data contains multiple test cases. The first line contains one integer Each of the Each of the following The sum of values of |
---|---|

Output format |
For each test case output either the minimal number of heroes that Vasya must lose to defeat the boss, or - 1 if Vasya cannot defeat the boss. |

Examples |
Input data
2 4 18 4 4 5 9 4 1 6 3 3 4 27 4 4 5 9 4 1 6 3 3
Output data
1 -1 |

Time limit | 1 second |
---|---|

Memory limit | 256 megabytes |

Let us call the integer number a bit palindromic, if its first digit is the same as its last digit. We use decimal notation without leading zeroes. Your task is to count how many a bit palindromic numbers are there between *l* and *r*, inclusive.

The following numbers are a bit palindromic in the first sample test: 8, 9, 11, and 22.

The numbers in the second sample test — 1251 and 1261.

Input format |
Input data contains multiple test cases. The first line contains one integer Each test case is described by a single line that contains two integers: |
---|---|

Output format |
For each test case output one integer: how many a bit palindromic numbers are there in the given range. |

Examples |
Input data
3 8 25 1251 1266 12 21
Output data
4 2 0 |

Time limit | 2 seconds |
---|---|

Memory limit | 256 megabytes |

Nick is a freshman. He studies trees in his Algorithms class. He studies polynomials in his Algebra class. And he likes to create and combine. He has recently come up with a problem he cannot solve. Help him!

You are given a rooted tree with *n* vertices, numbered from 1 to *n*. There is a value in each vertex, initially all values are equal to 0. For a vertex *v* let us denote as *d*[*v*] the depth of the vertex *v* — the number of vertices on a path from the root of the tree to *v*, in particular the root itself has depth equal to 1.

You are also given *k*. You must process queries of two types.

- You are given a vertex
*v*and a polynomial*q*(*t*) =*q*_{0}+*q*_{1}*t*+*q*_{2}*t*^{2}+ ... +*q*_{k}*t*^{k}. For each vertex*u*in a subtree of the vertex*v*you must add*q*(*d*[*u*]) to the value in that vertex. - You are given a vertex
*v*and a polynomial*q*(*t*) =*q*_{0}+*q*_{1}*t*+*q*_{2}*t*^{2}+ ... +*q*_{k}*t*^{k}. For each vertex*u*on a path from the root of the tree to*v*, inclusive, add*q*(*d*[*u*]) to the value in that vertex.

All arithmetic operations are performed modulo 10^{9} + 7.

Help Nick to find the values in all vertices after all operations.

Input format |
Input data contains multiple test cases. The first line of input data contains integer The description of test cases follow. Each description starts with two integers: The following The integer It is guaranteed that the sum of values of |
---|---|

Output format |
For each test case output |

Examples |
Input data
1 4 2 2 4 2 0 3 1 2 0 1 0 2 3 1 0 0 2 1 0 0 1
Output data
12 7 4 2 |

Time limit | 5 seconds |
---|---|

Memory limit | 256 megabytes |

Andrew is analyzing subscription graph in one social network. This graph is directed: if the user *a* is subscribed to the user *b*, it is not always the case that the user *b* is in turn subscribed to the user *a*.

Andrew's boss has asked him to find for each user *x* the number of users *y* such that it is possible to reach user *y* from user *x* in the subscription graph.

There is no reason to find the exact values, they look ugly and are non-relevant almost immediately, so Andrew wants to find approximate values. Find values that differ from the correct ones at most by a factor of two.

Input format |
The first line of input contains two integers The following |
---|---|

Output format |
Output Note: judges use exact values to check your answers. However, judges don't promise that it is possible to find exact values in each test case given time and memory constraints of this problem. They recommend to try to find approximate value. In the given example it is possible to reach all five users from the user 1. But the given answer 7 is acceptable, it differs from 5 less than by a factor of two. Similarly, the answer 2 is acceptable for the user 4. |

Examples |
Input data
5 6 1 2 1 3 2 4 2 5 3 5 4 2
Output data
7 3 2 2 1 |