# Internet Problem Solving Contest

## Problem H – Hats of various colors

You and your fellow revolutionaries have been captured by the evil archduke, and now you’re all waiting for execution in the archduke’s dungeons. Fortunately, a thousand year old tradition states that all prisoners must be given a last chance to go free if they can solve a logic puzzle.

The warden explains what will happen:

• Every prisoner will receive a red or blue hat. The prisoners will be seated so that they can see everyone else’s hat, but not their own hat. The prisoners must stay completely silent.

• When the warden shouts “Now!”, all prisoners must immediately and simultaneously choose whether to raise their hand or not. Everyone will see everyone else, but they must still stay silent.

• The warden will (privately) ask every prisoner what is the color of their own hat. If all prisoners answer correctly, the archduke has to let them go. If anyone makes a mistake, they will all be executed.

In both subproblems, there are N = 13 prisoners. In the easy subproblem H1, the hats are of C = 2 different colors (red and blue). In the hard subproblem H2, there are C = 4000 available hat colors.

### Problem specification

Write a program that describes the prisoners’ strategy.

This problem is special. Usually, you can write a program in any programming language, and you only submit the computed output data, not your source code. This task is the exact opposite. You only submit source code – specifically, a program written in the Lua 5.3 language. (See below for an introduction.)

We will run N copies of your program and allow them to communicate according to the rules. If all N programs answer correctly, you win.

Your program can use these variables:

• `N`: the number of prisoners.
• `C`: the number of different colors.
• `myself`: your own ID – a number between 1 and N, inclusive.
• `colors`: an array of visible hat colors. For every i between 1 and N, `colors[i]` will be a number between 1 and C, inclusive, except for `colors[myself]` which will be `nil`.
• `raise`: a function which takes a single boolean argument (whether you raise your hand or not), and returns an array of N booleans (for each prisoner, whether they raised their hand). You must call `raise` exactly once.
• `answer`: initially unset. You must set it to a number between 1 and C, inclusive – the number you want to announce as the color of your hat.

### Limits

These functions won’t exist: `debug.debug`, `io.*`, `loadfile`, `math.random`, `math.randomseed`, `os.*`, `package.*`, `print`, `require`.

We will run 300 test cases. (In total, your program will run 300 × N times.) The memory limit is 256 MB (for the sum of your N programs). The time limit is 10 seconds (for the sum of your 300 × N runs).

If you’d like, you can test your solution with our testing program: `lua h-test.lua solution.lua` .

### Introduction to Lua

If you don’t know the Lua language, here’s a quick introduction:

• Variables: `foo_bar = a + b`
• Literals: `nil`, `true`, `false`, `123`, `0xFF`, `"a string"`
• Arithmetic: `1+2 == 3`, `1-2 == -1`, `2*3 == 6`, `3/2 == 1.5`, `3//2 == 1`, `7%5 == 2`, `2^3 == 8`
• Comparison: `a == b`, `a ~= b`, `a < b`, `a <= b`, `a > b`, `a >= b`
• Logic: `a and b`, `a or b`, `not a` (note that `nil` and `false` count as false, and everything else counts as true, including `0` and `""`)
• Math: `math.abs(x)`, `math.floor(x)`, `math.max(a, b, c, d)`, `math.pi`, etc.
• Binary: `a & b` (AND), `a | b` (OR), `a ~ b` (XOR), `a >> b` (right shift), `a << b` (left shift), `~a` (NOT)
• “If” statement: `if ??? then ... elseif ??? then ... else ... end`
• “While” loop: `while ??? do ... end`
• Numeric “for” loop: `for i = 1, 128 do ... end`
• Functions: `function some_name(a, b, c) local d = 7; return a + d; end`
• Local variables (in functions and control structures): `local l = 123`
• Arrays (tables): `arr[idx]` (indexed from 1), `{ 1, 2, 3 }` (new array), `#arr` (array length)
• Comments: `--[[ multiple lines ]]`, `-- until end of line`
• Newlines and semicolons are optional: `a = 1 b = 2 + 3 c = 4 * 5`

For more details, refer to the Lua manual and the language grammar, or other on-line resources – though you probably won’t need most parts.

### Example

``````my_bool = colors == 1 or myself > 6

hands = raise(my_bool)

if hands or not hands then