Problemele 10-12 pentru pregatirea LOT-ului
New Cow Brands
The cows are beside themselves: Farmer John has decided to use RFID
tags instead of branding the cows with red-hot irons that cause
intense pain.
The RFID tags contain a code that is N (3 <= N <= 15) characters
(each in the range 'A'..'Z') in length. No character appears twice
in the code. The character chosen for any given position in the
code is chosen from a supplied set for that position. The set is
always given in alphabetical order.
A machine generates the codes in alphabetical order. Each new batch
of cows uses the next unused set of codes. FJ keeps track of the
number of codes he has already used.
Help FJ confirm the RFID brands to be used for the next set of cows.
Given the count of the starting and finishing brands (1 <= start < finish
<= 22,000,000 and finish-start < 2000), print (in alphabetical order) the
brands that will be used. See the I/O specifications for an example.
PROBLEM NAME: brand3
INPUT FORMAT:
- Line 1: Three space-separated integers, respectively: N, start, and
finish.
- Lines 2..N+1: Line i+1 contains a number (1..26) of characters that
are the valid characters for position i in the RFID code
SAMPLE INPUT (file brand3.in):
4 6 13
ABC
CDELQ
CFH
ABC
INPUT DETAILS:
Four positions in the RFID code; print the 6th through 13th codes.
OUTPUT FORMAT:
- Lines 1..finish-start+1: Line i contains RFID code # start+i-1
SAMPLE OUTPUT (file brand3.out):
ADHB
ADHC
AECB
AEFB
AEFC
AEHB
AEHC
ALCB
OUTPUT DETAILS:
Here are the first 20 codes:
1 ACFB 5 ADFC 9 AEFB 13 ALCB 17 ALHC
2 ACHB 6 ADHB 10 AEFC 14 ALFB 18 AQCB
3 ADCB 7 ADHC 11 AEHB 15 ALFC 19 AQFB
4 ADFB 8 AECB 12 AEHC 16 ALHB 20 AQFC
Word Games
The cows are playing Scrabble but, sad to say, they do not have the
vocabulary to play at the tournament level. Bessie wants your help
for just the first move. Given her rack (a "rack" is a holder of
Scrabble letters) of N (3 <= N <= 10) letters (which might or might
not be unique and might include one or more blank "wild card" tiles)
along with a scrabble dictionary of D (10 <= D <= 50000) words,
print the words she might use (by searching the dictionary).
The 27 possible letters are upper-case 'A'..'Z' and the '#' symbol,
which represents a "wildcard" and can stand for any letter. If two
'#'s appear in one rack, each can represent a different letter when
played.
The dictionary words can be read, one per line, from file whose
name is 'scrbl.txt' (the file name is all lower case letters, unlike
the file's contents). The letters in Bessie's rack can always be
used to make at least one word. Each word in the dictionary is
unique. Remember that you are running on Linux: each input line
ends with a '\n' character; no 'return' characters are present.
PROBLEM NAME: scrbl
INPUT FORMAT:
- Line 1: Two space-separated integers, N and D.
- Line 2: N letters (with no intervening blanks) that are the letters
in Bessie's Scrabble rack.
SAMPLE INPUT (file scrbl.in):
4 49891
IAFR
INPUT DETAILS:
Four letters: I, A, F, and R.
OUTPUT FORMAT:
- Lines 1..??: Each line contains a single word that appears in the
scrbl.txt dictionary. Print the output in the order the words
appear in the dictionary.
SAMPLE OUTPUT (file scrbl.out):
AIR
FAIR
FAR
FIR
IF
OUTPUT DETAILS:
These words do actually appear in the real dictionary used for this
problem.
Serious Cow Tag
Farmer John's N (1 <= N <= 1000) cows (conveniently numbered 1..N)
are going to play a game of Serious Cow Tag. In Serious Cow Tag,
each cow chooses a grid point in the pasture (-7500 <= X <= 7500,
-7500 <= Y <= 7500) such that the distances between all pairs of
cows are unique.
The cows play in turn, starting with cow #1 and continuing with
cows #2, #3, and so on (as long as the cow is still in the game).
When it is a cow's turn to play, she finds the nearest cow still
playing, ambles over to that cow to tag her, and then returns to
her original location. As soon as a cow is tagged, she is out of
the game.
The game ends when only one cow remains, and she is declared the
winner.
Farmer John is taking bets with neighboring farmers as to which cow
will win, so he would like to know the winner in advance. Write a
program that will read a description of the cows' positions and
determine the winner.
PROBLEM NAME: cowtag
INPUT FORMAT:
- Line 1: A single integer N, the number of cows
- Lines 2..N+1: Line i+1 contains two space-separated integers that
describe the location of cow i.
SAMPLE INPUT (file cowtag.in):
3
0 0
0 3
4 3
INPUT DETAILS:
Three cows at (0, 0), (0, 3) and (4, 3).
OUTPUT FORMAT:
- Line 1: The number of the winning cow.
SAMPLE OUTPUT (file cowtag.out):
3
OUTPUT DETAILS:
Cow 1 goes first and tags the nearest cow, cow 2. Cow 2 is eliminated
so she does not get a turn. Cow 3 then tags the only remaining cow,
cow 1. She is the last cow left, so she wins.
