Ако обичате задачите по информатика,
ако искате да влезете в отбора по програмиране на ПУ,
да спечелите награди
и да се запознаете с Ваши колеги...
ПРАВИЛА:
Право на участие имат всички студенти от Пловдивски университет.
Всеки месец ще бъдат публикувани по три задачи, като срокът за решаването им е 30 дни. Допустими езици за програмиране са Pascal u C++ (допустими са и Delphi и MS Visual C++, но програмата трябва да е конзолна). Решенията трябва да включват:
* по един .EXE файл за всяка от решените задачи (тези файлове ще бъдат тествани)
* сорс-кода на програмите, като при компилирането му не трябва да има разлика с .EXE файла
* текстов файл съдържащ трите имена, ЕГН, фак. номер и специалност на студента-участник.
* по желание описание на използвания алгоритъм - също в текстов файл (не се оценява)
Всяка от задачите се проверява с 10 теста, като за всеки тест се дават по 10 точки. Програмата не трябва да извежда нищо на екрана, а единствено да чете от входния файл данни (един пакет във всеки входен файл), да извърши нужните изчисления и да запише резултата в изходния файл. Всякакви изключения от това правило, въвеждане от клавиатурата и потребителски интерфейс НЯМА да бъдат толерирани! При грешен формат на изхода или сгрешено име на изходния файл точките се намалят на половина и участникът губи право на бонуси за съответната задача. Забранява се и запис на диска, като изключение прави еднократния запис на изходния файл.
Бонусите са следните:
* за всяка задача с 10 от 10 верни отговора, точките се утрояват (300 точки)
* за всяка задача с поне един работещ тест, се дава бонус от 10 точки.
* за три напълно работещи задачи - бонус от 70 точки.
Така максималният брой точки за една задача е 310, а за съответния месец - 1000 т.
За всеки тест се получават или 10 точки при вярно решение, или някое от следните съобщения:
* Wrong Answer (WA) - грешен отговор, 0 точки
* Time Limit Exceeded (TL) - надвишен времеви лимит, 0 точки
* Run-Time Error (RT) - грешка по време на изпълнение на програмата, 0 точки
* Wrong Format (WF) - грешен формат на изходния файл, 0 или 5 точки по преценка на журито
Задачите се оценяват на компютър с процесор Intel Celeron 400 MHz под операционна система Windows.
Всички решения, както и въпроси по задачите изпращайте на адрес psabev@bulgaria.com.
Размерът на всички изпратени файлове трябва да е не по-голям от 1 MB.
ЗАДАЧА 1. Прости числа (PRIMES.EXE)
При зададено число К, изведете К-тото по ред просто число.
Ограничения: 0 < К < 1 000 000
1 сек. за работа на програмата
Вход: Във файлът PRIMES.INP е записано единствено число K.
Изход: Във файлът PRIMES.OUT запишете единствено число - К-тото поред просто число.
Примери:
PRIMES.INP | PRIMES.OUT |
1 | 2 |
PRIMES.INP | PRIMES.OUT |
3 | 5 |
ЗАДАЧА 2. Художествена галерия (GALLERY.EXE) В художествена правоъгълна галерия с МхN квадратни стаи са изложени картини на различна стойност. Във всяка от квадратните стаи или е изложена точно една картина, или е поставена алармена инсталация. От всяка стая може да се премине в съседните й.
Крадец влиза в стая (1,1) и трябва да излезе през стая (M,N). За да не задейства алармената инсталация, той трябва да минава през всяка стая най-много по веднъж, като задължително не трябва да преминава през квадратна стая, в която няма картина.
Целта е да заграби "плячка" с максимална стойност, като няма ограничение в броя картини, които крадецът може да открадне.
Ограничения: 0 < M,N < 20
Цената на една картина е не повече от 100 000.
10 сек. за работа на програмата
Вход: На първият ред на файла GALLERY.INP са записани числата N и M.
На всеки от следващите N реда са записани по M числа - цените на картините.
Ако цената на дадена картина е 0, това означава, че в съответната стая няма картина, а алармена инсталация. През такива стаи не бива да се преминава.
Изход: Във файлът GALLERY.OUT запишете единствено число - максималната "плячка", която би могъл да вземе крадеца - сума от цените на всички заграбени картини.
Примери:
ALLERY.INP | GALLERY.OUT |
5 7 2 3 0 4 0 10 5 1 1 7 20 3 5 6 9 7 1 2 3 4 8 8 0 0 3 4 0 0 5 6 7 9 10 3 100000 | 100151 |
ЗАДАЧА 3. С хода на коня (HORSE.EXE) Да се обиколи шахматна дъска с хода на коня, при зададена начална позиция на коня, като фигурата трябва да премине през всяко поле точно по веднъж.
Ходът на коня е Г-образен и представлява преместване с 2 позиции по едната ос и 1 позиция по другата.
Дъската е стандартна шахматна дъска с размери 8х8.
Ограничения: 1 сек. за работа на програмата
Вход: Файлът HORSE.INP съдържа два символа, указващи началните координати на коня.
Първият символ е главна буква от A до H, а вторият - цифра от 1 до 8
Изход: Файлът HORSE.OUT съдържа 63 реда, съдържащи по два символа, указващи пътя на коня.
HORSE.INP | HORSE.OUT |
B2 | D3 B4 C6 ... |
УСПЕХ!