CCC '11 S5 - Switch

View as PDF
Submit solution
Points: 12 (partial)
Time limit: 1.0s
Memory limit: 256M
Problem type
Canadian Computing Competition: 2011 Stage 1, Senior #5

You are walking by a row of K (4 \le K \le 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 Specification

The first line of input will consist of the integer K, 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 for 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.

Note: At least 30% of the test cases will have K \le 10.

Comments


  • 0
    JamesLangstaff  commented on Feb. 13, 2024, 7:53 p.m.

    I am having an algorithmic problem, suppose you have the case 1, 0, 0, 0, 0, 1. Mine will do 1, 1, 0, 0, 0, 1 then 1, 1, 1, 0, 0 1, then instead of doing the optimal thing it makes it 0, 0, 0 , 0, 0, 1. Which is obviously not correct, any ideas?


  • 5
    noYou  commented on July 16, 2020, 3:55 p.m.

    Why is the memory limit so low? 64mb is really little.


    • 8
      Evanhyd  commented on Feb. 19, 2021, 8:29 p.m.

      Because this question is amazing. You don't have to brute force it with memoization, but rather, there are optimal methods to choose the next possible switch position, which takes less than 5 MB to complete. Hope people find this useful.


  • 3
    op8  commented on July 3, 2020, 8:30 p.m.

    I'm a bit confused by the wording of this question - it says that you're walking along the row (presumably once), so how are you supposed to handle a test case like 100001? The only way to do it is if you are allowed to choose whatever bulb you like (not just walking along the row).


    • 2
      maxcruickshanks  commented on July 3, 2020, 8:57 p.m.

      You are able to toggle any light in any order.


      • 3
        op8  commented on July 4, 2020, 3:07 p.m.

        ah okay, thanks - I interpreted that comment as saying that you can choose either direction to walk along the row (left to right or right to left).


  • 3
    Dordor1218  commented on May 20, 2018, 2:20 p.m.

    It says "You are walking by a row" so do you need to do it from right to left or can it be random


    • 10
      zxyl  commented on May 20, 2018, 6:19 p.m.

      It can be random.


      • 9
        Jacky  commented on April 29, 2019, 12:00 a.m.

        thx


      • 9
        jjjding2  commented on Oct. 5, 2018, 1:22 p.m. ← edit 9

        thx


      • 9
        Dordor1218  commented on May 20, 2018, 11:20 p.m.

        okie thx


  • 89
    root  commented on Jan. 30, 2017, 9:33 p.m.

    "You can only turn on lights that are off." - I certainly hope so.


  • 2
    bobhob314  commented on Dec. 26, 2015, 10:30 p.m. ← edited

    Hey guys, not sure why I'm getting RTE on DMOJ but not locally. Any ideas?


    • 2
      XIAOAGE  commented on Dec. 26, 2015, 10:48 p.m.

      the integer array is too huge. It takes up more than 64M


      • -4
        bobhob314  commented on Dec. 26, 2015, 10:54 p.m.

        Thanks bud.