\documentclass[lang=english,palatino]{../soi2} % Change to the right language!
\soiround{First Round 2015} % To be displayed in the header

\begin{document}

\task{Bazaar}{bazaar}
This summer mouse Stofl was in Alamaty, the biggest city in Kasachstan. He was really impressed by the bazaar where he bought some diamonds. Those diamonds are sold using a special auction: every potential buyer chooses an amount of gold nuggets he wants to bid. The highest bid gets a diamond, but everyone has to pay their bid. To make it a bit more interesting and to prevent the richest from getting all the diamonds there is an additional rule: every person is only allowed to spend a given amount of gold nuggets during an auction.

Mouse Stofl will travel again to Alamaty to cheer for the swiss IOI team. He wants to visit the diamonds auction again. Help him to buy as much diamonds as possible with the allowed amount of gold nuggets.

\section{The game}
There are in total $A$ auctions. During each auction $D$ diamonds are auctioned. (This allows your program to analyze the strategies of the other programs and to develop a counter strategy). In each auction you have $G$ gold nuggets you are allowed to spend.

An auction consists of $D$ bid rounds. In each of those rounds each player bids covered his bid $B$ (i.e. the other players don't know what your bid is). The player with the highest bid receives a diamond. If multiple players have the same highest bid then the diamonds will be sawed up resulting in one piece of the same size for every of those players. Every player has to pay their bid every round no matter who won. The sum of all bids of one player during one auction may not exceed $G$.

\section{Input / Output}
Your program will be started by a game server. It has to read from stdin and output the moves to stdout.

On game start you receive one line with four space separated integers: $N$, the number of players (incl. your program); $A$, the number of auctions; $D$, the number of bid rounds per auction (which corresponds to the number of diamonds); and $G$, the number of gold nuggets per auction you are allowed to spend.

Afterwards $A$ auctions are played. In each there are $D$ bid rounds. A bid round looks like this:

\begin{enumerate}
  \item You output an integer $B$, the amount if gold nuggets you want to bid on the active diamond.
  \item You receive one line with $N-1$ space separated integers, the bids of the other players for the active diamond. The order of the players stays the same during the whole game.
\end{enumerate}

As soon as $A$ auctions were played your program should exit.

\section{Examples}
\begin{verbatim}
> 3 1 3 1000
< 100
> 20 80
< 50
> 70 80
< 25
> 120 80
\end{verbatim}

Explanation: There are 3 players in total. In the first round you bid 100 gold nuggets, the other two players bid 20 and 80 gold nuggets respectively. You receive one diamond. After the three rounds each player owns one diamond.

\section{Constraints}
\begin{itemize}
  \item $2 \leq N \leq 10$
  \item $1 \leq A \leq 1000$
  \item $1 \leq D \leq 1000$
  \item $1 \leq G \leq 10^9$
\end{itemize}

\section{Evaluation}
The evaluation for the creativity task is different from the one for the other tasks. You get

\begin{itemize}
  \item 30 \% of the points for a program which plays the game correctly i.e. it respects the rules and plays at least as good as the sample bots.
    Important: It is not allowed to simply submit the code of a sample bot. However it is allowed and recommended to use them as an example how to properly perform input/output in your programming language.
  \item The remaining 70\% of the points will be rewarded according to the performance during the tournament on the SOI day.
\end{itemize}

So please optimize your program not only so that it wins against the sample bots, then we will also test it against the submissions of the other participants.

This year you are allowed to submit multiple programs (maximum 3 per participant) and your best program will be used for the ranking.
Bundle these programs in a zip archive and submit that. The last submission counts for this task!

This year you are allowed to submit multiple programs (maximum 3 per participant, your last 3 submissions count) and your best program will be used for the ranking. We want to encourage you with this to implement riskier strategies as well as to try out several different strategies.

\section{Hints}
For interactive tasks it is important to flush the output buffer after every round to ensure that the server can see your output.

Use the following commands:

\begin{itemize}
  \item C/C++: \verb|fflush(stdout);|
  \item C++: \verb|cout << flush;|
  \item Pascal: \verb|flush(output);|
  \item There are similar commands in other languages.
\end{itemize}

Furthermore it is important that your program does not wait for more characters than the server provides you as input. Especially spaces and line breaks in C format strings are a frequent source of errors. For example if you read the last variable of the input with \verb|scanf("\%d ", &x);|, the scanf function will wait for the next char which is not a space or a line break. However you will only receive such a char after you provided your next move. To solve this use instead \verb|scanf("\%d", &x);| (no whitespaces after \verb|\%d|).

\section{Sample bots, server and visualization}
During the first round we will provide the following material:

\begin{itemize}
  \item sample bots in various programming languages.
  \item a server program you can use to let your program compete against itself or another program.
  \item a visualization to view simulated games.
\end{itemize}

You can download them [[file:bazaar20141022|here]].

\subtaskmarker{sub1}

\end{document}