Google Code Jam Qualification Round 2014 Problem D. Deceitful War 题解

Problem

Naomi and Ken sometimes play games together. Before they play, each of them gets identical-looking blocks of wood with masses between 0.0kg and 1.0kg (exclusive). All of the blocks have different weights. There are lots of games they could play with those blocks, but they usually play something they call War. Here is how War works:

  1. Each player weighs each of his or her own blocks, so each player knows the weights of all of his or her own blocks, but not the weights of the other player’s blocks.
  2. They repeat the following process N times:
    1. Naomi chooses one of her own blocks, with mass ChosenNaomi.
    2. Naomi tells Ken the mass of the block she chose.
    3. Ken chooses one of his own blocks, with mass ChosenKen.
    4. They each put their block on one side of a balance scale, and the person whose block is heavier gets one point.
    5. Both blocks are destroyed in a fire. Continue reading “Google Code Jam Qualification Round 2014 Problem D. Deceitful War 题解”

Google Code Jam Qualification Round 2014 Problem B. Cookie Clicker Alpha 题解

Introduction

Cookie Clicker is a Javascript game by Orteil, where players click on a picture of a giant cookie. Clicking on the giant cookie gives them cookies. They can spend those cookies to buy buildings. Those buildings help them get even more cookies. Like this problem, the game is very cookie-focused. This problem has a similar idea, but it does not assume you have played Cookie Clicker. Please don’t go play it now: it might be a long time before you come back.

Problem

In this problem, you start with 0 cookies. You gain cookies at a rate of 2 cookies per second, by clicking on a giant cookie. Any time you have at least C cookies, you can buy a cookie farm. Every time you buy a cookie farm, it costs you C cookies and gives you an extra F cookies per second.

Once you have X cookies that you haven’t spent on farms, you win! Figure out how long it will take you to win if you use the best possible strategy. Continue reading “Google Code Jam Qualification Round 2014 Problem B. Cookie Clicker Alpha 题解”

Google Code Jam Qualification Round 2014 Problem A. Magic Trick 题解

Problem

Recently you went to a magic show. You were very impressed by one of the tricks, so you decided to try to figure out the secret behind it!

The magician starts by arranging 16 cards in a square grid: 4 rows of cards, with 4 cards in each row. Each card has a different number from 1 to 16 written on the side that is showing. Next, the magician asks a volunteer to choose a card, and to tell him which row that card is in.

Finally, the magician arranges the 16 cards in a square grid again, possibly in a different order. Once again, he asks the volunteer which row her card is in. With only the answers to these two questions, the magician then correctly determines which card the volunteer chose. Amazing, right?

You decide to write a program to help you understand the magician’s technique. The program will be given the two arrangements of the cards, and the volunteer’s answers to the two questions: the row number of the selected card in the first arrangement, and the row number of the selected card in the second arrangement. The rows are numbered 1 to 4 from top to bottom.

Your program should determine which card the volunteer chose; or if there is more than one card the volunteer might have chosen (the magician did a bad job); or if there’s no card consistent with the volunteer’s answers (the volunteer cheated). Continue reading “Google Code Jam Qualification Round 2014 Problem A. Magic Trick 题解”