Round 3: November 28th, 1997
Problem 1: Channels against Floods
Problem 2: Choosing the Stones
Problem 3: Numbers


The child laughs:
"Playing is my wisdom and my love!"
The youngman sings:
"Love is my game and my wisdom!"
The old man is quiet:
"Wisdom is my love and my game!"
Lucian Blaga (1895-1961)
Romanian poet and philosopher

Problem 1: Channels against Floods (30 points)

The Fighting Comission against Natural Calamities has built in Bihor a net of channels linking the main rivers of this county. We call the connection,in the same point, of two rivers (at the most a river and at least a channel), a confluence. Each channel makes a unidirectional connection between two confluences. For every river there is only one confluence, situated at the entry of that river in the county. Each river passes only once through the county of Bihor.
Your task is to conduct the surplus of water in every river with the help of the channels and to make sure that the flow of each river and channel is, at the most, equal with the maximum flow. Initially, the flow in the channels is null (zero) and the maximum flow of each channel, the present flow of each river and the maximum flow of each river are given (known).

Input Data:
The input file INPUT.TXT has the following structure:
n m c             -the number of rivers, the no. of channels, the no. of 
                   confluences
DMAX1 DA1         -the maximum flow and the present entry flow for the 
                   first river
...
DMAXn DAn         -the maximum flow and the present entry flow for the 
                   river no. n
D1 CIN1 COUT1     -the channel no. 1, between the confluences CIN1 and 
                   COUT1, with the maximum flow D1
...
Dm CINm COUTm     -the channel number m, between the confluences CINm 
                   and COUTm, with the maximum flow Dm

Output Data:
The output file OUTPUT.TXT has the following structure:
      DR1     -the flow of the first river
      ...
      DRn     -the flow of the river no. n
      DC1     -the flow of the first channel
      ...
      DCm     -the flow of the channel no. m

The first n confluences are those situated at the entrances in the county of the rivers with the same numbers. CINx and COUTx take values between 1 and n for the confluences situated at the entry points of those rivers in the county, and between n+1 and c for the other confluences.
All the numbers are integers. c can be maximum 100. If there's no solution, the message NO will be displayed, on one line, in the output file.

Example Input and Output:
INPUT.TXT
3 3 4
1000 100
1000 1100
500 1000
600 3 4
800 4 1
200 2 4

OUTPUT.TXT
800
900
500
500
700
200

Maximum execution time: 1 second/test on a 486DX2/66 MHz.

Vlad Marius,
Politehnica University,
Bucharest.


Problem 2: Choosing the Stones (25 points)

"Choosing the Stones" is a game in which two players extract, in turns, stones from two heaps. At each move, one player can extract the same number of stones from the both heaps or a number of stones from one of the heaps. The player who takes (out) the last stone winns.
You are asked to test if, for an initially given configuration, the first player has a winning strategy or not. And if so, you are to display a move of the first player so that, after this move, the second player be in a clear losing position (whatever strategy he would adopt, the latter can't win, considering that the former makes no mistakes).

Input Data:
The name of the input file is read from the keyboard. The input file contains only one line of the following form:
      n m
, where n is the number of stones from the first heap and m is the number of stones from the second heap.
n, m are natural (positive integer) numbers smaller than 1.0E+18. To make it simpler, we suppose that n<=m.

Output Data:
The name of the output file is read from the keyboard. The output file can contain the message:
      Player 1 is in a losing position.
or:

First Example:

      Input:
      1 2
      
      Output:
      Player 1 is in a losing position.

Second Example:

      Input:
      5 6
      
      Output:
      Player 1 has a winning strategy.
      0 3
      5 3

Execution time: 1 second/test on a 586/133 MHz.

Emanuela Mateescu,
"Grigore Moisil" High School,
Iasi.


Problem 3: Numbers (20 points)

Given a positive integer number, 0<=n<=2,000,000,000, find all its representations of the following form:
n=((x+y)^2+3x+y)/2, where x and y are natural (positive integer) numbers.

Input Data:
The file NR.IN has only one line containing the number n.

Output Data:
The file NR.OUT has the following structure:
      x1 y1
      x2 y2
      ...
      xn yn
, where xn and yn are numbers that satisfy the above mentioned condition.

Example Input and Output:
      NR.IN
      7

      NR.OUT
      1 2
Execution time: 1 second/test on a 586/133 MHz.

Maria & Adrian Nita,
"Emanuil Gojdu" High School,
Oradea
.

Translated into English by
Ioana Lucaciu.


[First Round] [Previous Round] [Next Round] [Last Round] [Romāna] [Go Back!]