INFOMAN брой 4
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
ÞÛÛÛ ÞÛÝ ÛÝ ÞÛÛÛÛÛ ÛÛÛÛÛ ÞÛÛ ÛÛÝ ÞÛÛÝ ÞÛ ÛÝ
ÞÛ ÞÛÛÝ ÛÝ ÞÛ ÞÛ ÛÝ ÞÛÞÛ ÛÝÛÝ ÞÛ ÛÝ ÞÛÛÝ ÛÝ
ÞÛ ÞÛ ÛÝ ÛÝ ÞÛ ÞÛ ÛÝ ÞÛ ÛÜÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ ÛÝ
ÞÛ ÞÛ ÛÝÛÝ ÞÛÛÛÛ ÞÛ ÛÝ ÞÛ Û ÛÝ ÞÛÛÛÛÛÛÝ ÞÛ ÛÝÛÝ
ÞÛ ÞÛ ÛÛÝ ÞÛ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÛÝ
ÞÛÛÛ ÞÛ ÛÝ ÞÛ ÛÛÛÛÛ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
E-mail: Û Û Home Page:
infoman@musala.com ßßÛ http://infoman.musala.com/
ß
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
SYDYRVANIE
ÄÄÄÄÄÄÄÄÄÄÄÄ
TEMA AWTOR
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄ
1. Balkanska olimpiada po programirane. Kontrolen test. Nakov
Resheniq na zadachite i komentari.
2. Informaciq za predstoqshti sastezaniq. (Infoman)
3. Maksimalen potok w mreva Star Guhtar
4. Zakliuchenie. (Infoman)
Balkanska olimpiada po programirane. Kontrolen test. Nakov
Resheniq na zadachite i komentari. ÄÄÄÄÄ
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
Predi po-malko ot mesec se prowede kontrolno systezanie za Balkaniadata
po informatika za uchenici. Kontrolnoto beshe w Sofia i trqbwashe da oprede-
li nacionalniq otbor na Bulgaria, s kojto tia shteshe da uchastwa na 6-tata
Balkanska olimpiada po informatika - Ankara`98. Kontrolnoto se systoq, zada-
chite dade docent Krasi Manev i tozi pyt te ne biaha nikak trudni. Nacional-
niqt otbor, kojto se opredeli beshe takuw:
1. Svetlin Nakov (Veliko Turnovo)
2. Peter Mitrov (Sofia)
3. Boian Krosnov (Stara Zagora)
4. Peter Petrov (Sofia)
Kogato wsichki ochakwaha zaminawaneto za Ankara i weche si bqha dali zadgra-
nichnite pasporti, nasheto milo ministerstwo na wunshnite raboti zabrani na
bulgarskiq nacionalen otbor da uchastwa w Balkaniadata. Prichinata: Turcite
pokanili za uchastie Turskiq Kipar, no ne pokanili Grutskiq Kipar i gurcite
se razsyrdili i kazali che nqma da uchastwat i che shet boikotirat Balkania-
data. I poneve Bulgaria otkraj wreme wse se podmazwa na niakogo i nikoga ne
e imala sobstwena wunshna politika, reshila da podkrepi Gurciq i da se otka-
ze ot uchastie w towa elitno mevdunarodno systezanie po programirane s gole-
mi nagradi i swetowno izwestie. I to w moment, kogato Bulgaria ima naj-sil-
niq si nacionalen otbor - i chetirimata klasirali se w otbora sa uchastwali
i drug pyt na Balkaniada, a nqkoi i po dwa pyti. 3-ma ot chetirimata bulgar-
ski geroi weche imat specheleni medali ot predishni Balkaniadi. Oswen towa
kakto wsichki znaem w rezultat na serioznata podgotowka w poslednite 3-4 go-
dini winagi rumynskiq otbor wzema pyrwoto miasto i zlatnite medali po Balka-
niadite po informatika, no tazi godina toj e slab, zashtoto e izcqlo s nowi
hora, koito niamat tolkowa opit i ne sa uchastwali drug pyt. Tazi godina be-
she edinstweniqt zlaten shans bulgarite da pobedqt na Balkaniadata i da spe-
celqt pyrwoto mqsto (s nagrada Computer Pentium II) i da wzemat zlatnite me-
dali, poneve drugite strani oswen Rumyniq po tradiciq ne sa mnogo silni. Do-
godina i chetirimata ot nacionalniq otbor shet zawurshat i nqma da imat pra-
wo da uchastwat. Da ne goworim che Kipar e ostrow w Egeisko more blizko do
Izrael i ne samo nqma nishto obshto s Balkanskiq poluostrow, no dave ne e w
Evropa,a e chast ot Azia i izobshto nqma prawo da uchstwa na Balkaniada. No
Bulgaria winagi e imala takiwa uprawnici, koito nikoga ne sa mislili za neq
i zatowa niama da uchastwa na towa mevdunarodno systezanie, za koeto inache
sa bili namereni pari. Ostanaloto go propuskam, zahtoto e necensorno...
A sega komentar po zadachite ot kontrolata. Pyrwa zadacha (SIMILAR.PAS)
e attachnata kym tozi broj na spisanieto. Tq beshe dolu gore lesna i na neq
poweche trqbwashe da se wnimawa otkolkoto da se misli. Uslowieto, reshenie-
to i programata, koqto go realizira za wyw fajla SIMILAR.PAS. Wtora zadacha
beshe po zadadena azbuka i zadaden tekst da se zakodira tekst s kod na Huff-
man. Pochti uchastnici imaha maksimalniq broj tochki i poneve e elementarno
lesna, nqma da q komentiram. Tq beshe na nivo gradski krug na olimpiada. Po-
slednata zadacha beshe naj-serioznata i beshe reshena ka`estweno samo ot nq-
koi uchastnici. Opisanieto i reshenieto sa wyw fajla PLATKA.PAS.
Informatici bulgarski, ne se otchajwajte, ima shansowe pyk da se uchast-
wa w mevdunarodnata olimpiada po informatika w Portugalia. Zasega nqma pari,
no towa move i da se uredi, oswen ako wunshnoto ministerstwo ne zapowqda da
ne se hodi.
Da ne dramatizirame neshtata, wsichki nie znaem che sme kadyrni informa-
tici, programisti, hackeri, phrackeri, crackeri, webmasteri, computer mania-
ci, administratori, ripperi, carderi, hardueristi, softueristi i t.n. i pri
wsichki sluchai nikoj ne move da ni spre da se izmuknem ot tazi dupka Bulga-
ria i da otidem da rabotim nqkyde w niakoq normalna strana i da viweem kato
normalni hora i znaem che kydeto i da otidem shte blesnem s nashite zxnaniq
i umeniq i shte bydem naj-dobrite, naj-kadyrnite i naj-cenenite. Ne kazwam
da zarqzwate olimpiadite, no kakto wivdame ot tqh weche nqma nikakyw smisyl.
Ot systezaniqta sushto. Wse nqma pari, wse nqma koj da ni uchi, wse zadachi-
te koito se dawat niamat reshenie, wse sami si plastame uchastiqta po syste-
zaniqta, wse sme po-dobri ot drugite, no stoim bez rabota, a nekadyrnicite
si klatqt krakata i wzimat ludi pari, winagi ni prekarwat, wse ni precakwat,
i nie nikoga ne se otkazwame da uchastwame po systezaniqta, no ne zaradi sa-
mite tiah ili pyk za nagradite ot po 4-5 bona ili 1 knivka, a samo zashtoto
sme maniaci. Nie sme dobri i kadyrni specialisti i w normalnite strani towa
e napylno dostatychno na edin mladev za da probie i stane golqm chowek. Ni-
koga ne se predawajte :-))
Informaciq za predstoqshti sastezaniq (Infoman)
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄ
Na 08.07.98 w Plovdiv shte se systoi kontrolata za mevdunarodnata olimpi-
ada po informatika.
Pyrwite dwe zadachi ot tradicionniqt konkurs po programirane na spisanie
"PC Magazine Bulgaria" izlqzoha w poslednite dwa broq na spisanieto. Srokyt
wse oshte ne e minal. Zadachite na sa mnogo lesni, no ne sa i mnogo trudni
i shans za klasirane bi trqbwa da ima wseki, kojto si gi reshi kakto trqbwa.
Nagradata i tazi godina e moshten Computer, osiguren ot Risk Elektronics.Os-
wen towa ima i oshte nqkolko nagradi, no te sa za wseki,kojto byde dopusnat
do finalniq kryg, t.e. e w pyrwata desqtka za cqla Bulgaria spored ocenkata
na jurito.
Za tezi, koito ne uchastwat redowno w konkursi, napomnqme,che w spisanie
"Computer" na wseki dwa meseca izliza po edna konkursna zadacha i se dawat
rezultati ot predishnite zadachi. Na wsqka zadacha se dawa i reshenie.
Spisanie "Personal Computer World" sushto pochti wyw wseki broj dawa po
edna zadacha po informatika s nagrada za naj-dobroto reshenie.
Westnik "Computer News" i tazi godina organizira systezanie po programi-
rane. Pyrwite dwe zadachi sa izlezli wyw poslednite broewe na westnika. Nag-
radata tazi godina e $1000 w broj.Zadylvitelno uslowie za uchastnicite e da
imat abonament za westnika do kraq na godinata. Inache uchastie w konkursa
ne se dopuska!
Maksimalen potok w mreva Star Guhtar
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄ
Zadachata za namirane na maksimalen potok w mreva e dosta stara i e ed-
na ot naj-znachimite optimizacionni zadachi w teoriqta na grafite i kombi-
natornata optimizaciq. Tq e reshena predi dosta wreme i ima ogromno prilo-
venie. ~rez optimalen potok w graf move da se reshat zadachite za linejno-
to optimirane, za maksimalno dwojkosychetanie, za wershinno pokritie, za
maksimalno nezawisimo mnovestwo ot wurhowe w graf, transportna zadacha,za-
dachi za optimizirane na proizwodstwoto i oshte bezbroj ekstremalni kombi-
natorni zadachi s praktichesko znachenie, kakto i mnogo zadachi, koito se
dawat po olimpiadite. Primer e zadachata ot podborniq kryg tazi godina.Po-
wecheto algoritmi za reshawane se osnowawat na posledowatelno podobrenie
na pyrwonachalno nulew potok.Izpolzwajki teoremata za maksimalniq potok i
minimalniq razrez, move da se naprawi efektiwen polinomialen algoritym za
reshawane na zadachata. Predstawenoto reshenie (POTOK.PAS) izpolzwa stan-
dartniq algoritym na Ford-Fulkerson.
Zakluchenie (Infoman)
ÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄ
E, qsno e che pyrwonachalnata ideq wseki da prashta materiali ne move da
se realizira, poneve nikoj ne prashta, no wse pak dokato Star Gruhtar se za-
nimawa s INFOMAN, toj nqma da umre i shte ima redowno statii za wsqko syste-
zanie!
Redakciqta na spisanie INFOMAN moli wseki kojto e aboniran za spisanieto
da pomaga za negowoto izdawane i da izprashta statii, resheni zadachi s pod-
robno opisanie na algorityma i programata, koqto gi reshawa. Ako nqkoj ima
poweche informaciq za predstoqshite systezaniq ili informaciq za drugi sys-
tezaniq ili konkursi (w towa chislo i mevdunarodni), molim da q izprati na
redakciqta, za da move tq da byde publikuwana.
Izprashtajte materiali za INFOMAN! Za momenta towa e edinstweniqt nachin
za negowoto syshtestwuwane.