[RTK-tekmovalci] Razmigajmo možgančke

[Mojca Miklavec]

Pozdravljeni,

državno tekmovanje IJS iz programiranja je že skoraj pred vrati -
nagrade so vsekakor vredne truda, zatorej začnite z razgibavanjem
možgančkov, dokler je še čas!


1. Za zamudnike in tiste, ki ste spregledali, ker ste se prijavili v
zadnjih nekaj dneh:
    http://rtk.ijs.si/prijava/majica.html
(majice so sicer že naročene, a če bo vaša velikost na voljo, jo bomo
skušali priskrbeti)


2. Privlačne nagrade so tudi za mačko in miš! http://rtk.ijs.si/mackamis.html
Pošljite svoje programe, dokler je čas, popestrite zaključno
prireditev z vašo prebrisano mišjo, ki zna uteči vsaki mački, in
mačko, ki ulovi še tako zvito miš!

3. Čas je za razmigovanje možgančkov, da ne bosti prišli na tekmovanje
čisto nepripravljeni. Amerika ponuja zanimiv sistem za priprave (USACO
OPEN prične jutri in traja do 1. maja!!!):

a) Trening:
    http://train.usaco.org/usacogate

b) Tekmovanje:
    http://ace.delos.com/contestgate


a) Trening je namenjen nekoliko bolj izkušenim, a to ne pomeni, da ga
ne bi mogli uporabljati tisti iz prve skupine: prične se z lažjimi
nalogami, zahtevnost se hitro stopnjuje, naučite se lahko ogromno. Če
se boste uspešno prebili skozi vse naloge, vam olimpijada prihodnje
leto gotovo ne uide! Do tekmovanja sicer ne boste mogli rešiti vseh
nalog, vendar je portal res izvrstna vaja!
Za 1. skupino velja: če nalog ne znate rešiti, to še ne pomeni, da bi
se morali prestrašiti državnega tekmovanja, saj so naloge na našem
državnem tekmovanju bistveno lažje od tistih, ki jih amerika uporablja
za usposabljanje svoje olimpijske ekipe.

b) Tekmovanje je namenjeno vsem in bo potekalo od 28. aprila do 1.
maja. Tekmuje se v štirih kategorijah, za vas najbrž prideta v poštev
dve:
- LEVEL 1 za prvo (in morda drugo?) skupino, lažja
- BRONZE DIVISION za drugo in tretjo skupino

Najboljšim in najbolj zagrizenim tekmovalcem, ki se bodo udeležili
USACO Open tekmovanja in ki bodo reševali dodatno nalogo iz tega
maila, obljubljamo NAGRADE na samem državnem tekmovanju (v kakšnem
obsegu, je predvsem odvisno od odziva).

----------------------------------------------------------------------
Tole je copy-paste iz domače strani tekmovanja
(http://oldweb.uwp.edu/academic/mathematics/usaco/2006/National/National.htm)

* FOR non-USA STUDENTS and those USA students who do not wish
       to attend the USAICO: The tournament will open on Friday,
       April 28 and run through Monday, May 1.

The U S Open is FOUR HOUR tournament with four divisions:
        * A very challenging invitation-only GOLD DIVISION
        * A challenging invitation-only SILVER DIVISION
        * An easier BRONZE DIVISION to everyone

The U S Open LEVEL 1 competition is a 55 minute contest especially
designed for beginning programmers.
----------------------------------------------------------------------



3. Ogrevalna naloga - rešitve pošljite na rtk.ogrevanje na gmail.com

Tekmovalni komisiji je letos priprava majic povzročala več preglavic,
kot so si sprva predstavljali. Vsak tekmovalec je napisal, katero
številko majice si želi (in to željo morajo organizatorji spoštovati),
potem pa še nekaj barv, ki so mu všeč (česar organizatorjem ni treba
striktno upoštevati, a želijo si ustreči željam čimvečih tekmovalcev
hkrati).

Organizatorji so želje dobili v naslednji obliki:
V prvi vrstici sta dve števili M in N, kjer je M število možnih barv
(2 <= M <= 15) in N število tekmovalcev (2 <= N <= 200). Sledi
najprej M vrstic z imeni barv(*) in štirimi števili, od katerih vsako
pove, ali ima dobavitelj na voljo majice določene barve in določene
velikosti (po vrsti: S M L XL).
"modra 1 1 0 1" npr. pomeni, da ima dobavitelj na voljo dovolj modrih
majic velikosti S in M, da nima nobene majice velikosti L ter da ima
na zalogi dovolj modrih majic velikosti XL.

(*) Vsako ime barve je dolgo največ 20 znakov in je sestavljeno iz črk
angleške abecede brez presledkov.

Sledi še N vrstic, kjer je za vsakega tekmovalca navedeno najprej
število barv N_i, ki jih je napisal v obrazec (1 <= N_i <= M) ter nato
N_i števil (med 1 in M), od katerih
vsako predstavlja svojo barvo.

Primer:

5 6
modra 1 1 0 1
rdeca 1 1 1 0
roznata 1 1 1 1
rumena 1 0 1 1
bela 1 0 0 0
S 3 5 4 1
M 2 2 1
L 3 3 1 2
XL 1 1
S 1 5
M 3 3 2 4


Da bi ocenili, kako srečni bodo tekmovalci z izbiro majic, prištejemo
za vsakega tekmovalca, ki je dobil tako majico, kot jo je zapisal na
prvem mestu, 5 točk, in dve točki, če je tekmovalec dobil take barve
majico, kot jo je napisal na seznam, a ne na prvo mesto.

Če npr. kupimo modre in rdeče majice, bo ocena srečnosti tekmovalcev sledeča:
- 2 točki za prvega, ki bo dobil modro majico
- 5 točk za drugega, ki bo dobil rdečo majico
- 2 točki za tretjega, ki bo dobil rdečo majico (ker modrih ni na voljo)
- 5 točk za četrtega, ki bo dobil modro majico
- 0 točk za petega, ki lahko dobi katerokoli majico
- 2 točki za šestega, ki bo dobil rdečo majico
Skupaj torej 16 točk.

Če bi kupili bele in rumene majice, bi bila ocena zadovoljstva 10 točk.

Naloga za 1. skupino
------------------------------

Ker so bili programerji prezasedeni s pripravami nalog za tekmovanje,
se je tajnica (ki ima sicer dober instinkt) sama odločila za dve barvi
majic. Izračunaj, kako dobra je bila njena izbira!

S standardnega vhoda čisto na začetku prebereš še dve števili, ki ti
povesta barvi majic, ki jih je izbrala tajnica ("2 4" bi pomenilo, da
je izbrala rdrečo in rumeno), nato pa še vse ostale podatke, torej (za
rdečo in modro majico):

2 1
5 6
modra 1 1 0 1
rdeca 1 1 1 0
roznata 1 1 1 1
... itd ...

Na standardni izhod izpiši eno številko, in sicer oceno srečnosti
tekmovalcev (ki se računa po zgornjem zgledu), če jim priskrbimo
majice v omenjenih dveh barvah.


Dodatna naloga:
Pomagaj nam povedati, koliko majic moramo naročiti.
Izpiši še tri dodatne vrstice (po spodnjem zgledu, upam, da opis ni
potreben; barvi majic izpiši v istem vrstnem redu, kot si jih dobil
med naročili v prvi vrstici):

rdeca: 2 M 1 L
modra: 1 S 1 XL
vseeno: 1 S


Naloga za 2. in 3. skupino
------------------------------
Komisija se je odločila kupiti štiri različne barve majic. Poišči
tiste štiri barve, ki bodo skupno najbolj osrečile tekmovalce. Če je
možnih kombinacij več, izpiši katerokoli izmed njih, vendar poskrbi,
da bo vsak tekmovalec vedno dobil tisto od štirih barv, ki jo je
najprej napisal (razen če ni napisal nobene od štirih).

V istem vrstnem redu kot so se barve pojavlile na vhodnih podatkih,
izpiši štiri barve, ki bodo skupno najbolj osrečile tekmovalce ter
povej, koliko katerih majic je potrebno naročiti (glej zgled - upam,
da je "format izpisa" dovolj jasen).

Primer izpisa:

modra: 1 XL
rdeca: 1 M
rumena: 1 M 1 L
bela: 2 S