Programming Contest Sample Problems

Greed Control (AI Round)

This example problem is adapted from AoPS's Greed Control forum game.

Problem Setup

Greed control is an $n$-player game, played in $10$ rounds.

In each round, you choose an integer between $0$ and $10$.

You gain points equal to the number you chose divided by the number of people who chose the same number as you.

To aid in your decision making, you also get the results of the previous round, so you can see what numbers people chose before.

Implementation Details

You will need to write a Python function, which takes a state as input, and returns an integer from $0$ to $10$.

The state is a list of the $n-1$ numbers that other players picked in the previous round. If this is the first round, the list will be empty. The order of your opponents within the array will remain consistent.

Return Format

Return a single integer between $0$ and $10$.

Invalid Return

If you make an invalid return or time out, we will treat it as if you chose the number $0$.

Scoring

On any given round, if you pick the integer $k$, then your score is $$\frac{k}{\text{total number of people who picked }k}$$ Your final score is the sum of your scores over the 10 rounds.

Feedback

At the end of the game, you can see all total scores, and the choices that each player made for each round.

Minimum Sum of Digits (Optimization Round)

Given an integer $K$, output a positive integer $N$ such that the sum of the (decimal) digits of $N \cdot K$ is minimized.

Input

The first line of each test-file contains a single integer $T$ denoting the number of test-cases.

$T$ lines of input follow, each containing one integer $K$

Output

Output $T$ lines, each containing a single integer $1 \le N < 10^{10^5}$

Scoring

Your score will be calculated as $$S(N_1 \cdot K_1) + S(N_2 \cdot K_2) + \cdots + S(N_T \cdot K_T),$$ where $S(x)$ is the sum of the decimal digits of $x$. The goal is to minimize this value.

Tasks

Task 1: $T = 100$, $1 \le K \le 100$.

Task 2: $T = 10$, $10^4 < K < 10^6$.

Task 3: $T = 10$, $10^6 < K < 10^8$.

Task 4: $T = 10$, $10^{17} < K < 10^{18}$.