INFOMAN брой 13
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
ÞÛÛÛ ÞÛÝ ÛÝ ÞÛÛÛÛÛ ÛÛÛÛÛ ÞÛÛ ÛÛÝ ÞÛÛÝ ÞÛ ÛÝ
ÞÛ ÞÛÛÝ ÛÝ ÞÛ ÞÛ ÛÝ ÞÛÞÛ ÛÝÛÝ ÞÛ ÛÝ ÞÛÛÝ ÛÝ
ÞÛ ÞÛ ÛÝ ÛÝ ÞÛ ÞÛ ÛÝ ÞÛ ÛÜÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ ÛÝ
ÞÛ ÞÛ ÛÝÛÝ ÞÛÛÛÛ ÞÛ ÛÝ ÞÛ ÞÛÝ ÛÝ ÞÛÛÛÛÛÛÝ ÞÛ ÛÝÛÝ
ÞÛ ÞÛ ÛÛÝ ÞÛ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÛÝ
ÞÛÛÛ ÞÛ ÛÝ ÞÛ ÛÛÛÛÛ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
ЕДИНСТЕНОТО В БЪЛГАРИЯ СПИСАНИЕ ЗА ЗАДАЧИ ПО ИНФОРМАТИКА
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
E-mail: Ü ÜÜ Home Page:
infoman@musala.com ßÛ Û Û http://infoman.musala.com/
брой 13 - Май, 1999 Û ßÜÜß (c) INFOMAN Team Bulgaria
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
СЪДЪРЖАНИЕ
ÄÄÄÄÄÄÄÄÄÄÄÄ
ТЕМА АВТОР
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄ
1. Няколко думи от главния редактор (Infoman)
2. PC Magazine / Bulgaria - V конкурс по програмиране Светлин Наков
3. Отново за задачата "КАРТИНА" от международната олимпиада Петър Петров
4. Една статия за симетрични игри Преслав Наков
5. Една задача за една функция и едно нейно решение Васил Поповски
6. Ловци на духове - една класическа задача Star Gruhtar
7. Бързо коренуване на числа Петър Петров
8. Пакетиране на тръби Стоян Йорданов
9. Търсене на път в триъгълник Преслав Наков
10. Благословии относно организаторите на международната
олимпиада по информатика Португалия'98 Светлин Наков
11. Предстоящи състезания по информатика (Infoman)
11. Доброто старо заключение (Infoman)
Няколко думи от главния редактор (Infoman)
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄ
Повече от месец INFOMAN не беше напомнял за себе си. Това беше така, за-
щото главният виновник за неговото съществуване и главен редактор на списа-
нието Светлин Наков си стоеше вкъщи и си решаваше задачи по информатика. И
понеже през този период нямаше никакви състезания, той не сметна за необхо-
димо да издаде нов брой. Но наближи финалния кръг на олимпиадата по информа-
тика за ученици, читателите на списанието постоянно се увеличаваха,получиха
се и завидно количество статии и се наложи да излезе нов брой на списанието.
Ето го сега пред вас. INFOMAN 13. Фаталният брой. Броят който бе написан от
най-много хора до момента и броят с най-много читатели до момента - над 100
редовни абонати. Списание INFOMAN вече не се издава само от главният му ре-
дактор, а от неговите читатели. Първоначалната идея INFOMAN да бъде списани-
ето на информатиците, което ще се издава от тях самите започна да се реали-
зира. Даже статиите, които се получиха в редакцията бяха много и оставихме
половината за следващия, който ще излезе в края на Май или началото на Юни,
за да публикува решенията на задачите от 4-ти (финален) кръг на олимпиадата
по информатика за ученици. Трябва да споменем, че някои злонамерени или не-
информирани читатели пуснаха неверния слух, че в края на април ще има състе-
зание по информатика в Ямбол. Това не беше вярно, но за да провери информа-
цията отговорният екип на INFOMAN трябваше се обади лично в Ямбол и в минис-
терството на образованието. Стана ясно, че въпросното състезание ще бъде на
5-7 юни в същия град. Трябва да отбележим официалния протест на някои състе-
затели, които няма да могат да участват, защото състезанието ще съвпадне с
изпитните дни от изпита "SAT", които са само два пъти в годината. За съжеле-
ние INFOMAN е независима неофициална организация без никаква власт и затова
не може да направи нищо по въпроса. Все пак тези състезания се организират
и провеждат от министерството. Искаме да отбележим, че списание INFOMAN има
голямо желание да направи едно състезание за всички свои читатели, но проб-
лемът е в липсата на пари.Ако някой наш читател може да осигури спонсорство
з организиране на състезание по информатика, молим да се свърже с нас. Идея-
та на едно такова състезание е да се срещнат и състезават ученици, студенти,
професионалисти и изобщо всички читатели заедно, а не в различни възрастови
групи, както обикновено. Известни са датите на всички състезания за ученици
до края на учебната година. Можете да ги видите в предпоследната статия.
INFOMAN иска да благодари специално на всички, които изпращат статии и ма-
териали за публикуване. Давайте така, информатици!
Посетете страницата на INFOMAN на адрес
http://www.infoman.org
PC Magazine / Bulgaria - V конкурс по програмиране Светлин Наков
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄ
Измина и предварителният кръг на 5-тия конкурс по програмиране на списа-
ние PC Magazine Bulgaria. Предлагам на всички читатели моите решения на две-
те задачи от брой 3/1999 на PC Magazine. Условията, анализът и самите реше-
ния ще намерите във файловете buca.pas и MONOPOL.PAS.
Отново за задачата "КАРТИНА" от международната олимпиада Петър Петров
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄ
По повод на писмата, които получих от някои читатели на INFOMAN относно
решението на задачата "PICTURE" от международната олимпида по информатика в
Португалия, което беше публикувано в предния брой на INFOMAN, искам да отбе-
лежа, че бях допуснал "грешка" в решението. Всъщност грешката беше резултат
от различно тълкуване на условието на задачата. Статията ми можете да проче-
тете от файла picture2.pas.
Една статия за симетрични игри Преслав Наков
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄ
Много задачи, свързани със симетрични игри се появиха напоследък и зато-
ва ви написах една интересна статия, в която съм изследвл проблема в дъбочи-
на. Вижте файла simetr.htm. Файлът е HTML документ.
Една задача за една функция и едно нейно решение Васил Поповски
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
Преди много време решавах една задача за една функция, която ми се сто-
ри интересна. Разгледайте я. Файлът е fx.pas.
Ловци на духове - една класическа задача Star Gruhtar
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄ
Преди няколко години филмът "Ловци ан духове" беше доста популярен. Попу-
лярна стана и задачата по информатика за разпределение на ловци и духове,ко-
ято стана класическа в раздела изчислителна геометрия в равнината.Решението,
което предгам се базира на идеи от книгата "Introduction to algorithms" и е
блестящ пример за техниката в програмирането наречена "разделяй и владей".
разгледайте фйала ghosts.pas за повече информация.
Бързо коренуване на числа Петър Петров
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄ
В много ситуации, главно при алгоритмите за тримерна графика, се нуждаем
от бързо коренуване на цели числа. Функциите за коренуване, които ни предла-
гат езиците за програмиране на високо ниво и аритметичните копроцесори на
ниско ниво, често пъти се оказват доста бавни, защото използват реални чис-
ла. Предлагам ви една статия за коренуване на числа, която вероятно ще ви е
интересна - файлът е isqrt.txt.
Пакетиране на тръби Стоян Йорданов
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
Изпращам ви решение на една задача за опаковане на тръби в кашон, която
ни дадоха на олимпиадата в София. Файлът е trybi.pas.
Търсене на път в триъгълник Преслав Наков
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄ
Търсенето на път в триъгълник не е само една класическа задача от раздели-
те "теория на графите" и "динамично оптимиране". На основата на алгоритмите,
които ви предлагам в статията triangle.htm могат да се решават и голям брой
други задачи. Изобщо става въпрос за дърсене на екстремален път в безконту-
рен граф.
Благословии относно организаторите на международната
олимпиада по информатика Португалия'98 Светлин Наков
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄ
Между другото използвам страниците на INFOMAN, за да изразя протестът си
срещу безотговорното отношение на организаторите към участниците в междуна-
родната олимпиада по информатика. До момента никой не е получил документите
(грамоти, сертификати) за медалите от международната олимпиада. С други ду-
ми, дадоха ни медали, но само за украса, защото нямаме документи че сме ги
спечелили от олимпиада. И когато се наложи да кандидатстваме за някой запа-
ден университет, няма да имаме доказателство за големите си успехи. Случаят
е без прецедент в историята на компютърните състезания и олимпиади. Все пак
всички участници имат сертификати, че са участвали в олимпиадата, но за ме-
далите нямат нищо. Аз, понеже имам познати и от други страни, ги попитах да-
ли имат сертификати, но те ми се оплакаха, че също нямат. Вероятно въобще и
няма да получим.
Относно решенията на журито на задачите от олимпиадата, трябва да отбеле-
жим, че наистина има грешни и неработещи решения, а някои не се компилирват
или забиват при добре подбрани тестови примери. Някои пък дават и грешен ре-
зултат. Изобщо работата е свършена професионално.За щастие правилни решения
има публикувани в INFOMAN и не е нужно никой негов читател да се бори с из-
мислиците на международното жури.
Относно задачата за картините, ограничението за броя правоъгълници да е
5000 е наистина печатна грешка, довела до объркване на много участници. Аз
лично бях жертва на тази грешка и не можах да реша задачата, защото се опит-
вах да я подкарам за 5000 правоъгълника и не ми остана време другите задачи.
Предстоящи състезания по информатика (Infoman)
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄ
Подборният (финалният) кръг на олимпиадата по информатика за ученици ще
се проведе на 15-16 май в София в сградата на ФМИ (факултет по математика и
информатика) на Софийския университет. Компютрите ще бъдат осигурени и няма
да има нужда всеки да си носи. Олимпиадата ще се проведе в два състезателни
дни. Хората събрали 80% от точките на осмия в класирането ще бъдат приемани
без конкурсен изпит във ВУЗ. (Този критерий се променя всяка година, затова
всички ще се решава на място). От олимпиадата ще се избере проекто-национал-
ният отбор за международната олимпиада и Балканиадата.
Пролетният турнир по информатика за средношколци ще се проведе на 6 юни
в град Ямбол.
Присъственият кръг на конкурса за програмни продукти, условията на който
публикувахме в предните два броя ще се проведе в края на месец юни в Сливен.
напомняме на всички че крайният срок за предаване на програмните разработки
и рефератите е 20 май.
Доброто старо заключение (Infoman)
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄ
Напомняме на всички читетели на INFOMAN, че редакцията на списанието ще
е много благодарна на всички които ни изпращат статии, задачи и други мате-
риали за публикуване. Не забравяйте изискванията - задачите да бъдат решени
и алгоритмите да бъдат обяснени, а статиите да са на тема алгоритми и зада-
чи по информатика. Изпращайте ни и всякаква информация за състезания, които
предстоят.
Не забравяйте, че информатиката е основата на програмирането и че всички
програмисти, които не са добри информатици са си чисти занаятчии!
Учете информатика. Тя е същината на компютърните науки.
Успех на всички информатици!
File List:
isqrt.txt
fx.pas
ghosts.pas
infoman13.txt
buca.pas
picture2.pas
simetr.htm
triangle.htm
trybi.pas