СЪСТЕЗАНИЕ ПО ПРОГРАМИРАНЕ

Ако обичате задачите по информатика,
ако искате да влезете в отбора по програмиране на ПУ,
да спечелите награди
и да се запознаете с Ваши колеги...

ПРАВИЛА:

Право на участие имат всички студенти от Пловдивски университет.
Всеки месец ще бъдат публикувани по три задачи, като срокът за решаването им е 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 запишете единствено число - максималната "плячка", която би могъл да вземе крадеца - сума от цените на всички заграбени картини.

Примери:

 

GALLERY.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 ...

 

УСПЕХ!