----------------------------------- bugzpodder Thu May 22, 2003 5:15 pm [contest]CCC type contest ----------------------------------- seeing that a lot of people are interested in the CCC type contest, i thought i might as well post a question and see how it goes. post your source code here. btw run-time counts. i aint want to wait 30 hours for your program to finish (you'll see why). i'll be the judge and i'll tell you if your correct or not. mods will probably give you bits for this but I'll have to talk to them first. btw these are ranked as "hard". they are not that hard though. your goal is to create a reasonable program that does the following. the run-time should be reasonable for *all* test cases. lets say 30 seconds tops. Number Triangles Consider the number triangle shown below. Write a program that calculates the highest sum of numbers that can be passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right. 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 In the sample above, the route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30. PROGRAM NAME: numtri INPUT FORMAT The first line contains R (1 time limit-># of submission->submission date ----------------------------------- Martin Sat May 24, 2003 12:23 pm ----------------------------------- I'm doing it dynamically now...(I finally think I'm beginning to understand) Right now I'm leaving to play D&D, but I'll post it later. ----------------------------------- Homer_simpson Mon May 26, 2003 8:01 pm ----------------------------------- could u explain a lil more about what we're suppose to do with that triangle? ----------------------------------- Martin Wed May 28, 2003 10:10 pm ----------------------------------- Alright, I haven't gotten the problem dynamically, but here's my recursive solution. Feel free to mess around with this. var f : int open : f, "numtri.in", get var n : int get : f, n var tri : array 1 .. n + 1, 1 .. n + 1 of int for i : 1 .. n + 1 for j : 1 .. n + 1 tri (i, j) := -1 end for end for var c : int := 1 for i : 1 .. n for j : 1 .. c get : f, tri (i, j) end for c += 1 end for var highest : int := -1 proc Sum (r, c : int, sum : int) if r not= n + 1 then put r, " ", c Sum (r + 1, c, sum + tri (r, c)) if tri (r + 1, c + 1) not= -1 then Sum (r + 1, c + 1, sum + tri (r, c)) end if else highest := max (sum, highest) end if end Sum Sum (1, 1, 0) close : f open : f, "numtri.out", put put : f, highest close : f This works perfectly, tis just sloooooowwwwww...... ----------------------------------- Homer_simpson Wed May 28, 2003 10:15 pm ----------------------------------- what does ccc stand for anyway? ----------------------------------- Tony Wed May 28, 2003 10:18 pm ----------------------------------- look in above threads... Canadian Ccomputer Ccompetition ----------------------------------- Martin Wed May 28, 2003 10:23 pm ----------------------------------- Actually I think it's Computing not Computer, but not 100% sure on that one. ----------------------------------- Tony Wed May 28, 2003 10:33 pm ----------------------------------- ether way, the point is the same... some dumb contest we write to show off our programming skillz. ----------------------------------- bugzpodder Sun Jun 01, 2003 9:08 am ----------------------------------- on that note, I got silver in stage 2 :S ----------------------------------- Tony Sun Jun 01, 2003 7:25 pm ----------------------------------- is stage two already over? ----------------------------------- Martin Sun Jun 01, 2003 8:57 pm ----------------------------------- Silver, eh? Well, I guess that means that you're not programming enough. I'm going to have to ban you from the site so that you can get back to developing your not so mad skillz. Heh, just kidding. Gratz Jack...there's always next year (remember, you've gotta beat the euclid too...although next year I plan on being a much better programmer. After I hand in my final project, I swear I'm not going to touch turing for the rest of my life.) ----------------------------------- bugzpodder Sun Jun 01, 2003 9:17 pm ----------------------------------- stage 2 was this weekend they got lucky ;) i'll kick their ass next year, or else i am not Jackie Ralph got silver also. :S ----------------------------------- Martin Sun Jun 01, 2003 9:33 pm ----------------------------------- Huh? How many silver medals were there? And who won? ----------------------------------- bugzpodder Mon Jun 02, 2003 7:37 am ----------------------------------- more than one ;) silver does sound like you are second but oh well. top 4 gets gold and top 12 gets silver. i could be 5th or 12th for all i know. ----------------------------------- bugzpodder Mon Jun 02, 2003 5:22 pm ----------------------------------- anywayz i've made my program (Actually i was lazy and i just modified martin's program for a couple of lines (and made a shorter and *much* faster)) and run time: 6.in 1.083 seconds 7.in 2.704 seconds 8.in 0.551 seconds 7 is the largest which has N=349 ----------------------------------- Catalyst Thu Jun 05, 2003 10:56 pm ----------------------------------- can you send me those files so i can try my prog? ----------------------------------- rizzix Fri Jun 06, 2003 10:44 pm ----------------------------------- you guys so interested in contests, try TopCoders.com. You can even take part in sponsored contests (i u are of legal age), and win cash! but mid u these guys are GOOD! we are nothing compared to them LOL ----------------------------------- bugzpodder Fri Jun 06, 2003 11:02 pm ----------------------------------- whats ur rating/user name there? my friend has a rating of 2148 after just 3 contests. i am on my 16 contest and my rating is still barely above 1200