Problemele 7-9 pentru pregatirea LOT-ului
7.Wonderprime Brands
The cows are forever competing to see who has the best brand. The
latest rage is brands that are 'Wonderprimes'. You probably already
know that a brand consists of a sequence of digits that does not
begin with 0; brands actually look a lot like positive integers.
A wonderprime is a number that can be partitioned into two prime
numbers, each of which has at least D digits and, of course, doesn't
start with 0. When D=2, the number 11329 is a wonderprime (since it
connects 113 and 29, both of which are prime).
Only a few of the cows have wonderprime brands, but they all want
one. Your job is to find the first wonderprime greater than or equal
to a supplied integer N (1 <= N <= 2,000,000,000). No integer greater
than 2,000,000,000 will be required.
PROBLEM NAME: wpb
INPUT FORMAT:
- Line 1: Two space-separated integers: D and N
SAMPLE INPUT (file wpb.in):
2 11328
OUTPUT FORMAT:
- Line 1: A line that contains the first wonderprime no smaller than
N.
SAMPLE OUTPUT (file wpb.out):
11329
8.The Eating Puzzle
Bessie is on a diet where she can eat no more than C (10 <= C <=
35,000) calories per day. Farmer John is teasing her by putting out
B (1 <= B <= 21) buckets of feed, each with some (potentially
non-unique) number of calories (range: 1..35,000). Bessie has no
self-control: once she starts on a feed bucket, she consumes all
of it.
Bessie is not so good at combinatorics. Determine the optimal
combination of feed buckets that gives Bessie as many calories
without exceeding the limit C.
As an example, consider a limit of 40 calories and 6 buckets with
7, 13, 17, 19, 29, and 31 calories. Bessie could eat 7 + 31 = 38
calories but could eat even more by consuming three buckets: 7 +
13 + 19 = 39 calories. She can find no better combination.
PROBLEM NAME: eatpuz
INPUT FORMAT:
- Line 1: Two space-separated integers: C and B
- Line 2: B space-separated integers that respectively name the number
of calories in bucket 1, 2, etc.
SAMPLE INPUT (file eatpuz.in):
40 6
7 13 17 19 29 31
OUTPUT FORMAT:
- Line 1: A single line with a single integer that is largest number
of calories Bessie can consume and still stay on her diet.
SAMPLE OUTPUT (file eatpuz.out):
39
9.Dream Counting
Bessie was daydreaming one day as she drifted between wakefulness
and that delicious drowsiness that we all feel when we are tired.
For a moment, she counted sheep as couldn't quite sleep. Bessie's
mind is razor sharp and visualizes the numbers as she counts. She
started noticing the digits and wondered: how many instances of
each digit appear in a counting sequence?
Write a program to answer this question. Given two integers M and
N (1 <= M <= N <= 2,000,000,000 and N-M <= 500,000), how many of
occurences of each digit appear?
Consider the sequence 129..137: 129, 130, 131, 132, 133, 134, 135, 136,
137. Count the digits to find:
1×0 1×5
10×1 1×6
2×2 1×7
9×3 0x8
1×4 1×9
PROBLEM NAME: dream
INPUT FORMAT:
- Line 1: Two space-separated integers: M and N
SAMPLE INPUT (file dream.in):
129 137
OUTPUT FORMAT:
- Line 1: Ten space-separated integers that are the counts of the
number of each digit (0..9) that appears while counting
through the sequence.
SAMPLE OUTPUT (file dream.out):
1 10 2 9 1 1 1 1 0 1
OUTPUT DETAILS:
One zero, ten ones, etc.