Задача

← →
ertong (2003-10-28 19:39) [0]

Вот только что сотрел задачи олимпиады по программированию за 3 последних года. Интересно, что среди "стандартных" задач, можно увидеть нечто оригинальное. Но может, я еще мало "стандартных" задач видел??? Потом не каждая задача дается сразу. Задачи ниже мне все таки не удалось решить. Но решение же есть!!!

Листики.
Прямоугольные листики лежат на столе 100х100 так, что стороны параллельны сторонам стола. Листики могут перекрываться, но не могут быть закрытыми и прикасатся сторонами. Написать программу, чтобы подсчитала минимальное количество листиков, для получения данного многоугольника. Количество углов многоугольника до 20.

P.S. Извиняюсь, возможно, за непонятный перевод с украинского.

Листики 2
Есть N(N<10000) прямоугольников (стороны параллельны осям координат), они имеют разные цвета. На экране рисуют эти прямоугольники по-очериди, начиная с первого. Написать программу, которая подсчитает количество пикселей, которые закрашены в цвет первого прямоугольника.

Коректор
Операции вставки, уничтожения и замены будем называть елементарными. Нужно написать программу для превращения строки S1 в строку S2 за минимальное количество елементарных операций.

Сообщение
З пункта А в пункт В посылается сообщение с симолов 1 и 0. Сообщение послали по двом каналам связи. Хакер Вася перехватил два сообщения и изменил их следующим методом: любую часть сообщения, что имеет две единички переворачивает. И это действие повторяет несколько раз(для разных участков сообщения). Два сообщения обрабатывались независимо. Потом он отправил их в пункт В. Написать программу, которая проверит, можно ли из первого сообщения получить второе, и если можно то какими действиями.

Пример:

REPORT.DAT REPORT.SOL
100011100 YES
001011001 6 9
3 8
1 5

Шифрограмма
С клавиатуры вводится строка, в которой зашифровано действие сложения. Все цифры заменены на буквы, причем одинаковые цифры заменены на одинаковые буквы, разные цифры заменены на разные буквы. Нужно вывести одно из вариантов этой операции сложения.
Пример:
Ввести: ten+ten+forty=sixty
Вывести: 850+850+29786=31486

← →
ertong (2003-10-29 08:29) [1]

← →
Radionov Alexey (2003-10-29 08:48) [2]

про "Коректор" - расстояние Левенштейна, кажется. Вещь широко распространенная.

← →
stone (2003-10-29 09:22) [3]

> Нужно написать программу для превращения строки S1 в строку
> S2 за минимальное количество елементарных операций.

S2 = S1; :))

← →
LordOfSilence (2003-10-29 09:34) [4]

2 stone © (29.10.03 09:22) [3]
Смотри, не перепутай! (с) ;-)

← →
Думкин (2003-10-29 09:59) [5]

> stone © (29.10.03 09:22) [3]

:-((
Докажи что сие - есть одна из
> елементарных о -
или слабо?

← →
ertong (2003-10-29 16:52) [6]

2 stone
S2 : = S1;
:)))

2 Radionov Alexey

> расстояние Левенштейна

Ищу ...
Читаю ...

← →
ertong (2003-10-30 07:57) [7]

← →
Ertong (2003-10-30 15:45) [8]

← →
Ertong (2003-10-31 17:08) [9]

> Шифрограмма
Нашел приемлимое решение. Просто перебрать все перестановки чисел :)
Хотя 10! - это не маленькое число, но алгоритм в несколько секунд вложится.
Сначало я слишком переоценил сложность алгоритма :(

Если кто знает лучше решение то кидайте сюда.

Задача Найти похожие ветки