списание ИНФОМАН

INFOMAN брой 4

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.

File List:

similar.pas
platka.pas
potok.pas
infoman4.txt