Input file: logo.in
The University trademark attorneys have no threshold of embarrassment. They now want to check every possible image for trademark infringement - even at the pixel level. You (having no threshold of embarrassment for the jobs you'll take) have been employed to write a program to check documents automatically.
You are to assume that you are given the dimensions of an image HEIGHT and WIDTH, and then an array of those dimensions filled with 0's and 1's. You are to scan the image looking for any occurrence of a 7 by 7 subarray containing:
0100010 1111111 0101010 0101010 0101010 0111110 0001000
(the subarray must be a contiguous 7 by 7 block of cells). Should you find any occurrence of the "logo block", you are to print "Trademark Infringement Located". Should you find no such 7 by 7 block within the array, you are to print "Trademark Infringement Not Located". Your program should continue processing images until a line with "end of input" is encountered..
Sample Input:
12 30 010111001010001010101000101010 000011110101010001010100010100 000001010100010101000010101000 101010110101010000101010101000 101010001010101010100010101000 001111111111010100010101000101 110010101000000101010000101000 010010101000100101010111010100 111010101011010100101010000011 000011111011010010100000111111 010000100010100010101010001010 110101000001010111101010001011 6 5 01000 10001 00011 11100 10010 01001 8 8 10110100 00001111 01010001 11101010 10101000 01010111 11010000 10101000 end of input Associated output: Trademark Infringement Located Trademark Infringement Not Located Trademark Infringement Not LocatedDownload Input Test Data Set
Download Output for Test Set
Input file: schedule.in
You are determined to optimize the obtaining of your degree with as little work as possible. You have been able to determine how many actual hours per week are required by various courses, and given the credit hours associated with those courses, the idea is to accumulate as many credit hours as possible providing the weekly work stays beneath some tolerance.
Input: You will be given a dataset beginning with an integer value of TOLERANCE on the initial line. The following lines will have the form COURSE_NUMBER HOURS_OF_WORK HOURS_OF_CREDIT. Each of these quantities is an integer. The data will be terminated with the line "end of input".
Problem: Determine a set of courses that maximizes the total number of credit hours but such that the total number of hours of work is less than or equal to the tolerance.
Output: Print the associated course numbers - one per line - of an optimum schedule and, as a last line, print
"this schedule yields <total credit hours>hours of credit with <total hours of work> hours of work".
Example:
Given the input:
40 304 20 3 105 6 1 336 10 3 352 2 3 315 6 3 370 1 3 345 8 3 378 15 3 201 7 5 555 9 5 end of input
The output should be:
105 352 315 370 345 201 555 this schedule yields 23 hours of credit with 39 hours of workDownload Input Test Data Set 1
Download Output for Test Set 1
Download Input Test Data Set 2
Download Output for Test Set 2
Download Input Test Data Set 3
Download Output for Test Set 3
Input file: polygon.in
The input consists of a number N (greater than or equal to three) followed by N lines each containing a pair of integers I J. These N pairs are the vertices of a polygon specified in counterclockwise fashion. You are to compute the area of the polygon and print "The area of the polygon is <area>". Then proceed to the next polygon doing the same, and continuing until a line with "end of input" is encountered. You may assume the boundary of the polygon does not overlap itself.
It is easy to prove that the area of such a polygon with integer vertices is either an integer or an integer plus ½. If the area is an integer plus ½, the output should use the fractional form (i.e. with " ½").
Sample Input:
3 0 0 1 1 0 1 4 -1 -1 2 -1 2 2 -1 2 5 1 2 2 3 3 5 0 3 0 2 end of input
Associated output:
The area of the polygon is 1/2 The area of the polygon is 9 The area of the polygon is 3 1/2Download Input Test Data Set
Download Output for Test Set
Input file: cypher.in
The Aggies have discovered the substitution cipher (a couple of millennia behind the rest of the world). That's the substitution encoding in which certain letters are always replaced by certain other letters (e. g. , "a" is always encoded as "r", "b" is always encode as "j", etc.).
One way to decode such messages is to use facts about letter frequencies. Thus if "e" is the most common letter used in standard text and "z" is the most common letter occurring in (a large amount of) encoded text, then we conclude that "e" must have been encoded as "z". We would then proceed to the next most commonly occurring letter used in text and match that with the next most commonly occurring letter occurring in the encoding. This proceeds until we have matched the least commonly occurring letter in standard text with the least commonly occurring letter in the encoded text. At that point, we have determined the entire code and can encode or decode any message. We use only lower case letters and no blanks in both standard and encoded text.
The trouble is that the language employed by Aggies has not only strange words but unusual spellings: it's a language of its own. Nevertheless, even though we cannot understand it, we should be able to employ these ideas to determine the substitution ciphers used in Aggietalk. Given a large sample of standard Aggietalk, we could count letter frequencies. Given a large sample of encoded Aggietalk, we could also count letter frequencies. We then just match the most frequent with the most frequent, and so on..
Example: I am given the standard text and I determine the following letter counts in it
a 1203 b 637 c 124 d 938 e 458 f 139 g 2351 h 830 i 283 j 923 k 269 l 574 m 1943 n 787 o 2233 p 372 q 1137 r 468 s 5634 t 3206 u 76 v 859 w 583 x 502 y 914 z 1471
I am given some encoded text and I determine the following letter counts:
a 57 b 43 c 77 d 38 e 143 f 743 g 258 h 34 i 66 j 98 k 26 l 84 m 164 n 76 o 94 p 53 q 99 r 32 s 246 t 39 u 85 v 49 w 27 x 71 y 52 z 46
Thus I infer that:
s is encoded as f t is encoded as g g is encoded as s o is encoded as m m is encoded as e z is encoded as q a is encoded as j q is encoded as o d is encoded as u j is encoded as l y is encoded as c v is encoded as n h is encoded as x n is encoded as i b is encoded as a w is encoded as p l is encoded as y x is encoded as v r is encoded as z e is encoded as b p is encoded as t i is encoded as d k is encoded as h f is encoded as r c is encoded as w u is encoded as k
Thus the encoded message:
mldjfonsppsmejbfdkakaider
decodes to:
ojiasqvgwwgomaesiububnimf
(which makes perfect sense in Aggietalk.)
Input: You will be given an arbitrary number of lines of standard Aggietalk text. All characters will be lowercase. The first blank space on a line indicates the end of characters of text. A line having a blank space in the very first position of a line indicates the end of the standard text.
Next will follow an arbitrary number of lines of encoded Aggietalk text. Again, all characters will be lowercase. The first blank space on a line indicates the end of characters of text. A line having a blank space in the very first position of a line indicates the end of the encode Aggietalk text.
Finally, you will be given an encoded Aggietalk message. This will be on a single line and be terminated by a blank space.
Output: Print out the translation into standard Aggietalk of the encoded message. Download Input Test Data Set 1
Download Output for Test Set 1
Download Input Test Data Set 2
Download Output for Test Set 2
Download Input Test Data Set 3
Download Output for Test Set 3
Input file: boxes.in
You will be given a description of a maze followed by some movements of a robot within the maze. You will determine if the movements can be made without crashing into the walls of the maze.
Description of the maze: Two dimensions HEIGHT and WIDTH will be given and we imagine that the maze is imposed onto a rectangular grid of HEIGHT boxes by WIDTH boxes. Then the barriers are specified in the form I J DIR, where 1 <= I <= HEIGHT, 1 <= J <= WIDTH, and DIR is either N, E, S, or W. The interpretation of this is that there is a barrier on the north, east, south, or west side, respectively, of box (I,J). (Consider box (1,1) is in the northwest corner and box (HEIGHT,WIDTH) is in the southeast corner.) There will be one triple of barrier descriptions per line and the lines of barrier descriptions will be terminated with the line "end of barriers".
Description of robot position and movements: Following the line reading "end of barriers", there will be a line containing a single pair I J satisfying 1 <= I <= HEIGHT and 1 <= J <= WIDTH. This is the initial position of the robot. Subsequent lines will have only one character, and that being either N, E, S, or W. The interpretation is that the robot is to move one box north, east, south, or west side, respectively. If a move is impossible either because the robot would have to cross a barrier or because the robot would run off an edge of the maze, that move is ignored and a message is printed "robot cannot move <DIR> from box <I,J>". If a move would not cross a barrier or move off the edge, a message is printed "robot moves to box <I,J>". The tracking stops when the message "end of instructions" is reached.
Sample:
Given the input
6 7 1 2 E 1 2 S 1 4 S 1 6 S 3 2 N 3 2 E 3 3 S 3 5 S 5 3 N 5 4 W 5 4 S 5 5 W 2 4 E end of barriers 2 3 S W E N E E S S end of instructions
the resulting maze is [picture]
and the output should be
robot moves to box 3, 3 robot cannot move W from box 3, 3 robot moves to box 3, 4 robot moves to box 2, 4 robot cannot move E from box 2, 4 robot cannot move E from box 2, 4 robot moves to box 3, 4 robot moves to box 4, 4Download Input Test Data Set 1
Download Output for Test Set 1
Download Input Test Data Set 2
Download Output for Test Set 2
Download Input Test Data Set 3
Download Output for Test Set 3
Download Input Test Data Set 4
Download Output for Test Set 4
Input file: relation.in
You will be given relations defined on sets of the form {1, 2, …, n} and you will determine if the relations have the properties of reflexivity, symmetry, and transitivity.
Recall that for
Reflexivity: for i = 1, …, n, i must be related to i.
Symmetry: for i = 1, …, n, and j = 1, …, n, if i is related to j then j must be related to i.
Transitivity: for i = 1, …, n, j = 1, …, n, and k = 1, …, n, if i is related to j and j is related to k, then i must be related to k.
Input: On the first line, you will be given the value of N, indicating that the set has elements (1, 2, …, N}.
On succeeding lines, until you encounter the line with "end of relation", you will have pairs of integers I J, indicating that I is related to J. There may follow additional descriptions of relations (each beginning with a line with N and followed by lines of I J pairs) until a line with "end of input" in encountered.
Output: For each relation, print out the line
this relation is (not) reflexive, (not) symmetric, and (not) transitive.
Where the not's are used if appropriate.
Example:
for the input:
3 1 1 2 2 1 3 3 3 end of relation 4 1 2 2 1 1 3 2 3 2 2 1 1 4 4 end of relation end of input
the output should be:
the relation is reflexive, not symmetric, and transitive the relation is not reflexive, not symmetric, and transitiveDownload Input Test Data Set
Download Output for Test Set
this problem was not used in the competition
Input file: sums.in
Given positive integer values N, you are to find all sets of distinct, positive integers that add to N. Precede each such group with the line "These sets add to <N>" and continue processing values of N until a line with "end of input" is encountered. The numbers in the set may be in any order and the sets themselves may be in any order; but remember: no number may appear in a set more than once.
Sample Input:
12 6 8 1 end of input
Associated output:
These sets add to 12 12 1 11 2 10 3 9 4 8 5 7 1 2 9 1 3 8 1 4 7 1 5 6 2 3 7 2 4 6 3 4 5 1 2 3 6 1 2 4 5 These sets add to 6 6 1 5 2 4 1 2 3 These sets add to 8 8 1 7 2 6 3 5 1 2 5 1 3 4 These sets add to 1 1