CEOI'98 Round I

Square - Cards - Subtract

Problem	SQUARES	CARDS	SUBTRACT
Program name	SQUARES.EXE	CARDS.EXE	SUBTRACT.EXE
Source name	SQUARES.PAS SQUARES.C SQUARES.CPP	CARDS.PAS CARDS.C CARDS.CPP	SUBTRACT.PAS SUBTRACT.C SUBTRACT.CPP
Input file	SQUARES.IN	CARDS.IN	SUBTRACT.IN
Output file	SQUARES.OUT	CARDS.OUT	SUBTRACT.OUT
Time limit per test	10 seconds	10 seconds	10 seconds
Number of tests	10	10	10
Points per test	3	3	4
Total points	30	30	40

The maximum total score for Round I is 100 points.

SQUARES

Problem description

We are given N squares in the coordinate plane whose sides are parallel to the coordinate axes. All the corners have integer coordinates and the squares do not touch or overlap.

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.

Input data

The first line of the input file SQUARES.IN contains the integer N, 1 £ N £ 1000, the number of 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.

Output data

The first and the only line of the output file SQUARES.OUT should contain the number of squares that are visible from the origin.

Examples

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 ]

CARDS

Problem description

Alice and Bob have a set of N cards labelled with numbers 1 ... N (so that no two cards have the same label) and a shuffle machine. We assume that N is an odd integer.

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₁, a₂, ..., a_N. Then she arranges the cards so that the position a_i holds the card numbered a_i+1, for every 1 £ i £ N-1, while the position a_N holds the card numbered a₁.

This way, cards are put in some order x₁, x₂, ..., 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₁, p₂, ..., p_N which Alice reveals to Bob, together with the number S. Bob's task is to guess the order x₁, x₂, ..., x_N in which Alice originally put the cards just before giving them to the shuffle machine.

Input data

The first line of the input file CARDS.IN contains two integers separated by a single blank character : the odd integer N, 1 £ N £ 1000, the number of cards, and the integer S, 1 £ S £ 1000, the number of double shuffle operations.

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).

Output data

The output file CARDS.OUT should contain N lines which describe the order of cards just before they were given to the shuffle machine.

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).

Examples

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 ]

SUBTRACT

Problem description

We are given a sequence of N positive integers a = [a₁, a₂, ..., a_N] on which we can perform contraction operations.

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 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 [a₁, a₂, ..., 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₁, ..., a_i-1, a_i-a_i+1, a_i+2, ..., a_N]

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]
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₁, a₂, ..., a_N 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 data

The first line of the input file SUBTRACT.IN 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 a_i, 1 £ a_i £ 100.

Output data

Output file SUBTRACT.OUT 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 i^th 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.

Examples

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 ]

HTML by Pongtawat Chippimolchai, 1 June 1998.