Ccc 2007!

[StixandRox]

For S5 (others too easy in my opinion, although 3 was rough) is the width always odd? If not I guess I would just place it in between the pins and knock over two on each side...yeah that would work. It doesn't specify so I thought Id ask your opinions =/

[zylum]

can anyone post the problems for the senior?

[StixandRox]

Anyone have some solutions in Turing or C++ for s3 or s2 (Yeah s2 was too easy thats why I want to see anothers XD). Ill post mine if someone posts theres first (incase mine sux I can upgrade ;p). s3 is the only one I think is wrong though....not good at linking (s4 was easier linking though)

[zylum]

klopyrev, for your s5, i get a stack overflow for n > 8000, k = w = 1... dp would be better in this case.

[PaulButler]

StixandRox @ Tue Feb 27, 2007 11:29 pm wrote:

For S5 (others too easy in my opinion, although 3 was rough) is the width always odd? If not I guess I would just place it in between the pins and knock over two on each side...yeah that would work. It doesn't specify so I thought Id ask your opinions =/

Why start from the center? Just go pin-by-pin and knock over the [width] number of pins following that pin. You don't have to worry about zeros at the end of the pins, just stop [pins - width] from the end.

[StixandRox]

PaulButler @ Wed Feb 28, 2007 6:51 am wrote:

StixandRox @ Tue Feb 27, 2007 11:29 pm wrote:

For S5 (others too easy in my opinion, although 3 was rough) is the width always odd? If not I guess I would just place it in between the pins and knock over two on each side...yeah that would work. It doesn't specify so I thought Id ask your opinions =/

Why start from the center? Just go pin-by-pin and knock over the [width] number of pins following that pin. You don't have to worry about zeros at the end of the pins, just stop [pins - width] from the end.

Wow I always do stuff like that, thanks makes better sense ^^;

[klopyrev]

zylum wrote:

klopyrev, for your s5, i get a stack overflow for n > 8000, k = w = 1... dp would be better in this case.

I posted another solution later that doesn't have this problem. That one uses dp.

KL

[Clayton]

Enjoy
NOTE: All input comes from a file "sX.in" where X is the problem number and output is either to the screen, or a file "sX.out". Also, S4 and S5 must be finished running in <= 1 minute on a P4 machine at 3.6GHz. Good luck

S1: Federal Voting Age

Problem Description:
For the big election on Feb. 27 2007, the government has commissioned an electronic voting system, and you have been hired as a sub-contractor for this very grand programming project.

Your task is to write the system that determines whether a given person is old enough to vote. The voting age is 18, so given someone's birthday, you must determine whether that person will be 18 years of age on the day of the election.

Input Specification:
The input will consist of a number n (1 <= n <= 100) on a single line, indicating the number of birthdays to evaluate. Then, each following n lines, will be of the form y m d, where y is the year of a potential voter's birth (0 <= y <= 2007), m (1 <= m <= 12) is the month of birth, and d (1 <= d <= 31) is the day. It is assured that each birthday is a correct and valid date.

Output Specification:
For each date in the input, output a line with either "Yes" if the voter is eligible to vote, or "No" otherwise.

Sample Input:
5
1933 10 29
1989 2 28
1961 11 23
1999 12 31
1989 2 27

Output for Sample Input:
Yes
No
Yes
No
Yes


S2: Boxes

Problem Description:
Nowadays, almost any item can be bought and sold on the internet. The problem is shipping. Before an item can be sent, it must be carefully packaged in a cardboard box to protect it.

While items come in many shapes and sizes, finding a box just the right size can be a problem. If the box is too small, the item will not fit. If the box is unnecessarily big, shipping cost will be higher, and the item is more likely to move around inside the box, and it may break.

Cardboard box manufacturers offer a fixed set of standard box sizes. Your task is to find the standard box size with the smallest volume into which an item will fit.

Each box is a rectangular prism with a given length, width, and height. Each item is also a rectangular prism with a given length, width, and height. An item may be rotated by multiples of 90 degrees in any direction before being packed into a box, but when it is packed, its faces must be parallel to the faces of the box. An item will fit into a box as long as its dimensions are equal to or less than the dimensions of the box.

Input Specification:
The first line of input will contain a single integer n, 0 < n < 1000, the number of different sizes of boxes available. The next n lines will contain a single integer m, 0 < m < 1000, the number of items to be packaged. The next m lines will contain three integers each, giving the length, width, and height of an item. All dimensions will be in millimeters and in the range from 1 mm to 2000 mm.

Output Specification:
Output is to consist of m lines, one for each item in the input. For each item, output a line containing a single integer, the volume (in mm^3) of the smallest box into which the item will fit. The same size of box may be reused for any number of items. If an item does not fit in any box, print the line: "Item does not fit."

Sample Input:
3
1 2 3
2 3 4
3 4 5
5
1 1 1
2 2 2
4 3 2
4 3 3
4 4 4

Sample Output:
6
24
24
60
Item does not fit.


S3: Friends

Problem Description:
In a certain school, it has been decided that the students are spending too much time studying and not enough time socializing. To address this situation, it has been decided to give every student a friend. Friendship is one-way. That is, if Janet is assigned to be Sarah's friend, Janet must be friendly to Sarah, but Sarah is not required to reciprocate.

The assignment of friends is done by computer using student numbers. Every student is assigned exactly one friend. Sometimes, a 'circle of friends' occurs. For example, if Marc is assigned Fred, Fred is assigned Lori, Lori is assigned Jean, and Jean assigned Marc, we have a circle of 4 friends containing Marc, Fred, Lori, and Jean. In the circle, we can say that Marc has a separation of 0 from Fred, of 1 from Lori, of 2 from Jean, and of 3 from Marc.

Your task is to identify, given the computer assignment of friends, whether the two students are in the same circle of friends, and if so, determine their separation.

Input Specification:
Input begins with a single integer n (2 <= n <= 9999), on a line by itself, indicating the number of students in the class. The next n lines contain the computer assignment of friendship. An assignment is the form x y (where 1 <= x <= n, 1 <= y <= n, x != y). For example, 1234 8765 is a possible friendship assignment indicating that student 1234 must be friends with student 8765.

Following friendship assignments, there are a series of lines containing two student numbers, separated by a single whitespace. These lines represent the pairs of students that you will determine if they are in the same circle of friends and, if so, their separation. The last line of input can be identified by the use of the 0 0 as the friend assignment.

Output Specification:
For each case, you are to print, on a seperate line, either "Yes" or "No" depending on whether they are in the same circle of friends. If the answer is "Yes", follow the output "Yes" with a single whitespace and then an integer indicating the friend's seperation.

Sample Input:
6
1 2
2 3
3 1
10 11
100 10
11 100
1 100
2 3
0 0

Output for Sample Input:
No
Yes 0


S4: Waterpark (timed)

Problem Description:
The local waterpark has a great slide complex, with many paths crisscrossing down the hill. There is one start point and one end point, but at various points one can turn and take different paths. Walter and Wanda are wondering exactly how many different ways there are to go down the slide. Can you solve their problem?

More precisely, there are n marked points (including the start at 1 and the end at n) where the paths down the hill may split or merge. All the paths move down the hill to higher numbered positions; some paths will actually cross over without meeting, but we don't have to worry about that. We won't worry about the collisions between sliders that can happen either. Out problem is simply to determine the number of different sequences of marked points we can follow down the hill.

For example, at one small waterpark, there are 4 points with direct slides from 1 to points 2 and 4; from 2 to 3 and 4; and from 3 to 4. There are 3 ways down the hill. You can check this by seeing that we can go (1, 2, 3, 4), (1, 2, 4) or (1, 4).

(Here is a hint: think about starting at the bottom of the slide.)

Input Specification:
Input begins with a single integer n (1 <= n <= 9999), on a line by itself, indicating the number of marked points. The next n lines contain point pairs of the form x y where 1 <= x < y <= n. For example, 1234 8765 indicates a direct slide from point 1234 to point 8765. The last line of input will be indicated by the point pair 0 0.

Output Specification:
The output is an integer, which is the number of different paths from piont 1 to point n. you can assume that the number of paths will be less than 2 ^ 30. It is possible that there is no path from point 1 to n, in which case the number of paths is 0.

Sample Input:
4
1 2
1 4
2 3
2 4
3 4
0 0

Output for Sample Input:
3


S5: Bowling for Numbers (timed)

Problem Description:
At the Canadian Carnival Competition (CCC), a popular game is Bowling for Numbers. A large number of bowling pins are lined up in a row. Each bowling pin has a number printed on it, which is the score obtained from knocking over that pin. The player is given a number of bowling balls; each bowling ball is wide enough to knock over a few consecutive and adjacent pins.

For example, one possible sequence of pins is: 2 8 5 1 9 6 9 3 2

If Alice was given two balls, each able to knock over three adjacent pins, the maximum score Alice could achieve would e 39, the sum of two throws: 2 + 8 + 5 = 15 and 9 + 6 + 9 = 24.

Bob has a strategy where he picks the shot that gives him the most score, then repeatedly picks the shot that gives him the most score from the remaining pins. This strategy doesn't always yield the maximum score, but it is close. On the test data, such a strategy would get a score of 20%

Input Specification:
Input consists of a series of test cases. The first line of input is t 1 <= t <= 10, indicating the number of test cases in the file. The first line of each test case contains three integers n k w. First is the integer n, 1 <= n <= 30000, indicating the number of bowling pins. The second integer k, 1 <= k <= 500, giving the number of balls available to each player. The third and final integer is w, 1 <= w <= n, the width of the bowling ball (the number of adjacent pins it can knock over.) The next n lines of each test case each contain a single non-negative integer less than 10000, giving the score of the pins, in order. 20% of the test data will have size n <= 50

Output Specification:
For each test case, output the maximum achievable score by the player. This score is guaranteed to be less than one billion.

Sample Input:
1
9 2 3
2
8
5
1
9
6
9
3
2

Output for Sample Input:
39

[haskell]

I honestly don't see why it surprises that someone finished all 5 of these problems... They are very simple, and very similar to the types of problems at USACO. If you practiced there, you'd probably make a time record or something. Or at the very least, have these types of problems down.

But then again, I'm guessing this is for Highschool students? Or am I mistaken?

Anyways, those problems combined with USACO's could be a good training for the next competition.

[Clayton]

Yes, this is highschool students....

[Flikerator]

I finished s1, s2, and s4 in roughly 35 minutes and finished 5 at the 1:10 mark...3 took me until the 2:20 mark to finish. I just kept making so many errors. I found 3 the hardest, 5 was pretty simple.

They all work for the test data, but I managed to fumble 3 if a ring of friends has only 1 person (2 or more is fine). The way I did it was putting people in a ring of friends and then determining if each set was in any of the rings of friends. The way I did it made an error for any circle with 1 friend, I was in the middle of fixing and time ran out so Im finger crossed on that one.

5 will only work for some test data. I wanted it to work from all cases in under a minute (efficient) so I did it recursivly in a way that would never repeat the same step; which it wont, but it will only go so far down the pins (Its efficient it just won't always work. The best case would have to be in a certain range). For instance, with a width of 3 and 2 balls it would go until 10. Luckily the pins were 9 so its alright. However if the pins were 15 and the highest set was somewhere past 10 then it wouldn't work. The more balls / distance the better the chances I got it right.

1, 2, and 4 were too simple in my opinion. Although 4 looked like it was going to be tough.

[PaulButler]

Flikerator @ Wed Feb 28, 2007 3:47 pm wrote:

They all work for the test data, but I managed to fumble 3 if a ring of friends has only 1 person (2 or more is fine). The way I did it was putting people in a ring of friends and then determining if each set was in any of the rings of friends. The way I did it made an error for any circle with 1 friend, I was in the middle of fixing and time ran out so Im finger crossed on that one.

A ring of friends should never only have one person. "A [friend] assignment is of the form x y (where [...] x [is not equal to] y)" therefor a circle of one friend can't exist.

[Flikerator]

PaulButler @ Wed Feb 28, 2007 5:17 pm wrote:

Flikerator @ Wed Feb 28, 2007 3:47 pm wrote:

They all work for the data, but I managed to fumble 3 if a ring of friends has only 1 person (2 or more is fine). The way I did it was putting people in a ring of friends and then determining if each set was in any of the rings of friends. The way I did it made an error for any circle with 1 friend, I was in the middle of fixing and time ran out so Im finger crossed on that one.

A ring of friends should never only have one person. "A [friend] assignment is of the form x y (where [...] x [is not equal to] y)" therefor a circle of one friend can't exist.

Correction sorry, I mean a ring with only two people. When I found two people not in a ring I assigned them and looked for a match. For isntance if 2 3 havn't been placed in a circle then;

I would place them in a ring (if Im starting a new one) and then search for a new person (starting with 3). If I found one I would add that person to ring. So I found 3 6 then 6 would be added to the ring {2, 3, 6} and I would look for another starting in 6.

Anything with {n1, n2} crashed and I ran out of time before I could fix it (Small tiny error). Would be nice if I got full marks, but the competition was fun either way.

[Anon]

hey, I just got my results from the CCC senior, and it turn out that there seems to be some extra whitespace in many of the input files.
I was using the java BufferedReader to read the input line by line (I was using java 1.4, so I didnt have access to the scanner class)

I was just wondering, did anyone else have this problem?

This read error cuts my score by 30 points, but if the excess whitespace is removed, most of my programs run just fine. Is it too late to do anything about this?

thanks

[MihaiG]

ya, i brute forced s5 then


then i hear that one of the sample input was like 600kb file...and i was like ...oh f*ck


but i only did s1 and s5

i had 20 mins lef tos i did j1,j2,j3

meh