ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА ШУМЕН’03

22 ноември 2003

ТЕМА ЗА 11–12 КЛАС (ГРУПА A)

Задача A1.  НУБИЯ

Банкнотите на нубийските долари са напечатани във всички целочислени положителни номинали.  В един нубийски магазин има купувач, който разполага с банкноти от a₁, a₂, ..., a_m долара, а продавачът – с банкноти от b₁, b₂, ..., b_n долара. Измежду банкнотите, както при купувача, така и при продавача, може да има и с еднаква стойност. За всяко цяло положително число долари в магазина има стока с тази цена. Напишете програма NUBIA.EXE, която пресмята цената на най-скъпата стока, за която купувачът има достатъчно пари, но не може да я купи, защото продавачът не е в състояние да му върне точното ресто?

Входните данни се четат от стандартния вход. На първия ред е записан броят m, (1 <= m <= 100 000), следван от a₁, a₂, ..., a_m, а на втория ред – броят n, (1 £ n £ 100 000), следван от b₁, b₂, ..., b_n. Всичките стойности на банкноти са цели положителни числа,  по-малки от един милион и са разделени с интервали. Изходните данни трябва да бъдат отпечатани на стандартния изход като едно цяло число. Ако задачата няма решение, трябва да се изведе числото 0.

Пример

Вход

3 3 5 7

2 2 6

Изход

14

ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА ШУМЕН’03

22 ноември 2003

ТЕМА ЗА 11–12 КЛАС (ГРУПА A)

Задача A2.  ГОНИТБА

След поредната дълга и безсънна нощ прекарана пред компютъра и запълнена с игри от всякакъв вид и калибър, Геймърчо Калпазански заспал върху меката и удобна клавиатура. Геймърчо попаднал в един геймърски кошмар. Въоръжен само с моторна резачка, на която й бил свършил бензина, на хексагонално бойно поле (образувано от шестоъгълници), бил подгонен от група извънземни. Освен това, било непрогледна нощ и Геймъчо не виждал нищо, включително, как се движат извънземните, той знаел само началното им положение. На Калпазански не му оставало да прави нищо друго, освен да печели време и да се надява, че ще дойде помощ. Но той бил много уморен (все пак бил заспал от умора) и въобще не го бивало в логическите игри. Вие трябва да му помогнете, да не бъде хванат от извънземните, колкото се може по-дълго време.

Дадена е хексагонална дъска N на M (виж фиг. 1). Дъската е съставена от два вида полета, свободни и препятствия. В полетата, които са препятствия не може да има играч или извънземно. Полетата, които са свободни изискват време за преминаване. Дадени са началните позиции на играча и извънземните. С течение на времето, Геймърчо и извънземните се местят от поле в поле, като за да преминат от едно поле (i, j) в друго съседно на него, се изисква поне време T_i,j, зададено за всяко поле (i, j). Нищо не пречи Геймърчо или извънземно да прекарат повече време в някое поле от необходимото за неговото преминаване. Играчът или извънземните не могат да ходят в полета, които са препятствия. Геймърчо и извънземните се движат едновременно. Ако след време t, Геймърчо се озове в едно поле с извънземно, то Геймърчо е хванат. Геймърчо винаги може да бъде хванат.

Напишете програма CHASE.EXE, която намира максималното време, което Геймърчо може да играе преди да бъде хванат. Отговорът трябва да се основава само върху играта на Геймърчо и да не зависи от играта на извънземните (Геймърчо не ги вижда), тоест както и да играят те, той да не бъде хванат колкото се може по-дълго време.

На фигура 1 е показана хексагонална дъска 6 x 3. Всеки ред на дъската съдържа еднакъв брой шестоъгълничета. Съседни на едно поле са 6-те полета, с които има обща стена (виж фиг. 2)

ВХОД

Първият ред на стандартния вход съдържа три числа N, М, К, които са съответно броят на редовете и колоните на дъската (3 <= N, M <= 100), и броят на извънземните (2 <= K <= 50). Следват N реда с по M символа на всеки ред (между символите няма празно място), които задават вида на полетата на дъската. J-тия символ на I-тия ред задава състоянието на позиция (I, J). Ако символът е ‘X’, това означава поле препятствие. Иначе полето е свободно и на съответното място има цифра от ‘1’ до ‘9’, която задава времето за преминаване на полето. На следващия ред има две числа X и Y (1 <= X <= N, 1 <= Y <= M), задаващи началните позиции на играча. Следват K реда, всеки съдържащ две числа X_i и Y_i, задаващи началната позиция на i-тото извънземно (1 <= X_i <= N, 1 <= Y_i <= M). Никое извънземно не е в началното поле на играча.

ИЗХОД

На единствения ред на стандартния изход програмата трябва да изведе едно число, равно на максималното време, което Геймърчо може да играе, преди да бъде хванат, независимо как играя извънземните.

ПРИМЕР

Вход

4 4 2

1123

123X

4XX3

241X

1 2

4 1

4 3

Изход

6

ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА ШУМЕН’03

22 ноември 2003

ТЕМА ЗА 11–12 КЛАС (ГРУПА A)

Задача A3.  ДЕЛИМОСТ

Дадени са N естествени числа (1 <= N <= 2¹⁵), всяко не по-голямо от 2²⁰. Да се напише програма DIV.EXE, която избира M (1 <= М <= N) числа измежду дадените, така че N да дели сумата им.

Програмата въвежда данните си от единствения ред на стандартния вход. Първото число от реда е N, след което следват N естествени числа не по големи от 2²⁰ , разделени с по един интервал.

Стандартният изход на програмата трябва да се състои от един ред. Ако задачата няма решение, програмата трябва да изведе числото –1. Ако задачата има решение, първото число от изходния ред е М, след което трябва да следват M-те избрани от програмата числа, разделени с по един интервал. Ако съществува повече от едно решение, трябва да се изведе едно, кое да е решение на задачата.

ПРИМЕРИ

вход             изход

3 2 2 1                 2 1 2

вход изход

5 1 2 3 4 1             2 2 3