Sample Output - IME – Instituto de Matemática e Estatística UERJ
Transcrição
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