Код программы: a := a xor B; b := a xor B; a := a xor B; Разобраться в ней не так уж сложно. Задача g6 1002: Трамвайные билеты
.RU

Код программы: a := a xor B; b := a xor B; a := a xor B; Разобраться в ней не так уж сложно. Задача g6 1002: Трамвайные билеты


Задача g6_1001: Проблема с A и B.

Поменять значения переменных A и B между собой, не заводя дополнительных переменных. Входной файл input.txt содержит числа a и b (0 <= a, b <= 32767). В выходном файле output.txt должны содержаться значения этих переменных после обмена.

Решение g6_1001: Первая мысль, приходящая в голову, это написать программу, похожую на эту:

A := B;

B := A;

Естественно, это программа работать не будет (в обеих переменных будет значение B).
Теперь поищем правильное решение. Обозначим начальное значение A за A1, B за B1. Тогда необходимо, чтобы по окончании работы программы A равнялось B1, а B - A1.
0) A = A1; B = B1;
1) Занесем в переменную A результат суммирования A и B (A := A + B):
A = A1 + B1; B = B1;
2) Занесем в переменную B разность A и B (B := A - B):
A = A1 + B1; B = A1;
3) Занесем в переменную A разность A и B (A := A - B):
A = B1; B = A1;

Код программы:

A := A + B;

B := A - B;

A := A - B;

Ура!
Этого решения хватило мне, чтобы сдать эту задачу в школе на уроке, однако дома я нашел в этом алгоритме несколько слабых моментов:
1) Возможно переполнение переменных. Это зависит от настроек компилятора.
2) А что, если переменные не числовые? Например char.

Это привело меня ко второму решению:
Для начала разберемся, что такое логическая операция xor. Вот несколько ее свойств:
1) A xor A = 0;
2) A xor B = B xor A;
3) A xor (A xor B) = B;
Их нам вполне достаточно, чтобы написать новую программу, которая меньше зависит от типа данных A и B:
Код программы:

A := A xor B;

B := A xor B;

A := A xor B;

Разобраться в ней не так уж сложно.


Задача g6_1002: Трамвайные билеты.

Написать программу определения количества шестизначных "счастливых" трамвайных билетов, у которых сумма первых трех цифр совпадает с суммой трех последних.
Оптимизировать решение по времени выполнения. Количество билетов вывести в файл output.txt

Решение g6_1002:
Логично устроить цикл в цикле, затем считать сумму первых и последних трех цифр и сравнивать их между собой.
Как считать сумму цифр?

For Spec := 1 to 3 do

Begin

K := K + Luck mod 10;

Luck := Luck div 10;

End;

где Luck - число, в котором надо посчитать сумму цифр, K - сумма цифр (более правильная реализация с циклом while, но это я предоставлю реализовать вам ;).
Итак, у нас два цикла, в которых перебираются 1000 чисел, итого 1000000 итераций, т.е. мы перебираем все возможные билеты, но делаем это не очень явно.
Попробуем разогнать программу в 1000 раз :). В этом нам поможет динамическое программирование, т.е. сохранение уже полученных однажды результатов.
Рассмотрим трехзначное число. Сумма цифр этого числа может принимать значения от 0 до 27, т.е. мы можем просто посчитать сколько чисел от 0 до 999 с данной суммой цифр и записать это значение в массив от 0 до 27.
Т.к. второе число также трехзначное, то мы можем пользоваться для него тем же массивом данных. Тогда, после подсчета кол-ва чисел с данной суммой цифр, мы можем достаточно просто подсчитать количество "счастливых билетов":

For I := 0 to 27 do

L := L + M[I] * M[I];

где I - счетчик, L - кол-во счастливых билетов, M - массив значений суммы цифр.
Удачи вам в реализации!


Задача g6_1003: Шифр Цезаря.

Написать программу, реализующую сдвиг по ключу(ключ задается) только для больших русских букв(буква Ё не используется).
Пример:
Входные данные:
АБЯ - строка, 2 - ключ.
Выходные данные:
ВГБ

Решение g6_1003:
Здесь стоит создать строку длиной 32 символа и заполнить ее русским алфавитом (его можно извлечь из ASCI-таблицы). Допустим, мы считали одну букву. Осуществим поиск этой буквы в строке. Если буква не найдена (т.е. это не большая русская буква), то выводим ее. Если же буква найдена, то к ее позиции прибавляем значения ключа. От числа получаем остаток от деления на 32 (сдвиг циклический) и выводим букву, соответствующую новой позиции.

Задача g6_1004: Равновеликие прямоугольники.

Прямоугольники, площади которых равны, называются равновеликими. Написать программу, находящую все возможные целочисленные стороны равновеликих прямоугольников заданной площади. Одинаковые прямоугольники, получающиеся заменой сторон, печатать не надо.
Входные данные:
Площадь четырехугольника (1<=n<=50000).
Выходные данные:
Стороны четырехугольника (A*B)

Пример входных данных:
12
Пример выходных данных:
1*12
2*6
3*4

Решение g6_1004:
Попробуем упростить задачу. Разберемся, что такое площадь прямоугольника. Площадь прямоугольника - произведение длин двух прилежащих сторон. Т.е. задачу можно представить как нахождение всех пар множителей, дающих заданный результат.
Рассмотрим алгоритм эффективного поиска множителей данного числа. (Кстати, эта задача была на одной из олимпиад несколько лет назад)
Мы будем искать одновременно два сопряженных множителя, т.е. множителя, которые при перемножении дают искомое число.
Код программы:

MaxF := trunc(sqrt(N)); {Первый множитель данного числа не может

быть больше корня из этого числа, в то время как сопряженный с

ним множитель всегда не меньше этого корня}

For F := 1 to MaxF do

If N mod F = 0 then Writeln (F, N div F);

Вот и все! Для примера я приведу авторское решение:

{Равновеликие прямоугольники. Решение А.Никитина, Самара }

program equrectangle;

var p:word; {переменная для площади}


procedure find_and_print_side(a,b:word);

begin

if (a<=b) then begin

if (a*b=p) then writeln(a,'*',b);

inc(a); find_and_print_side(a,p div a);

end;

end;


begin { основная программа }

assign(input,'square.in'); reset(input); readln(p); close(input);

assign(output,'square.out'); rewrite(output);

find_and_print_side(1,p);

close(output);

end.

По моему мнению, оно неэффективное. Для этого я проделал небольшой эксперимент:
1) Заменил ограничение на N<=1000000000.
2) Исправил в авторском решении тип переменных с word на longint.
На тесте 98765432 я не дождался, пока программа найдет ответ, а если ввести какое-нибудь большое простое число, то она будет проводить n итераций, в то время как моя программа независимо от числа производит sqrt(n) операций. Ура мне :)


Задача g6_1005 - MIME64.


Пpи пеpедаче файлов по телекоммуникационным каналам, помимо дpугих возможных ваpиантов, используется так называемый фоpмат MIME64 (Multitask Internet Mail Extensions; '64' означает использование 64-символьной стpоки-шаблона). Этот фоpмат позволяет пеpевести исходный ASCII-текст, включающий как символы "человеческого" алфавита, так и pяд специальных символов, в "видимый фоpмат".

Механизм кодиpовки для этого фоpмата следующий:
1) исходный текст pассматpивается как последовательность битов;
она pазбивается, слева напpаво, на 6-битовые отpезки (если последний отpезок "неполный", то он дополняется битовыми нулями);
2) каждая 6-битовая комбинация тpактуется как число (естественно, из диапазона 0..63);
3) число заменяется символом с соответствующим поpядковым номеpом из стpоки-шаблона, состоящей из 26 заглавных букв латинского алфавита (A..Z), 26 стpочных букв того же алфавита (a..z), цифp (0..9) и еще двух символов ("+" и "/"), то есть из стpоки

^ ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz 0123456789+/

Задача:
=================
Написать программу декодирования сообщения в формате MIME.
Hа вход пpогpаммы подается непустой текстовый MIME64-файл (MIME64.IN).
Сфоpмиpовать соответствующий ASCII-текст (или еще что-то), поместив его в выходной файл (MIME64.OUT).
Попытаться выяснить, что же было закодировано.

Решение g6_1005:
Задача была предложена на школьной OL11 в 2000 году. Тогда я не сумел ее решить (ламер), но сейчас я ее добил.
Задача имеет практическое применение: сейчас такая программа встроена во все почтовые клиенты, а раньше людям приходилось самим писать программы-распаковщики.
Итак, на вход поступает строка, с алфавитом в 64 символа(кодируется 6-ю битами), а на выход должно поступать строка с алфавитом 256 символов (кодируется 8-ю битами). Задача заключается в преобразовании потока 6-битных в поток 8-битных.
Для решения этой задачи логично использовать буфер (в данном случае хватит буфера длиной 16, точнее 12 бит - переменной word).
На первом этапе мы считываем одну букву и получаем ее номер в строке:

Repeat

Read(C);

If (C in ['0'..'9']) or (C in ['A'..'Z']) or (C in ['a'..'z'])

or (C = '+') or (C = '/') then begin

Spec := Pos(C, S) - 1;

PushBuff(Spec);

end;

Until EOF;

S - строка шаблон.

Здесь присутствует процедура PushBuff. Приведем ее текст:

Procedure PushBuff (Inp : byte);

begin

Buffer := Buffer shl 6; {сдвинули содержимое на 6 бит влево}

Buffer := Buffer or Inp; {добавили новое 6-и битное число

(первые 2 бита - нули)}

BIB := BIB + 6; {буфер увеличился на 6 бит}

If BIB >= 8 then PopBuff; {выбрасываем содержимое}

end;

BIB - количество бит в буфере.

Процедура PopBuff - выбрасывет содержимое буфера:

Procedure PopBuff;

var

Work : word;

Ans : byte;

begin

Work := Buffer;

Work := Work shr (BIB - 8); {Оставляем в переменной "самые

старые" 8 бит}

BIB := BIB - 8; {теперь бит меньше}

Buffer := Buffer shl (16 - BIB);

Buffer := Buffer shr (16 - BIB); {очищаем буфер от

выброшенных битов}

Ans := Work;

Write (chr(Ans)); {выводим ответ}

end;

Не так уж сложно, не правда ли?!

Задача g6_1006: Скобки.

Проверить корректность расстановки скобок в арифметическом выражении.
Выражение задается из файла "input.txt" и может содержать произвольное количество круглых скобок.
Программа должна выдать одну строчку: "правильно" или "неправильно".

Решение g6_1006:
Сначала разберемся, что считать правильной расстановкой скобок:
1) количество открытых скобок всегда больше либо равно количеству закрытых.
2) в конце выражения количество закрытых скобок равно количеству открытых.
В этой задаче возможно употребление, так называемого "конечного автомата", который изменяет свое состояние в зависимости от входных данных. Этот автомат должен иметь счетчик скобок, первоначально инициализированный нулем. Тогда:
1) при появлении символа "(" - увеличить счетчик на 1;
2) при появлении символа ")" - уменьшить счетчик на 1;
3) при появлении символа EOF - прекратить работу;
4) игнорировать появление любого другого символа.
Автомат мы создали, теперь надо правильно воспользоваться им для решения предложенной задачи.
Посмотрим на счетчик: он содержит количество открытых, но еще не закрытых скобок. Если счетчик стал меньше нуля, значит появилась лишняя закрывающая скобка, т.е. выражение неверно (нарушение пункта 1).
Если после завершения работы конечного автомата счетчик не равен нулю (т.е. не все скобки закрыты) то выражение неверно (нарушение пункта 2).
Полученная программа будет короткой и красивой :) Ура, ура, ура!!!

Задача g6_1007: Куль хацкеры.

Расшифровать файл, зашифрованный шифром Цезаря, не имея ключа. Шифруются только большие русские буквы.

Решение g6_1007:
Вспомнили задачу 1003? Сначала я хотел разобрать задачу расшифровки шифра с ключом, но потом мне это показалось неинтересным, т.к. расшифровка - та же самая расшифровка с ключом (32 - n)!
Теперь мы попытаемся сделать расшифровку не имея ключа. Для этого нам придется немного коснуться основ криптографии. Каждый текст имеет свою специфику - некоторые символы встречаются в нем часто, другие реже, но в среднем частота символов примерно одинакова. Этим мы можем воспользоваться в нашем нелегком труде - написании взламывающей программы.
Для начала нам понадобиться таблица-эталон с частотой встречи букв в стандартном русском тексте. Она выглядит примерно так:

А := 0.074438;
Б := 0.016189;
В := 0.050396;
Г := 0.019352;
Д := 0.028179;
Е := 0.089613;
Ж := 0.010010;
З := 0.016637;
И := 0.074109;
Й := 0.014743;
К := 0.032171;
Л := 0.037507;
М := 0.031160;
Н := 0.067640;
О := 0.113329;
П := 0.026275;
Р := 0.049378;
С := 0.056569;
Т := 0.063209;
У := 0.023785;
Ф := 0.001466;
Х := 0.009276;
Ц := 0.004299;
Ч := 0.014236;
Ш := 0.006525;
Щ := 0.004035;
Ъ := 0.000240;
Ы := 0.017820;
Ь := 0.016222;
Э := 0.004256;
Ю := 0.007210;
Я := 0.019724;

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

Пусть алфавит состоит из трех букв: {А, Б, В} с частотами:
А := 0.1;
Б := 0.3;
В := 0.6;

На вход мы получаем сообщение состоящее из того же алфавита, но с частотами:
А := 0.35;
Б := 0.55;
В := 0.1;

Теперь посчитаем нашу хитрую функцию для всех возможных сдвигов: {0, 1, 2}
[0] := |0.1 - 0.35| + |0.3 - 0.55| + |0.6 - 0.1| = 1; - очень скверно
[1] := |0.1 - 0.55| + |0.3 - 0.1| + |0.6 - 0.35| = 0.9; - скверно
[2] := |0.1 - 0.1| + |0.3 - 0.35| + |0.6 - 0.55| = 0.1; - скверно, но верно

Минимальная сумма получилась для сдвига 2, следовательно он и является ключом!
Другой способ решения состоит в том чтобы считать не сумму модулей, а сумму квадратов (он несколько более правильный, т.к. мелкие погрешности в нем почти исчезают), но и мой алгоритм расшифровывает практически все.
Пожалуй, в следующий раз надо сломать RSA-алгоритм ;)

^ ДОПОЛНЕНИЕ ОТ 18.02.02:
Недавно узнал еще один способ решения этой задачи, заключающийся в оценивании редко и часто встречающихся сочетаний букв. Например: четыре согласные подряд - плохое сочетание, а окончание "-ий", "-ой" или "-ый" - хорошее. Для каждого сдвига считается разность хороших и плохих сочетаний - в каком сдвиге эта разность наибольшая - тот и лучший.

Задача g6_1008: Редкое имя. (castle.ssu.samara.ru/olymp/ - задача 1003)


Входной файл input.txt:
содержит список учащихся школы. В каждой строке через пробел заданы Фамилия
Имя и Отчество ученика. Требуется определить, какое имя самое редкое.
Число учеников в школе <= 10000.

Файл результата output.txt: содержит одну строку с искомым именем.

Пример input.txt:
Пушкин Александр Сергеевич
Луканов Александр Сергеевич
Соколова Любава Викторовна
Иванов Иван Иванович
Сидоров Иван Петрович

output.txt для данного примера
Любава

Решение g6_1008:
Эта задача была на втором туре областной олимпиады в Самарской области.
Не будем говорить, как из формата ФИО получить только имя, я надеюсь, что вы можете сделать это сами.
Я думаю, у этой задачи есть несколько решений, однако приведу свое, может быть слишком хитрое и запутанное для данной задачи, но все же верное, а также мои идеи по поводу несостоятельности некоторых других методов решения этой задачи.
Сначала я расскажу, что такое хэш-функция. Хэш-функция - это метод упорядочивания неупорядочиваемых (еле напечатал :) множеств. Звучит ужасно, но может быть будет понятно на примере.
Итак, я использовал хэш-функцию - функцию, которая по входной строке возвращает ее контрольную сумму, т.е. сумму кодов всех символов этой строки.
Для начала я создал массив из элементов word размер около 10000 элементов (хэш-функция от самого длинного русского имени наверняка в него поместится). Для ускорения работы я завел еще один массив такого же размера (о его предназначении позже).
После преобразования ФИО -> Имя -> Контрольная сумма мы увеличиваем значение элемента с номером, равным контрольной суммы, на 1 (мы используем позиционную хэш-функцию). Если до этого он был 0, то в другой массив заносим номер строки, где он встретился, чтобы в случае необходимости быстро найти его.
После того как мы прочитали весь файл мы ищем в нашем массиве минимальный ненулевой элемент, в другом массиве находим номер строки, в которой впервые встретилось это имя, читаем из нее ФИО и преобразовываем его в имя. Затем выводим его.
У меня еще была идея создать массив из строк string, который бы помещался в 64 кб. паскалевской памяти, а затем искать в нем самый редкий элемент, но при количестве имен 10000 длина строки была бы ограничена 5-ю символами, а в русском языке есть такие имена как Наталья и Наталия, Александр и Алексей и пр. в которых первые пять символов одинаковы, т.е. такое решение не было бы корректным(позже я просматривал тесты и думаю, что такое решение тоже бы прошло).
Конечно моя простенькая хэш-функция тоже могла завалиться, но шансы на это были гораздо меньше.


Задача g6_1009: Уравнение. (castle.ssu.samara.ru/olymp/ - задача 1010)


входной файл: input.txt
файл результата: output.txt
время на тест: 1 секунда

Задано уравнение:
a*x+b*y=c,

где a,b,c,x,y - целые неотрицательные числа.
Заданы коэффициенты a,b,c. Требуется определить x,y.

Формат входного файла:
a b c

Формат файла результата:
каждая строка содержит пару x y, удовлетворяющую уравнению.
Требуется найти все возможные решения. Решения в файле результата должны быть отсортированы по возрастанию x.

Ограничения:
a<=10000, b<=10000, c<=10000

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

Файл результата для данного примера:
0 3
1 2
2 1
3 0

Решение g6_1009:
Это простая задача. Только сначала надо все хорошенько представить на бумаге.
Из уравнения ax + by = c выразим x:
x = (c - by) / a;
Т.к. коэффициенты целые и неотрицательные, то
Xmax = c / a; - при y = 0;
Затем выражаем y через x:
y = (c - ax) / b;
Перебираем все целые x от 0 до Xmax, получаем для них значения y, если y целое - выводим.
Просто!

Задача g6_1010: Вирусы.

На поле размером n*n (n<=500) расположено m (1<=m<=10) вирусов. За каждый ход вирус заражает 4 соседние с ним клетки. Положение вирусов задано координатами на поле.
Определить, за какое наименьшее количество ходов будет заражено все поле.

Решение g6_1010:
Ура! У нас маленький юбилей - 10-я разобранная задача.
Эта задача встретилась мне на командном турнире среди школьников и студентов, проводимом АО ICL КПО ВС, в Казани в 2000г.
Попробуем снова решить эту задачу. Рассмотрим возможность создания массива, изображающего игровое поле, которые будут заполняться по мере прохождения периода. Это приведет к необходимости сканирования массива 500*500 каждый период и достаточно сложным операциям над ним.
Представим, что у нас на поле один вирус и клетка с координатами X, Y и нужно определить, за сколько ходов данная клетка будет заражена. Это делается достаточно просто:
H = |X - I| + |Y - J| - где I, J - координаты вируса. Представим это на рисунке:

6543456
5432345
4321234
321*123
4321234
5432345
6543456

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

Задача g6_1011: Города.

Широко известна игра "Города". Называется какой-нибудь город, допустим, "Саратов". Кончается на "в", значит требуется назвать другой город, у которого в названии первая буква "в". Это может быть "Воронеж". Следующий город должен начинаться на "ж" и т.д. Запрещено повторять название городов. Надо написать программу, которая из набора названий городов (все названия разные) строит цепочку максимальной длины.

Решение g6_1011:
Типично рекурсивная задача (что такое рекурсия, можно узнать в разделе "Алгоритмы").
Заводим массив, в котором хранятся все названия городов, массив, который хранит максимальную на данный момент цепочку, массив, который хранит цепочку, составляемую сейчас, и булевский массив, хранящий флаги, использован город или нет.
В основной программе вызываем рекурсивную процедуру со всеми возможными начальными городами. При запуске рекурсивной процедуры помечаем город как использованный и заносим его в цепочку, запускаем цикл, в котором проверяем, если город еще не использован и его первая буква такая же как последняя буква нынешнего города, то запускаем рекурсивную процедуры для нового города. Если ни один город не удовлетворяет этим условиям, то сравниваем нынешнюю и максимальную цепочку по длине и, если нынешняя цепочка длиннее, то меняем их местами. Помечаем город как неиспользованный, выходим из рекурсивной процедуры.
Все просто!

Задача g6_1012: КВН.

Написать программу, определяющую минимально возможное количество игроков в команде КВН, если известно, что девушек в команде больше X%, но меньше Y%.

Формат входных данных
В первой строке входного файла записаны числа X и Y, разделенные пробелом. X и Y - целые, 1 <= X,Y <= 100.

Формат выходных данных
Нужно вывести одно число - минимальное количество членов команды при ограничениях, заданных во входном файле.

Пример ввода
40 50

Правильный вывод для примера
7

Решение g6_1012:
Это задача A с командного турнира по программированию "ИМ-Y2K" в СамГУ.
Решение у нее достаточно простое - достаточно организовать два цикла: A - от 1 до 101 (всего человек в команде) и B от 1 до A (количество девушек среди них).
Если в цикле X < B / A * 100% < Y то выводим A и выходим из программы.
Единственная сложность - это догадаться сделать цикл для A от 1 до 101, а не до 100. Для того, чтобы понять, чем объясняется верхняя граница 101, достаточно разобрать пример с X = 99, Y = 100.

Задача g6_1013: Коррекция кода.

По некоторому каналу связи передается сообщение, имеющее вид последовательности нулей и единиц. Из-за помех возможен ошибочный прием некоторых сигналов: нуль может быть воспринят как единица и наоборот. Для повышения вероятности правильного приема сигналов было решено передавать каждый сигнал трижды. Теперь передатчик вместо 1 всегда передает 111, а вместо 0 всегда 000.

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

Формат входных данных
Во входном файле одна строка, в которой могут быть только символы "0" и "1". Длина строки - число, кратное трем, большее двух и меньшее 760.

Формат выходных данных
Вы должны вывести в одну строку раскодированное сообщение.

Пример ввода
110111010001

Правильный вывод для примера
1100

Решение g6_1013:
Это задача B с командного турнира по программированию "ИМ-Y2K" в СамГУ.
Она тоже простая. Достаточно организовать два цикла: один вида
repeat ... until EOF
и другой, вложенный в него
for x := 1 to 3 do ...
В начале первого цикла мы обнуляем значение некоторой переменной, а во втором цикле, если нам встретилась "1", увеличиваем значение этой переменной на 1. По окончании работы цикла for проверяем: если значение переменной равно 2 или 3, то выводим "1", если 0 или 1 то "0".
Просто!

Задача g6_1014: Исправления.

Дан текст, заканчивающийся точкой. Среди символов текста особую роль играет символ #, появление которого в тексте означает удаление предыдущего символа. Соответственно, k символов # подряд отменяют k предыдущих символов текста, если таковые имеются на текущей строке.
Требуется написать программу, преобразующую текст с учетом указанного значения символа #.

Замечания:
1) Если в какой-то момент перед некоторым символом # на этой строке не осталось символов, то его следует игнорировать.
2) В выходной файл символы # выводить не следует ни в каком случае.
3) Если в результате преобразований все символы в строке входного файла были удалены, то в выходном файле в этом месте следует вывести пустую строку.

Формат входных данных
Во входном файле не менее одной и не более 100 строк текста. Признаком окончания ввода служит точка (символ "." ). Каждая строка содержит не более 200 символов.

Формат выходных данных
Для каждой строки входного файла следует вывести ее преобразованный вариант в соответствующей строке выходного файла.
Завершающую текст точку в выходной файл писать не надо.

Пример ввода
Hello ww#orld! #
a##abc#
the##he end.

Правильный вывод для примера
Hello world!
ab
the end

Решение g6_1014:
Это задача D с командного турнира по программированию "ИМ-Y2K" в СамГУ.
Я думаю, что здесь логично использовать массив из символов char длиной в 200 символов. При последовательном чтении строки по одному символу этот символ следует добавлять в массив и увеличивать счетчик, показывающий на следующий элемент на 1. При появлении символа # указатель следует уменьшить на 1 (предварительно убедившись, что он больше 0). Когда мы доходим до конца строки, то последовательно выводим все символы нашего массива, переходим к следующей строке и устанавливаем указатель на последний символ на 1, а если на нашем пути попалась точка, то выводим содержимое массива и выходим из программы.

Задача g6_1015: Степень.

Дано два целых положительных числа: a и b.
Требуется написать программу, которая находит цифру, на которую оканчивается число a^b.

Формат входных данных
В первой строке входного файла записаны числа a и b, разделенные пробелом.1 <= a, b <= 10000.

Формат выходных данных
В выходной файл следует записать одну цифру - ту, на которую оканчивается число a^b.

Пример ввода
2 2

Правильный вывод для примера
4

Решение g6_1015:
Это задача F с командного турнира по программированию "ИМ-Y2K" в СамГУ.
Эххх... Как все было просто два года назад :) Вообще-то это сейчас просто, а тогда было сложно... молодость... золотое время... ;) (если честно, то сейчас мне живется лучше чем два года назад :Р )
Итак, к задаче. Нам надо найти ПОСЛЕДНЮЮ цифру a^b. На последнюю цифру не влияет никакая цифра, кроме последней цифры числа a^(n-1). Это упрощает задачу и нам жизнь. Каждый раз нам следует возводить в степень ТОЛЬКО ПОСЛЕДНЮЮ цифру и при получении числа большего 9 получать ТОЛЬКО ПОСЛЕДНЮЮ цифру. Проиллюстрируем на примере:

if b 1 then

for c := 2 to b do begin

last := last * a;

last := last mod 10;

end;

Вот и все! (насколько я помню, два года назад мы эту задачу не решили втроем :( )


Задача g6_1016: Диски (castle.ssu.samara.ru/olymp/ - задача 1004)

На полке имеются N коробок с CD-дисками. (1<=N<=100)
За 1 шаг можно либо снять любой из дисков с полки, либо поставить его между любыми двумя другими, либо с любого края.
За какое минимальное число шагов можно переставить диски так, чтобы в итоге все диски с одинаковой тематикой находились рядом?

input.txt:
название 1, тематика 1
...
название N, тематика N

output.txt:
K

где K - требуемое число шагов.

пример input.txt:
Web-Design 2000, web-дизайн
Quake III, игры
Windows 2000, софт
Коллекция клип-артов, web-дизайн

output.txt:
2

Решение g6_1016:

Эта задача со второго тура Самарской областной олимпиады школьников по программированию(задача 1004 на сервере областной олимпиады).
Итак, мы имеем набор строк с текстом, которые надо преобразовать во что-нибудь более простое для обработки. Для этого используем мою любимую хеш-функцию, считающую суммы ASCII кодов всех символов слова, в данном случае это будет тематика диска.
Теперь у нас есть массив чисел, где количество чисел равно количеству дисков. Теперь совершим над этим массивом преобразование, похожее на сжатие RLE. Заведем два массива, один хранящий хеш-функцию, а другой количество дисков одной тематики, идущих подряд. Т.е.:
1, 1, 1, 2, 2, 1
преобразуется в два массива:
1, 2, 1
3, 2, 1
Теперь найдем самую часто встречающуюся тематику и самую большую группу подряд идущих дисков этой тематики. А теперь начинается самое интересное - то, до чего я дошел сам :).
Мы нашли самую большую группу и теперь будем двигаться в обе стороны, ища группу таких же по тематике(самой частой!) дисков, при этом будем считать, сколько дисков лежат между самой большой и этой группой. Если количество дисков в группе меньше, чем количество дисков между этой группой и максимальной, то возьмем все эти диски и переложим к максимальной группе(обнулим значение количества дисков в этой группе). На каждый диск уходит две операции. Если же количество дисков в группе больше, то вынем все диски между этими группами(обнулим значения счетчиков) и забудем об этих дисках (не забыв прибавить к счетчику перестановок по 2 операции на каждый диск), это значит, что мы одной операцией мы взяли диск, а второй поставили куда душе угодно(куда надо).
Когда все наиболее часто встречающиеся диски будут сложены в одну группу, заменим ее хеш-код на 0, например, чтобы функция поиска наиболее часто встречающейся тематики не обрабатывала 0.
Теперь проведем проверку: если у всех дисков либо код тематики равен 0, либо длина последовательности подряд идущих дисков равна 0, то пишем значение счетчика перестановок и выходим из программы. Иначе повторяем с поиска самой частой тематике, пока не будет выполнено условие выхода.
^ Как оказалось это еще не все, теперь идет еще интереснее: наш читатель Axel нашел тест, на котором выше приведенное решение не работает.
Мы нашли количество перестановок с помощью эвристического алгоритма, однако это не всегда наименьшее количество. Теперь надо написать рекрсивную процедуру, реализующую полный перебор. Это делается точно также, (т.е. находим группу и идем от нее вправо-влево) но только мы рассматриваем два варианта - удалить диски между группами или перенести группу. При этом не забываем считать количество действие и, в случае если оно превысило значение эвристически найденного или текущего наименьшего в данный момент, то больше рекурсию не запускаем. Это позволит отсечь большую часть ненужных веток и ускорит полный перебор во много раз.



Задача g6_1017: Демократия в опасности

Л.Волков
В одном из островных государств Карибского бассейна все решения традиционно принимались простым большинством голосов на общем собрании граждан, которых, к счастью, было не очень много. Одна из местных партий, стремясь прийти к власти как можно более законным путем, смогла добиться некоторой реформы избирательной системы. Главным аргументом было то, что население острова в последнее время значительно возросло, и проведение общих собраний перестало быть легкой задачей.
Суть реформы состояла в следующем: с момента введения ее в действие все избиратели острова делились на K групп (необязательно равных по численности). Голосование по любому вопросу теперь следовало проводить отдельно в каждой группе, причем считалось, что группа высказывается "за", если "за" голосует более половины людей в этой группе, а в противном случае считалось, что группа высказывается "против". После проведения голосования в группах подсчитывалось количество групп, высказавшихся "за" и "против", и решение вопрос решался положительно в том и только том случае, когда групп, высказавшихся "за", оказывалось более половины общего количества групп.
Эта система вначале была с радостью принята жителями острова. Когда первые восторги рассеялись, очевидны стали, однако, некоторые недостатки новой системы. Оказалось, что сторонники партии, предложившей систему, смогли оказать некоторое влияние на формирование групп избирателей. Благодаря этому, они получили возможность проводить некоторые решения, не обладая при этом реальным большинством голосов!
Пусть, например, на острове были сформированы три группы избирателей, численностью в 5, 5 и 7 человек соответственно. Тогда партии достаточно иметь трех сторонников в каждой из первых двух групп, и она сможет провести решение всего 6-ю голосами "за", вместо 9-и, необходимых при общем голосовании.
Вам надо написать программу, которая определяет по заданному разбиению избирателей на группы минимальное количество сторонников партии, достаточное, при некотором распределении их по группам, для принятия любого решения.
Ввод.
Входной файл для этой задачи состоит из двух строк. В первой строке файла записано натуральное число K < 101 - количество групп избирателей. Во второй строке через пробел записаны K натуральных чисел, которые задают количество избирателей в группах. Для упрощения определения понятия "большинство голосов" будем полагать, что и число групп, и количество избирателей в каждой группе суть нечетные числа. Вы можете также считать, что население острова не превосходит 10001 человек.
Вывод.
В выходной файл следует записать единственное натуральное число - минимальное количество сторонников партии, способное решить исход голосования.

Пример файла input.txt.
3
5 7 5

Пример файла output.txt.
6

Решение g6_1017:

Для контроля над группой, нам достаточно простое большинство голосов в ней. В более маленькой группе нам нужно меньше людей, чтобы иметь простое большинство голосов в ней.
Отсортируем массив с количеством людей в группе по неубыванию. Возьмем (K div 2 + 1) первых групп (минимальных) и найдем сумму всех L = G[N] div 2 + 1, где G - отсортированный массив, с количеством людей в группе, N принимает значение от 1 до K div + 1.
Группы равноправны, а мы контролируем только наименьшие.
Разделяй и властвуй.

Задача g6_1018: Пуговицы
Л.Волков
Как уже несомненно стало известно всем, Екатеринбург добился права на проведение Летних Олимпийских игр 2032 года. Планируется, что России, как стране-организатору Олимпийских игр, будет разрешено внести минимальные изменения в программу Олимпиады. Так, с целью улучшения общего командного результата, было решено заменить соревнования по плаванию первенством в абсолютно новой игре "Пуговицы".
Правила игры очень просты. Перед двумя играющими находится кучка из K пуговиц. Играющие по очереди берут пуговицы из кучки, причем за один ход каждый из них может взять от 1 до L пуговиц. Выигрывает тот из спортсменов, которому удастся взять последнюю пуговицу.
Правила олимпийских соревнований будут лишь немного сложнее обычных. Тот из игроков, которому по жребию выпадает делать первый ход, получает возможность собственноручно назначить число K, руководствуясь в своем выборе только ограничениями 3 <= K <= 100 000 000 (именно столько пуговиц заготовлено для олимпийского турнира). Тот из игроков, который будет ходить вторым, выбирает, в свою очередь, число L, которое должно отвечать условию 2 <= L < K.
Задача
На вашу команду возлагается очень ответственная задание: необходимо написать программу, которая помогала бы второму игроку делать свой выбор. Другими словами, по заданному числу пуговиц в кучке K, необходимо определить такое число L, которое гарантирует победу второму игроку при наилучшей игре обеих сторон.
Так, например, если в кучке всего три пуговицы, то победу второму игроку обеспечивает выбор L=2. В самом деле, если первый игрок своим ходом заберет одну пуговицу, то второй сможет выиграть, взяв обе оставшихся пуговицы и, напротив, если первый возьмет две пуговицы, то второй победит, взяв последнюю. Исходные данные
Вход для этой задачи состоит из одной строки, в которой записано единственное число K - количество пуговиц в кучке, выбранное первым игроком.
Результат
На выход следует записать единственное целое число L - максимальное количество пуговиц, которое можно взять за один ход - обеспечивающее победу второму игроку. Если таких чисел несколько, то следует вывести наименьшее из них. Если таких чисел нет, то следует вывести число 0.

Пример исходных данных
3

Пример результата
2

Решение g6_1018:
Это вроде бы простая задача. Нам достаточно разбить число пуговиц на некоторое число одинаковых групп так, что в каждой группе находится целое количество пуговиц(l), большее единицы.
Ответом будет количество пуговиц в группе - 1. Это значит, что независимо от хода первого игрока, второй игрок может дополнить имеющуюся группу пуговиц до необходимого количества(l).
Реализуется это перебором от 2 до квадратного корня из числа пуговиц, и проверкой, является ли число делителем количества пуговиц. В случае если количество пуговиц - простое число, то ответом будет K-1(легко доказывается).


Задача g6_1019: Банки
Имеется N банок с целочисленными объемами V1, ..., Vn литров, пустой сосуд и кран с водой. Можно ли с помощью этих банок налить в сосуд ровно V литров воды?
Исходная информация содержится в файле input.txt в первой строчке - количество банок N<100, затем N строчек с объемами банок и в последней строчке объем сосуда.
Программа должна вывести в файл output.txt одно из двух слов YES! или NO.

Решение g6_1019:

kolumbiya-strana-udivitelnaya-pervij-raz-moyo-znakomstvo-s-etoj-volshebnoj-stranoj-proizoshlo-v-fevrale-2007-goda-po-vozvrasheniyu-iz-kolumbii-ya-v-bukvalnom-smi-stranica-3.html
kolya-18-let-drug-tani-student-kulinarnogo-uchilisha.html
kolyada-zhivaya-skazka-kolyada.html
komand-a-znatok-i-iz-rabochih-materialov-komandi-znatokov.html
komanda-gimnazii-5-g-minsk-voprosi-zadaniya-3.html
komanda-kontakt-gimnaziya-10-g-minska-10-e-klassi-voprosi-zadaniya-3.html
  • desk.bystrickaya.ru/opticheskie-sistemi-i-pribori-kontrolnoe-zadanie-40-mif-2-4-2001-god-42-lukina-galina-stepanovna-avtor-sostavitel.html
  • doklad.bystrickaya.ru/udk802809-1-82091-bbk-81-2-83-34-stranica-10.html
  • notebook.bystrickaya.ru/indikatori-kompleksonometricheskogo-titrovaniya-analiticheskaya-himiya.html
  • thescience.bystrickaya.ru/itogovie-pokazateli-effektivnosti-realizacii-federalnoj-celevoj-programmi-razvitie-elektronnoj-komponentnoj-bazi.html
  • testyi.bystrickaya.ru/6-chut-vishe-srednego-6-obsheobrazovatelnaya-shkola.html
  • student.bystrickaya.ru/10rezultati-vneurochnoj-deyatelnosti-uchashihsya-i-vospitatelnoj-raboti.html
  • tests.bystrickaya.ru/literatura-srednevekovij-rusi.html
  • college.bystrickaya.ru/2-sistema-antikrizisnogo-upravleniya-personalom.html
  • esse.bystrickaya.ru/r-yackr-a-n-reznikov-m-roshal-l-komarova-a-rapoport-redakciya-virazhaet-osobuyu-blagodarnost-za-uchastie-v-podgotovke-knigi-a-i-naftulevu-i-a-l-svencickomu-6bk-88-362-stranica-8.html
  • paragraf.bystrickaya.ru/zadaniya-ii-tura-mezhregionalnoj-olimpiadi-shkolnikov-po-istorii-tatishev-stranica-4.html
  • textbook.bystrickaya.ru/gosudarstvennoe-upravlenie-osnovnimi-narodnohozyajstvennimi-kompleksami.html
  • universitet.bystrickaya.ru/tridcat-tretij-kilometr-kniga-rasschitana-na-massovogo-chitatelya.html
  • grade.bystrickaya.ru/ob-organizacii-podgotovki-naseleniya-municipalnogo-rajona-ishimbajskij-rajon-v-oblasti-grazhdanskoj-oboroni-i-zashiti-ot-chrezvichajnih-situacij-prirodnogo-i-tehnogennogo-haraktera.html
  • thescience.bystrickaya.ru/izuchenie-rezhimov-raboti-diodov-i-tranzistorov-v-elektronnih-shemah-chast-5.html
  • lecture.bystrickaya.ru/analiz-sostoyaniya-i-perspektivi-razvitiya-transportnoj-sistemi-chast-8.html
  • literatura.bystrickaya.ru/spisok-sokrashenij-redakcionno-izdatelskim-sovetom-tomskogo-politehnicheskogo-universiteta-izdatelstvo-tomskogo.html
  • control.bystrickaya.ru/chto-mne-nakonec-to-pozvoleno-napisat-otchet-o-tom-dele-kotoroe-v-opredelennom-otnoshenii-mozhno-schitat-vershinoj-kareri-moego-druga-stranica-12.html
  • lektsiya.bystrickaya.ru/postanovlenie-ob-utverzhdenii-polozheniya-o-vvedenii-v-dejstvie-tamozhennih-naznachenij-predusmotrennih-tamozhennim-kodeksom-respubliki-moldova-stranica-8.html
  • kontrolnaya.bystrickaya.ru/programma-prednaznachena-dlya-cikla-tematicheskogo-usovershenstvovaniya-naimenovanie-cikla.html
  • school.bystrickaya.ru/istoriya-taganrogskogo-parka-kulturi-i-otdiha-xixxx-v.html
  • spur.bystrickaya.ru/market-leader-intermediate-business-english-stranica-14.html
  • control.bystrickaya.ru/ekologicheskaya-ekspertiza-v-rossii-chast-6.html
  • books.bystrickaya.ru/dorozhnogo-dvizheniya.html
  • otsenki.bystrickaya.ru/sbornik-materialov-dlya-diagnostiki-predstavleniya-na-pmpk-i-korrekcii.html
  • institut.bystrickaya.ru/tehnologiya-vozdelivaniya-kormovih-mnogoletnih-trav-na-nesipolzuemih-zasolennih-zemlyah-s-soderzhaniem-solej-v-pahatnom-gorizonte-01-03-.html
  • klass.bystrickaya.ru/antikorrupcionnie-zakoni-poyavyatsya-osenyu-tv-7-mayak-novosti-14-07-2008-yakovlev-evgenij-20-00-7.html
  • school.bystrickaya.ru/igrovaya-koncepciya-kulturi.html
  • prepodavatel.bystrickaya.ru/tema-2-analiz-tehniko-organizacionnogo-urovnya-i-drugih-uslovij-proizvodstva.html
  • books.bystrickaya.ru/duhovno-muzikalnie-sochineniya-v-otechestvennom-notoizdanii-i-bibliografii-konca-xviii-nachala-xxi-vv-05-25-03-bibliotekovedenie-bibliografovedenie-i-knigovedenie.html
  • control.bystrickaya.ru/bryanceva-e-a-chtenie-skazki-v-kataeva-cvetik-semicvetik-mdou-ds-458.html
  • thesis.bystrickaya.ru/programma-disciplini-ekonomika-i-politika-stran-yugo-vostochnoj-azii-dlya-napravleniya-080100-62-ekonomika-podgotovki-bakalavra-avtor-d-i-n-kanaev-evgenij-aleksandrovich.html
  • textbook.bystrickaya.ru/k-rasporyazheniyu-rosmorrechflota.html
  • notebook.bystrickaya.ru/intellektualnaya-igra-s-z-lovcova-vitebsk-2005.html
  • literature.bystrickaya.ru/doklad-ob-osushestvlenii-gosudarstvennogo-kontrolya-nadzora-v-sfere-deyatelnosti-svyazannoj-s-oborotom-prekursorov-narkoticheskih-sredstv-i-psihotropnih-veshestv-v-2010-godu.html
  • institut.bystrickaya.ru/suhoj-polet-rasskazivaet-nachalnik-otdela-zagranichnih-pasportov-ufms-rossii-po-novosibirskoj-oblasti-elena-maksimova-vse-taki.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.