Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
whos doing DWITE?
Author Message
Paul

Posted: Sat Nov 27, 2004 12:39 am   Post subject: (No subject)

Still, he might be #1 for the CCC.

zylum

Posted: Sat Nov 27, 2004 3:27 pm   Post subject: (No subject)

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

Posted: Sat Nov 27, 2004 3:29 pm   Post subject: (No subject)

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

Posted: Sun Nov 28, 2004 2:26 pm   Post subject: (No subject)

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

Posted: Sun Nov 28, 2004 2:44 pm   Post subject: (No subject)

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

Posted: Sun Nov 28, 2004 3:04 pm   Post subject: (No subject)

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

Posted: Mon Jan 03, 2005 11:56 am   Post subject: (No subject)

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

Posted: Mon Jan 03, 2005 12:40 pm   Post subject: (No subject)

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

Problem Set2.doc
Description:
Filename:  Problem Set2.doc
Filesize:  70.5 KB

bugzpodder

Posted: Mon Jan 03, 2005 12:43 pm   Post subject: (No subject)

Problem 1: Cannon

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

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

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

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
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 5 of 5  [ 69 Posts ]
Goto page Previous  1, 2, 3, 4, 5
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: