Almost Daily Contest #2
Now that I know what to expect, let's get on with it. Expect a less chaotic contest this time.
Submission Rules: Please send submissions by email to [email protected] so that I can accurately judge who sent what before whom. It would be most helpful if the entries were in plain text format so that I can easily cut and paste, and named appropriately including the adc you're submitting for, your name and the difficulty level (ex. adc2_prelude_advanced.txt).
Beginner:
Most numbers have an interesting trait. If you continually reverse the number and add the result to the original number, you'll have a palindromic number. A palindromic number is a number whose digits are the same both forward and backward, for example, 2002, 121, and any single digit number.
Your mission, should you choose to accept it, is to write a function in C or C++:
int palNum(int n);
that returns the first palindromic number with n as the original. This function should be able to correctly print the first 50 values of n. For example:
for (int i = 0; i <= 20; i++)
cout<< palNum(i) <<endl;
This should print
0
1
2
3
4
5
6
7
8
9
11
11
33
44
55
66
77
88
99
121
22
Intermediate:
Create a type that works in both C and C++ (no classes, sorry). This type will be called Integer, and has the following interface:
Integer a = makeInteger("12345");
Integer b = makeInteger("54321");
printf("%s\n", toString(addInteger(a, b)));
printf("%s\n", toString(subInteger(a, b)));
Your task is to create an integer type of arbitrary length and implement addition and subtraction. The internal workings of Integer are irrelevant as long as the interface is as above. All of the functions in the interface must run in a reasonable amount of time for very large numbers. Integer must be able to handle negative numbers as well as positive numbers and all combinations of the two.
Speed and elegance are of primary importance, though you will be graded on correctness and portability.
Advanced:
Your task is the same as for the Intermediate task with two (quite major) differences. You advanced people must implement multiplication and division that runs in a reasonable amount of time. The interface is the same except addInteger and subInteger become mulInteger and divInteger:
printf("%s\n", toString(mulInteger(a, b)));
printf("%s\n", toString(divInteger(a, b)));
Speed is very important.
Contest End: Saturday, August 9, 2003
Notes:
For the Intermediate and Advanced tasks, entries will be tested against each other. The fastest implementation with correct answers will probably be the winner, but exceptionally elegant solutions may take the prize.
In the Beginner task, speed isn't a primary concern, though the function shouldn't take an exceptionally long time to print the first 50 palindromic numbers. Keep in mind past contests when working up an implementation for this problem.
Test ideas:
In order to improve the contests so that everyone may participate and have fun, I'll try new things as we move along. This time I'm going to see if I can't even the playing field for the beginner task. If you've submitted an entry to the advanced task and the beginner task, you will automatically be docked 3 points for every category in the beginner task. If you've submitted an entry to the intermediate and beginner tasks, you will be automatically docked 1 point for every category in the beginner task. This is just a test, depending on how things go I may decide to change the amount of points removed or eliminate the rule completely during the course of this contest.
If you have comments, questions or suggestions, please PM me so that we can work to improve the ADC.
