2003. október 26.
2003. október 26-án, vasárnap került megrendezésre egyetemünkön negyedszer az ACM International Collegiate Programming Contest válogatója. A cél a legjobb három csapat kiválasztása volt, akik képviselhetik a BME-t a lengyelországi regionális elődöntőn, melyet 2003. november 14-16 között a varsói egyetemen tartanak. Szintén e régióba tartozik Ausztria, Horvátország, Csehország, Németország, Szlovákia és Szlovénia is. A döntőben, melyet 2004 márciusában rendeznek meg Prágában, a régió legjobb csapata vehet részt.
Az egyetemi válogatóra 19 három fős csapat jelentkezett, és küzdötte végig az 5 órát, mely rendelkezésükre állt a kiadott 7, váltakozó nehézségű algoritmikus jellegű feladat megoldásához. A szabályoknak megfelelően minden csapat pontosan 1, azonos konfigurációjú számítógépet használhatott. így alakult ki végül szoros versenyben az alábbi végedmény:
| Helyezés | Versenyzők | Megoldott feladatok (időrendben) | Összidő |
|---|---|---|---|
| 1 | Földényi Tamás, Pallos Péter, Hargitai Gábor Bálint | BCEFG | 12:56 |
| 2 | Siroki László, Guta Balázs, Szabadka Zoltán | BCDFG | 13:53 |
| 3 | Felföldi Zsolt, Szabó Péter, Bácsi László | BCDEG | 14:00 |
| 4 | Ráth István, Vágó Dávid, Szirják Csaba | BCEFG | 14:55 |
| 5 | Csillag Kristóf, Ritter Ádám, Golda Bence | BDEFG | 17:15 |
| 6 | Agocs Albert, Szoboszlay Dániel, Babos Attila | BCEFG | 17:36 |
| 7 | Flach Attila, Gyebnár Gábor, Sáfár Szilveszter | BCEFG | 22:45 |
| 8 | Deák Péter, Sipka Bálint, Hubár Tamás | CDG | 09:33 |
| 9 | Borosan Péter, Takács Gábor, Herendi Gergely | EG | 07:15 |
| 10 | Csordés Hunor, Tran Thanh Long, Kiss Ákos | BC | 08:07 |
| 11 | Bodó Péter, Hamar Gábor, Horváth Botond György | EG | 09:36 |
| 12 | Hajés Gergely, Hajdú János, Molnár Viktor | C | 02:35 |
| 13 | Pápai Tivadar, Vajk Tamás, Földesi Tamás | G | 03:35 |
| 14 | Boromissza Gergely, Horváth Janos, Budai Balázs | G | 05:35 |
| 15 | Balog Gergely, Tóth Rudolf, Porcs-Makkay Ákos | 00:00 | |
| 16 | Ádam György, Temesváry Andras, Fekete Gabor | 00:00 | |
| 17 | Kovács Tamás, Kiss Ákos, Balatoni Emese | 00:00 | |
| 18 | Gerner Karoly, Krizsán Dóra, Újfalusi Melinda | 00:00 | |
| 19 | Dady Róbert Kálman, Péntek Zsolt, Tefner Roland | 00:00 |
A tesztelés során minden programnak egy adott teszt bemeneten kellett az adott teszt kimenetet produkálnia. Az alábbiakban mindegyik feladathoz megadjuk a használt teszt adatokat, és egy lehetséges megoldást is. A példamegoldások és a tesztadatok külön könyvtárban találhatók.
A lappal vagy versennyel kapcsolatos kérdéseket, észrevételeket, javaslatokat az [email protected] címre lehet küldeni.
2: 20 cases with 6 moves
3: 50 cases with 7 moves
4: 50 cases with 8 moves
5: 100 cases with 9 moves
6: 100 cases with 10 moves
7: 100 cases with 11 moves
8: 200 cases with 12 moves
9: 200 cases with 13 moves
10: 200 cases with 14 moves
11: 200 cases with 15 moves
12: 200 cases with 16 moves
13: 300 cases with 17 moves
14: 300 cases with 18 moves
15: 20 cases with 6 moves
Input files:
1: sample input
2: a bunch of images of size 1 (all possible tree shapes)
3: a bunch of images of size 2 (all possible tree shapes)
4: a bunch of images of size 4 (all possible tree shapes)
5: a bundh of images of size 8 (converted from icons, quantized a bit)
6: a bunch of images of size 16 (converted from icons, quantized a bit)
1: sample input
2-5: just horizontal walls of various separation
6-10: just vertical walls of various separation
11-15: grids of various separation
16-24: random with various number of walls
25-30: random with 30 walls
31: a case with 0 walls
1: sample input
2-7: from Charlie
8: some small case
9-13: random cases with 100000 numbers
14: a case in which all numbers are the same
15: a case in which all numbers are different
16: a case with 100000 numbers all the same
bio.1-16.dat: 125 random cases each
bio.17-20.dat: let p and d vary, hold e and i at 0 (about 150 cases each)
bio.21-24.dat: hold p and i at 0 (about 150 cases each)
bio.25-28.dat: hold p and e at 0 (about 150 cases each)
bio.29.dat: sample input/output
1: sample input
2-5: 30 random cases each
6-10: 30 random cases with small t_i (<= 2)
11-12: 30 random cases each with n = 25, h = 16
13: a few cases to check tie-breaking
14-15: 30 random cases each with medium t_i (<= 12)
16-17: 30 random cases each with n = 25, h = 16, t_i <= 12
18-19: 30 random cases each with n = 25, h = 16, t_i <= 2
1: Just a few games I got from the actual game
2: 3 uniform boards
3: 50 row boards
4: 50 col boards
5: 500 random boards
6: 500 random boards
7: sample input
ACM International Collegiate Programming Contest
1999 East Central North America Regional Contest
November 13, 1999
University of Waterloo
Chief Judge: Howard Cheng <[email protected]>
These are the sample solutions, test inputs and test outputs used for the
1999 East Central North America regional contest of the ACM International
Collegiate Programming Contest. Please see
http://plg.uwaterloo.ca/~acm00/regionals/
for the problem set, contact information, standings and so forth.
The judges (collectively or individually, as appropriate) hold copyright
on the solutions and test data. If you distribute them, you must do so
with this README file. If you make altered versions of the files available
to others, then you must clearly indicate the changes that you have made
in addition to observing any restrictions on the original files. You
may use this data set for educational purposes, personal edification and
running practice contests. If you find a commercial application for these
files then you will need to contact the authors before making use of them
in that way.
To be considered correct, the following (Unix) command-line should
produce no output for each test case:
./my-pX < X.N.dat | diff - X.N.diff
Additionally, the programs must run in 16MB of RAM and 5s of CPU time on
the particular sort of Sparc Ultra/4 that we were using and not generate
any runtime errors. I understand that
char x[10];
for( i=0 ; i < 10 ; i++ ) scanf( "%d", x+i );
appears to work on Intel processors running certain operating systems.
On the machine used this would generate a bus error due to using an
unaligned pointer to an integer quantity. (Moreover, this code could
get the wrong answer or generate a segmentation fault on some machines
that don't get bus errors, depending on how memory is arranged.)
Differences in malloc() implementations will give greatly different
results with incorrect programs.
If you solved a problem in Pascal ... different Pascal implementations
vary wildly. For that matter, so do C++ implementations. We used
gcc/g++ 2.95.2 with -ansi and -O2 flags.
Java solutions were tested on an Intel Pentium II-400 PC running IBM
VisualAge C++ on Windows NT. The run time is limited to 15s on this
machine.
Some of the judge's solutions were not built in the contest environment.
In particular, one of the solutions to G runs too long but was used to
check the output of the other programs. They were not tested on every
platform in existence, so they might conceivably rely on
platform-dependent issues (such as mentioned above) to function correctly.
Derek Kisman wrote solutions to all problems except A and C in the contest
environment. He was working in contest conditions. His solutions to A
and C were written later.
The solutions were created before the problem details were finalized, so
some may show rudiments of earlier requirements. Modifying the programs
to work with changed specifications was not always done with grace.