COCI 2008/2009, Contest #1

Task JEZ

Luka found a very unusual game board in his attic. Surprisingly, it consists of R·C square cells. The rows are numbered 0 to R-1 top to bottom and the columns 0 to C-1 left to right.

What makes the board unusual is the way in which the cells are coloured. Each cell is either grey or white:

• white, if the row and column numbers of the cell, when represented in binary, have at least one digit 1 in the same position. For example, the cell (4, 5) would be white.
• grey, otherwise. For example, the cell (2, 5) would be grey.

Luka's hedgehog likes walking on this unusual board and does it in an unusual way. The hedgehog starts his walk in the cell (0, 0) and continues in the zig-zag pattern as in the second image above. While the hedgehog is walking, Luka counts how many grey squares it visited.

After visiting K squares, the hedgehog gets tired and falls asleep. Luka then goes to bed too, happy that he was able count the grey squares.

Knowing the dimensions of the board and the number K beforehand, however, it is possible to write a program that calculates the result faster. This is your task.

Input

The first line contains two integers R (1 ≤ R ≤ 1,000,000) and C (1 ≤ C ≤ 1,000,000), the dimensions of the board.

The second line contains the integer K (1 ≤ K ≤ R·C), the total number of squares the hedgehog visits. Note that this number may not fit in a 32-bit integer.

Output

Scoring

Examples

10 10
6

5

3 5
11

8

10 10
100

51

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 1.00s
Memory Limit: 32M
Added: Oct 18, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

I read what the problem defines as grey, however shouldn't (2,5) be a white cell as well instead of grey? (2,5) in binary is (10,101). They both share a 1 in the first index(same position), so why isn't it a white cell?

For this problem, binary digits are lined up and compared from the least-significant (right-most) bit. So:
[code]
4: 100
5: 101
   ^--- two 1's at the same position, therefore white
[/code]
but:
[code]
2:  10
5: 101
   ^^^-- no 1's line up, therefore grey
[/code]

 
4: 100 
5: 101 
   ^--- two 1's at the same position, therefore white 

 
2:  10 
5: 101 
   ^^^-- no 1's line up, therefore grey