--- tags: homework, 109, cpi title: '[109-cpi] HW14' --- # Homework 14 > Week 17 (01/04), Due: 01/11 09:00:00 * 範圍：**character** * NOJ --- ## Abbreviation > [name=Judge Girl] ### Description Write a program to extract abbreviations from input. For example, if you are given three strings "national", "taiwan", "university", you must answer "NTU". Note that there are four words that will not appear in the abbreviation - "of", "and", "the", and "at". For example, "the", "united", "states", "of", "america", will become "USA". ### Input The input is a sequence of words consisting of lowercase letters and periods only. A set of words to form an abbreviation must ends with the last word having a '.' (period) at the end. For the previous "NTU" example, you will have "national" "taiwan", then "university.". Please note that there is a period '.' at the end of "university". You must process all inputs until EOF. The last word of the input is guaranteed to have an ending '.'. It is also guaranteed that all abbreviations will have at least one character. #### Limit The number of characters in a word including the ending period is no more than 127. The length of an abbreviation is no more than 127. ### Output You must output all abbreviations from the input, one per line. #### Subtasks | | Score | |:--------- | ----- | | #0 | $30$ | | #1 | $30$ | | #2 | $40$ | | **Total** | $100$ | ### Example Input 0 ``` the united states of american. taiwan high speed rail. national taiwan university. metropolitan rapid transit. north atlantic treaty organization. european union. united kingdom. national chiao tong university. university of hong kong. massachusetts institute of technology. university of california at san diego. national aeronautics and space administration. immigration and naturalization service. ``` ### Example Output 0 ``` USA THSR NTU MRT NATO EU UK NCTU UHK MIT UCSD NASA INS ``` ### Hint - 本題搬運自 [Judge Girl](https://judgegirl.csie.org/problem/0/276) --- ## Similar Strings > [name=Judge Girl] ### Description Write a program to determine if two words are similar. Two words are similar if the one of the following two conditions is true. - The lengths of the two strings are the same, and one string can be obtained by switching two consecutive characters in the other string. For example, `best` and `bets` are similar. - The lengths of the two strings differ by 1, and shorter string can be obtained by deleting one character from the longer string. For example, `best` and `bet` are similar. - Two strings are equal. Now given a set of pairs of strings, determine whether if they are similar. The first line of the input is the number of pairs of string, $n$ . The length of string is no more than 80. Each pair of string has two lines. The output has $n$ lines. If the i-th pair is similar, the output is `yes`. Otherwise the output is `no`. ### Input <!-- #### Limit --> ### Output #### Subtasks | | Score | |:--------- | ----- | | #0 | $30$ | | #1 | $30$ | | #2 | $40$ | | **Total** | $100$ | ### Example Input 0 ``` 4 best bets bet best bet bat sample sample ``` ### Example Output 0 ``` yes yes no yes ``` ### Hint - 本題搬運自 [Judge Girl](https://judgegirl.csie.org/problem/0/130) --- ## Play with Words Too > [name=Judge Girl] ### Description 寫一個程式，去「玩轉字」吧！\ 你的程式應要能夠支持下列指令： Write a program (again) to play with words. Your program should support the following commands. * `insert left x n` Insert n characters of x at the beginning of a word. * `insert right x n` Insert n characters of x at the end of a word. * `insert k x n` Insert n characters of x so that the first of them will become the k-th character of this word. * `print` Print the current content of the word in the following format: if the word is `gooooooooooooooooooooooooooogle`, you should print `g 1 o 27 g 1 l 1 e 1 $`. In other words, you should encode all consecutive sequences with the same character into character-length pairs, then print a dollar sign to indicate the end of the word. x 是 字元，n和k則都是正整數。 Where x is a alphanumeric character and both n and k are positive integers. ### Input The input data contains a sequence of commands described above. You may assume that all commands are valid. That is, k would not exceed the current length of the word plus 1. The total length of the word would less then 2147483647. <!-- #### Limit --> ### Output You should output the content of the word in the compressed format described above whenever you read the print command. #### Subtasks | |Score | |:---|-----:| | #0 |$35$ | | #1 |$35$ | | #2 |$30$ | | **Total** | $100$ | ### Example Input 0 ``` print insert left g 2 insert right e 1 insert 3 l 1 insert 2 o 2 print insert 4 o 25 print ``` ### Example Output 0 ``` $ g 1 o 2 g 1 l 1 e 1 $ g 1 o 27 g 1 l 1 e 1 $ ``` ### Hint * 原題搬運至 [Judge girl](https://judgegirl.csie.org/problem/0/47) * 如會 `TLE`，請告知助教 --- ## Food Ingredients in Common > [name=Judge Girl] ### Description A Food has many ingredients. For example, a cake is made of egg, flour, sugar, and butter and an omelet is made of egg, bacon, and ham. As a result the common ingredients of cake and omelet is egg. Now write a program to determine the common ingredients of given two foods. ### Input The first line of the input is $n$, the number of foods. Each of the next $n$ lines starts with the food, followed by a number $i$, then number of ingredients, then followed by the names of the $i$ different ingredients. All names of food and ingredients consist of lower case letter only. The next line is $m$, the number of queries. Each of the following $m$ line has the names of two foods. #### Limits - $n$ is positive and no more than $100$ - $i$ is positive and no more than $10$ - The length of food and ingredient names are positive and no more than $64$. ### Output The output has $m$ lines. The $i$-th line lists the names of common ingredients for the $i$-th query. You must output the names in dictionary order. If there is no common ingredients for a query, you must output `“nothing”`. It is guaranteed that no ingredient is called `“nothing”`. ### Sample Input ``` 3 cake 4 egg flour sugar butter omelet 4 egg bacon ham butter bread 1 flour 2 cake omelet omelet bread ``` ### Sample Output ``` butter egg nothing ``` ### Hint * 原題搬運至 [Judge Girl](https://judgegirl.csie.org/problem/0/98) --- ## A Simple BASIC Interpreter > [name=Judge Girl] ### Description Write a simple BASIC interpreter. A simple basic program has two parts -- a variable declaration part and a statement part. The variable declaration part is always the first line (line 0) in the program. It has all the variable declaration and their initial values, and ends with `"END"`. For example the following is an example of variable declaration part. It declares 8 variables and gives them initial values. ``` N = 2 F = 2 ONE = 1 TWO = 2 R = 0 S = 0 ZERO = 0 HUNDRED = 100 END ``` The rest of a simple BASIC program is the statement part, starting with line 1. Each line is a statement. There are five possible statements. - A GOTO statement transfers controls to another line. For example, the following command transfers control to line 1. ``` GOTO 1 ``` - An IF statement transfers control to another line if the condition is true, or to the next line if the condition is not true. For example the following command transfer control to line 11 if N is greater than HUNDRED. The condition can only take the form of "variable1 op variable2", where variable1 and variable2 are two variables and op is `"=="`, `"!="`, `">"`, `"<"`, `">="`, or `"<="`. ``` IF N > HUNDRED GOTO 11 ``` - An assignment statement assign an expression to a variable. For example the following statement assigns N with the sum of N and ONE. The expression can only take the form of "variable1 op variable2", where variable1 and variable2 are two variables and op is `"+"`, `"-"`, `"*"`, `"/"`, or `"%"`. ``` N = N + ONE ``` - A PRINT statement prints the value of a variable and a new line. For example the following statement prints the value of N in a line. ``` PRINT N ``` - A STOP statement stops the execution of the simple BASIC program. ### Input There input is a simple BASIC program. #### Limits - Lengths of variables are between 1 to 7. - There are at most 100 variables and 1000 lines in the program. - A variable name consists of uppercase letters and/or digits. ### Output The output is the results of all PRINT statements. ### Sample Input ``` N = 2 F = 2 ONE = 1 TWO = 2 R = 0 S = 0 ZERO = 0 HUNDRED = 100 END IF N > HUNDRED GOTO 11 F = TWO + ZERO R = N % F IF R == ZERO GOTO 9 F = F + ONE S = F * F IF S <= N GOTO 3 PRINT N N = N + ONE GOTO 1 STOP ``` ### Sample Output ``` 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 ``` ### Hint * 原題搬運至[Judge Girl](https://judgegirl.csie.org/problem/0/270) * 將大量重複使用的部分設計成函式，可以簡化程式碼。