Sample Output - IME – Instituto de Matemática e Estatística UERJ

IME 04-10859 - DESENV. E IMPLEMENTAÇÃO DE ALGORITMOS – 30/05/2015
Este caderno contém 14 páginas com a descrição de 10 problemas definidos a seguir:
A – Excuses, excuses! (Valladolid 409)
B – Word-Search Wonder (Valladolid 422)
C – Named Extension Dialing (Valladolid 886)
D – Soundex Indexing (Valladolid 739)
E – Power Strings (Valladolid 10298)
F – I love Strings!!! (Valladolid 10679)
G – Automatic Correction of Mispellings (Valladolid 11048)
H – Extend To Palindromes (Valladolid 11475)
I – Plágio Musical (Musical Plagiarism Valladolid 11837)
J – Secret Word (Valladolid 12467)
Desafios:
K – The longest constant gene (Valladolid 1227)
L – Top 10 (Valladolid 1254)
M – Life Forms (Valladolid 11107)
N - Hnelpig Arnde (Valladolid 12274)
1. Os alunos podem trabalhar em grupos de 2, usando um micro apenas.
2. Alguns dos problemas são do site da Universidade de Valladolid.
3. Pode ser consultado qualquer material escrito. Não se pode usar pen-drives nem
Internet na aula, a menos que seja expressamente permitido pelo professor.
4. Os problemas serão posteriormente checados para verificar sua originalidade.
5. A pontuação dos problemas está na página da disciplina.
6. As linguagens permitidas são: Pascal, C, C++. JAVA quando permitido
expressamente,
7. Usaremos o sistema BOCA para submissão e correção dos problemas.
- Cada dupla receberá um código: time1 a time40, com password inicial igual
ao nome do time, que poderá ser trocada. Esse nome será usado em todo o
curso.
- Para acessar o sistema BOCA usar a URL http://152.92.106.xxx/boca , xxx
será informado no início de cada aula.
- Logar usando os parâmetros da dupla.
- Submeter cada programa com o nome correto: Ex: A.pas, C.cpp, B.c
8. Resolver e programar com calma.
Boa sorte.
1
Problema A(Valladolid 409)
Excuses, Excuses!
Judge Ito is having a problem with people subpoenaed for jury duty giving rather lame
excuses in order to avoid serving. In order to reduce the amount of time required
listening to goofy excuses, Judge Ito has asked that you write a program that will search
for a list of keywords in a list of excuses identifying lame excuses. Keywords can be
matched in an excuse regardless of case.
Input
Input to your program will consist of multiple sets of data.
•
•
•
•
•
•
Line 1 of each set will contain exactly two integers. The first number
(1 ≤ K ≤ 20) defines the number of keywords to be used in the search. The
second number (1 ≤ E ≤ 20) defines the number of excuses in the set to be
searched.
Lines 2 through K+1 each contain exactly one keyword.
Lines K+2 through K+1+E each contain exactly one excuse.
All keywords in the keyword list will contain only contiguous lower case
alphabetic characters of length L (1 ≤ L ≤ 20) and will occupy columns 1
through L in the input line.
All excuses can contain any upper or lower case alphanumeric character, a
space, or any of the following punctuation marks [SPMamp".,!?&] not including
the square brackets and will not exceed 70 characters in length.
Excuses will contain at least 1 non-space character.
Output
For each input set, you are to print the worst excuse(s) from the list.
•
•
•
The worst excuse(s) is/are defined as the excuse(s) which contains the largest
number of incidences of keywords.
If a keyword occurs more than once in an excuse, each occurrance is considered
a separate incidence.
A keyword ``occurs" in an excuse if and only if it exists in the string in
contiguous form and is delimited by the beginning or end of the line or any nonalphabetic character or a space.
For each set of input, you are to print a single line with the number of the set
immediately after the string ``Excuse Set #". (See the Sample Output). The following
line(s) is/are to contain the worst excuse(s) one per line exactly as read in. If there is
more than one worst excuse, you may print them in any order.
After each set of output, you should print a blank line.
2
Sample Input
5 3
dog
ate
homework
canary
died
My dog ate my homework.
Can you believe my dog died after eating my canary... AND MY HOMEWORK?
This excuse is so good that it contain 0 keywords.
6 5
superhighway
crazy
thermonuclear
bedroom
war
building
I am having a superhighway built in my bedroom.
I am actually crazy.
1234567890.....,,,,,0987654321?????!!!!!!
There was a thermonuclear war!
I ate my dog, my canary, and my homework ... note outdated keywords?
Sample Output
Excuse Set #1
Can you believe my dog died after eating my canary... AND MY HOMEWORK?
Excuse Set #2
I am having a superhighway built in my bedroom.
There was a thermonuclear war!
3
Problema B (Valladolid 422)
Word-Search Wonder
The Pyrates Restaurant was starting to fill up as Valentine McKee walked in. She scanned the
crowd for her sister, brother-in-law, and nephew. Seeing her sister waving from the far end of
the restaurant, she made her way back to their booth. ``Hi, Valentine,'' her sister and brother-inlaw, Niki and Dennis Chapman, greeted her.
``Hi, guys,'' she replied. ``What are you doing, Wade?'' she asked her nephew. He was busy
working on one of the restaurant's activity sheets with a crayon.
``I'm doing a word search game,'' Wade explained. ``I have to find all of these words in this big
mess of letters. This is really hard.'' Wade looked intently at the paper in front of him.
``Can I help?'' asked Valentine, looking across the table at the activity sheet.
``Sure. These are the words we're looking for. They're the names of different kinds of Planes,
Trains, and Automobiles.''
Input
The first line will specify the length (in characters) of the sides of the letter matrix (the matrix of
letters is square). The length, l, will be in the range 1≤ l ≤ 100. The next l lines of input will be
the matrix itself, each line will contain l uppercase letters.
A list of words will follow. Each word will be on a line by itself; there will be 100 or fewer
words. Each word will be 100 or fewer characters long, and will only contain uppercase letters.
The final line of input will contain a single zero character.
Output
Your program should attempt to find each word from the word list in the puzzle. A word is
``found'' if all the characters in the word can be traced in a single (unidirectional) horizontal,
vertical, or diagonal line in the letter matrix. Words may not ``wrap around'' rows or columns,
but horizontal and diagonal words may proceed from right to left (``backwards''). For each word
that is found, your program should print the coordinates of its first and last letters in the matrix
on a single line, separated by a single space. Coordinates are pairs of comma-separated integers
(indexed from 1), where the first integer specifies the row number and the second integer
specifies the column number.
If a word is not found, the string ``Not found'' should be output instead of a pair of
coordinates.
Each word from the input can be ``found'' at most once in the puzzle.
Sample Input
5
EDEEE
DISKE
ESEEE
ECEEE
EEEEE
DISC
DISK
DISP
0
Sample Output
1,2 4,2
2,1 2,4
Not found
4
Problema C (Valladolid 886)
Named Extension Dialing
The marketing research group of the S&TC (String & Tin Can) telephone company recently
concluded its analysis of leading-edge services that could be developed for its CENTREX
(business user) customers. The analysis showed that ``Named Extension Dialing'' (NED) has the
highest profit potential. To maximize profit by minimizing non-recurring expenses, S&TC has
contracted your team to develop a module for the automated attendant system that implements
NED.
Currently when a call is placed to a business' primary number, the caller is greeted with the
pleasant, and almost human, message ``You have reached XYZ Corporation. If you know your
party's extension, please dial it now, or stay on the line for an operator.'' NED will allow the
sentence, ``If you know your party's name, dial the first letter of the first name followed by the
first letters of the last name of your party now,'' to be added to the message.
Input
Input to your software module will be a directory of names and extensions, one per line,
followed by lines containing arbitrary numeric strings dialed by people calling XYZ
Corporation. These strings will have more than 1 digit. Each directory entry consists of a first
name, one space, a last name, one space, and a 4-digit phone extension. Names can contain any
combination of up to twenty lower and upper case letters. No input line will exceed 80
characters.
Output
For each dialed number, the program is to output, on one line starting in the first column, the list
of extensions to which the number could be referring. If the dialed number exactly matches an
extension, output the extension; otherwise, output the list of extensions that correspond with
names that match the dialed number, the numbers should be output in the same order as they
appeared in the input. Multiple extensions that match a dialed number are to be separated from
each other by single spaces. The dialed number must match the characters in the name exactly.
(Homophonic matching of names was already completed in an earlier contest.) If the input fails
to match any names or extensions, output `0'.
Sample Input
Barry Charles 4384
John Smith 2315
Susan Small 5764
Alexis Baxter 4652
Kim Rohde 6678
22
5764
2345
22298
Sample Output
4384 4652
5764
0
4652
5
Problema D (Valladolid 739)
Soundex Indexing
The Soundex Index System was developed so that similar sounding names, or names with
similar spelling could be encoded for easy retrieval. It has been used by the U.S. Bureau of the
Census, and some States use it to help encode your driver's license number. Your task is to read
a sequence of names, one at a time and one per line, compute the corresponding soundex code,
and write to the output file the name and its soundex code (one line of output per name).
Names will contain from 1 to 20 upper case, alphabetic characters (ASCII values 65 thru 90,
inclusive). Names shorter than 20 characters will NOT be padded with blanks. Thus a name will
consist of upper case letters only.
How to generate the Soundex Code:
A Soundex Code always consists of a letter followed by three digits. Here are the rules for
soundex encoding:
1. The first letter of a name appears as the first and only letter in the soundex code.
2. The letters A, E, I, O, U, Y, W and H are never encoded, but do break successive code
sequences (see next rule).
3. All other letters are encoded EXCEPT when they immediately follow a letter (including the
first letter) that would be encoded with the same code digit.
4. The soundex code guide is:
Code Key Letters and Equivalents
1
B, P, F, V
2
C, S, K, G, J, Q, X, Z
3
D, T
4
L
5
M, N
6
R
5. Trailing zeros are appended to short codes so all names are encoded with a letter followed by
three digits.
6. Longer codes are truncated after the third digit.
Input
The input file contains a list of names, one per line. Each name will not exceed 20 characters,
and you may assume that only upper case letters will be used. Your program should continue to
read names until the end of the file is detected.
Output
The output written to the file should consist of a column of names and a column of their
corresponding soundex codes. Write the headings ``NAME" and ``SOUNDEX CODE" in the first
line of the output file in columns 10 and 35, respectively. After the heading line, the names and
soundex codes should be written (one pair per line) with the name starting in column 10 and the
soundex code beginning in column 35. The comment ``END OF OUTPUT" should appear at
the end of the output file on the line immediately after the last name. This comment should be
written starting in column 20.
6
Sample Input
Sample Output
LEE
KUHNE
EBELL
EBELSON
SCHAEFER
SCHAAK
NAME
LEE
KUHNE
EBELL
EBELSON
SCHAEFER
SCHAAK
SOUNDEX CODE
L000
K500
E140
E142
S160
S200
END OF OUTPUT
|
|
|
|
|
|__ Column 35
|
|__ Column 20
|__ Column 10
7
Problema E (Valladolid 10298)
Power Strings
Given two strings a and b we define a*b to be their
concatenation. For example, if a = "abc" and b = "def" then
a*b = "abcdef". If we think of concatenation as
multiplication, exponentiation by a non-negative integer is
defined in the normal way: a^0 = "" (the empty string) and
a^(n+1) = a*(a^n).
Each test case is a line of input representing s, a string of
printable characters. For each s you should print the largest
n such that s = a^n for some string a. The length of s will be
at least 1 and will not exceed 1 million characters. A line
containing a period follows the last test case.
Sample Input
abcd
aaaa
ababab
.
Sample Output
1
4
3
8
Problema F (Valladolid 10679)
I love Strings!!!
Hmmmmmm…………strings again :) Then it must be an easy task for you.
Well……you are given with a string S of length not more than 100,000 characters (only
‘a’-‘z’ and ‘A’ – ‘Z’). Then follows q (q < 1000) queries where each query contains a
string T of maximum length 1,000 (also contains only ‘a’-‘z’ and ‘A’ – ‘Z’). You
should determine whether or not T is a substring of S.
Input
First line contains an integer k (k < 10) telling the number of test cases to follow.
Each test case begins with S. It is followed by q. After this line there are q lines each of
which has a string T as defined before.
Output
For each query print ‘y’ if it is a substring of S or ‘n’ otherwise followed by a new
line. See the sample output below.
Sample Input
2
abcdefghABCDEFGH
2
abc
abAB
xyz
1
xyz
Sample Output
y
n
y
9
Problema G (Valladolid 11048)
Automatic correction of misspellings
Some text editors offer a feature to correct words which seem to be written incorrectly.
In this problem you are asked to implement a simple Automatic Correction of
Misspellings (ACM). ACM takes care of the following misspellings of words:
1. One letter is missing (e.g., letter is written leter) or too much (e.g., letter is
written lettter).
2. One letter is wrong (e.g., letter is written ketter)
3. The order of two adjacent letters is wrong (e.g., letter is written lettre)
ACM is based on a dictionary of known words. When a text contains a word which is
not in the dictionary, ACM will try to replace it by a similar word of the dictionary.
Two words are similar if we can transform one word into the other by doing exactly one
of the misspellings listed above. An unknown word is left unchanged if there is no
similar word in the dictionary.
Input Specification
The first line of the input will give the number n of words in the dictionary (n ≤ 10000).
The next n lines contain the dictionary words. The following line will give the number
of query words q (q ≤ 1000). The next q lines contain the query words. You may
assume that each word in the input consists of 1 to 25 lower case letters ('a' to 'z').
Output Specification
For each query word, print one line with the query word followed by one of the
following possibilities:
1. is correct, if the word occurs in the dictionary.
2. is a misspelling of <x>, where <x> is a word of the dictionary similar to the
query word, and the query word is not in the dictionary. In the case that there are
several possibilities, select the word from the dictionary which appeared earlier
in the input.
3. is unknown, if cases 1 and 2 do not apply.
Sample Input
Sample Output
10
this
is
a
dictionary
that
we
will
use
for
us
6
su
as
the
dictonary
us
willl
su is a misspelling of us
as is a misspelling of is
the is unknown
dictonary is a misspelling
of dictionary
us is correct
willl is a misspelling of
will
10
Problema H (Valladolid 11475)
Extend To Palindromes
Your task is, given an integer N, to make a palidrome (word that reads the same when you
reverse it) of length at least N. Any palindrome will do. Easy, isn't it? That's what you thought
before you passed it on to your inexperienced team-mate. When the contest is almost over, you
nd out that that problem still isn't solved. The problem with the code is that the strings generated
are often not palindromic. There's not enough time to start again from scratch or to debug his
messy code. Seeing that the situation is desperate, you decide to simply write some additional
code that takes the output and adds just enough extra characters to it to make it a palindrome
and hope for the best. Your solution should take as its input a string and produce the smallest
palindrome that can be formed by adding zero or more characters at its end.
Input
Input will consist of several lines ending in EOF. Each line will contain a non-empty string
made up of upper case and lower case English letters (`A'-`Z' and `a'-`z'). The length of the
string will be less than or equal to 100,000.
Output
For each line of input, output will consist of exactly one line. It should contain the
palindrome formed by adding the fewest number of extra letters to the end of the
corresponding input string.
Sample Input
aaaa
abba
amanaplanacanal
xyz
Sample Output
aaaa
abba
amanaplanacanalpanama
xyzyx
11
Problema I (Valladolid 11837)
Plágio musical
As notas musicais são unidades básicas da música ocidental tradicional. Cada nota é associada a
uma frequência. Duas notas musicais cujas frequências fundamentais tenham uma relação de
potência de 2 (uma metade da outra, uma duas vezes a outra, etc.) são percebidas como muito
similares. Por isso, todas as notas com esse tipo de relação recebem o mesmo nome, como
descrito a seguir. Há doze notas básicas, em uma sequência crescente de frequências, cada nota
separada da anterior por uma mesma distância na escala musical (essa distância é chamada de
meio-tom). Sete dessas doze notas são representadas por letras do alfabeto (A, B, C, D, E, F e
G). A tabela abaixo mostra a distância, em meio-tons, entre essas notas.
Notas
A-B B-C C_D D-E E-F F-G G-A
Número de meios-tons
2
1
2
2
1
2
2
Note que há cinco notas que não são representadas pelas letras do alfabeto: as que estão entre A
e B, entre C e D, entre D e E, entre F e G e entre G e A.
As notas podem ser modificadas por duas alterações cromáticas: sustenido e bemol,
representadas respectivamente pelos s´ımbolos ‘#’ e ‘b’. Sustenido altera a nota em meio tom
para cima, e bemol altera a nota em meio tom para baixo. Uma nota com alteração cromática é
denotada pelo nome da nota seguida pelo símbolo da alteração. Note que com esse esquema
conseguimos representar todas as doze notas.
Uma melodia pode ser representada por uma sequência de notas musicais. Por exemplo,
A A D C# C# D E E E F# A D G# A
é uma melodia muito conhecida. Note no entanto que, como as distâncias entre os meios-tons
são sempre iguais, a mesma melodia pode ser escrita iniciando em outra nota (dizemos que a
melodia está em outro tom):
B B E D# D# E Gb Gb Gb G# B E A# B
Sua vizinha é uma famosa compositora que suspeita que tenham plagiado uma de suas músicas.
Ela pediu a sua ajuda para escrever um programa que, dada a sequência de notas da melodia de
sua música, e a sequência de notas de um trecho de melodia suspeito, verifique se o trecho
supeito ocorre, em algum tom, na música dada.
Entrada
A entrada é composta por vários casos de teste. A primeira linha de um caso de teste contém
dois inteiros M e T (1 ≤ M ≤ 100000, 1 ≤ T ≤ 10000, T ≤ M), indicando respectivamente o
número de notas da música e do trecho suspeito de ter sido plagiado. As duas linhas seguintes
contém M e T notas, respectivamente, indicando as notas da música e do trecho suspeito.
As notas em cada linha são separadas por espaço; cada nota é uma dentre ‘A’, ‘B’, ‘C’, ‘D’,
‘E’, ‘F’ ou ‘G’, possivelmente seguida de um modificador: ‘#’ para um sustenido ou ‘b’ para
um bemol.
O último caso de teste é seguido por uma linha que contém apenas dois números zero
separados por um espaço em branco.
Saída
Para cada caso de teste, imprima uma única linha contendo um caractere: ‘S’ caso o trecho
realmente tenha sido plagiado pela música ou ‘N’ caso contrário.
43
Exemplo de Entrada
C E G Bb
16 4
D F# A
D G A B C D G G G C D E F# G C C
00
GGCD
12 2
Exemplo de Saída
C C# D D# E F F# G G# A A# B
S
CD
N
12 2
N
C Db D Eb E F Gb G Ab A Bb B
S
CD
12
Problema J (Valladolid 12467)
Secret Word
Alicia and Roberto like to play games. Today, Roberto is trying to guess a secret word that
Alicia chose. Alicia wrote a long string S in a piece of paper and gave Roberto the following
clues:
•The secret word is a non-empty substring(A substring of S is defined as any consecutive
sequence of characters belonging to S. For example, if S = abcd then a, abcd, ab, bc and bcd are
some of the substrings of S but ac, aa aabbccdd and dcba are not substrings of S) of S (possibly
equal to S).
• S starts with the secret word reversed.
Roberto knows Alicia very well, and he’s sure that if there are several possible secret words that
satisfy the clues above, Alicia must have chosen the longest one. Can you help him guess the
secret word?
Input
The first line of the input file contains a single integer number T ≤ 150, the number of test cases.
T lines follow, each with a single string S. S will only contain lowercase English letters. The
length of S will not exceed one million characters.
Output
For each test case, output the secret word in one line.
Explanation of the sample cases:
•colombia: if you take c and reverse it you get c. colombia starts with c, so this satisfies the two
clues above. Furthermore, c is the longest word that satisfies the two clues so it must be the
secret word.
• abcdba: if you take ba and reverse it you get ab. abcdba starts with ab and there’s no longer
substring that satisfies the two clues.
•neversayeven: if you take even and reverse it you get neve. neversayeven starts with neve and
there’s no longer substring that satisfies the two clues.
• neveroddoreven: this case is a palindrome so if we reverse it we get the same string.
neveroddoreven starts with neveroddoreven (since they are the same) and obviously there’s no
longer substring that satisfies that, so this is the secret word.
•listentothesilence: Notice the secret word might be somewhere in the middle of the big word.
Sample Input
5
colombia
abcdba
neversayeven
neveroddoreven
listentothesilence
Sample Output
c
ba
even
neveroddoreven
sil
13