INFOMAN брой 12
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
ÞÛÛÛ ÞÛÝ ÛÝ ÞÛÛÛÛÛ ÛÛÛÛÛ ÞÛÛ ÛÛÝ ÞÛÛÝ ÞÛ ÛÝ
ÞÛ ÞÛÛÝ ÛÝ ÞÛ ÞÛ ÛÝ ÞÛÞÛ ÛÝÛÝ ÞÛ ÛÝ ÞÛÛÝ ÛÝ
ÞÛ ÞÛ ÛÝ ÛÝ ÞÛ ÞÛ ÛÝ ÞÛ ÛÜÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ ÛÝ
ÞÛ ÞÛ ÛÝÛÝ ÞÛÛÛÛ ÞÛ ÛÝ ÞÛ ÞÛÝ ÛÝ ÞÛÛÛÛÛÛÝ ÞÛ ÛÝÛÝ
ÞÛ ÞÛ ÛÛÝ ÞÛ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÛÝ
ÞÛÛÛ ÞÛ ÛÝ ÞÛ ÛÛÛÛÛ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
ЕДИНСТЕНОТО В БЪЛГАРИЯ СПИСАНИЕ ЗА ЗАДАЧИ ПО ИНФОРМАТИКА
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
E-mail: Ü ÜÜ Home Page:
infoman@musala.com ßÛ Û Û http://infoman.musala.com/
брой 12 - Април, 1999 Û ÛÜÜÜ (c) INFOMAN Team Bulgaria
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
СЪДЪРЖАНИЕ
ÄÄÄÄÄÄÄÄÄÄÄÄ
ТЕМА АВТОР
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄ
1. Интро (Infoman)
2. Състезанието в Монтана - коментари и решения Светлин Наков
3. Нов подход за някои задачи от международната олимпиада Петър Петров
4. Отборна работа при участие в ACM Flip Flop
5. Старата задача за намиране на граф по степените му Васил Поповски
6. PC Magazine Bulgaria отново се излагат Дебиан Файърлолски
7. Заключение (Infoman)
Интро (Infoman)
ÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄ
INFOMAN 12 вече е пред вас! По стара традиция той излиза след всяко със-
тезание за ученици за да публикува решенията на задачите,а сега интересът е
насочен към провелото се на 7 април в Монтана състезание по информатика, за
което INFOMAN ви даде информация в предишния си брой. Състезанието протече
гладко и задачите бяха на ниво. Монтана е хубав град. Неизвестно защо мнози-
на от имащите желание да участват не дойдоха, защото си мислеха, че няма да
има състезание. Такава информация INFOMAN не е подавал! В INFOMAN пишеше,че
състезание ще се проведе и състезание се проведе и то по точно описания на-
чин. Толкова ли е паднало доверието към нашето национално списание? Вярно,
че някои хора в Монтана не знаеха, че ще има състезание по информатика, но
те нямат нищо общо с него. Незивестно е защо някои наши читатели търсеха ин-
формация от тях, а не от нас, но това си остана за тяхна сметка.Коментари и
решения на задачите можете да прочетете в статията на победителят в състеза-
нието - Светлин Наков.
INFOMAN иска да благодари специално на всички, които изпращат статии и ма-
териали за публикуване.Най-после идеята списанието да се издава от неговите
читатели започва да се сбъдва.В този брой статиите на главния редактор дори
са по-малко останалите - нещо, което не се е случвало в нито един предходен
брой.
Обещаните от преди известно време сорс кодове на програмите от известната
книгата на Преслав Наков "Основи на компютърните алгоритми" вече са достъп-
ни за теглене от web-сайта на INFOMAN:
http://www.infoman.org
Всеки който се интересува от тях може свободно да си ги изтегли. По-трудно
е вече да се намерят двете части на книгата, защото запасите почти се прода-
доха, а ново издание не е имало. Искаме да информираме всички фенове на та-
зи книга, че в момента се пишат и следващите й части и след известно време
(ама не много скоро) ще се излязат и те.
Състезанието в Монтана - коментари и решения Светлин Наков
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄ
Хубаво състезание беше. За тези, които не знаят на 7 април 1999 година
в град Монтана се проведе състезание по информатика за ученици към пролетна-
та конференция на съюза на математиците в България. Дадени бяха три задачи,
на две от които прилагам условията и решенията (zala.pas и tri.pas).Третата
задача беше много трудна и не само, че никой не успя да я реши по време на
състезанието, но никой не успя да я реши и след това. Според авторът й доц.
Асен Рахнев тя може да се сведе до минимално обхващащо дърво или до комбина-
ция от задача за назначенията (унгарски алгоритъм) и динамично оптимиране.
Все пак решение в INFOMAN така и не се получи. накратко уаловието й беше та-
кова: В една фирма за преводи работели N преводача, които превеждали от бъл-
гарски на M други езика. Всеки преводач имал скорост на превеждане за всеки
език (брой страници на ден), като разбира се знаел само някои от езиците, а
за тези, които не знаел, скоростта му на превеждане била 0. Във фирмата пос-
тъпила заявка за превеждане от български на чужди езици - по определен брой
страници за всеки от езиците. Търси се минималният брой дни, за които фирма-
та може да извърши преводите, при условие, че дин преводач може да превежда
на ден на не повече от един език. Броят на преводачите и на езиците на е по-
вече от 100. Надявам се ако някой читател може да реши задачата, да изпрати
решение в редакцията на INFOMAN.
Нов подход за някои задачи от международната олимпиада Петър Петров
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄ
Изпращам ви решения на две от задачите от международната олимпиада по ин-
форматика през 1998 година. Едната задача е решена доста по-добре отколкото
в брой 7 на INFOMAN, а другата просто е интересна. Имената на файловете са
picture.pas и camelot2.pas
Отборна работа при участие в ACM Flip Flop
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄ
Отскоро не живея в България и не знам точно как вървят тук науките, но в
USA най-елитното състезание по информатика e това на ACM. И понеже то е дос-
та пулярно и в България, смятам че статията, която ви изпращам ще е интерес-
на за повечето от вас. Разгледайте файла acm.txt.
PC Magazine Bulgaria отново се излагат Дебиан Файърлолски
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
Предлагаме ви част от писмото на нашия анонимен читател, подписал се ка-
то "Дебиан Файърлолски", изпратено по e-mail на редакцията на INFOMAN от IP
address: [195.138.141.17] :
Ха здравейте информатичета, хакерчета, програмистчета и т.н. Четохте ли
условията на V-тия конкурс по програмиране на списание PC Magazine Bulgaria?
Ако не сте, направо сте изтървали! В условията на задачите пише: /цитирам/
"Решенията на задачата трябва да включват блок-схема на алгоритъма
на решението на един от следните езици - C, C++, Basic, Pascal".
Каква интересна терминология! Какъв прекрасен изказ! Дали пък "блок-схемите"
не са нововъведение в последните версии на езиците за програмиране C, C++,
Basic и Pascal? Аз, като прост програмист потърсих в документациите на Mic-
roft и Inprise. Ама йок, това е останало недокументирано! Гледам аз в речни-
ка и кво да видя: "блок-схема на алгоритъм (program flowchart) - схематично
представяне на структурата на една програма, показващо действията,изпълнява-
ни от програмата, и реда на изпълнението им. Блок-схемата се състои от стан-
дартни блокчета и свързващи линии между тях. За яснота линиите могат да бъ-
дат със стрелки ...и т.н. и т.н.". Сега вече разбирам до каква степен компю-
търно неграмотни са тези, които пишат статията. Не се знае кой е неграмотни-
ят, но това което са публикували в PC Magazine Bulgaria е некадърна излага-
ция пред цяла България. И това, разбира се е не е за пръв път. Миналата го-
дина пак беше допусната същата очебийна грешка в условията. Всъщност реноме-
то на този конкурс-менте падна много миналата година, когато шепа некадърни-
ци бяха допуснати до финалния кръг, а някои от програмите на най-добрите до-
казани специалисти по информатика и програмиране "бяха пратени на мама си",
поради небрежността и некадърността на проверяващите. И докога ще продължа-
ва това? Докога този конкурс-мафия, провеждащ се от разни случайни недодяла-
ни люде ще публикува неграмотни условия и ще оценява решенията както му дой-
де? Аз предлагам този път направо да теглим томбола кой ще се класира за фи-
налния кръг, а там да хвърляме чоп. Така ще е по-честно.
И няма смисъл да се мъчите да проследите писмото. Аз и без това никога по-
вече няма да участвам във вашия конкурс-томбола,пък и кой съм няма значение.
Заключение (Infoman)
ÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄ
Редакцията на INFOMAN ще е много благодарна на всички абонати на списани-
ето които ни изпращат статии, задачи и други материали за публикуване.
Не забравяйте, че информатиката е основата на програмирането и че всички
програмисти, които не са добри информатици са си чисти занаятчии!
Учете информатика. Тя е същината на компютърните науки.
Успех на всички информатици!
File List:
infoman12.txt
camelot2.pas
create.pas
acm.txt
picture.pas
tri.pas
zala.pas