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 2010-7. “Broken scenery”


    Once in 1985 eight-bit Petr was carrying in his eight-bit truck some granny's home-made monochrome jam and sprite scenery for another sequel to a famous game for a well-known game console. But a broken pixel appeared on the road, a square wheel cracked, and truck instantly got upside down. Petr, his jam and the scenery got thrown out to the road, the truck got covered with yellow circles of explosions, blinked for a while and disappeared.
    Petr caught his breath and got horrified – the fragile scenery was smashed into smithereens, moreover, the fragments got mixed with the pieces of granny's jam, and it's impossible to distinguish between them! Luckily, Petr had got the documents describing his cargo (because he worked legally only), that contained the bit-masks of the scenery. “Great,” Petr thought, “now I just have to put the fragments together according to the template, and after that carry the scenery in my arms”.

    Task. Help Petr put the fragments together, ignoring the pieces of granny's jam, and come home till 6 PM.

    Streams. The input stream consists of a whitespace separated (spaces, new line characters) number sequence, describing a two-dimensional pixel map. “0” means an empty cell, “1” – a filled one; every line, except for the last one, ends with number “9”, and the last one ends with “8”, which is a sign of an end of the image. For instance:

    1 1 1 1 0 9
    1 1 1 1 0 0 1 1 1 9
    1 1 1 1 0 0 0 1 1 9
    1 1 1 1 0 0 1 0 1 0 9
    0 0 0 0 0 0 1 0 0 0 9
    1 1 0 1 0 0 1 1 1 9
    1 1 0 1 1 8

    A figure is a set of vertically and horizontally (not diagonally) adjacent filled cells. Figures are not to be rotated – the pixels are magnetized in one direction in advance, therefore Petr, who is a qualified nuclear physicist, could arrange the fragments in right direction by himself.
    All the figures in the input data are numbered from 0 to N, from top to bottom, from left to right.

    In our case above the figures are to be numbered in the following way:

    (0)
    (1)
    (2)
    (3)
    (4)
     OOOO 
     OOO 
     O  OO  O
     OOOO
    OO 
     O OO  OO 
     OOOO
     OOO 
     OOOO

    The figure numbered with “0” is always a template, according to which the figures are to be assembled. In the example above the figures are brought together in the following way:

    2111
    2411
    2441
    2222
    (figure 3 is superfluous in this case).
    A single possible solution is guaranteed to exist in every case.
    An output stream must consist of space separated integers that are the numbers of figures put together in a correct way, written from top to bottom, from left to right.
    In this example the correct output is:
    2 1 4

    Example
    Input stream:
    1 1 1 1 0 9
    1 1 1 1 0 0 1 1 1 9
    1 1 1 1 0 0 0 1 1 9
    1 1 1 1 0 0 1 0 1 0 9
    0 0 0 0 0 0 1 0 0 0 9
    1 1 0 1 0 0 1 1 1 9
    1 1 0 1 1 8
    Output stream:
    2 1 4

     
       
    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: 396
    All visitings: 830032
    Web ststistics: