Problemele 13-15 pentru pregatirea LOT-ului
The Moronic Cowmpouter
Inexperienced in the digital arts, the cows tried to build a
calculating engine (yes, it's a cowmpouter) using binary numbers
(base 2) but instead built one based on base negative 2! They were
quite pleased since numbers expressed in base -2 do not have a sign
bit.
You know number bases have place values that start at 1 (base to
the 0 power) and proceed right-to-left to base1, base2, and so
on. In base -2, the place values are 1, -2, 4, -8, 16, -32, ...
(reading from right to left). Thus, counting from 1 goes like this:
1, 110, 111, 100, 101, 11010, 11011, 11000, 11001, and so on.
Eerily, negative numbers are also represented with 1's and 0's but
no sign. Consider counting from -1 downward: 11, 10, 1101, 1100,
1111, and so on.
Please help the cows convert ordinary decimal integers (range
-2,000,000,000..2,000,000,000) to their counterpart representation
in base -2.
PROBLEM NAME: neg2
INPUT FORMAT:
- Line 1: A single integer to be converted to base -2
SAMPLE INPUT (file neg2.in):
-13
OUTPUT FORMAT:
- Line 1: A single integer with no leading zeroes that is the input
integer converted to base -2. The value 0 is expressed as 0,
with exactly one 0.
SAMPLE OUTPUT (file neg2.out):
110111
OUTPUT DETAILS:
Reading from right-to-left:
1*1 + 1*-2 + 1*4 + 0*-8 +1*16 + 1*-32 = -13
DNA Assembly
Farmer John has performed DNA sequencing on his prize milk-producing
cow, Bessie DNA sequences are ordered lists (strings) containing
the letters 'A', 'C', 'G', and 'T'.
As is usual for DNA sequencing, the results are a set of strings
that are sequenced fragments of DNA, not entire DNA strings. A pair
of strings like 'GATTA' and 'TACA' most probably represent the
string 'GATTACA' as the overlapping characters are merged, since
they were probably duplicated in the sequencing process.
Merging a pair of strings requires finding the greatest overlap
between the two and then eliminating it as the two strings are
concatenated together. Overlaps are between the end of one string
and beginning of another string, NOT IN THE MIDDLE OF A STRING.
By way of example, the strings 'GATTACA' and 'TTACA' overlap
completely. On the other hand, the strings 'GATTACA' and 'TTA' have
no overlap at all, since the matching characters of one appear in
the middle of the other, not at one end or the other. Here are some
examples of merging strings, including those with no overlap:
GATTA + TACA -> GATTACA
TACA + GATTA -> TACAGATTA
TACA + ACA -> TACA
TAC + TACA -> TACA
ATAC + TACA -> ATACA
TACA + ACAT -> TACAT
Given a set of N (2 <= N <= 7) DNA sequences all of whose lengths
are in the range 1..7, find and print length of the shortest
possible sequence obtainable by repeatedly merging all N strings
using the procedure described above. All strings must be merged
into the resulting sequence.
PROBLEM NAME: dna
INPUT FORMAT:
- Line 1: A single integer N
- Lines 2..N+1: Each line contains a single DNA subsequence
SAMPLE INPUT (file dna.in):
4
GATTA
TAGG
ATCGA
CGCAT
OUTPUT FORMAT:
- Line 1: Length of the shortest possible string obtained by merging
the subsequences. It is always possible -- and required -- to
merge all the input strings to obtain this string.
SAMPLE OUTPUT (file dna.out):
13
OUTPUT DETAILS:
Such string is "CGCATCGATTAGG".
Cow Phrasebook
Ever the innovator, Farmer John is teaching cows to speak some
phrases in human language. He writes each new phrase the cows learn
in his phrase book, a total of M (1 <= M <= 1,000) so far.
When Farmer John is on a vacation, he can only communicate with his
cows by telephone. Being an active vacationer, FJ visits beaches
and fine restaurants when away from the farm. When he returns, his
answering machine is full of N (1 <= N <= 10,000) messages, many
potentially from the cows.
FJ vacations frugally and thus gets poor telephone service. Many
of the recorded messages cut off before they are complete. Help FJ
determine whether the recorded messages are from the phrasebook by
determining if the message begins a phrase.
You will be given the phrasebook and a set of texts of the recorded
messages. Count the number of recorded messages that are the beginning
(prefix) of a phrase from the phrase book.
Complete phrases are from 1 to 60 characters in length, each of which
is either a letter (upper or lower case), a period (.), comma (,),
question mark (?) or space. There are no leading spaces, trailing
spaces, or double spaces in a phrase. Comparisons are case-sensitive,
and a phrase is in fact, considered to be prefix of itself.
PROBLEM NAME: phrase
INPUT FORMAT:
- Line 1: Two space-separated integers, M and N
- Lines 2..M+1: Phrases from the phrase book, one per line.
- Lines M+2..M+N+1: Phrases spoken by cows, one per line.
SAMPLE INPUT (file phrase.in):
3 4
I will not buy this record, it is scratched.
My hovercraft is full of eels.
Do you want to come back to my place? Bouncy, bouncy.
I will not buy this rec
My helicopter is
Do you want to come back
I will not buy this cat.
INPUT DETAILS:
Three input phrases (record, eels, bouncy); four query phrases
(buy, helicopter, come back, cat).
OUTPUT FORMAT:
- Line 1: A single integer that is the count of the number of messages
that were proper prefixes of the phrasebook.
SAMPLE OUTPUT (file phrase.out):
2
OUTPUT DETAILS:
The messages 'I will not buy this rec' and 'Do you want to come back'
are valid prefixes of the phrasebook.
