USACO 2013 US Open, Bronze
Problem 2. Blink
Contest has ended.
Log in to allow submissions in analysis mode
Problem 2: Blink [Videh Seksaria and Brian Dean, 2013]
Unhappy with the dim lighting in his barn, Farmer John has just installed a
fancy new chandelier consisting of N (3 <= N <= 16) lights bulbs arranged
in a circle.
The cows are fascinated by this new light fixture, and enjoy playing the
following game: at time T, they toggle the state of each light bulb if its
neighbor to the left was turned on at time T-1. They continue this game
for B units of time (1 <= B <= 10^15). Note that B might be too large to
fit into a standard 32-bit integer.
Given the initial states of the light bulbs, please determine their final
states after B units of time have elapsed.
PROBLEM NAME: blink
INPUT FORMAT:
* Line 1: Two space-separated integers, N and B.
* Lines 2..1+N: Line i+1 contains the initial state of bulb i, either
0 (off) or 1 (on).
SAMPLE INPUT (file blink.in):
5 6
1
0
0
0
0
INPUT DETAILS:
There are five light bulbs. The first is initially on, and the others are off.
OUTPUT FORMAT:
* Lines 1..N: Line i should contain the final state of bulb i, either
0 (off) or 1 (on).
SAMPLE OUTPUT (file blink.out):
1
1
1
0
1
OUTPUT DETAILS:
The light bulb states are as follows:
Time T=0: 1 0 0 0 0
Time T=1: 1 1 0 0 0
Time T=2: 1 0 1 0 0
Time T=3: 1 1 1 1 0
Time T=4: 1 0 0 0 1
Time T=5: 0 1 0 0 1
Time T=6: 1 1 1 0 1
Contest has ended. No further submissions allowed.