Computer Science Canada

My solutions

Author:  JSBN [ Tue Feb 25, 2003 11:01 am ]
Post subject:  My solutions

Ok, Many of you probably did the competition today. It was easy (for me) untill i hit the poetry question, which i did not finnish. here are my answers for the first 3 questions of the competition. I will try to put up what was required ASAP:

Question 1 (Trident)

code:
var t : int
var s : int
var h : int


put "Enter tine length:"
get t
put "Enter tine spacing:"
get s
put "Enter handle lenght:"
get h


for i1 : 1 .. t

    for i2 : 1 .. 3
        put "*" ..

        for i3 : 1 .. s
            put " " ..
        end for

    end for

    put ""

end for

if s = 0 then
else
    for i4 : 1 .. (5 + s * 2) - 2
        put "*" ..
    end for
    put ""
end if

for i5 : 1 .. h
    for i6 : 1 .. s + 1
        put " " ..
    end for
    put "*"
end for


Question 2 (Pictures)

code:
%LARGER AMOUNTS OF PICTURES WILL REQUIRE MORE TIME FOR CALCULATION
var C : int
var z : int
var t2 : int
var d1 : int
var d2 : int

loop

    put "Enter number of pictures"
    get C
    t2 := 65000
    exit when C = 0
    for i1 : 1 .. C
        for i2 : 1 .. C
            z := i1 * i2

            if z = C then
                if (i1 + i2) * 2 <= t2 then
                    t2 := (i1 + i2) * 2
                    d1 := i1
                    d2 := i2

                    exit
                end if
            end if
        end for
    end for
    put "Minimum Perimeter is ", t2, " with the dimensions ", d1, " X ", d2
    put ""
end loop


Question 3 (Snakes and Ladders)

code:

var sum : int
var loca : int := 1

loop
    put "Enter sum of dice:"
    get sum

    if sum = 0 then
        put "You Quit!"
        quit
    end if
    if loca + sum > 100 then
    else
        loca := loca + sum
    end if
    if loca = 9 then
        loca := 34
    elsif loca = 40 then
        loca := 64
    elsif loca = 67 then
        loca := 86
    elsif loca = 99 then
        loca := 77
    elsif loca = 90 then
        loca := 48
    elsif loca = 54 then
        loca := 19
    end if



    put "You are now on square ", loca
    exit when loca = 100
end loop
put "You Win!"

Author:  Tony [ Tue Feb 25, 2003 11:28 am ]
Post subject: 

nice, thats 3*15 = 45? Id say better then half the people.

I'll upload poetry, floorplan, subtrings when I get a comfirmation that they're correct. Unfortunatly I wasn't able to solve S5 - Trucks in the remaining 30 minutes and I'll be kicking myself... but mostly my teacher for the whole end of the year if that would cost me my stage 2 Evil or Very Mad

Right now my score suppost to be 60. Confused

Can someone post a solution to trucks problem?!

Author:  Asok [ Tue Feb 25, 2003 12:06 pm ]
Post subject: 

for amusement purposes take a look at my rediculously longer (still works) version of J2:
code:

var picnum : int
var x, y : real
var counter : int := 0
x := 10
y := 1
loop
    put "Enter number of pictures:"
    get picnum
    if picnum = 0 then
        exit
    end if
    counter := 0
    var total : array 1 .. picnum of real
    var integers : array 1 .. picnum of int
    var finished : array 1 .. picnum of real
    var perimeter : array 0 .. picnum of real
    var smallest : real := 999999
    for i : 1 .. picnum
        integers (i) := i
    end for
    for i : 1 .. picnum
        total (i) := picnum / i
        for k : 1 .. picnum
            if total (i) = integers (k) then
            counter := counter + 1
                finished (counter) := total (i)
            end if
        end for
    end for
    for l : 1 .. counter
        perimeter (l) := finished (l) * 2 + finished (counter - l+1) * 2
       if perimeter (l) < smallest then
             smallest := perimeter (l)
             x:= finished (l)
             y:= finished (counter - l+1)
        end if
    end for
    put "Minimum perimeter is ", smallest, " with dimensions ", y, " x ", x
    put " "
end loop


and JSBN, your J3 is incorrect, you're missing:
code:
if roll >=2 and roll <=12 then

that way the sum of 2 dice is between 2 and 12, on yours you can do like 32 which is impossible in the scenario.

Author:  Dan [ Tue Feb 25, 2003 1:36 pm ]
Post subject:  ccc

i got all of the question on j lvl done but 5, dam flooring!, i ran out of time Sad

i will post my awsers soon, i lefted my disk at school Laughing

Author:  Tony [ Tue Feb 25, 2003 2:40 pm ]
Post subject: 

ya, the floor one was tricki Wink

and as far as I can tell, this year is MUCH harder then last years.

Also, Asok... The problem didn't ask to verify the sum, so you assume the correct input. Maybe I'm playing with "special" dice? Very Happy

Author:  Asok [ Tue Feb 25, 2003 9:47 pm ]
Post subject: 

no the problem specifically said the roll was the sum of 2 dice from 2-12 I'll double check that today but I'm pretty sure of it. It makes more sence, also in the example they never used numbers above 12.

Author:  Tony [ Wed Feb 26, 2003 2:30 am ]
Post subject: 

exactly... the input is 2-12 or 0, you dont need to double check that, although I do see your consern for rolling 99 on first move and winning the game. But since the program is designed to help "visualize" the game on the larger screen, we're to assume the correct input.

I'm not saying you're wrong, its actually nice that you think of such details... but I'm just saying that program would work without that Wink

Author:  Delta [ Thu Mar 20, 2003 7:14 pm ]
Post subject:  ????????????????????????????????????

What Test is this and where can I recieve the questions so that I can answer them and test my skills. If someone could send me them I'd much appreciate it. Thnx. :D

Author:  Asok [ Fri Mar 21, 2003 11:56 am ]
Post subject: 

this is the Canadian Computing Competition, sadly their site hasn't been updated to post the questions however you can view the other questions from previous contests here: http://www.cmc.uwaterloo.ca/ccc/index.html

Author:  bugzpodder [ Sat May 24, 2003 10:42 am ]
Post subject: 

you dont mind truck problem in C++ right tony? i figured you still want to see it after 3 month Wink i dont want to touch turing before stage 2 next week. anwyazy i am working on the trucking thing right now.

Author:  bugzpodder [ Sat May 24, 2003 12:07 pm ]
Post subject: 

anywayz, here is my solution for truck. it worked for 3 test cases, so obvious there is a bug in it. this in theory works for me but i dont know why it doesnt work for test case 4 and 5. i spent about an hour debugging it. any one who can catch the error gets bits (i've never donated bits b4 but i suppose the donate bits function works?)

code:

#include<fstream>
using namespace std;
int C,R,D;
int city[1000][1000];  //city[i][j] - max weight from i to j
int maxw=100000;     // max weight the truck can carry

int min(int a,int b){  //minimum
    if (a<b) return a; else return b;
}

void flow(int dest){   //part of max flow algorithm
     int flow[1000];    //flow[i] the maximum weight from city 0 to city i
     bool visited[1000];  //if visited
     int maxflow,maxloc,i,xyzzy;  //maxflow-highest unused path
                                         // maxflow - the index of highest unused path
     for (i=0;i<C;i++){    //initialize
         flow[i]=0;
         visited[i]=false;
     }
     flow[0]=maxw;


     while (true){
           maxflow=0;
           maxloc=-1;

         for (i=0;i<C;i++){  //find the highest unused path
             if (flow[i]>maxflow && !visited[i]){
                maxflow=flow[i];
                maxloc=i;
             }
         }
         if (maxloc==dest || maxloc==-1) break;  //found, quit
         visited[maxloc]=true;  //visited
         for (i=0;i<C;i++)     
             if (city[maxloc][i]>0){  //update all its neighbours
                xyzzy=min(maxflow,city[maxloc][i]);
                if (flow[i]<xyzzy)
                   flow[i]=xyzzy;
             }
     }

     maxw=min(maxw,flow[dest]);  //find the maximum weight for dest city

}

int main(){
    ifstream fin("truck4.in");
    ofstream fout("truck.out");
    fin>>C>>R>>D;
    int t1,t2,d,i,j;

    //Input
    for (i=0;i<R;i++) {
        fin>>t1>>t2>>d;
        city[--t1][--t2]=d;
        city[t2][t1]=d;
    }

    for (i=0;i<D;i++) {fin>>t1;flow(--t1);}  //check all dest cities
    fout<<maxw<<endl;  //output

    fin.close();
    fout.close();
    return 0;
}

Author:  Asok [ Sat May 24, 2003 12:13 pm ]
Post subject: 

what are the 5 test cases so I can try to debug this.

Author:  bugzpodder [ Sat May 24, 2003 12:26 pm ]
Post subject: 

here is a *much much* faster version for the bigger test cases. instead of calculating flow seperately for each destination city, i do them all at once so in case of 1000 destination cities, i do not calculate things 1000 times repeatedly.

the test cases are attached. truck.in, truck.out are sample I/O. the rest are contest I/O. it fails on truck4 and truck5.

code:

#include<fstream>
using namespace std;
int C,R,D;
int city[1000][1000];
int dest[1000];
int maxw=100000;

int min(int a,int b){
    if (a<b) return a; else return b;
}

void flow(){   //part of max flow algorithm
     int flow[1000];
     bool visited[1000];
     int maxflow,maxloc,i,xyzzy;
     for (i=0;i<C;i++){
         flow[i]=0;
         visited[i]=false;
     }
     flow[0]=maxw;

     while (true){
           maxflow=0;
           maxloc=-1;

         for (i=0;i<C;i++){
             if (flow[i]>maxflow && !visited[i]){
                maxflow=flow[i];
                maxloc=i;
             }
         }
         if (maxloc==-1) break;
         visited[maxloc]=true;
         for (i=0;i<C;i++)
             if (city[maxloc][i]>0){
                xyzzy=min(maxflow,city[maxloc][i]);
                if (flow[i]<xyzzy)
                   flow[i]=xyzzy;
             }
     }
//     cout<<maxw<<endl;
     for (i=0;i<D;i++)
         maxw=min(maxw,flow[dest[i]]);

}

int main(){
    ifstream fin("truck.in");
    ofstream fout("truck.out");
    fin>>C>>R>>D;
    int t1,t2,d,i,j;

    //Input
    for (i=0;i<R;i++) {
        fin>>t1>>t2>>d;
        city[--t1][--t2]=d;
        city[t2][t1]=d;
    }
    for (i=0;i<D;i++) {fin>>dest[i];dest[i]--;}
    flow();
    fout<<maxw<<endl;
    cout<<maxw<<endl;
    fin.close();
    fout.close();
    return 0;
}

Author:  Tony [ Sat May 24, 2003 12:57 pm ]
Post subject: 

hey bugz. can you please put some comments into your program... I kind of get lost in there and dont quite understand the logic Sad

Author:  bugzpodder [ Sat May 24, 2003 1:23 pm ]
Post subject: 

my 2nd program is almost same as the first program. the comments are all there in the first program (i think i only changed 2-3 lines)

Author:  nate [ Sat May 24, 2003 1:49 pm ]
Post subject:  Heres my Answers

Here are my answers for the J2 and J3 questions I just want to know if they are right or almost right. They are pretty uneffeicent but I was wondering if they work and if I entered the contest what would my mark be for them? estamites are fine!

-Nate

Author:  JSBN [ Sat May 24, 2003 2:26 pm ]
Post subject: 

my answers are more efficient... (not as much code)
also for your picture one, try putting in 456 for yours, and mine. Persoinally i dont like to have to cut my pictures......

Author:  nate [ Sat May 24, 2003 3:30 pm ]
Post subject:  lol

lol i know i was trying to fix that but w.e

-nate


: