(Glen here.) Recently, there was some discussion about this year's IOI in a group chat, and Ker Yang remarked that the first task, " Souvenirs ", was basically a math question. Of course, I had to have a look. The original description is pretty long, so here's a rewriting in a more math olympiad style: Sheldon is buying french fries from a fast food restaurant, which sells fries in $N$ different sizes (with packagings labelled from largest to smallest from $0$ to $N-1$), with integer costs $P_0 > P_1 > \ldots > P_{N-1} > 0$. To buy fries, Sheldon can pay $\$M$ where $M$ is a positive integer, and then define a sequence $i_1,i_2,\ldots$ as follows: $i_1$ is the smallest integer such that $P_{i_1}\le M$, and in general, $i_k$ is the smallest integer $>i_{k-1}$ such that $P_{i_k} \le M - P_{i_1} - \cdots P_{i_{k-1}}$. If no such $i_k$ can be defined, the sequence terminates. Then, Sheldon receives the fries with labels $i_1,i_2,\ldots$ along with his chang...
Comments
Post a Comment