whos doing DWITE?

[Paul]

Still, he might be #1 for the CCC.

[zylum]

that set was relatively simple in my oppinion except for maybe bugzpodders problem.. P1 P2 and P5 were really easy. P4 could have easily been done using simple recursion or just some looping, and if you know the math P3 wouldnt have been that hard although it was the hardest problem in the set thanks to bugzpodder

[bugzpodder]

Paul, somebody's gotta take #1

thx zylum... but the math isnt that hard right? it is high school factoring, and i think everyone knows how to factor??

[Andy]

o rite bugz.. yea u need to take the derivitive to see if there are double roots... but i dont think u really need synthetic division... since the roots are integers

[bugzpodder]

the roots are rational numbers. synthetic division divides out the double roots (instead of using derivatives)
why didnt you participate?

[Andy]

calculus/algebra midterms on that same day.. during the contest

[thegoose]

Just wondering, who is doing the DWITE edition II on January 11th? (check the DWITE site for more details)

[bugzpodder]

Here is a set of problems richard sent me... you can anticipate these type of problems on the dwite...

[bugzpodder]

Problem 1: Cannon
Made by: Simon Parent

Sharktooth Pete has finished the construction of his awesome cannon. So, he walks to point (0,0) at the testing range, facing in the positive x-direction (X marks the spot, yarr!), and prepares to test his masterpiece. What he most wants to impress people with, however, is the accuracy of the cannon. Therefore, he wants to be able to mark the point where the cannonball will land (within one metre). To this end, he has commissioned you to write a program for him that will calculate where it will land given some initial conditions. He has gathered data on the shape of the terrain, in the form of a series of points.

Sharktooth Pete also remembers from his physics class that the x and y positions of the cannonball at time t will be:
xt = vtCos(θ)
yt = vtSin(θ) - 0.5gt²

Input: (cannon.in)
10 test cases, each case is as follows:
Line 1: v, the velocity in m/s, 0 <= V <= 100
Line 2: θ, the angle up from horizontal the cannon is aimed, 0 <= θ <= 90
Line 3: g, the constant of acceleration due to gravity in m/s², 0 <= g <= 100
Line 4: N, the number of points in the terrain curve, 2 <= N <= 10000
Line 5~N+4: he coordinates of the N points, -10000 <= X, Y <= 10000, two per line.

The terrain curve will be given in order from left to right and it will not double back on itself. That is, the X coordinates will be strictly increasing.
All numbers in the input file are integers.
Sharktooth Pete will always be standing on the terrain curve (pirates don't float well).

Output: (cannon.out)
You will output two numbers for each test case on one line: the coordinates that the cannonball lands at, rounded to the nearest integer.


Sample Input (1 test case):
20
30
10
2
0
0
50
5

Sample Output:
29 3

Test Case Sizes:
Test Case N
1 2
2 11
3 100
4 100
5 100
6 2
7 3
8 1000
9 1000
10 10 000


Problem 2: Goose Game
Made by: Richard Peng

Yes, you heard it right. The geese are smart enough to invent games (somebody got to stop teaching them math). They invented the game with the following rule and have challenged you to play it.
You are given two finite sequences of positive integers. The game consists of making consecutive moves. You are allowed to make the following move. You remove the last K1 numbers (K1≥1) from the first sequence (possibly the whole sequence) and find their sum S1 and the last K2 numbers (K2≥1) from the second sequence (again you can remove the whole sequence) and find their sum S2. Then you calculate the cost of the move to be (S1 - K1)*(S2 - K2). You continue to make moves until you remove all the numbers in both sequences. The total cost of the game is the sum of the costs of all moves. Your goal is to minimize this total cost. You are not allowed to leave one of the sequences empty, while the other is not.
The geese, however smart they maybe, are not able to realize that there exist an optimal way to play this game. However, you realize that it is easily solvable with the help of a computer, so you decide to write a program GAME, that computes the minimum total cost of the game.

Input: (game.in)
Input data is read from the file. Each test case consists of three lines.
Line 1: two space-separated integers, L1 and L2 (1 ≤ L1, L2 ≤ 2000), which denote the lengths of the two sequences.
Line 2: L1 space-separated integers, which are the elements of the first sequence. Line 3: L2 space-separated integers, which are the elements of the second sequence.
The elements of the sequences do not exceed 1000.

Output: (game.out)
Your program has to output one line per test case to the file contains only one number - the minimum total cost of the game as described above.

Sample Input (1 test case):
3 2
1 2 3
1 2

Sample Output:
2

Test Case Sizes:
Test Case L1 L2
1 20 20
2 110 80
3 200 130
4 400 80
5 1000 333
6 510 910
7 1200 1400
8 700 1800
9 1998 1370
10 2000 1999


Problem 3: Dummy Code
Made by: Aidin Kashigar

The Dummies are a group of genetically-modified human beings. Unlike us normal beings, they see everything as numbers. They live by numbers and they talk by numbers. So, one would not be surprised to see them communicate using a written sequence of numbers.

One of the Dummies, who happens to be an excellent programmer, has faced a programming challenge. He is a teacher of the language of the Dummies. This language, which clearly consists of a sequence of numbers, is more formally known as GieLle. The teacher is given three essays, written in GieLle and with lengths L1, L2, L3 <= 1000, and he has to find the longest increasing subsequence of number in the writing. Call it a plagiarism detection machine or just a plain old Dummies Problem.

You are to help this Dummy by outputting the length of the longest common increasing subsequence of numbers in the three essays.

Input: (dummy.in)
The input consist of 10 test cases with each two cases separated by a blank line, each case consist four lines:
Line 1: L1, L2, L3, the length of the three essays.
Line 2: L1 numbers that make up the 1st essay.
Line 3: L2 numbers that make up the 2nd essay.
Line 4: L3 numbers that make up the 3rd essay.
All numbers are guaranteed to fit in a signed 32-bit integer.
The values of L1, L2 and L3 for each test case are:

Output: (dummy.out)
For each test case, print one number on a line by itself. The length of the longest common increasing subsequence.

Sample Input (1 test case):
3 3 3
1 2 1
2 1 2
1 3 2

Sample Output:
2

Explanation:
The dummy sequence is 1,2.

Test Case Sizes:
Test Case L1 L2 L3
1 5 5 5
2 10 10 10
3 20 100 100
4 50 100 100
5 100 100 100
6 100 1000 1000
7 200 1000 1000
8 500 1000 1000
9 1000 1000 1000
10 1000 1000 1000


Problem 4: The Insane Geese
Made by: Richard Peng

The Geese have gone insane!!! They plan to dig a series of tunnels connecting the trees they live in. This way, they hope to be able to communicate and travel from any tree to any other tree without being above the ground. Since the geese lives in a populated area, any such construction would cause major disruption. As a result, the geese have asked you to find the construction plan which will cause the least disturbance (which means the total length must be kept the shortest possible). You are to write a program that reads 10 data sets, each containing a set of points. The program is to output the least possible total length which a network that connects all the points.

Input: (insane.in)
Each input contains 10 test cases with every two cases are separated by a blank line. Each case contains:
Line 1: one number, N, the number of locations (trees)
Line 2~N+1: 2N numbers, two per line, the coordinates of the locations of the trees on a Cartesian plane.
All coordinates are guaranteed to fit in a 16-bit signed integer.

Output: (insane.out)
The output consists of 10 lines, each containing the output to the respective case rounded to 2 decimal places. If less than 10 lines are outputted before the program was terminated, the lines that were outputted will be marked against the correct answer of case 1, 2, 3"¦ respectively.

Sample Input (2 test cases):
3
0 0
0 1
1 0

4
0 0
3 3
4 4
6 6

Sample Output:
2.00
9.90

Explanation:
Case 1: Connect the 1st point to the 2nd and 3rd.
Case 2: Connect the 2nd to the 1st, 3rd and 4th.

Test Case Sizes:
Test Case N
1 10
2 10
3 1 000
4 1 000
5 1 000
6 100 000
7 100 000
8 100 000
9 100 000
10 1 000 000