Олимпиада

[Witaliy]

Уважаемые форумчанини!

У меня скоро будет олимпиада из информатики, и я имею два вопроса :
Кто-то имеет ссилки на закачивание книг по подготовке (или по развязыванию задач) из информатики?

Развяжите кто может такие задачи (хоть одну из них...) :

Задача 2. Арифметическое выражение
Задана строка, в которой могут быть только цифры и знаки +, - *, /. Вычислить значение выражения. Результат выполнения каждой операции и окончательный результат является целым числом и по модулю не превышает 30000.
Входные данные: В первой строке входного файла содержится строка символов (цифры и знаки арифметических операций) длиной не более 50-ти без всякого пропуска.
Исходные данные: единственное число - результат выполнения выражения.
Пример входных данных:
2+5*3-8/2
Пример исходных данных:
13

Задача 3. Спираль.
Известно, что квадратная таблица(N на N) заполнена натуральными числами по спирали, например, для N = 5:

1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

Найти число, которое будет находиться в данной таблице на пересечении и той строки и j-того столбца.


Входные данные: В первой строке входного файла содержится три целых числа: NN30000 - размер ква-дратной таблицы, и - номер строки, j -номер столбца, на пересечении которых расположенное искомое число.
Исходные данные: входной файл содержит единственное число - ячейка таблицы, которых находится на пересечении и-го строки и j-го столбца.
Пример входных данных:
5 2 3
Пример исходных данных:
18

Задача 4. Расписание на слагаемые.
Сколькими разными способами можно разложить натуральное число N на слагаемые. Например, число 5 можно разложить 7-ма способами, а именно: 5, 1+4, 1+2+2, 2+3, 1+1+1+1+1, 1+1+1+2, 1+1+3. Заметим, что 2+3 и 3+2 - это один и тот же способ.
Входные данные: В первой строке входного файла содержится единственное натуральное число N<122.
Исходные данные: входной файл содержит единственное целое число - количество разных способов расписания заданного числа на слагаемые.
Пример входных данных: 5
Пример исходных данных: 7




Заранее благодарю !

[mihali4]

А приз, который вам вручат за победу на олимпиаде, вам достанется? Или (по справедливости) с нами поделитесь?
По поводу литературы:
- первая тема в "Общих вопросах Дельфи"
- раздел "Книги" на сайте нашего клуба (ссылочка в самом низу каждой страницы форума, если вы не заметили самого верхнего горизонтального меню, опять-таки на каждой странице)
Туда же - по поводу задач для тренировки...

[Plague]

Хотябы начало решений предложите, я думаю найдется кто подскажет,
что дальше делать.
А по поводу тренировок ищите что нибуть связанное
с "ACM программированием".

[Ламер_001]

вторую задачу сам как то решал в первый раз следующим образом:
все выражение представляем как строку.
1) ищем операцию '*' или '/'
при нахождении выделяем число слева и число справа, одновременно удаляя их из строки вместе с операцией. производим операцию и результат вставляем в строку на место (внимательней с индексами)
2) если не нашли умножения или деления ищем + или - и выполняем то же самое
3) если ни того ни другого нет то имеем решение.

этот метод простой в реализации и наглядности. но очень долго будет работать с длинными выражениями. если необходимо ускорить то используем метод который реализован в компиляторах (соответственно самый быстрый и оптимальный)

всю запись нам надо будет представить в виде дерева где у каждого элемента не более 2 потомков и только 1 родитель (за исключением корня, конечно же)
теперь об элементах дерева: это либо число либо операция. создаем 2 поля - один значение другой операция (0, 1, 2, 3, 4). если операция = 0 то этот элемент является значением иначе - это операция. за корень графа берется либо сложение либо вычитание. делим строку в данном месте на 2 части. из них рекурсивно тем же методом получаем потомков. что бы разбить очередную строку на потомков ищем в ней операцию (причем операции + и - имеют больший приоритет), если же не нашлось таковой то значит это число.
после формирования всего дерева начинаем просмотрю "вглубину". ищем последнюю операцию. берем 2х ее потомков, производим операцию и переписываем значение. делаем до тех пор пока корень не станет числом. он и будет значением.

со спиралью задачу тож когда то решал. точное решение не помню но идея такая: заполнять по следующему принципу

x:=0;
for k := 1 to n do
 begin
  for i:=k to n-k do
   begin
     x:=x+1;
     a[k][i]:=x;
   end;
  for i:=n-k+1 downto k+1 do
   begin
     x:=x+1;
     a[i][k]:=x;
   end;   
  for i:=n-k+1 downto k+1 do
   begin
     x:=x+1;
     a[n-k+1][i]:=x;
   end;   
  for i:=k to n-k+1 do
   begin
     x:=x+1;
     a[i][k]:=x;
   end;     
end;

что то вроде этого. проверить не могу, сам посмотришь. там по моему при k=n будет прикол) ну в общем сам попробуй разобраться, идею проще нарисовать чем объяснить, но думаю судя по циклам поймешь.


третью не встречал но есть такая идея:
берем число 5

k = 1;
для х = 5 до 2
y = x;
пока (y >= х div 2)
k = k+1;
y = y-1;
кц
кц

теперь о сути.
возможные сочетаяния но без повторения будем считать как бы по рекурсии:
сначала 5
затем возьмем из 5ти 1 и получаем 4+1
затем возьмем еще 1 и получим 3+2
следующая операция даст то же самое значит пора прекращать))
теперь разложим 4ку из первого т.е. будем раскладывать 4ку но в уме прибавлять еще нашу 1 которая там есть.
из 4 отнимаем 1 получаем 3+1
еще раз отнимаем получаем 2+2
т.о. мы получили еще 2 варианта (3+1)+1 и (2+2)+1
далее берем 3
вычитаем 1 получаем 2+1
получаем еще один вариант ((2+1)+1)+1
и полудняя 2 получится (((1+1)+1)+1)+1

итого:
5
4+1
3+2
(3+1)+1
(2+2)+1
((2+1)+1)+1
(((1+1)+1)+1)+1



вроде бы так. если хреново объяснил - спрашивай. код за тебя писать не буду ибо лень) удачи на олимпиаде

[Ламер_001]

ну о книгах что сказать не знаю. тут больше практики надо. часто встречается длинная арифметика, геометрия ну иногда рекурсия бывает. но 70% это нестадартные задачи. особо методов решения не найдешь. выучи методы сортировки. так же про дерево двоичного поиска прочти. внимательней с временем выполнения, а при работе со строками следи за памятью. не спеши использовать QSort т.к. сталкивался что организаторы составляют специальный массив который при этом методе работает медленее всего (если начинать с элемента находящегося в середине).

[LeBron]

Witaliy... Знакомые лица Земляк, почти с одного населенного пункта. Год назад человек не умел почти ничего (правда, я в то время не умел ничего вообще), а сейчас уже на республиканку нацелен.
Эти задачи были у нас районом в прошлом году. Или в позапрошлом, не помню... Если вдруг кто-небудь наткнеться на эту тему и ему станет интересно, как делать 3ую (по номеру 4ая) задачу, то там 3-д динамика по сумме слагаемых, числу слагаемых и последнему слаогаемому. Разбивания, перебирания, рекурсия и все остальное не катит, так как ответ может быть больше миллиарда, если не ошибаюсь (кажеться, 121 вырано ограничением именно потому, что это последнее число, для которого ответ вмещаеться в лонгинт).

[SunKnight]

2-я задача, по моему, на конечные автоматы из курса дискретной математики.

на пересечении и той строки и j-того столбца.

Это как понимать?

[LeBron]

Сообщение от SunKnight

Это как понимать?

строки с номером i и столбца с номером j. У нее есть решение через "формулу", но с такими ограничениями проще симулировать. Я вот как раз перечитываю условие, мне казалось, что там ограниченния были для симуляции, а сдесь что-то не понятно. Если размерность до 30000, то естественно надо делать или оптимальной симуляцией (не за квадрат, а за O(n)), или "формулой". Эх, не помню, надо будет у себя поискать старые условия ,там должно быть. Фишка в том, что за нее было только 20 баллов кажется, а за последнюю 50. Вот не думаю, что сдесь правильное решение стоит только 20 пойнтов.