INFOMAN брой 17
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
ÞÛÛÛ ÞÛÝ ÛÝ ÞÛÛÛÛÛ ÛÛÛÛÛ ÞÛÛ ÛÛÝ ÞÛÛÝ ÞÛ ÛÝ
ÞÛ ÞÛÛÝ ÛÝ ÞÛ ÞÛ ÛÝ ÞÛÞÛ ÛÝÛÝ ÞÛ ÛÝ ÞÛÛÝ ÛÝ
ÞÛ ÞÛ ÛÝ ÛÝ ÞÛ ÞÛ ÛÝ ÞÛ ÛÜÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ ÛÝ
ÞÛ ÞÛ ÛÝÛÝ ÞÛÛÛÛ ÞÛ ÛÝ ÞÛ ÞÛÝ ÛÝ ÞÛÛÛÛÛÛÝ ÞÛ ÛÝÛÝ
ÞÛ ÞÛ ÛÛÝ ÞÛ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÛÝ
ÞÛÛÛ ÞÛ ÛÝ ÞÛ ÛÛÛÛÛ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
ЕДИНСТЕНОТО В БЪЛГАРИЯ СПИСАНИЕ ЗА ЗАДАЧИ ПО ИНФОРМАТИКА
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
E-mail: ÜÜ ÜÜÜÜ Home Page:
infoman@musala.com Û Û http://infoman.musala.com/
брой 1/2000 (17) Û Û Март, 2000
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
----------------------------------------------------------------------------
СЪДЪРЖАНИЕ
ТЕМА АВТОР
1. Интро (Infoman)
2. Зимни Математически Състезания'2000 Мартин Русков
3. XVI Олимпиада по информатика - 2ри кръг (София) Мартин Русков
4. XVI Олимпиада по информатика - 3ти кръг Мартин Русков
5. Задачка (Infoman)
6. Заключение (Infoman)
----------------------------------------------------------------------------
Интро (Infoman)
Здравейте читатели на Инфоман. Имам добра новина за вас - Инфоман про-
дължава да излиза. И все пак с цената на някои промени. Вече Светлин Наков
не е главен редактор. Добре известният на всички ни информатик се отдаде на
заслужена пенсия (по-точно започна да си изкарва хляба с информатика.) Това
неизбежно ще се случи на всеки един от нас някой ден и рано или късно ще
трябва да остави задачите по информатика и да се захване с комерсиално про-
грамиране. Така или иначе за неопределен период от време аз ще издавам Инфо-
ман. Това няма да промени много неща - пак ще публикуваме решенията на зада-
чите от състезанията в България (а може би и някои в чужбина,) пак ще има ня-
кои интересни задачи с ефективни решения, пак ще ви съобщаваме важни новини
за състезанията (стига и ние да ги знаем) и, не на последно място, пак ще се
надяваме вие да ни пишете.
Новостта, която се надявам да въведа, е задачите, които се публикуват
тук да не са само на ниво състезания по информатика за средношколци, но да
има задачи за по-малките или по-нови програмисти, които сега навлизат в деб-
рите на алгоритмите, както и за студенти, които отдавна вече не пишат задачи,
в които се използва само алгоритъма на Дейкстра (всъщност в последното не
съм сигурен.) Общо взето надявам се с общи усилия да направим списанието ин-
тересно за всички, които се занимават с програмиране.
По-конкретно, бих се радвал, ако ми изпратите задачите от втори и трети
кръг на олимпиадата по информатика за вашите град и възраст, ако тук ги няма
публикувани. Дори да не можете да ми изпратите решения, изпратете условията
и аз ще се опитам да ги реша. Ако имате алтернативни решения на задачите,
публикувани тук, с удоволствие ще публикуваме и тях. Аз, новият главен ред-
актор, се казвам Мартин Русков. Уча в Софийската Математическа Гимназия и
съм 10-ти клас. Занимавам се с програмиране от доста малък, но истински алго-
ритми (разбирай нещо по-сложно от сортиране и рекурсия) уча от 4 години.
Всъщност надеждата ми е голяма част от публикуваните материали да не бъдат
писани от мен, но това ще стане ясно с течение на времето.
29.2.2000
Мартин Русков
(нов) главен редактор на списание INFOMAN
----------------------------------------------------------------------------
Зимни Математически Състезания'2000 Мартин Русков
Редовното ЗМС се проведе тази година в Русе. Както обикновенно, отново
имаше организационни проблеми. Гостите на града бяха настанени в доста долно-
пробни общежития (мога само да зъжалявам хората, които прекарват там цяла
учебна година.) Самото състезание също се проведе при крайно лоши условия.
Освен редовното закъснение (с което всички вече свикнахме,) имаше проблеми и
със задачите и предаването. За съжаление доц. Рахнев не дойде и всички учени-
ци от 8 до 12 клас решаваха едни и същи задачи. Като резултат, в класирането
при по-малките имаше отбори, които бяха решили само част от една задача (по
правилата на ACM, по които се провеждат и ЗМС това е невъзможно - вж бр.8)
Друг проблем беше,че групата 10-12 клас беше разделена в две сгради и понеже
нямаше начин двете сгради да осъвместяват навреме обявените резултати, резул-
татите станаха известни чак след края на състезанието. Но както вече казах,
ние сме свикнали и можем само да благодарим на Краси Манев, че се опита да
направи нормално състезание в ненормалните условия в България.
Авторските решения и тестовете на задачите могат да се намерят (без
обяснение и доказателство) на:
http://debian.fmi.uni-sofia.bg/sc-club
а аз ви предлагам алтернативни. Файловете са hacker.c и snow.c (от Мартин
Русков) и text.c(от Мартин Вълканов).Другите две задачи - bibliot.c и book.c,
ще бъдат публикувани в брой 18 заради малки организационни проблеми.
----------------------------------------------------------------------------
XVI Олимпиада по информатика - 2ри кръг (София) Мартин Русков
На 27.2.2000 се проведе общинския кръг на олимпиадата по информатика в
София. Имаше една задача с 2 подусловия. Кръгът беше организиран доста лошо
и, както ще видите от условието, нямаше зададени стандартни вход и изход. Ня-
ма начин и повечето от вас да не забележат, че б) подусловие може да бъде
"решено" само с едно извеждане на намерено по друг начин или дочуто от някъ-
де число. Задачите също бяха лесни и затова голямото предизвикателство се се
сведе до това кой ще напише най-ефективен алгоритъм.Предлагам ви най-доброто,
което аз можах да измисля.Подусловие а) е във файла flowa.c. За б) съм напис-
ал две решения като всъщност flowb2.c е усъвършенстване на алгоритъма от
flowb1.c.
----------------------------------------------------------------------------
XVI Олимпиада по информатика - 3ти кръг Мартин Русков
Мина и трети кръг на олимпиадата. Задачите бяха 3 и бяха доста разноо-
бразни, както и непосредственте реакции на участващите.Имаше от типа игри на
дъска, за които се търси най-кратък път,един стандартен алгоритъм и една поч-
ти нерешима за 4 часа задача (това все пак е мое лично мнение.)Приложили сме
файловете game21.pas и 4vyrha.pas (от Светлин Наков) и off.c (от Мартин
Русков). Третата задача ще бъде публикувана в следващия брой, заради труд-
ността и и защото този брой доста се забави и бързаме да го издадем.
----------------------------------------------------------------------------
Задачка (Infoman)
От този брой нататък имаме намерение да даваме по една задача. Повечето
от тях няма да имат еднозначен отговор и решенията ще се оценяват по скорост,
по точност или брой получени решения и може би дори по компактност. Това ес-
тествено значи,че ще има няколко класирания,но това няма значение т.к. и без
това засега нямаме награден фонд :(. Ето я и първата задача:
Даден е полиомът
P(x) = a[0]*x^n + a[1]*x^(n - 1) + ...+ a[n-1]*x + a[n]
Да се разложи доколкото е възможно.
Входът се състои от n+1 реални числа разделени с интервали, като на i-то мяс-
то стои a[i]. Като изход да се изведе разложения полином.
Пример:
Вход: 1 1 -2
Изход: (x+2)(x-1)
----------------------------------------------------------------------------
Заключение (Infoman)
Надявам се когато и аз изоставя алгоритмите да се намери и някой друг
инфоман, който да се захване със единственото (поне доколкото знам) списание
за информатика в България.А дотогава да си пожелаем успешна и приятна работа.
А-а-а, и надявам се стилът ми да не е много труден за четене... :)
----------------------------------------------------------------------------
File List:
game21.pas
flowa.c
flowb1.c
flowb2.c
4vurha.pas
hacker.c
infoman17.txt
off.c
snow.c
sqr.c
text.c