Βγήκε on-line το επίσημο ελληνικό site για το imagine cup. Η διεύθυνση είναι
http://www.imaginecup.gr. Αλήθεια... έχει δηλώσει κανείς από εσάς συμμετοχή?
Για να πάρετε μια ιδέα σχετικά με την κατηγορία αλγορίθμων του διαγωνισμού σας παραθέτω ένα πρόβλημα που κλήθηκαν να λύσουν οι περσυνοί διαγωνιζόμενοι. Μπορείτε να δείτε και άλλα προβλήματα
εδώ.
Question 1: Origami
The Computomatons were extremely adept at the art of folding paper. In fact, it is theorized that the true origins of the Japanese art of origami are rooted in the Computomatons. This puzzle involves understanding the art of folding paper. In this puzzle, we will always fold paper in the same direction.
There are two kind of foldings:
- those which look like a valley (V)
- those which look like a mountain (^)
On this picture, from left to right, you have two valleys, one mountain, two valleys and two mountains. In the problem, we use U for valleys and D for mountains. So this paper folding can be encoded as UUDUUDD (it is implied when using that description that the distance between two foldings is always the same).
Given a paper that has been folded and unfolded, your job is to find the easiest way (the way that requires as few foldings as possible) to fold this paper.
Input: the sequence of foldings: U for mountain, D valley
Output: a list of position of where to completely fold the paper
Each folding is done by moving the right part of the paper on top of the left part
Example:
UUDUUDD => 3,1,0
Let see why 3, 1, 0 is a good answer:
The foldings are numbered from left to right, starting with 0. Now let’s fold in position 3. When folding, the larger part (or the left part if both part are the same size) will stay still. Since position 3 is right in the middle, the left part will not move and the right part will be moved on top of the left part.
Folding in 1 will give this
And we just have to fold in 0 to complete the folding.
Another example:
DUDUUDD => 0,2,1,0
Note that when folding pos 0 in first step, the left part goes beneath the right part because it is smaller.
Interface:
You will have to provide to the judges an assembly that contains a class that implements the interface you'll find in the client.dll.
It consists of a single function with the following signature:
int[] Fold(bool[] foldings);
foldings parameter is an array of boolean.
A folding is true if it's a mountain folding (D in our example) and false if it's a valley folding (U in our example)
The function must return the array of positions where to fold in order to get a single rectangle form.
Tester syntax:
You can test your solution by executing tester.exe [solution] (where solution is the name of the dll file you created).
This will test your solution on 20 different foldings and output for each test if it passed or failed.
