Polish version    English version  
  History of OI

 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery

Task: Special Forces Manoeuvres

Secretly Organized Tactical Infantry Exercises (SORTIE) take place in the Błędowska Desert. The main part of the SORTIE shall be the disarmament of a bomb, hidden in an unknown location in the desert.

The first part of the manoeuvres is an airborne operation. The commandos jump individually, in a predetermined order, from a helicopter hovering above the desert. Upon landing, each commando digs in and moves no further. Only then does the next commando proceed.

There is a survival radius defined for each commando. If the distance between the commando and the bomb is equal to (or smaller then) the survival radius, the commando will perish should the bomb go off. The command wants to minimize the number of soldiers taking part in the operation, but it wants to be sure that at least one of them survives the possible explosion.

We shall assume for our purposes that the Błędowska Desert is a plain and we shall identify the positions of the dug in commandos with points on this plane. We are given a sequence of commandos to jump. None of them may miss his turn, i.e. if the i-th commando jumps from the helicopter, than all those before him have already jumped. For each of the commandos we know his survival radius and the coordinates of the point he is going to land in, should he be required to jump.


Write a programme which:
  • reads from the standard input a description of each commando,
  • calculates the minimal number of commandos to jump,
  • writes the outcome to the standard output.


In the first line of the standard input there is a single integer n ( 2 <= n <= 2 000) -- the number of commandos. The following n lines contain descriptions of commandos -- one per line. The description of each commando is comprised of three integers: x, y and r ( -1000 <= x, y <= 1000, 1 <= r <= 5000). The point (x, y) denotes the landing place of the commando, and r denotes his survival radius. If the commando finds himself within the survival radius r from the bomb, he will perish should the bomb go off.


In the first and only line of the standard output your programme should write a single integer - the minimal number of commandos required to jump in order to secure the survival of at least one of them, or a single word NIE (NO in Polish) if it is not possible to have an unconditional certainty that one of the commandos survives.


For the input data:
2 2 4
7 2 3
4 3 1
5 7 1
8 7 1
the correct outcome is:


This task may be solved using floating point types:
  • double or extended in Pascal,
  • double or long double in C and C++.
The use of float or real types may result in incorrect results due to the floating point arithmetic errors.

Print friendly version