Main
  About Cybernetics
  Olympiad Regulations
  Olympiad History
 
  • Photo
  • Video



  •   Examples of Tasks
      Organizing Committee
      Current Olympiad
     
  • Teams Registration
  • Participants
  • Olympiad Results

  • Login:

    Password:

     
     RUS / ENG
        News
     
    Task 2008-6. "Strange son of lumiere"

    There is k switches linked somehow among themselves. Each switch can be only in two states: "on" and "off". The system works as follows: when someone switches the switch (only one for time), the state change both this switch, and all switches linked to it directly. Lighting will switch only when all switches are able "on".

    Task. What least number of steps necessary for turning on lighting?

    Notes. Initially all switches are in position "off".

    Stream. The input stream sets number of switches k and a symmetric matrix of links in the size k where on an intersection i th string and j th column there is 1 if i th switch is linked with j th, or 0 if it is not linked. The output stream should specify the minimum number of steps necessary for inclusion of all switches, or - 1 if such state is impossible.

    Example
    Input stream:
    3
    1 0 1
    0 1 0
    1 0 1
    Output stream:
    2

     
       
    19.02.2013 17:19
     
    Cyber XIV. Results of Distance Session of Olympiad . . . -->

    21.01.2013 15:59
     
    Key for a training session . . . -->

    29.02.2012 12:41
     
    Video of the Olympiad . . . -->

    29.02.2012 12:12
     
    The results of Main Session of Olympiad on Cybernetics . . . -->

    News archive
     
    Back to news archive -->


    Today visitings: 65
    All visitings: 810449
    Web ststistics: