Enclosed please find:
1) IOI/USACO Disk: This disk contains information and problems from all previous IOI competitions and all USACO competitions including the problems and a set of solutions to the 1994 qualifying round. Please distribute these disks to the contestants.
2) Local Coordinator Information Sheet: This document contains an explanation of all the steps that must be taken to conduct a local Competition Round. This round must be conducted on March 11, 12, or 14. Please read this document carefully.
2) White Envelopes: Each contestant is provided with his or her own white envelope which contains the problem(s) to be solved within a strict five hour time limit. All of the information necessary to solve the problem(s) is enclosed in that envelope. Keep this envelope secure until the day of the Competition Round. No one may open their envelope except the contestants and then only when the contest begins. Please follow this rule to the letter.
3) TEST DATA. Once the time limit is up, you should have each student run the TEST DATA that appears on the back of the Information Sheet. Please enter this information into an ASCII text file for the students to use. You may ask the student to do this for you after the competition is over if you wish. Please keep this TEST DATA confidential until that time.
Please fill out and return the Local Coordinator Information sheet along with all the contestants' work. Also check that all contestants fill out and include their Information Sheets with their solutions disk.
2) Schedule five hours for the contestants to write their program(s). If you have more than one contestant, all should write their programs during the same 5-hour period. It is important to keep the problems confidential.
3) Provide each contestant with a blank, formatted 3.5" disk (IBM or MAC) on which to store and submit their program(s). Please have them write: Competition Round 1994, Name, Address, City, State, Zip, Ph #, and disk type ( IBM or MAC) on the disk. No disks, other than the blank, formatted disk, are allowed in the area during the competition. No outside materials, printed or electronic may be used during the contest. If a student has questions about a programming or system command, you may provide this information personally or provide a reference book to answer these questions. Of course students may use paper and pencil to work out their ideas.
4) The sealed envelope provided for each contestant contains the problems to be solved. Keep them confidential until the day of the competition. Distribute the envelopes at the moment the contest begins.
5) After five hours, ask each contestant to stop programming and to turn in their disk to you. Working with one contestant at a time, have each student run the program using the inputs from: a) SAMPLE RUNS that was given to them. Also, have each contestant run the b) TEST DATA found at the end of the problems. You can enter this test data in the proper disk format ahead of time or wait for assistance by the contestant. Please try to work with the student so problems of reading the input data are eliminated. ( You may use adult helpers if you have many students to process.)
6) Have each contestant provide a printed copy of the program(s) and the results of all the runs a, b.
7) Have each contestant provide a (one page max) printed explanation of the solution(s) in English/outline form. This may be written after the 5 hour time limit. Each problem should have an English algorithm associated with it.
8) Submit on a disk the contestant's program(s) (FENCE.***, ARITH.*** where *** = PAS, C or BAS) in an ASCII text file along with a copy of the English/outline algorithm (FENCE.ALG, ARITH.ALG) that was written after the five-hour limit. Be sure to print the name, address, city, state, zip and disk type (IBM or MAC) on the label of each disk.
9) Place each contestant's work in an envelope with his or her name, address, city, state, zip printed on the outside. Also include the Contestant Information Sheet. Mail all the envelopes together. Include the Local Coordinator Information Sheet. We must receive your entries no later than Monday, March 21, 1994. The top 12-16 contestants will be announced on Monday, April 4, 1994.
* x3 y3
x5 y5 / \
x y * * / \
/ \ / \
/ * \
x6 y6* x4 y4 \
| \
| \
x1 y1*----------------* x2 y2
Write a program which will do the following:a) Test an array of vertices {xi yi }, i = 1,....N to see if the array is a valid fence. A valid fence is one that has no intersections.
b) Suppose a person (with no height) is standing in the plane at position (x y) and looks at the fence. What sides can the person see? The program must identify all sides of the fence that are visible or partially visible from (x y). This means there exists a ray from (x y) to the side which does not intersect any other side of the fence. A side that is parallel to the line of sight is not considered visible. In the figure above the segments x3 y3 x4 y4 and x5 y5 x6 y6 x1 y1 consisting of two sides are visible or partially visible from x y. If only part of a side is visible, the entire side should be listed in the visible segment. Do not list just the visible portion.
Input file: FENCE.DAT
Each data set in FENCE.DAT consists of:
a) N (the number of corners in the fence, N<=30)
b) A sequence of corners consisting of two integers (each with absolute value <100) separated by a space and every two adjacent corners also separated by a space. The corners are given in counter-clockwise order. The sequence can continue on a new line if necessary.
c) A position x y for the person observing the fence.
Output file: FENCE.SOL file .
The data set in FENCE.SOL consists of:
a) M (the number of visible sides).
b) A listing of each fence segment (one or more sides that are connected) with one segment per line.
or
a) The message "NO FENCE" if the sequence given in the FENCE.DAT is not a valid fence.
Different data sets will be separated by an empty record (that is, a line containing only the end of the line character.
Sample Run
Input
FENCE.DAT 4 0 0 2 0 1 1 0 1 2 2 4 0 0 2 0 1 1 1 -1 3 0 5 0 0 2 0 2 2 1 1 0 2 4 3 13 0 0 7 0 5 2 7 5 5 7 3 5 4 9 1 8 2 5 0 9 -2 7 0 3 -3 1 5 5 13 0 0 7 0 5 2 7 5 5 7 3 5 4 9 1 8 2 5 0 9 -2 7 0 3 -3 1 5 10 16 0 0 2 0 2 1 3 1 4 0 4 2 3 2 3 3 4 4 2 4 2 3 1 3 0 4 0 2 1 2 1 1 2 2Output
FENCE.SOL 2 2 0 1 1 0 1 NO FENCE 2 2 0 2 2 1 1 0 2 7 -2 7 0 3 -3 1 0 0 7 0 5 2 7 5 5 7 3 5 5 7 5 5 7 3 5 4 9 1 8 2 5 0 9 8 0 0 2 0 2 1 3 1 4 0 4 2 3 2 3 3 4 4 2 4 2 3 1 3 0 4 0 2 1 2 1 1
Write a program that finds all arithmetic progressions of length n in the set S of bisquares. The set of bisquares is defined as the set of all integers of the form p^2 + q^2 (where p and q are non-negative integers). As input, your program should accept the length of progressions N to search for and an upper bound M to limit the search to the bisquares in the range from 0 to M. Each line of the input file ARITH.DAT contains N M. Assume M <=10,000.
Sample Run
ARITH.DAT 8 200 10 100 ARITH.SOL Arithmetic progressions of length 8 taken from bisquares within the range from 0 to 200: Difference of 12: 1 13 25 37 49 61 73 85 13 25 37 49 61 73 85 97 25 37 49 61 73 85 97 109 37 49 61 73 85 97 109 121 Difference of 24: 1 25 49 73 97 121 145 169 2 26 50 74 98 122 146 170 25 49 73 97 121 145 169 193 26 50 74 98 122 146 170 194 There are 8 progressions. Arithmetic progressions of length 10 taken from bisquares within the range from 0 to 1000: Difference of 12: 1 13 25 37 49 61 73 85 97 109 13 25 37 49 61 73 85 97 109 121 Difference of 24: 2 26 50 74 98 122 146 170 194 218 26 50 74 98 122 146 170 194 218 242 101 125 149 173 197 221 245 269 293 317 761 785 809 833 857 881 905 929 953 977 Difference of 36: 421 457 493 529 565 601 637 673 709 745 Difference of 48: 4 52 100 148 196 244 292 340 388 436 52 100 148 196 244 292 340 388 436 484 202 250 298 346 394 442 490 538 586 634 Difference of 60: 5 65 125 185 245 305 365 425 485 545 65 125 185 245 305 365 425 485 545 605 Difference of 72: 29 101 173 245 317 389 461 533 605 677 Difference of 84: 29 113 197 281 365 449 533 617 701 785 37 121 205 289 373 457 541 625 709 793 73 157 241 325 409 493 577 661 745 829 121 205 289 373 457 541 625 709 793 877 205 289 373 457 541 625 709 793 877 961 Difference of 96: 8 104 200 296 392 488 584 680 776 872 104 200 296 392 488 584 680 776 872 968 Difference of 108: 9 117 225 333 441 549 657 765 873 981 There are 21 progressions. TEST DATA FENCE.DAT 27 2 3 3 3 4 4 4 5 3 6 2 6 1 5 0 4 0 3 0 2 1 1 2 1 3 0 4 1 5 0 6 1 7 0 8 1 7 2 7 3 6 3 6 4 5 4 5 2 4 2 3 2 2 2 7 1 27 2 3 3 3 4 4 4 5 3 6 2 6 1 5 0 4 0 3 0 2 1 1 2 1 3 0 4 1 5 0 6 1 7 0 8 1 7 2 7 3 6 3 6 4 5 4 5 2 4 2 4 0 3 2 7 1 ARITH.DAT 7 100 12 1000 22 100000