GREATEST COMMON SUBSEQUENCE Source: GCS.(PAS,C,CPP) Input File: GCS.IN Output File: GCS.OUT Your task is to write a program that computes the LENGTH of the longest common substring of two given strings. The substring does not have to be connected. Examples: longest common string 1 string 2 substring length ------------------------------------------------------- abcabcabc aabbcc abbcc 5 aabcc 5 aabbc 5 belaljubljana belakrajina belajna 7 xxxyyyzzz aaabbbccc 0 Note that in the first example there are several different longest common substrings, but they all have the same length. You may assume all strings consist of lower-case letters only.Your program should work for fairly long strings (several hundred characters long). INPUT DATA: The file GCS.IN contains in the first line an integer N.The rest of the file contains 2*N lines which represent N input pairs of strings. OUTPUT DATA: N lines of output, the k-th line contains an integer which is the length of the longest common substring of the (2*k)-th and (2*k+1)-th input string. SAMPLE INPUT AND OUPUT: INPUT: 3 ikarus dedalus onetwothreefour fivesixseveneight odnekdajlepesoljubljankeslovele allepseodurskebiloninobene OUTPUT: 3 3 13 MAGIC SQUARES Source: MAGIC.(PAS,C,CPP) Input File: MAGIC.IN Output File: MAGIC.OUT Following the success of the magic cube, Mr. Rubik invented its planar version, called magic squares. This is a sheet composed of 8 equal-sized squares (see Figure 1). --------- |1|2|3|4| |8|7|6|5| --------- Figure 1: Initial configuration In this task we consider the version where each square has a different colour. Colours are denoted by the first 8 positive integers (see Figure 1). A sheet configuration is given by the sequence of colours obtained by reading the colours of the squares starting at the upper left corner and going in clockwise direction. For instance, the configuration of Figure 1 is given by the sequence (1,2,3,4,5,6,7,8). This configuration is the initial configuration. Three basic transformations, identified by the letters 'A', 'B' and 'C', can be applied to a sheet: 'A': exchange the top and bottom row, 'B': single right circular shifting of the rectangle, 'C': single clockwise rotation of the middle four squares. All configurations are available using the three basic transformations. ---------------------------------------------------------------------- A: 1 2 3 4 --------- |8|7|6|5| |1|2|3|4| --------- 8 7 6 5 B: 1 2 3 4 --------- |4|1|2|3| |5|8|7|6| --------- 8 7 6 5 C: 1 2 3 4 --------- |1|7|2|4| |8|6|3|5| --------- 8 7 6 5 Figure 2: Basic transformations ---------------------------------------------------------------------- The effects of the basic transformations are described in Figure 2. Numbers outside the squares denote square positions. If a square in position p contains number i, it means that after applying the transformation, the square whose position was i before the transformation moves to position p. You have to write a program that computes one of possible sequences of basic transformations that transforms the initial configuration of Figure 1 to a specific target configuration. Input Data The file MAGIC.IN contains rows of 8 positive integers, the descriptions of the target configuration. End of data is given by end of file. Output Data For each given target configuration the output in MAGIC.OUT consists of the folowing block of lines: In the first line there is the length L of the transformation sequence. On the following L lines there is the sequence of identifiers of basic transformations, one letter in the first position of each line. There is no blank lines between blocks. Example Input and Output -------------------------------------------------------------- MAGIC.IN MAGIC.OUT 6 4 2 8 1 3 5 7 7 8 7 6 5 4 3 2 1 A C A B C C B 1 A Oil Deposits Source: OIL.(PAS,C,CPP) Input File: OIL.IN Output File: OIL.OUT The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid. The input file contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 # m # 100 and 1 # n # 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either `*', representing the absence of oil, or `@', representing an oil pocket. For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets. Example input: 1 1 * 3 5 *@*@* **@** *@*@* 1 8 @@****@* 5 5 ****@ *@@*@ *@**@ @@@*@ @@**@ 0 0 Example output: 0 1 2 2 Snail Source: SNAIL.(PAS,C,CPP) Input File: SNAIL.IN Output File: SNAIL.OUT A snail is at the bottom of a 6-foot well and wants to climb to the top. The snail can climb 3 feet while the sun is up, but slides down 1 foot at night while sleeping. The snail has a fatigue factor of 10%, which means that on each successive day the snail climbs 10% × 3 = 0.3 feet less than it did the previous day. (The distance lost to fatigue is always 10% of the first day's climbing distance.) On what day does the snail leave the well, i.e., what is the first day during which the snail's height exceeds 6 feet? (A day consists of a period of sunlight followed by a period of darkness.) As you can see from the following table, the snail leaves the well during the third day. Day Initial Height Distance Climbed Height After Climbing Height After Sliding 1 0 3 3 2 2 2 2.7 4.7 3.7 3 3.7 2.4 6.1 -- Your job is to solve this problem in general. Depending on the parameters of the problem, the snail will eventually either leave the well or slide back to the bottom of the well. (In other words, the snail's height will exceed the height of the well or become negative.) You must find out which happens first and on what day. The input file contains one or more test cases, each on a line by itself. Each line contains four integers H, U, D, and F, separated by a single space. If H = 0 it signals the end of the input; otherwise, all four numbers will be between 1 and 100, inclusive. H is the height of the well in feet, U is the distance in feet that the snail can climb during the day, D is the distance in feet that the snail slides down during the night, and F is the fatigue factor expressed as a percentage. The snail never climbs a negative distance. If the fatigue factor drops the snail's climbing distance below zero, the snail does not climb at all that day. Regardless of how far the snail climbed, it always slides D feet at night. For each test case, output a line indicating whether the snail succeeded (left the well) or failed (slid back to the bottom) and on what day. Format the output exactly as shown in the example. Example input: 6 3 1 10 10 2 1 50 50 5 3 14 50 6 4 1 50 6 3 1 1 1 1 1 0 0 0 0 Example output: success on day 3 failure on day 4 failure on day 7 failure on day 68 success on day 20 failure on day 2 The Sultan's Successors Source: SULTAN.(PAS,C,CPP) Input File: SULTAN.IN Output File: SULTAN.OUT The Sultan of Nubia has no children, so she has decided that the country will be split into up to k separate parts on her death and each part will be inherited by whoever performs best at some test. It is possible for any individual to inherit more than one or indeed all of the portions. To ensure that only highly intelligent people eventually become her successors, the Sultan has devised an ingenious test. In a large hall filled with the splash of fountains and the delicate scent of incense have been placed k chessboards. Each chessboard has numbers in the range 0 to 99 written on each square and is supplied with 8 jewelled chess queens. The task facing each potential successor is to place the 8 queens on the chess board in such a way that no queen threatens another one, and so that the numbers on the squares thus selected sum to a number at least as high as one already chosen by the Sultan. (For those unfamiliar with the rules of chess, this implies that each row and column of the board contains exactly one queen, and each diagonal contains no more than one.) Write a program that will read in the number and details of the chessboards and determine the highest scores possible for each board under these conditions. (You know that the Sultan is both a good chess player and a good mathematician and you suspect that her score is the best attainable.) Input will consist of k (the number of boards), on a line by itself, followed by k sets of 64 numbers, each set consisting of eight lines of eight numbers. Each number will be in the range 0 to 99. There will never be more than 20 boards. Output will consist of k numbers consisting of your k scores, each score on a line by itself and right justified in a field 5 characters wide. Sample input 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 48 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 Sample output 260 URL Source: URL.(PAS,C,CPP) Input File: URL.IN Output File: URL.OUT Given the set of URLs (Uniform Resource Locator) the task is to count the number of the correct URLs corresponding to the following grammatical rules. Explanation of some notational constructs: xxx yyy - xxx should be followed by yyy xxx | yyy - xxx or yyy should appear "xxx" - xxx should appear explicitely xxx - rule xxx should be applied [ xxx ] - xxx is optional *[ xxx ] - xxx is repeated zero or more times httpurl = "http://" hostname [ "/" hpath [ "?" search ]] hpath = hsegment *[ "/" hsegment ] hsegment = *[ uchar | ";" | ":" | "@" | "&" | "=" ] search = *[ uchar | ";" | ":" | "@" | "&" | "=" ] hostname = *[ domainlabel "." ] domainlabel domainlabel = alpha | alpha *[ alphadigit | "-" ] alphadigit uchar = alpha | digit | safe | extra alphadigit = alpha | digit alpha = "a".."Z" | "A".."Z" digit = "0".."9" safe = "$" | "-" | "_" | "." | "+" extra = "!" | "*" | "'" | "(" | ")" | "," Input Data The file URL.IN consist of several test cases. In the first line of each test case, there is an integer N. Each of the following N lines contains an URL. End of input is terminated by end of file. Output Data For each test case the file URL.OUT contains a line with an integer which is the number of the correct URLs from the test case. The correct URL is the one which conforms to the gramatical rule "httpurl". Sample Input and Output Input: 4 http://www.rtk.si http://www.nexor.com/public/rfc/rfcs/rfc1738.txt http://av.yahoo.com/bin/query_uk?p=Tralala&z=2&hc=0&hs=0 http://vlado.mat.uni-lj.si/sreda/sreda.htm 3 http://www.3com.com http://www-ai.ijs.si\slais\slais.html http://www.ijs.si/cgi-bin/email?lang=[en] Output: 4 0 WILDCARDS MATCHING Source: WILDC(PAS,C,CPP) Input File: WILDC.IN Output File: WILDC.OUT In everyday live we often use wildcards when e.g. searching strings in a file (ra?unalnik) or specify a set of filenames (*.txt). Typically, when specifying wildcard strings, two special charactes are used: '*' matching zero or more charactes and '?' matching any single character. Examples of matching: data string wildcard string abcdefg = abcdefg abcdefg = abc* abcdefg = abc?efg abcdefgh = ab?*e*f?h abcdefgh = * abcdefg = ??????? The task is to write a program counting the number of successful matches between strings and wildcards. Input Data The file WILDC.IN contains in the first line integer N. In the following 2*N lines are pairs of data-string and wildcard-string. Output Data The first and the only line of WILDC.OUT contains the number of sucessful matched pairs (data-string, wildcard-string). Sample Input and Output Input: 3 data-string wildcard-string *string*string Incorrect Example ???????????????? a a Output: 2 Crossing Wires Source: WIRES.(PAS,C,CPP) Input File: WIRES.IN Output File: WIRES.OUT A firm, producing chips, NELIT, suffered from lack of profit. So they decided to cut down producing costs. Their new design would be as simple as possible. With uninsolated wires they would connect components on the chip and afterwards they will isolate the wires only on part of segments where two wires have a common point. Help NELIT designers and write a program which counts pairs of wires which have at least one common point. Input: Input (WIRES.IN) consists of blocks of lines, describing sample chip. In the first line of each block, there is number N (<= 1000), which describes the number of wires. The following N lines consist of 4 nonnegative whole numbers, giving coordinates of the starting and ending point of each wire. After each block there is a blank line. The end of input is denoted by a block with 0 in the first line. Output: For each block, WIRES.OUT has a single line with number of wire pairs, which have at least one common point. There is no line corresponding to the last null block. Sample input/output: 3 0 0 1 1 0 1 1 0 2 0 2 1 2 0 0 1 1 2 0 3 1 3 0 0 2 2 0 2 2 0 1 0 1 2 0 Output: 1 0 1