parades .pdf

File information


Original filename: parades.pdf

This PDF 1.5 document has been generated by TeX / pdfTeX-1.40.16, and has been sent on pdf-archive.com on 29/03/2018 at 16:42, from IP address 85.245.x.x. The current document download page has been viewed 158 times.
File size: 235 KB (2 pages).
Privacy: public file


Download original PDF file


parades.pdf (PDF, 235 KB)


Share on social networks



Link to this file download page



Document preview



Problem:
The Parades
The Parades

The sun
sun is
is beating
beating down
down as
as you
you look
look down
down from
from your
The
your VIP
VIP stand
stand after
after aa very
very nice
nice lunch
lunch and
and
observe the
the colourful
colourful spectacular
spectacular below,
below, aa sea
sea of
observe
of humanity
humanity in
in an
an array
array of
of brightly
brightly colourful
colourful
costumes. It’s
It’s almost
almost time
time for
for the
the traditional
traditional North
costumes.
North Versus
Versus South
South Parade
Parade where
where the
the most
most
respected
members
from
each
region
will
line
up
and
parade
past
the
public
and
VIP
stands.
respected members from each region will line up and parade past the public and VIP stands.
A voice
voice behind
behind you
you interrupts
interrupts your
your thoughts,
thoughts, “It’s
A
“It’s almost
almost time,
time, the
the master
master of
of ceremonies
ceremonies
wants
you
to
calculate
and
announce
the
winners”.
The
winners
from
each
side
will
wants you to calculate and announce the winners”. The winners from each side will form
form an
an
identically
coloured
sequence
and
then
parade
together
receiving
great
honour
and
tribute
identically coloured sequence and then parade together receiving great honour and tribute
from the
the two
two presidents.
presidents. A
A certain
certain unease
unease descends
from
descends upon
upon you
you as
as you
you realize
realize the
the truth
truth of
of the
the
old
saying,
there
is
no
such
thing
as
a
free
lunch.
old saying, there is no such thing as a free lunch.

Task
Task
Announcing the
the signal
signal is
is given
Announcing
the winners
winners is
is aa complicated
complicated and
and difficult
difficult task.
task, When
when the
given the
the
members
in
the
parades
have
to
form
up
into
two
lines
in
what
to
many
seems
like
some
members in the parades have to form up into two lines in what to many seems like some
seemingly random
winners
areare
thethe
parade
members
seemingly
random sequence
sequence and
andthen
thenbegin
beginthe
theparade.
parade.The
The
winners
parade
memthat
form
the
longest
common
coloured
subsequence
contained
in
each
line.
In
this
case
to
bers that from the longest common coloured subsequence contained in each line. In this
avoidtoties
we ties
always
lexicographically
smaller smaller
sequence
— in other
words words
blue,
case
avoid
we want
alwaysthe
want
the lexicographically
sequence
– in other
green,
red
is
better
than
red,
green,
blue.
As
there
are
a
lot
of
colours
we
shall
restrict
blue,green,red is better than red, green, blue. As there are a lot of colours we shall restrict
ourselves to
to 52
52 colours
colours and
. . . Z .a. .z.. . z.
Your
task
is to
calculate
number
ourselves
and label
label them
them A
A..Za.
Your
task
is to
calculate
thethe
number
of
of winners
from
each
sequence
colours.
winners
from
each
sideside
andand
thethe
sequence
of of
colours.

Input
Input
Two lines
lines of
of input.
input. Each
Each line
line will
will contain
contain one
one string
Two
string of
of at
at most
most 98
98 characters.
characters.

Output
Output
Two lines
lines of
of output
output (terminated
(terminated with
with aa new
new line
Two
line character).
character). On
On the
the first
first line
line an
an integer
integer with
with
the
length
of
the
winning
sequence
and
on
the
second
the
actual
sequence
(the
lexicographthe length of the winning sequence and on the second the actual sequence (the lexicograph†

A few minor changes have been made to the original version, which appeared in MIUP 2017, organized
by Departamento de Inform´
atica da Universidade do Minho.

MIUP 2017

1
1

B The Parades

ically smaller in case of a tie). In the case where there is no common sequence then the
output is only one line with the value zero (0).

Sample Input 1
abcd
fbcf

Sample Output 1
2
bc

Sample Input 2
CabD
CDab

Sample Output 2
3
Cab

Sample Input 3
xxabABxxcdCDefEF
ABxyabCDxycdEFef

Sample Output 3
8
ABxxcdEF

Sample Input 4
wjfljrglejrfrlfjejflerjflerjflejwwwwaaaswswxxwqq
ljrrjfglejrfljrlfjelrjflerjflerjflejwwwwwxxwqq

Sample Output 4
39
ljrglejrfrlfjejflerjflerjflejwwwwwxxwqq

2


Document preview parades.pdf - page 1/2

Document preview parades.pdf - page 2/2

Related documents


parades
day excusions april june 2016
lzxindustries visualcortex basic patches
aspects of gaelic poetry
ista usermanual en gb
qunatsym

Link to this page


Permanent link

Use the permanent link to the download page to share your document on Facebook, Twitter, LinkedIn, or directly with a contact by e-Mail, Messenger, Whatsapp, Line..

Short link

Use the short link to share your document on Twitter or by text message (SMS)

HTML Code

Copy the following HTML code to share your document on a Website or Blog

QR Code

QR Code link to PDF file parades.pdf