Edinburgh Competition 2019
A. Palindrome
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Palindrome is a word that looks the same when you read it from the beginning and from the end. For example "kayak", "level". The same is with numbers: $$$909$$$, $$$1221$$$, $$$12321$$$ are palindromes. For a given list of numbers, please print how many of them are palindromes.

Input

In the first line of input we have a single number $$$1\leq n \leq 100$$$. In the next line there follows $$$n$$$ positive numbers, not bigger than $$$10^{50}$$$.

Output

Print a single number: how many among input numbers are palindromes?

Example
Input
4
3
546
74647
74565
Output
2

B. Efficient market
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

According to the efficient-market hypothesis you cannot systematicaly make money from stock market. While the validity of that is debatable, so it happened that you came into possesion of a leak of stock prices for the next $$$n$$$ days. There is $$$m$$$ companies and on the day $$$i$$$ you know that the stock of the company number $$$j$$$ is going to have value of $$$a_{i,j}$$$ pounds. We assume that you start with $$$d$$$ pounds on day $$$0$$$. What is the most money you can have after those $$$n$$$ days? Each day you can make as many transactions as you like and we assume that the value of stocks stays constant on each day.

Input

In the first row there are three numbers: $$$1\leq n \leq 50$$$, $$$1\leq m \leq 1000$$$ and $$$0.00\leq d \leq 10^6$$$. In the following $$$m$$$ rows there are descriptions of stock values of each company for each day $$$1.00\leq d_{i,j} \leq 10.00$$$.

Output

Print the maximal amount of money you can have by the end of the last day, up to two decimal places (we accept error of $$$0.01$$$). You can assume that the answer will be no bigger than $$$10^9$$$.

Example
Input
4 2 10.00
1.02 1.00 1.00 1.00
4.37 4.81 5.32 6.06
Output
13.87

C. Quick coffee
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Let's say we would like to give change of $$$d$$$ dollars after a puchase of coffee. The only coins that we can use have values $$$a$$$, $$$a+1$$$, ..., $$$b$$$. Is it possible to give out the change? We are interested in even harder quesion: for given $$$d$$$ and $$$a$$$ what is the smallest $$$b$$$ such that the change can be given?

Input

The input is two numbers $$$1\leq a\leq d\leq 10^9$$$.

Output

Print smallest $$$b$$$ such that $$$d$$$ is a sum of coins from range $$$a, ..., b$$$.

Examples
Input
19 60
Output
20
Input
100 914
Output
102

D. Calculated risk
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

We have a dice with $$$k$$$ sides that is rolled over and over again. You have to pay $$$£1$$$ for each time the dice is rolled. The prize is paid if at some you get a streak of $$$n$$$ consecutive ones (the dice shows 1). What is the mininum prize you should ask for in order to make profit from such game?

In other words what is the expected number of turns before streak of $$$n$$$ is hit.

For example let's say that the results of a regular $$$6$$$-sided dice are: $$$1,3,1,1,1$$$.

For $$$n=3$$$ you receive the prize after paying $$$£5$$$ for those $$$5$$$ turns.

Input

Input is two numbers $$$3\leq k\leq 20$$$ and $$$1\leq n \leq 5$$$.

Output

Print out the expected number of times you have to roll the dice to get a streak of $$$n$$$ ones. You can assume that the answer will be no bigger than $$$10^9$$$. We expect the accuracy of $$$10^{-4}$$$.

Example
Input
6 2
Output
42.00

E. Space guardians
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

An unknown solar system is guarded from the attacks of aliens by $$$n$$$ powerful starships. The starship number $$$i$$$ is located in the coordinates $$$(x_i, y_i, z_i)$$$ and is powerful enough to protect the region of space within the radious $$$r_i$$$. Sadly, the capitans of the starships have been arguing a lot and the senat decided to reorganize the defensive system according to the following rules:

  • A subset of the $$$n$$$ starships has to be chosen.
  • The chosen starships must have disjoint protected regions, so that capitans don't argue. (if two regions only just touch we treat them as disjoint)
  • The capitans of those starships will be payed more, but they will have to be responsible for radious 3 times bigger (those extended regions can intersect).
  • Finally, every point of space that was previously protected has to remain protected.
Input

First line of input contains $$$1\leq n \leq 100$$$: the number of starships. The n follwing lines describes the starships, in each line there are four numbers: $$$1\leq x_i, y_i, z_i, r_i \leq 10^4$$$.

Output

In the first line print how many starships you have chosen. In the second line print the numbers of the chosen starships. They can be in any order. If the answer does not not exist print "NO".

Example
Input
4
1 0 0 1
2 0 0 1
7 0 0 1
10 0 0 3
Output
2
2 4