173. Coins
time limit per test: 0.75
sec.
memory limit per test: 4096
KB
input: standard
output: standard
There is a row consist of N coins. Each coin lies heads up or tails up. There is also binary vector A with (K1) dimensions.
We accomplish M operations with our coins row: we select some consecutive K coins, and apply to selected coins transformation X for Di times (i=1..M, where i is a number of operation)
The transformation X for given row C with length K means:
1. We shift the row C in one position to the left in a cyclic way.
2. Then we scan the row C from the first (leftmost) coin to (K1)th coin: if coin Ci lies tails up, and Ai=1, then we turn over coin Ck
Obviously, that for constant coins row with length K transformation X is fully determined by vector A. But vector A haven't given to you. You have results of transformation L rows with length K (row of coins before transformation, and row after transformation). It is guarantied that there is exactly one vector A satisfied all L conditions.
Your task is to reconstruct initial row by given row after all operations being accomplished.
Input
There is four integer numbers in the first line of input: N, M, K, L (2<=N<=50, 1<=M<=10, 1<=L<=200, 2<=K<=N).
Second line contains description of accomplished operations, M pairs of positive integer numbers Si and Di. Si is a starting point of selected coins subrow, Di is a number of iterations of transformation (Si <= NK+1; Di <= 10^6).
There are the following L conditions determining transformation X, L blocks by two lines each: first line of each block contains a row before transformation, and the second line contains row after transformation. Each line consists of K symbols, 1 denotes tails, 0 denotes heads.
The last line contains N symbols  row of coins after all operations accomplished. ith symbol is 1 if ith coin lies tails up, and 0 otherwise.
Output
Write N symbols in single line of output: ith symbol must be 1 if ith coin of initial row laid tails up, and 0 otherwise.
Sample test(s)
Input
4 2 3 2
2 1 1 1
010
101
101
011
1010
Output
0110
Author:  Dmitry Orlov

Resource:  Saratov ST team Spring Contest #1

Date:  18.05.2003

Server time: 20180222 09:58:06  Online Contester Team © 2002  2016. All rights reserved. 

