zadachi

Задача 1: 4.10.2002 г.

Задача 1А - за по-напредналите и всички, които са участвали през
миналата година в студентски състезания по програмиране

Да се напише програма, която намира първия неповтарящ се символ
в даден низ.

Име на входния файл: CS.INP
Описание на входния файл:
Файлът съдържа един низ, в който може да се срещат произволни
символи от ASCII таблицата. Няма ограничение за дължината на низа.
Име на изходния файл: CS.OUT
Описание на изходния файл:
Файлът съдържа един символ - първия неповтарящ се символ или
"none" ако няма такъв символ.

Примерен входен файл:
tatoo

Изходен файл за примерния входен файл:
a

---------
Задача 1B - за студенти 1 курс и студенти, които досега не се
участвали в състезания по програмиране

Да се напише програма, която намира първия неповтарящ се символ
в даден низ.

Име на входния файл: CS.INP
Описание на входния файл:
Файлът съдържа един низ (не по дълъг от 255), в който се срещат
символи с ASCII кодове между 32 и 255.
Име на изходния файл: CS.OUT
Описание на изходния файл:
Файлът съдържа един символ - първия неповтарящ се символ или
"none" ако няма такъв символ.

Примерен входен файл:
tatoo

Изходен файл за примерния входен файл:
a

[Д.Монтаг, Н.Суджанен, Интервюта за програмисти,ИК "Софтех",София,2002,
стр.99]
-------------------------------------------------------------------
Задача 2: 11.10.2002 г.
Задача 2А - за по-напредналите и всички, които са участвали през
миналата година в студентски състезания по програмиране

Lonesome knight

This task is very simple. You are to determine how many fields on
the chessboard are under attack of the knight. There are no other
chess pieces on the board. Just in case we will remember you how
knight moves. First it moves on two fields in horizontal or vertical
direction and then on one more field perpendicular to the starting
direction.

Input - file knight.inp

The first line of the file contains the only number N, 1 <= N <= 100 —
the number of the test cases. Then N lines follow. Each of these lines
contains two characters (lowercase letter from 'a' to 'h' and integer
from 1 to 8) — usual chess description of the field where knight is placed.
Letter denotes horizontal position and number denotes vertical position.

Output - file knight.out

Output file should contain exactly N lines. Each line should contain the
only integer - number of the fields on the chessboard that are under attack
of the knight.

Sample Input

3
a1
d4
g6

Sample Output

2
8
6
[http://acm.timus.ru/problem.asp?id=1197]
------
Задача 2B - за студенти 1 курс и студенти, които досега не се
участвали в състезания по програмиране

Дадена е редица от цели числа a(i) с дължина n (т.е. 0<i<=n).
Да се намери най-малкото число i за което a(i)=a(i+1)+a(i+2).

Име на входния файл: seqm.INP
Описание на входния файл:
Първият ред на файла съдържа цялото число n - дължината на редицата
(2<n<10000). На следващите редове са дадени членовете на редицата,
отделени с интервал или край на ред.

Име на изходния файл: seqm.OUT
Описание на изходния файл:
Файлът съдържа единствено число - решението или 0 когато задачата няма
решение.

Примерен входен файл:
5
3 8 5 3 1

Изходен файл за примерния входен файл:
2
-------------------------------------------------------------------
Задача 3: 18.10.2002 г.
Задача 3А - за по-напредналите и всички, които са участвали през
миналата година в студентски състезания по програмиране

Colored bricks

There are lots of cubic bricks in the kindergarten. Children like to
build toy brick towers and then to drop them. It is clear that the higher
tower has been built the more interesting it is to drop it. The tower is
built by placing bricks one onto another and aligning their sides. The
tower is based on one brick. Thus the height of a tower is the number of
the bricks it is built of.

Each side of a brick is painted in one color. So the kids build colored
towers. In order to train the children's sense of beauty nannies teach
them to build the towers in such a way that each side of the tower would
be one-color. Thus the kids would like to build a tower with one-color
sides as high as possible.

Every nanny can easily solve this problem. Try your best to do it as well.

Input file - bricks.inp

The first input line contains a number N (1 < N <= 103) - the number of
bricks. The next N lines contain descriptions of bricks. Each brick is
described with a string of 6 capital latin letters denoting the color of
the corresponsding side (A - Azure, B - Blue, C - Cyan, G - Green, O -
Orange, R - Red, S - Scarlet, V - Violet, W - White, Y - Yellow). The
colors of the sides are given in the following order: front, right, left,
rear, top, bottom. A brick never has two sides of the same color.

Output file - bricks.out

Output file should contain the only number - the maximal height of a toy
tower that can be built of the given brick set.

Sample Input

4
GYVABW
AOCGYV
CABVGO
OVYWGA

Sample Output

3
[http://acm.timus.ru/problem.asp?id=1127]
------
Задача 3B - за студенти 1 курс и студенти, които досега не се
участвали в състезания по програмиране

Редици еднакви числа

Дадена е редица от N цели неотрицателни числа (N<10001).
Да се намери най-дългата подредица, съдържаща еднакви числа.

Вход:
Първият ред на файла съдържа число N - дължината на редицата.
Следващите редове съдържат точно N цели числа.
Последният ред на файла съдържа числото 0.

Име на входния файл: seqe.inp

Изход:
Ред на файла съдържа дължината на намерената подредица.

Име на изходния файл: seqe.out

Примерен входен файл:
16
1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 8
4
1 2 3 4
0

Изходен файл за примерния входен файл:
14
1

[http://www.math.bas.bg/~nkirov/2002/comp_ex.txt]
-------------------------------------------------------------------
Задача 4: 25.10.2002 г.
Задача 4А = задача 4В.
Дължина на редица
За всяко естествено число a дефинираме редицата
a_0 = a, a_1, a_2, ... a_n, ...
по правилото: ако a_n е четно число, то a_(n+1) = a_n/2, в
противен случай a_(n+1) = 3a_n + 1. Ако за някое n a_n = 1, то
тази стойност се счита за край на редицата (a_i означава a с
долен индекс i). Да се намери най-дългата редица за числата от
зададен интервал.

Име на входния файл: lenseq.INP
Описание на входния файл:
Файлът съдържа две цели числа a и b - зададния затворен интервал
(0<a<b<1000000).

Име на изходния файл: lenseq.OUT
Описание на изходния файл:
Съдържа едно число от зададениия интервал, чиято редица е най-дълга.

Примерен входен файл:
10 12

Изходен файл за примерния входен файл:
11

[Виж http://acm.uva.es/p/v1/100.html]
-------------------------------------------------------------------
Задача 5: 01.11.2002 г.
Задача 5А = задача 5В.

[http://acm.uva.es/p/v103/10390.html]
-------------------------------------------------------------------
Задача 6: 08.11.2002 г.

Целочислени траектории

Дадени са n цели числа (точки от числовата права) a_1, a_2, ..., a_n и още две числа (точки ) B и E. Траектория на точката B с дължина m наричаме редица от цели числа (точки) b_0=B, b_1, b_2, ..., b_m, получена по следното правило: b_(i+1) е симетрична точка на b_i относно някоя (точка) измежду дадените точки a_1, a_2, ..., a_n. Да се намери най-малкото разстояние между точка Е и края на траектория на B с дължина m. (a_ i означава a с долен индекс i).

Вход:
Първият ред на файла съдържа число n - дължината на редицата a_1, a_2, ..., a_n. Следващите редове съдържат точно n цели числа - елементите на редицата. На следващия ред са дадени двете числа B и E и дължината на траекториите m.

Име на входния файл: intraj.inp

Изход:
Едно цяло число - най-малкото разстояние между точка Е и края на траектория на B с дължина m.

Име на изходния файл: intraj.out

Примерен входен файл:
2
0 1
5 3 4

Изходен файл за примерния входен файл:
0

[Частен случай на http://www.math.bas.bg/~keleved/z-3-2002.htm]
-------------------------------------------------------------------
Задача 7: 15.11.2002 г.
Simply Subsets

[http://acm.uva.es/p/v4/496.html]
-------------------------------------------------------------------
Задача 8: 22.11.2002 г.
Square

[http://acm.uva.es/p/v103/10364.html]
-------------------------------------------------------------------
Задача 9: 29.11.2002 г.
Blocks

[http://acm.uva.es/p/v103/10365.html]
-------------------------------------------------------------------
Задача 10: 6.12.2002 г.
Новата игра на домино

В една детска градина имали няколко домина, плочките на които били размесени в една по-голяма кутия. Тъй като на децата им било омръзнало да играят на домино, учителката измислила нова игра: дала на всяко дете по равен брой плочки и за победител се обявявало това дете, което подреди най-дълга редица от дадените му плочки. Правилото за нареждане било това от играта на домино, т.е. две плочки могат да бъдат една до друга, ако на долепените страни на плочките има едно и също число. Разбира се, играта "не била честна", защото дължината на редицата зависела не само от умението на детето, а и от вида на плочките, които му са се паднали при раздаването. Е, всяко дете знаело, че дори в играта "Стани богат" на някои им се падат по-лесни, а на други по-трудни въпроси. Помогнете на всяко дете да подреди най-дългата възможна редица от плочките, които е получило.

Входен файл - domino.inp

Всеки пример започва с цяло число N (1<N<1000) и след него N двойки цифри, между 0 и 6, определящи вида на плочките, получени при раздаването. Между двете цифри в двойката няма интервал. Файлът съдържа няколко примери и последният ред на файла съдържа числото 0.

Изходен файл - domino.out

За всеки пример от входния файл се записва едно число - дължината на най-дългата редица, която може да се получи от дадените плочки.

Примерен входен файл:
5
11 22 33 12 23
3
54 16 23
10
66 65 50 04 11 22 33 12 33 03
0

Изходен файл - решение с данни от примерния входен файл:
5
1
6
-------------------------------------------------------------------
Честит празник 8 декември !
Весела Коледа !
Късмет на сесията !

Следваща задача - на 24.01.2003 г.

Край на файла.