INFOMAN брой 5
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
ÞÛÛÛ ÞÛÝ ÛÝ ÞÛÛÛÛÛ ÛÛÛÛÛ ÞÛÛ ÛÛÝ ÞÛÛÝ ÞÛ ÛÝ
ÞÛ ÞÛÛÝ ÛÝ ÞÛ ÞÛ ÛÝ ÞÛÞÛ ÛÝÛÝ ÞÛ ÛÝ ÞÛÛÝ ÛÝ
ÞÛ ÞÛ ÛÝ ÛÝ ÞÛ ÞÛ ÛÝ ÞÛ ÛÜÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ ÛÝ
ÞÛ ÞÛ ÛÝÛÝ ÞÛÛÛÛ ÞÛ ÛÝ ÞÛ ÞÛÝ ÛÝ ÞÛÛÛÛÛÛÝ ÞÛ ÛÝÛÝ
ÞÛ ÞÛ ÛÛÝ ÞÛ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÛÝ
ÞÛÛÛ ÞÛ ÛÝ ÞÛ ÛÛÛÛÛ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
E-mail: Ûßß Home Page:
infoman@musala.com ßßÜ http://infoman.musala.com/
ÜÜß
Issue 5 August, 1998 (c) INFOMAN Team Bulgaria
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
SYDYRVANIE
ÄÄÄÄÄÄÄÄÄÄÄÄ
TEMA AWTOR
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄ
1. Intro (Infoman)
2. Reshenie na zadacha 2 ot kontrolnoto systezanie za Boian Krosnov
opredelqne na otbora za mevdunarodnata olimpiada
po informatika - Setubal'98, Portugalia
3. Reshenie na zadachi 1 i 3 ot kontrolata za Svetlin Nakov
mevdunarodnata olimpiada
4. Zadachata za umnovenie na matrici - reshenie Star Gruhtar
5. Informaciq za predstoqshti sastezaniq (Infoman)
6. Oshte edna kombinatorna zadacha Star Gruhtar
7. Reshenie na zadacha 5 ot podborniq kryg na Nakov
nacionalnata olimpiada po informatika
8. Dobre poznatato zakluchenie (Infoman)
Intro (Infoman)
ÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄ
Lqtoto pochti izmina i dojde wreme za seriozna rabota. Kraj na pochiwki-
te. INFOMAN prodylvawa oshte po-smelo da zatwyrvdawa poziciite si na lider
w oblastta na podgotowkata za systezaniq po informatika i programirane w na-
shata strana, kato si ostawa edinstweniqt dostypen za uchenicite nachin za
sdobiwane s resheniqta na zadacite ot pochti wsichki po-wavni systezaniq i
konkursi po informatika w Bulgaria. Dokazatelstwo za towa e rqzko narastna-
liqt interes ot strana na nashite chitateli i utroqwaneto na tehniq broj.
Redakciqta se izwinqwa na wsichki chitateli, koito sa tyrsili web saita
na "INFOMAN" na stariq mu adres. Prichinata za izchezwaneto na oficialnata
stranica na spisanieto e sriw w servera na cyberspace.org. Nowata stranica
se namira na adres http://people.bulgaria.com/infoman.
Skoro zapochwa nowata uchebna godina i s towa se podnowqwa obuchenieto
po informatika i podgotowkata za olimpiadite i systezaniqta predstoi. Sled
broeni dni e i mevdunarodnata olimpiada po informatika w Setubal,Portugalia.
Ako uchastieto na bylgarskiq nacionalen otbor po informatika na naj-prestiv-
no mevdunarodno systezanie za uchenici ne se prowali kakto stana s Balkania-
data w Ankara tazi godina,w sledwashtiq broj na spisanieto ochakwajte komen-
tar i resheniq na zadachite. Na prowedenata kontrola w Plovdiv za uchastie
w Portugalia se opredeli sledniqt nacionalen otbor:
1. Svetlin Nakov - Veliko Turnovo
2. Boian Krosnov - Stara Zagora
3. Vasil Popovski - Plovdiv
4. Petar Petrov - Sofia
s rykowoditeli:
doc. Asen Rahnev - Plovdivski Universitet
doc. Krasi Manev - FMI na Sofijski Universitet
Otboryt trqbwa da zamine za Portugalia na 4-ti septemvri i da se wyrne na
12-ti septemvri, 1998g.
W tozi broj wi predstawqme reshenie na zadachite ot kontrolnoto systeza-
nie w Plovdiv,kakto i resheniq na nqkoi drugi interesni zadachi. Redakciqta
blagodari na wsichki, koito izpratiha materiali za tozi broj.
Reshenie na zadacha 2 ot kontrolnoto systezanie za Boian Krosnov
opredelqne na otbora za mevdunarodnata olimpiada ÄÄÄÄÄÄÄÄÄÄÄÄÄ
po informatika - Setubal'98, Portugalia
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
Predlagame reshenieto na zadacha 2 ot kontrolata za mevdunarodnata olim-
piada po informatika w Portugalia, dadena na 8-te uchenika, koito se boriha
za mqsto w nacionalniq otbor. Zadachata e matematicheska, no oswen slovnoto
matematichesko reshenie, koeto move da se izwede s elementi na wishata mate-
matika,syshtestwuwa chisto informaticheski metod za neinoto reshawane. Imen-
no tozi metod e opisan w prilovenioto reshenie - SECHENIE.PAS. Stawa wypros
za namirane liceto ne sechenie na kwadrat s okryvnost.Izpolzwaniq algoritym
e na principa razdeliaj i wladej i raboti s nqkakwa tochnost. Trqbwa da se
otbelevi che tozi metod ne e absolutno tochen i ne move winagi da nameri re-
zultata s tochnost 2 cifri sled desetichnata tochka.Ako slovim prekaleno go-
lqma tochnost na rezultata,programata shte e mnogo bawna za golemi kwadrati
i okryvnosti. Ako slovim malka tochnost, ne movem da namerim dwe cifri sled
desetichnata zapetaq. No pri wsichki sluchai namereniq rezultat e mnogo bli-
zyk do otgowora.
Reshenie na zadachi 1 i 3 ot kontrolata za Svetlin Nakov
mevdunarodnata olimpiada ÄÄÄÄÄÄÄÄÄÄÄÄÄ
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
Predlagam nqkakwo reshenie na zadacha 1 (BASIC.PAS) i dobro reshenie na
zadacha 3 (BANK.PAS). Nadqwam se da razberete algorityma na zadacha 3, wyp-
reki, che ne e obqsnen mnogo qsno. Toj ne move da se obqsni qsno s tekst, a
samo s nagledno pokazwane, koeto w spisanieto e newyzmovno. Usloviqta na za-
dachite i opisanieto na izpolzwanite alalgoritmi, kakto i primernite whodni
danni sa w syotwetnite fajlowe. Programite sa testwani i s testowete na vu-
rito i rabotqt prawilno.
Zadachata za umnovenie na matarici - reshenie Star Gruhtar
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄ
Zadachata za unovenie na matrici e tipichen primer za izpolzwane na di-
namichno optimirane pri reshawane na esktremalni kombinatorni zadachi po in-
formatika. Tq ima mnogo interpretacii, no wyw fajla MATRIX.PAS e dadena naj-
chesto sreshtanata. Tazi zadacha e dawana na kontrola za mevdunarodna olim-
piada. Druga interpretaciq na syshtata zadaha e dawana na zadochniq konkurs
po informatika na sp. Computer - zadachata za optimalna triangulaciq na iz-
pyknal mnogoygylnik. Zadachata e swyrzana i s chislata na Katalana.
Informaciq za predstoqshti sastezaniq (Infoman)
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄ
Pyrwoto systezanie za uchenici, koeto predstoi e chak prez January 1999
godina - zimnite matematicheski praznici. Za nego oshte nqma druga informa-
ciq.
Westnik "Computer News" i tazi godina organizira systezanie po programi-
rane. Pyrwite dwe zadachi otdawna izlqzoha, no krajniqt srok za izprashtane
na resheniq e 30 septemwri. Golqmata nagrada tazi godina e $1000 w broj. Za-
dylvitelno uslowie za uchastnicite e da imat abonament za westnika do kraq
na godinata. Za poweche informaciq chetete westnik "Computer News".
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.Wseki
kojto uchastwa redowno (prashta reshenie na wsichki zadachi) w tozi konkurs
pecheli bezplaten abonament za spisanieto.
Spisanie "Personal Computer World" sushto pochti wyw wseki broj dawa po
edna zadacha po informatika s nagrada za naj-dobroto reshenie.
Oshte edna kombinatorna zadacha Star Gruhtar
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄ
Poneve srokyt za izprashtane na zadacha 2 ot chetwyrtiq konkur po prog-
ramirane na spisanie PC Magazin Bulgaria weche izteche, shte si pozwolia da
publikuwam edno primerno reshenie na tazi srawnitelno lesna zadacha. Kakto
obiknoweno uslowieto na zadachata i opisanieto na algorityma sa wyw fajla s
sors koda - BUKVIIZR.PAS
Reshenie na zadacha 5 ot podborniq kryg na Nakov
nacionalnata olimpiada po informatika ÄÄÄÄÄ
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
Wypreki che tazi zadacha se reshawa samo s eksponencialna slovnost i do-
ri na byrz computer, za N=70 i M=19 ili 20 wyrwi bawno, smqtam che wse pak
sam uspql da q resha (poneve dawa prawilni rezultati). Wivte sami dali sym
praw.Uslowieto na zadachata i ideqta na algorityma s wyw fajla GAMECISL.PAS.
Dobre poznatato zakluchenie (Infoman)
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄ
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.