Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Automaton optimization
Time Limit: 2000MSMemory Limit: 65536K
Total Submissions: 621Accepted: 340


Linear cellular automaton is an infinite sequence of cells, each holding either 0 or 1. Cells are indexed with integers, extending from some chosen "zero" cell in both positive and negative directions.

In the initial (first) state all except the finite number of cells contain 0. Next state is computed from previous one by a simple rule: new cell value is 1 if the cell had exactly one neighbour with value 1, otherwise 0.

Although computing states is easy and fast, researchers are often interested in states after very many steps. Because these states may occupy large amount of memory, only parts of them are usually printed.

Your program must, given the initial state, quickly find values for S-th state for cells with indexes F, F + 1, …, F + L − 1.


Input file contains number of non-zero cells in the initial state N, followed by their indexes i1 i2 ... iN, and then integers S F L. All indexes are different.


1 ≤ S ≤ 109, −109F ≤ 109, 1 ≤ L, N ≤ 2000, −1000 ≤ ik ≤ 1000


Output file must contain L values, each of them either 0 or 1.

Sample Input

Sample Input 1
1 2
7 -5 5
Sample Input 2
1 -4 8

Sample Output

Sample Output 1
1 1 0 0 1
Sample Output 2
0 0 0 0 1 0 0 0


Bold texts appearing in the sample sections are informative and do not form part of the actual data.


Northeastern Europe 2006, Far-Eastern Subregion

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator