



































You are required to count the number of squares visible from the origin point O, O = (0,0).
A square is visible from the origin point O if there are two
distinct points A and B on one of its sides such that the interior of the
triangle OAB has no common points with any of the remaining squares.
Each of the following N lines describes a square by specifying integers
X, Y and L separated by single blank characters, 1 £ X,Y,L £
10000. X and Y are coordinates of the lower left corner (the corner with
the least X and Y coordinates) and L is the side length.
SQUARES.IN 3 2 6 3 1 4 1 3 4 1 SQUARES.OUT 3 SQUARES.IN 4 1 2 1 3 1 1 2 4 2 3 7 1 SQUARES.OUT 2[ Return to Top ]
The shuffle machine accepts the set of cards arranged in an arbitrary order and performs the following operation of double shuffle : for all positions i, 1 £ i £ N, if the card at the position i is j and the card at the position j is k, then after the completion of the operation of double shuffle, position i will hold the card k.
Alice and Bob play a game. Alice first writes down all the numbers from 1 to N in some random order: a_{1}, a_{2}, ..., a_{N}. Then she arranges the cards so that the position a_{i} holds the card numbered a_{i+1}, for every 1 £ i £ N1, while the position a_{N} holds the card numbered a_{1}.
This way, cards are put in some order x_{1}, x_{2}, ..., x_{N}, where x_{i} is the card at the i^{th} position.
Now she sequentially performs S double shuffles using the shuffle machine
described above. After that, the cards are arranged in some final order
p_{1}, p_{2}, ..., p_{N} which Alice reveals to
Bob, together with the number S. Bob's task is to guess the order x_{1},
x_{2}, ..., x_{N} in which Alice originally put the cards
just before giving them to the shuffle machine.
The following N lines describe the final order of cards after all the
double shuffles have been performed such that for each i, 1 £ i £
N, the (i+1)^{st} line of the input file contains p_{i}
(the card at the position i after all double shuffles).
For each i, 1 £ i £ N, the i^{th} line of the output
file should contain x_{i} (the card at the position i before the
double shuffles).
CARDS.IN 5 2 4 1 5 3 2 CARDS.OUT 2 5 4 1 3 CARDS.IN 7 4 6 3 1 2 4 7 5 CARDS.OUT 4 7 5 6 1 2 3[ Return to Top ]
One contraction operation consists of replacing adjacent elements a_{i} and a_{i+1} by their difference a_{i}a_{i+1}. For a sequence of N integers, we can perform exactly N1 different contraction operations, each of which results in a new (N1) element sequence.
Precisely, let con(a,i) denote the (N1) element sequence obtained from [a_{1}, a_{2}, ..., a_{N}] by replacing the elements a_{i} and a_{i+1} by a single integer a_{i}a_{i+1} :
con(a,i) = [a_{1}, ..., a_{i1}, a_{i}a_{i+1}, a_{i+2}, ..., a_{N}]Applying N1 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] con([12,6,3,5] ,3) = [12,6,2] con([12,6,2] ,2) = [12,8] con([12,8] ,1) = [4]Given a sequence a_{1}, a_{2}, ..., a_{N} and a target number T, the problem is to find a sequence of N1 contractions that applied to the original sequence yields T.
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 a_{i}, 1 £ a_{i} £ 100.
You can assume that at least one such sequence of contractions will
exist for a given input.
SUBTRACT.IN 4 5 10 2 5 2 SUBTRACT.OUT 1 2 1 SUBTRACT.IN 5 4 12 10 4 3 5 SUBTRACT.OUT 2 3 2 1[ Return to Top ]