Programming help needed

[Tom_Monkey]

Can anybody find the solution for the following program question? The language doesn't matter as long as you provide proper logic.

Thanks in advance!

Problem : Switch

Problem Description
You are walking by a row of K (4 <= K <= 25) lights, some of which are on and some of which are
off. In this initial configuration, there is no consecutive sequence of four lights that are on.
Whenever four or more consecutive lights are on, the lights in that consecutive block will turn off.
You can only turn on lights that are off.
What is the minimum number of lights you need to turn on in order to end up with all K lights off?
Input Description
The first line of input will consist of the integerK, indicating the number of lights. Each of the next
K lines will have either the integer 0 (to represent a light that is off) or the integer 1 (to represent
a light that is on).
Output Specification
Your program should output the minimum number of lights that must be turned on in order to have
all K lights be off.
Sample Input 1
5
1
1
0
1
1
Output for Sample Input 1
1
Explanation of Sample 1
Notice that turning on the third light will create five consecutive lights that are on, which will in
turn cause all of these five lights to be off.

 

[9981]

先说一下漏洞， K＝４的时候无解， 没法灭

 

[9981]

死做的办法是：

可以有一个第一盏灯开的位置， 应该是已经亮的第一灯的位置－３或者已经亮的第一轮连续灯的最后一个位置＋１， 否则的话第一盏灯灭不了。

有了这么一个循环， 下面可能继续套循环，基本上就是把所有可能性套出来， 再比较。

规则是， 因为只走一次， 所以你必须先想办法先把第一灯灭掉。灭掉以后， 剩下的灯同理， 一直到你灭掉所有的灯

 

[9981]

优化了一下，

四个灯灭的可能性有以下几种：

一起灭， 只要开一次灯。条件是， 第一盏灯和最后一灯中间少于３个灯， 即中间最多只有一个黑灯。

３个一起灭， 一个一起灭，灭３灯可能需要开１或者２盏灯的位置，条件是第这３个之间首尾已亮灯之间不超过３个灯， 剩下一个需要３灯， 所以共开 ４到５灯

两个一起灭， 两个一起灭，条件是两个灯之间不超过３个灯 一共开４－６次灯

两个灭， 一个灭， 一个灭， 一共８ － ９次灯

一个一个灭， 一共３＊４＝１２灯

这样可以从优化的可能一个一个顺下来， 找到解马上就停了， 好象只有 （３，１）和 （２，２）之间有overlap

 

[ottawalyli]

If the init config has to have at least 1 light on, then the answer is K/4

For example: when K = 25, then K/4 = 6: 1011 1011 1011 1011 1011 1011 1

Reason (briefly): the init config has at least K/4 lights off.
Just for fun: if the init config is directional, then pack "0111" from the end and turn on lights from the beginning.

 

[Tom_Monkey]

I hope I did not mislead you. They ask you to create a program to produce an output based on different input.

Different input under the same K can produce the different output...

 

[简单简单]

是这个问题吗？

http://code.google.com/codejam/contest/dashboard?c=433101

 

[buddy]

先说一下漏洞， K＝４的时候无解， 没法灭

为什么无解？

 

[Tom_Monkey]

Personally I don't think they are the same...

 

[9981]

为什么无解？

理解错了， 以为已开始有4个灯亮，应该是有不确定个灯亮。

我的死算法应该适用。优化算法重做。

 

[9981]

第一步， 将那K个起始数重组成数组，
连续的不亮灯和连续的亮灯合并同类项， 这样， 从下面的一组数
可以转化成
L_Off(0) , L_On(1), L_Off(1), L_On(2), L_Off(2)...L_On(n), L_Off(n)
而下面的sample数列：
0，0，1，0，1，1，0，1，1，1，0，0，0
可以表示为：
L_Off(0) = 2, L_Off(1) = 1, L_Off(2) = 1, L_Off(3) = 3
L_On(1) = 1, L_On(2) = 2, L_On(3) = 3

 

[9981]

第二步，
如果有L_Off(i)>=4, 这样L_On(i) 和L_On(i+1) 将不可能同时被灭。
如果我们能发现大于连续的4盏灯灭， 我们就可以把这n个数组继续分解， 分解后的数列中连续亮得灯和不亮的灯都不超过4盏。

第三步，
在分解后的数列里， 如果我们从头走到尾，让一组连续的灯灭， 有三种可能：
1。和后面一组亮灯连起来一起灭
2。不和后面一组亮灯连起来， 和在自己前面的暗灯一起灭
3。不和后面一组亮灯连起来， 和在自己后面的暗灯一起灭
但是每一组灯的决定可能是有限的，
if L_On(i)+L_Off(i) >4, 这组亮灯就不可能和下一组亮灯连起来。
if L_On(i) +L_Off(i)< 4 or L_On(i) + L_Off(i-1)<4, 这组灯就不可能自己灭。
所以根据不同等情况， 程序就可能没分支可能有分支。而每一次分支后， 就可以重复第三步的决定， 但是数列已经短了， 一直循环到走完。这样应该可以找到最小的亮灯数。

 

[9981]

又想了一些优化手段:

让一组灯自己灭的代价是至少开一盏灯， 这样如果连续两组灯之间只有1或者2盏灯， 那么显然让这两组灯一起灭效率更高；这样在解决方案中如果有过多自己灭的灯组， 就可以考虑合并。

当两组亮灯中间是3盏暗灯时，并且这两组亮灯也都是各有3盏， 或者2盏和3盏， 这两组亮灯可以选择自己灭或和另一侧的亮灯组合。