% topic: creativity
% difficulty: any
% usage: soi13
% author: sam

%% We say billionaire instead of millionaire, because the format of the show is owned and licensed by Sony Pictures Television (see http://en.wikipedia.org/wiki/Who_Wants_to_Be_a_Millionaire%3F)

\bigcaption{Who Wants To Be A Billionaire?}

In Mouseland, there is a famous TV show called ``Who Wants To Be A Billionaire?''. It's a quiz show where participants can win up to one billion mouse dollars. Mouse Stofl likes this game a lot, but if he had to answer questions himself, he would have no chance, because his general knowledge wouldn't be sufficient. However, he knows how to program, and he found it very fun to write a program which can answer questions from ``Who Wants To Be A Billionaire?''.

Now, he would like to make a competition between several such programs to see how good his own program is. So he asks you to write a program which can answer such multiple choice questions, using Wikipedia as source of knowledge.

At the SOI Day, there will be a grand quiz show, where the programs submitted by the participants will compete against each other.


\caption{Task}

You have to write a program which interactively answers one multiple choice question after the other. To simplify, there are no ``jokers''. 

Via standard input and standard output (stdin and stdout), your program will talk to QuizServer, a quizmaster program written by the SOI organizers.

After your program has read the quizmaster's question, it is allowed to make up to 25 queries to the English Wikipedia. It has to tell the quizmaster the title of the article it wants to look up, and the quizmaster will feed the article to your program (or tell that there is no such article). Once your program thinks it knows the answer, it tells the quizmaster its choice, and then, the next question follows.

Once a certain number of questions has been answered, the quizmaster tells your program to terminate and calculates the number of correct answers. The quizmaster will ask the same questions to the other programs, and at the end, the program with the highest score wins.


\caption{Input and Output}

The input directly starts with the first question. All questions come in the following format: 

The first line starts with an upper case Q (for ``query''), followed by one single space, followed by the query, which is followed by a question mark. The next four lines start with the lower case letters a, b, c and d, respectively, each followed by a space and a possible answer.

After reading the question (always five lines), your program can make up to 25 Wikipedia lookups. To do so, it has to print a line starting with an upper case L (for ``lookup''), followed by a space, followed by the string to look up. The quizmaster will make the lookup on Wikipedia using the following URL: 

\begin{verbatim}
http://en.wikipedia.org/w/index.php?action=raw&title=YOUR_STRING
\end{verbatim}

The answer will be in wiki format, so there is no need to parse HTML. If the article contains nothing but a redirect to another page, the quizmaster will fetch that other page. This counts as one lookup, not two. 

It will feed the article to your program in the following format: The first line starts with an upper case A (for ``article''), followed by the title of the article. If there was no redirect, the title is the same as your string. Then, it will feed you the text retrieved from Wikipedia, each line starting with an upper case C (for ``content''), followed by a single space and then the content. The article will be terminated by a line containing one single upper case E (for ``end''). If there is no article on Wikipedia for your string, there are no C lines, ie, the A line is directly followed by the E line. This also counts as one lookup, because the fact that a word has no article on Wikipedia is also a useful piece of information.

After no more than 25 lookups per question, your program has to print the answer: One line containing a lower case a, b, c or d. After this, the quizmaster will ask the next question, or it will print a line containing a single upper case T (for ``terminate''). In this case, your program should terminate.


\caption{Sample Communication}

Below is a sample communication log (shortened using ... for better readability).

\begin{verbatim}

QuizServer:        Q In which area is the term 'Foobar' most often used?
                   a in Gabon's airport terminology
                   b in computer programming
                   c in quantum physics
                   d in transportation business
your program:      L Foobar
QuizServer:        A Foobar
                   C {{Distinguish|FUBAR}}
                   C {{Other uses}}
                   C {{Redirect|Foo|FOO (Forward Observation Officer)|Artillery observer}}
                   C The terms '''foobar''' [[Wikipedia:IPA_for_English#Key|/'f??b??r/]], ...
                   C 
                   C The usage in [[computer programming]] examples and [[pseudocode]] varies; ...
                   C 
                   C == History and etymology ==
                   C The origins of the terms are not known with certainty, ...
                   E
your program:      L airport terminology
QuizServer:        A airport terminology
                   E
your program:      b
QuizServer:        T

\end{verbatim}

\caption{Scoring}

A program which respects the above protocol and is at least a little bit smarter than the provided sample bots will get at least 50\% of the points. The more questions your program answers correctly at the quizshow made by the SOI organizers, the closer your program's score will be to 100\%.

\caption{Remarks}

Do not hard code answers to questions you think might appear, that's not the idea of the game.

The size of your source code should not exceed 1 MB. This allows you to include some kind of vocabulary list, or other data, if you find this useful. But remember that you are not allowed to hard code answers.

After outputting something, do not forget to flush stdout. That's very important, because otherwise, your output will stay in the buffer instead of going to QuizServer. In C, use \texttt{fflush(stdout);}, in C++, use \texttt{std::cout << std::endl;}, and in Java, use \texttt{System.out.flush();}. In other languages, there are similar commands.

Note that the limits (up to 25 lookups per question, 1 MB of source code) are very loose. We chose them like this because we do not want to limit your creativity. So don't feel irritated if your program does not exhaust the limits: We believe that it's possible to write good programs which are far from exhausting the limits.

You can test your program with the QuizServer which you can download here: (TODO link)

Along with the the QuizServer, you get some sample programs, where you can see how to deal with input/output. If there is no sample program in the language of your preference, write an email to info at soi dot ch. Basically, you can choose every language you wish, provided that there is a free, portable compiler or interpreter available. If you have any doubts, ask in the forum.

You can use standard libraries such as C++ STL or java.lang.*. You can also use other libraries with general utility functions (such as string handling, for instance), but they should not be artificial intelligence specific or quiz show specific, and they should be free and portable. Again, if you have any doubts, you better ask in the forum.

If you have any other questions, don't hesitate to use the forum!


