ALICECUB - Alice’s Cube

Please click here to download a PDF version of the contest problems. The problem is problem A in the PDF.


Alice has received a hypercube toy as her birthday present. This hypercube has 16 vertices, numbered from 1 to 16, as illustrated below. On every vertex, there is a light bulb that can be turned on or off. Initially, eight of the light bulbs are turned on and the other eight are turned off. You are allowed to switch the states of two adjacent light bulbs with different states ("on" to "off", and "off" to "on"; specifically, swap their states) in one operation.

Given the initial state of the lights, your task is to calculate the minimum number of steps needed to achieve the target state, in which the light bulbs on the sub cube (1, 2, 3, 4) - (5, 6, 7, 8) are turned off, and the rest of them are turned on.

Alice's hypercube

Input

There are multiple test cases. The first line of the input contains an integer T, meaning the number of the test cases. There are about 13000 test cases in total.

For each test case there are 16 numbers in a single line, the i-th number is 1 meaning the light of the i-th vertex on the picture is on, and otherwise it’s off.

Output

For every test cases output a number with case number meaning the minimum steps needed to achieve the goal. If the number is larger than 3, you should output "more".

Sample

Input:
3
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 0 0 1 0 1 1 1 1 1 1
0 0 0 0 0 0 1 0 1 0 1 1 1 1 1 1

Output:
Case #1: 0
Case #2: 1
Case #3: more

Added by:Fudan University Problem Setters
Date:2009-11-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 C99 GOSU NODEJS OBJC PERL6 VB.NET
Resource:ACM/ICPC Regional Contest, Shanghai 2009

hide comments
2023-02-04 14:59:48 Simes
I've extracted the problem from the PDF. I hope that's ok? If there are any mistakes or discrepancies, assume the PDF is correct.
2018-08-03 07:46:39
"You are allowed to switch the states of two adjacent light bulbs with different states". This costs me most to debug.
2017-10-04 10:38:38
How to input data?
2017-06-21 08:14:21
easy!


Last edit: 2017-06-21 08:48:02
2017-03-02 19:31:05
@Marcin Sasinowski it's 2 and 10th digit mate, not 9th! count again! :D
2016-08-14 19:22:57 bksingh
use correct format for output,
what is the output format... is it same as mention in pdf ?

Last edit: 2016-08-14 19:26:26
2016-07-16 17:17:32
Good question. Note: for >3, output is more and use correct format for output. nice question.
2016-06-16 16:17:29
AC! Note that input contains blank line in between test cases. Plan your input accordingly. I wasted a lot of time to figure that out!. It should have been stated in the problem.
2016-03-14 00:16:26
TL

Last edit: 2016-03-14 02:15:46
2016-03-07 11:24:14 Liquid_Science
"Team AlphaCentauri (Tsinghua University) solved at 10 minutes" , took me half an hour ,but as they say to solve a problem quickly ,you must be able to fisrt solve it at all.

Last edit: 2016-03-07 11:24:35
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.