Date: 12 July 2010, Contest Problems: A-D, click here , Time: 100 minutes
Final scoreboard of the practice session is here.
Solved by 3 teams First team solvers: Kikkok –
Computer Engineering PSU Hatyai at 18 minutes
Problem explanation
The input integers must be read as string since they may contain
up to 100 digits and the integer data types (int,long int,long
long) cannot handle
such huge numbers. For each group of input integers, first test the
11-divisibility by applying the provided algorithm and then select the max
number.
Example solution program
C source code from Dr.Anant
Choksuriwong (Dept. of Computer Engineering, PSU Hatyai )
: AelevenDiv.c
Test Cases
|
Input |
Output |
|
g=7(7
groups), 31 lines (file Ainput.txt size 517 bytes) |
7 lines |
|
7 9 35
202 1180 132 222 1025 8415
9250 8990 10 1235
132 126 8419 3201 2310 4752 1321 35900 990 10 1235
132 126 8419400000000000000000000000000000 3201 2310 4752 1321 35900 990 6 . . . |
8415 4752 8419400000000000000000000000000000 23302253336563333569781435362320126 552211334455668877994421123300 1320 11 |
Solved by 6 teams First team solvers: Marwin –
Computer Engineering PSU Hatyai at 38 minutes
Problem explanation
For each polygon, read coordinates X, Y
into arrays and then calculate the area following the provided algorithm (the summation
formula).
Example solution program
C source code :
BpolygonArea.c
Test Cases
|
Input |
Output |
|
8
polygons(np=8),88 lines (file Binput.txt, size 624 bytes) |
8 lines |
|
8 4
1
1 3
1 3
3 1
1 7 4
0 4
7.5 7
7.5 7
3 9
0 7
0 4
0 4 51
314.5 56.5
167 151
259 51
314.5 5 ... |
2.00 25.50 7222.38 38113.02 6145.50 24482.89 43917.90 25112.60 |
Solved by 5 teams First team solver: Kikkok –
Computer Engineering PSU Hatyai at 34 minutes
Problem explanation
In order to get the lowest cost, for each task we must select the lowest-cost crew who has enough skill to do the task.
Problem type
Optimization, Greedy
algorithm
Example solution program
C source code : Clowestcost.c
Test Case
|
Input |
Output |
|
21
crews, 40 tasks (file Cinput.txt, 62 lines) |
1 integer |
|
0
1 100 1
2 150 2
3 200 3
4 250 4
5 300 5
6 350 6
7 400 7
8 450 8
9 500 9
10 550 10
11 600 11
12 650 12
13 700 13
14 750 14
15 800 15
16 850 16
17 900 17
18 950 18
19 1000 19
20 1050 20
21 1100 a0
1 9 b0
1 2 c0
2 5 d0
2 6 . . . |
127350 |
No team could solve this problem in time.
Problem explanation
Since all crew can work in parallel, the shortest time required for the maintenance work is the longest hours among crew members. The objective is to minimize the longest hours of the crew in the task scheduling. Dynamic programming algorithm is the best choice for finding the global optimum solution. Note that in this problem you have to deal with not only the task hours and levels but also the crew hours and levels.
Problem type
Optimization, Dynamic
programming (with multiple factors and constraints)
Example solution program
C source code: DshortestTimeDP.c
Test Case
|
Input |
Output |
|
The
same test case as problem C 21
crews, 40 tasks (file Dinput.txt, 62 lines) |
1 integer |
|
0
1 100 1
2 150 2
3 200 3
4 250 4
5 300 5
6 350 6
7 400 7
8 450 8
9 500 9
10 550 10
11 600 11
12 650 12
13 700 13
14 750 14
15 800 15
16 850 16
17 900 17
18 950 18
19 1000 19
20 1050 20
21 1100 a0
1 9 b0
1 2 c0
2 5 d0
2 6 . . . |
12 |
Problem Setter:
Seksun Suwanmanee, Department of Computer
Engineering, Prince of
Problems B, C and D: adapted from exercises in
C Program Design for Engineers, 2nd edition (Addison Wesley), by Jeri R. Hanly and Elliot B. Koffman,
2001.