Hacker cup 2013 final problem 1

Topics here are only Rebol 2 related

Hacker cup 2013 final problem 1

Postby MaxV on Thu May 16, 2013 9:40 am

Rebol is admintted as language in Hacker cup 2013! Can you solve this problem?

You are writing a new revolutionary archiver. The archive is essentially a pair of non-decreasing sequences of integers of equal length K: 0≤x_1≤...≤x_k and 0≤y_1≤...≤y_k.

The decompression algorithm proceeds as follows:
  1. Sequence (0,0), (x_1,y_1), ... (x_k,y_k), (x_k, 0), (0, 0) defines a polygon P
  2. Starting from the point (0,0), increase either x or y coordinate by 1 without moving outside of P. If both moves are available, you should increase y. After each step write 0 to output if incremented x or 1 otherwise.
  3. Repeat step 2 until you end up in point (x_k,y_k).

Example: decompression of sequence (3,4), (7,6), (7,8) will produce string 010101100100111:

fhc1.png
fhc1.png (3.17 KB) Viewed 513 times


Your task is to write a compression rate calculator, that is given binary string s find the smallest value of K for which there exists archive that decompresses to s.

Input

The first line contains a single integer T, T ≤ 20. T test cases follow, where each test case consists of one binary string with length ≤ 1000000.

The input file is a plain TXT file(uncompress it):
archiver.zip
(335.35 KB) Downloaded 30 times


Output

Output a single line containing the smallest possible K.

Example

Example input
Code: Select all
5
001
10011
0010101
1110
0110


Example output
Code: Select all
Case #1: 1
Case #2: 3
Case #3: 1
Case #4: 2
Case #5: 2
User avatar
MaxV
 
Posts: 104
Joined: Tue Jan 22, 2013 12:04 pm
Location: Italy

Re: Hacker cup 2013 final problem 1

Postby MaxV on Thu May 16, 2013 2:34 pm

This is hard, so I made an explaining sketch of the examples: http://www.sketchtoy.com/33665437

Draw # 2 is one of the most important to understand the algorithm.
Last edited by MaxV on Thu May 16, 2013 2:35 pm, edited 1 time in total.
User avatar
MaxV
 
Posts: 104
Joined: Tue Jan 22, 2013 12:04 pm
Location: Italy


Return to Rebol 2

Who is online

Users browsing this forum: No registered users and 1 guest

cron