Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: SUBTRACT
Description We are given a sequence of N positive integers a = [a1, a2, ..., aN] on which we can perform contraction operations.
One contraction operation consists of replacing adjacent elements ai and ai+1 by their difference ai-a _{i+1}. For a sequence of N integers, we can perform exactly N-1 different contraction operations, each of which results in a new (N-1) element sequence.
Precisely, let con(a,i) denote the (N-1) element sequence obtained from [a1, a2, ..., aN] by replacing the elements ai and a _{i+1} by a single integer ai-a_{i+1} :
con(a,i) = [a1, ..., ai-1, ai-a
_{i+1}, a_{i+2}, ..., aN]Applying N-1 contractions to any given sequence of N integers obviously yields a single integer. For example, applying contractions 2, 3, 2 and 1 in that order to the sequence [12,10,4,3,5] yields 4, since : con([12,10,4,3,5],2) = [12,6,3,5] Given a sequence a1, a2, ..., aN and a target number T, the problem is to find a sequence of N-1 contractions that applied to the original sequence yields T. Input The first line of the input contains two integers separated by blank character : the integer N, 1 <= N <= 100, the number of integers in the original sequence, and the target integer T, -10000 <= T <= 10000.
The following N lines contain the starting sequence : for each i, 1 <= i <= N, the (i+1) ^{st} line of the input file contains integer ai, 1 <= ai <= 100.
Output Output should contain N-1 lines, describing a sequence of contractions that transforms the original sequence into a single element sequence containing only number T. The ith line of the output file should contain a single integer denoting the i ^{th} contraction to be applied.
You can assume that at least one such sequence of contractions will exist for a given input. Sample Input 5 4 12 10 4 3 5 Sample Output 2 3 2 1 Source |

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

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator