eylerravi. me gavige ro III xarisxebis dajildoveba oRond maTematikaSi da isic 7-e klaselebis aris paraskevs 11 saaTze, SeiZleba Senic mag dros iyos.
xval vikiTxav skolaSi da mere davpostav.
* * *
ager SemTxveviT or kai amocanas wavawydi (adre maq gakeTebuli), romlebic USACO 2002-03 December Si moitanes, ager orive Tavisi testebiT, Tu rames ver gaigebT mkiTxeT:
PROBLEM 3: Captives of War [SSivek, Burnim, Abbott, Baek, 2002]
After the Bovine Uprising of 2002, the cows must keep watch over the
large number of human prisoners they captured.
They have a prison at coordinate (Px, Py) (where -100,000 <= Px <=
100,000 and -100,000 <= Py <= 100,000) and they want to construct as
many layers of fences as possible around the prison to make escape as
difficult as possible. It is unfortunate that, for this problem, the
prison is modeled as a single point.
In order to accomplish this, they have placed N (3 <= N <= 1000) fence
posts in the vicinity of the prison. Each fence completely surrounds
the prison and all fences inside it (i.e., no fence crossing). Among
the set of all fence post locations and the prison location, no three
points are collinear. Given the locations of these fence posts, you
must compute the maximum number of layers of non-intersecting nested
fences the cows can construct around the prison by placing straight
fence rails between the fence posts they have constructed. A guard
must be able to patrol between each pair of nested fences (and between
the inner fence and the prison), so leave at least a small amount of
space in the nestings (i.e., don't share a vertex between two nested
fences).
PROBLEM NAME: captives
INPUT FORMAT:
* Line 1: Three space-separated integers: N, Px, and Py.
* Lines 2..N+1: Two space-separated integers, Xi and Yi (-100000 <=
Xi, Yi <= 100000) specifying the coordinates of a fence post.
SAMPLE INPUT (file captives.in):
8 -1 0
2 2
2 -2
-2 2
-2 -2
0 10
8 0
-12 1
1 -5
OUTPUT FORMAT:
A single line with a single integer that is the maximum number of
layers of fences.
SAMPLE OUTPUT (file captives.out):
2
**********************************************************************
PROBLEM 4: Bovine Tennis Professionals [Romanian Olympiad via Stroe, 2002]
Those cows who play tennis professionally are ranked by the Bovine
Tennis Professionals (BTP) governing body.
Sometimes it is possible to predict perfectly the results of a tennis
match. If the rank difference between two cows is larger than a given
K (0 <= K <= N-1) (i.e., | cow1rank - cow2rank | > K) then the cow
with the better rank will always win in a match between the two cows.
There is a big single-elimination competition next week, with N cows
(N=1, 2, 4, 8, ..., 65536 -- always a power of two) from which one
will be chosen the winner. In the first round, N/2 matches are played
and the resulting N/2 winners proceed to the next round. On each
successive round, the winning half of the cows proceed in the
tournament until only one cow remains.
The rest of the cows (who are betting on the competition, of course)
want to know the rank of the lowest-ranked cow who has a chance of
winning the tournament, along with a scenario that would result in
her victory.
Your job is to calculate the lowest-ranked cow that could win the
tournament and show a schedule which would enable that cow to win.
PROBLEM NAME: btp
INPUT FORMAT:
* Line 1: Two space-separated integers: N and K
SAMPLE INPUT (file btp.in):
16 3
OUTPUT FORMAT:
* Line 1: A single integer that is the rank of the lowest-ranked
cow who could possibly win the tournament.
* Line 2: N rank numbers describing the first round matches. The
first pair of numbers describes the first match, the second pair
describes the second match, and so on. The first number in each
pair is the cow who must win for the lowest-ranked cow to
win the tournament.
* Line 3: N/2 rank numbers describing the second round matches, in
the same format.
* and so on; the last line should contain only one match (two rank
numbers). The first number (the winner) should be the number from
line 1.
SAMPLE OUTPUT (file btp.out):
11
3 1 5 2 6 4 7 16 8 13 9 14 10 15 11 12
5 3 8 6 9 7 11 10
8 5 11 9
11 8
[This is only one of many possible answers. A program will grade your
output.]
This post has been edited by KvaLe on 27 Jun 2005, 19:24
მიმაგრებული ფაილი ( Number of downloads: 38 )
usaco03_dec_captives_btp_tests.zip
· 
ოლიმპიადები და პროგრამირების ამოცანები, აბა ვივარჯიშოთ :)
