INFOMAN брой 14
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
ÞÛÛÛ ÞÛÝ ÛÝ ÞÛÛÛÛÛ ÛÛÛÛÛ ÞÛÛ ÛÛÝ ÞÛÛÝ ÞÛ ÛÝ
ÞÛ ÞÛÛÝ ÛÝ ÞÛ ÞÛ ÛÝ ÞÛÞÛ ÛÝÛÝ ÞÛ ÛÝ ÞÛÛÝ ÛÝ
ÞÛ ÞÛ ÛÝ ÛÝ ÞÛ ÞÛ ÛÝ ÞÛ ÛÜÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ ÛÝ
ÞÛ ÞÛ ÛÝÛÝ ÞÛÛÛÛ ÞÛ ÛÝ ÞÛ ÞÛÝ ÛÝ ÞÛÛÛÛÛÛÝ ÞÛ ÛÝÛÝ
ÞÛ ÞÛ ÛÛÝ ÞÛ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÛÝ
ÞÛÛÛ ÞÛ ÛÝ ÞÛ ÛÛÛÛÛ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
ЕЛЕКТРОННО СПИСАНИЕ ЗА ЗАДАЧИ ПО ИНФОРМАТИКА
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
E-mail: Ü Ü Ü Home Page:
infoman@musala.com ßÛ Û Û http://infoman.musala.com/
брой 14 - 14 Юни, 1999 Û Û (c) INFOMAN Team - Bulgaria
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
СЪДЪРЖАНИЕ
ÄÄÄÄÄÄÄÄÄÄÄÄ
ТЕМА АВТОР
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄ
1. Интро от главния редактор - остаряхме (Infoman)
2. Подборният кръг - решение на една от лесните задачи Star Gruhtar
3. Подборният кръг - решение на една от трудните задачи Мартин Русков
4. Студентското състезание в Благоевград - някои задачи Преслав Наков
5. Нещо и от пролетен турнир по информатика - Ямбол Кристиян Хараламбиев
6. Една класическа задача за дупка сред полето Светлин Наков
7. Задача за числа (неизвестен автор)
8. Финали на студентските състезания - коментари Пиянидиот Досвирков
9. Заключение (Infoman)
Интро от главния редактор - остаряхме (Infoman)
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄ
Повече от месец закъсня и този брой на нашето любимо списание INFOMAN.
И този път виновникът пак е главният редактор - Светлин Наков от Велико Тър-
ново. Като че ли когато човек осъзнае, че всичко с което се е занимавал до
момента остава един спомен в миналото, когато отмине и последното му състе-
зание, когато се налага да започне да се занимава със съвсем "занаятчийска"
работа вместо да измисля сложни алгоритми и когато е постигнал една от най-
важните си цели - да взеле без изпит във ВУЗ, ентусиазмът му да издава елек-
тронни списания за задачи по информатика лека-полека загасва. Ето защо през
периода на последните пет важни състезания INFOMAN не излезе и се натрупаха
доста нерешени задачи.И отново се получи старата позната ситуация - едни да-
ват задачите, а други не могат да ги решат и няма кого да попитат. Все пак
не сме зарязали всичко и си запазваме намерението което имаме от преди пове-
че от година да "изправим тази неправда". Просто напоследък главният редак-
тор, който движи цялата машина на INFOMAN беше много зает и нямаше време да
реши задачите,за които не се получиха решения и да публикува натрупаните ма-
териали. Само който не е завършвал училище с осигурено бъдеще не знае какво
означава бално настроение, а и после тези състезания през 2-3 дни, трябва и
да се работи, трябва да се ходи и по жени, и по купони, трябва балове да се
празнуват, и ... за INFOMAN не остава време. Но ...страшно няма, само да се
поосвободи малко нашият главен редактор и всички ще си е по старому. И рабо-
тата не е малко все пак - 6 задачи от подборния кръг в София, 7 от Благоев-
градското сътезание, 3 от финалния кръг от конкурса на PC Magazine Bulgaria
и 3 от Ямбол. Независимо от подкрепата на читателите все още нямаме решения
на всички задачи,но по въпроса се работи. В настоящия 14 брой ви предлагаме
решения на част от задачите от тези състезания, а останалите ще намерите в
следващите броеве. Очаква се към края на месеца да излези и 15 брой. Трябва
да поздравим и виновникът за съществуването на това списание INFOMAN, който
днес (14 юни) има рожден ден и пише в освободилата се "времева дупка" след
завръщането си от концерта на MetallicA настоящия брой 14 на 14 юни рано-ра-
но сутринта (или пък късно вечерта, зависи от гледната точка), и да му поже-
лаем още много, много успехи. Честито!
Остаряхме, остаряхме, училище завършихме, главният ни редактор стана на
19, вече не се интересува от информатика толкова много, захванал се е с ра-
бота, със занаятчийство (програмиране за пари) и вече няма да се учудя ако
INFOMAN си потърси друг главен редактор. (Предложения се приемат).
Измина и последната контрола за Балканската олимпиада по инофматика, ко-
ято ще се проведе в Янина, Гърция през Август. Националнията отбор,който ще
представя страната ни на това престижно международно състезание по информа-
тика е в 4-членен състав:
1. Мартин Христов - Стара Загора
2. Боян Кроснов - Стара Загора
3. Светлин Наков - Велико Търново
4. Кристиян Хараламбиев - Бургас
Няма как да не изкажем специалните поздрави от екипа на INFOMAN на учителя
на Старозагорския отбор - г-н Павлин Пеев, който успя да издигне на първите
места своите състезатели не само на подборния кръг, но на следващщите състе-
зания.
Е, стига сме ви отегчавали с наште проблеми, нека да преминем към същина-
та - решенията на задачите, с които разполагаме.
Подборният кръг - решение на една от лесните задачи Star Gruhtar
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄ
Предлагам ви две решения на задачата лесната задача "максимален квадрат"
от подборния (финален) кръг на олимпиадата по информатика за ученици. Поне-
же задачата беше дадена в лесния й вариант до N=60,тя може да се реше с оче-
видния алгоритъм, който му хрумва на всеки без да се замисля - O(N^4). Оба-
че ако искаме нашето решение да работи до N=200, трябва да подходим по друг
начин - да измислим алгоритъм със сложност O(N*N*N). Условието на задачата,
решение и описание на решението можете да намерите във файловете sqr1.pas -
баламско решение и sqr.pas - хитро решение.
Подборният кръг - решение на една от трудните задачи Мартин Русков
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄ
Много благодарим на Мартин Русков, че ни изпрати решение на една от най-
трудните задачи - "гледна точка". Трябва да отбележим, че въпреки, че реше-
нието по идея е вярно и много бързо, то би могло да пропусне някои "трудни"
тестове поради загуба на точност, понеже работи с реални числа за изчислява-
нето на тангенс. Едно възможно подобрение е да се пазят числата като обикно-
вена дроб. Именно поради тази малка грешка много участници не можаха да из-
карат максималния брой точки на тази задача по време на олимпиадата. Всичко
останало относно тази задача ще намерите във файла gle.c.
Студентското състезание в Благоевград - някои задачи Преслав Наков
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄ
Благодарим на Преслав Наков, автора на известната книга "Основи на ком-
пютърните алгоритми", за решенията на две от задачите от студентското състе-
зание в Благоевград.Решенията ще намерите във файловете inter.pas и red.pas.
За задачата за редицата (red.pas) трябва да допълним анализа на автора,като
отбележим, че задачата винаги има решение и това следва от принципа на Дири-
хле.
Нещо и от пролетен турнир по информатика - Ямбол Кристиян Хараламбиев
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
Благодарим и на нашия редове читател и фен, който е и член на националния
отбор на България за Балканиадата по информатика Кристиян Хараламбиев за ре-
шението на една трудна задача - задачата за низовете от пролетния турнир по
информатика който се проведе в Ямбол. Трябва да отбележим, че въпреки че ав-
торът на решението никъде не го е написал, то всъщност представлява приложе-
ние на мощния метод за решаване на екстремални комбинаторни задачи - динами-
чно оптимиране. Повече коментари - в match.pas.
Една класическа задача за дупка сред полето Светлин Наков
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄ
Задачата, която предлагам на всикчи читатели е стара и класическа, т.е.
често се срещат задачи на нейната основа, например в Ямбол от темата за 8-9
клас. Ето защо смятам, че ще е интересно за читателите да видят едно пример-
но нейно решение. Файлът е maxdupka.pas.
Задача за числа (неизвестен автор)
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
Настина много съжеляваме, но някой ни изпрати тази задача без да си на-
пише вътре името и поради небрежност от наша страна ние изгубихме името на
автора й, защото изтрихме пощата си след като си записахме прикрепените към
писмата файлове. Надяваме се че не сме обидили автора и ще се опитаме таки-
ва проблеми да не се случват отново. Условието на задачата и решението й ще
намерите във файла c2_88.pas.
Финали на студентските състезания - коментари Пиянидиот Досвирков
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
Въпреки, че този материал не се отнася до никоя задача или до решението
й, смятаме че е полезно да се даде малко гласност на една статия с конструк-
тивна критика, изпратена ни от нашият "анонимен" фен - Пиянидиот Досвирков.
Статията, публикувана едно към едно, можете да прочетете във blag99.txt.
Заключение (Infoman)
ÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄ
Информатици български, не се отчайвайте, INFOMAN ще го има и занапред,
информатиката ще я има и занапред, не се отчайвайте,дори и да сте завършили
училище и за вас да са свършили състезанията. Все пак можете да участвате в
конкурсите, които нямат възрастова граница, а един ден ще разберете, ще зна-
нията ви по информатика са много ценни и че именно те ви отличават от обик-
новените занаячии в компютърния бизнес. Успех на всички!
И не забравяйте да изпращате статии за INFOMAN. Само така то ще може да
излиза редовно и да е интересно.
File List:
infoman14.txt
c2_88.pas
gle.c
blag99.txt
inter.pas
match.pas
maxdupka.pas
red.pas
sqr.pas
sqr1.pas