Problemele 1-3 pentru pregatirea LOT-ului
Buy One Get One Free
Farmer John has discovered the Internet is buying bales of hay
online when he notices a special deal. For every bale of hay of
size A (1 <= A <= 1,000,000) he buys, he can get a bale of hay of
size B (1 <= B < A) for free!
The deal, however, is restricted: the larger bale must be high
quality hay and the smaller one must be low quality hay. FJ, being
a frugal and thrifty fellow, does not care: any quality of hay will
do as long as he saves some money.
Given a list of the sizes of N (1 <= N <= 10,000) bales of high
quality hay and M (1 <= M <= 10,000) bales of low quality hay, find
the maximum number of bales of hay Farmer John can purchase. He
can buy bales of high quality hay without getting the free bale of
low quality hay, but he cannot buy bales of low quality hay (i.e.,
he must get them for free in the deal).
PROBLEM NAME: buyfree
INPUT FORMAT:
- Line 1: Two space-separated integers: N and M.
- Lines 2..N+1: Line i+1 contains a single integer which is the size
of the ith bale of high quality hay.
- Lines N+2..N+M+1: Line i+N+1 contains a single integer which is the
size of the ith bale of low quality hay.
SAMPLE INPUT (file buyfree.in):
3 4
6
1
3
1
5
3
4
INPUT DETAILS:
There are 3 bales of high quality hay, with sizes 6, 1, and 3, and 4 bales
of low quality hay, with sizes 1, 5, 3, and 4.
OUTPUT FORMAT:
- Line 1: The maximum total number of bales of hay Farmer John can
obtain.
SAMPLE OUTPUT (file buyfree.out):
5
OUTPUT DETAILS:
Obviously, Farmer John can buy all the bales of high quality hay.
When he buys the size 6 high quality bale, he can get any low quality
bale for free (say, the bale of size 3). When he buys the size 3
high quality bale, he can get the size 1 low quality bale for free.
When he buys the size 1 high quality bale, however, he cannot get
any low quality bales for free (since the size must be strictly
less). The total, no matter how clever FJ is, comes to five bales.
Qualified Primes
Farmer John has begun branding the cows with sequential prime
numbers. Bessie has noticed this and is curious about the occurrence
of various digits in those brands.
Help Bessie determine the number of primes in the inclusive range
A..B (1 <= A <= B <= 4,000,000; B <= A + 1,000,000; one test case
has B <= A + 2,000,000 ) that contain a supplied digit D.
A prime is a positive integer with exactly two divisors (1 and
itself). The first primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, and,
29.
PROBLEM NAME: qprime
INPUT FORMAT:
- Line 1: Three space-separated integers: A, B, and D
SAMPLE INPUT (file qprime.in):
10 15 3
INPUT DETAILS:
How many primes in the range 10..15 contain the digit 3?
OUTPUT FORMAT:
- Line 1: The count of primes in the range that contain the digit D.
SAMPLE OUTPUT (file qprime.out):
1
OUTPUT DETAILS:
Just 13 in this range contains a '3'.
Lilypad Pond
Farmer John has installed a beautiful pond for his cows' esthetic
enjoyment and exercise. The rectangular pond has been partitioned
into square cells of M rows and N columns (1 <= M <= 30; 1 <= N <=
30). Some of the cells have astonishingly sturdy lilypads; others
have rocks; the remainder are just beautiful, cool, blue water.
Bessie is practising her ballet moves by jumping from one lilypad
to another and is currently located at one of the lilypads (see the
input data for the location's specifier). She wants to travel to
another lilypad in the pond by jumping from one lilypad to another.
She can jump neither into the water nor onto a rock.
Surprising only to the uninitiated, Bessie's jumps between lilypads
always appear as a sort of chess-knight's move: move M1 (1 <= M1
<= 30) 'squares' in one direction and then M2 (1 <= M2 <= 30; M1
!= M2) more in an orthogonal direction (or perhaps M2 in one direction
and then M1 in an orthogonal direction). Bessie sometimes might
have as many as eight choices for her jump.
Given the pond layout and the format of Bessie's jumps, determine
the smallest number of leaps that Bessie must make to move from her
starting location to her final destination, a feat which is always
possible for the given test data.
PROBLEM NAME: bronlily
INPUT FORMAT:
- Line 1: Four space-separated integers: M, N, M1, and M2
- Lines 2..M+1: Line i+1 describes row i of the pond using N
space-separated integers with these values: 0 indicates empty
water; 1 indicates a lilypad; 2 indicates a rock; 3 indicates
the lilypad Bessie upon which she starts; 4 indicates the
lilypad that is Bessie's destination.
SAMPLE INPUT (file bronlily.in):
4 5 1 2
1 0 1 0 1
3 0 2 0 4
0 1 2 0 0
0 0 0 1 0
INPUT DETAILS:
Bessie starts on the left in row 2; her destination is on the right in row
2. Several lilypads and rocks occupy the pond.
OUTPUT FORMAT:
- Line 1: A single integer that is the minimum number of jumps between
lilypads that Bessie must make to travel from her starting
place to her destination.
SAMPLE OUTPUT (file bronlily.out):
2
OUTPUT DETAILS:
Bessie cleverly hops onto the pad at row 1, column 3 on her way to the
right hand side.
