{"extraResources":{"example.01.mu":"TVXzATEwDQo="},"scoring":null,"notes":"","legend":"A mad scientist conducted $n$ independent identical experiments and claimed that $x$ of them were successful. It is well known that the mad scientist is wrong in exactly 90\\% of cases when determining the success of a single experiment. Your task is to write a program that calculates the minimum and the maximum possible number of successful experiments for all $x$ from $0$ to $n$. It is guaranteed that the total number of experiments is always divisible by $10$.","authorLogin":"amaydell","language":"english","timeLimit":1000,"output":"Print $n + 1$ lines. On the $i$-th line, output two integers separated by a space: the minimum and the maximum possible number of successful experiments for $x = i - 1$.","inputFile":"stdin","outputFile":"stdout","input":"The first line contains a single integer $n$, which is a multiple of ten ($10 \\le n \\le 10\\,000$).","authorName":"Anton Maydell","sampleTests":[{"output":"9 9\r\n8 10\r\n7 9\r\n6 8\r\n5 7\r\n4 6\r\n3 5\r\n2 4\r\n1 3\r\n0 2\r\n1 1\r\n","input":"10\r\n","inputFile":"example.01","outputFile":"example.01.a"}],"name":"Nine Out Of Ten","interaction":null,"memoryLimit":1073741824,"tutorial":"Let's consider the subproblem of maximizing the number of successful experiments. The set of successful experiments consists of two non-overlapping subsets: the mad scientist correctly identified a successful experiment and the mad scientist incorrectly identified an experiment as unsuccessful. Since these subsets do not overlap, we can maximize their sizes independently of each other. According to the problem statement, the size of the set of correctly identified experimental results is $\\frac{n}{10}$, and according to the condition, the size of the set of experiments that the scientist identified as successful is $x$. To maximize the number of correctly identified successful experiments, we use the fact that the experiments are independent and indistinguishable from each other, leading us to the result of $min(\\frac{n}{10}, x)$. The formula for the second subset is accordingly: $min(\\frac{9n}{10}, n-x)$. By summing these two minima, we obtain the formula for our subproblem: $min(\\frac{n}{10}, x) + min(\\frac{9n}{10}, n-x)$.\r\nThe second subproblem of minimizing the number of successful experiments is equivalent to the problem of maximizing the number of unsuccessful experiments, which can be solved similarly to the first subproblem, and the final formula for the minimization subproblem looks like this: $n - min(\\frac{n}{10}, 10-x) - min(\\frac{9n}{10}, x)$."}