прошедшая олимпиада 14-16.12.13

Имя входного файла input.txt
Имя выходного файла output.txt
Максимальное время работы на одном тесте 2 секунды
Ограничение по памяти 64 МБ
Однажды Вася прочитал в древней книге легенду о том, как один мудрец руководил обороной города. Для защиты города вокруг него были выкопаны глубокие рвы, сделаны высокие земляные насыпи, а на насыпях из заостренных и обожженных бревен были сделаны стены. Как гласила легенда, стена та сооружалась по определенной схеме, делающей это укрепление непреступным. А секрет заключался в том, что для каждой пары бревен одинаковой длины выполнялось условие, что между ними есть хотя бы одно более длинное бревно. Так же в легенде рассказывалось, что при строительстве использовались бревна длины 1, 2, …, N и было их очень много. Васе стало интересно узнать, какое максимальное количество бревен можно использовать при сооружении неприступной стены по описанной схеме. Напишите программу, которая будет вычислять это количество.
Формат входных данных:
Во входном файле задано целое число N (1 ≤ N ≤ 30) — количество различных видов бревен.
Формат выходных данных:
В выходной файл выведите, какое максиальное количество бревен может быть использовано.
Пример
input.txt output.txt
1 1
2 3
3 7

Имя входного файла input.txt
Имя выходного файла output.txt
Максимальное время работы на одном тесте 2 секунды
Ограничение по памяти 64 МБ
Вася все свое свободное время тратит на решение сканвордов. Сканводр представляет собой прямоугольную таблицу, в пустые клетки которой нужно вписывать слова по горизонтали и по вертикали. В сканводре каждое слово начинается сразу от непустой клеткой или от границы таблицы. Заканчиваются слова соответственно на границе таблицы или перед непустой клеткой. Никакие два слова не следуют друг за другом подряд и не накладываются. Слова могут пересекаться друг с другом только в том случае, если одно слово идет по горизонтали, а второе по вертикали. В сканворде не используются слова длиной меньше двух букв. Для каждого слова в непустые клетки или за границей сканворда записываются вопросы-подсказки, помогающие отгадать слово. Таким образом, любая несвободная клетка может содержать либо вопросы-подсказки, либо рекламу, а во все пустые клетки должны вписываться буквы слов-ответов.
Порешав сотни сканвордов, Вася решил создать свой собственный. Для начала он хочет составить прямоугольную таблицу размером N×M, а затем вписать туда свои слова. При составлении таблицы он случайным образом закрасил часть клеток и решил, что в них будут размещаться вопросы-подсказки. Но тут до него дошло, что при случайном формировании таблицы у него может не получиться правильный сканворд. Так как переделывать всю работу долго, он решил закрасить еще несколько клеток и получить правильный сканворд. Помогите Васе подсчитать, какое минимальное количество клеток придется закрасить.
Формат входных данных:
В первой строке входного файла заданы два целых числа N и M (3 ≤ N, M ≤ 1000). В последующих N строках записано по M символов, причем, символ "." обозначает клетку, в которую будут вписываться буквы, а символ "#" обозначает клетку, в которой будет размещаться вопрос-подсказки или реклама.
Формат выходных данных:
В выходной файл выведите, какое количество клеток нужно закрасить
Пример
input.txt output.txt
3 4
....
....
.... 0
4 3
###
#.#
###
#.# 2

Имя входного файла input.txt
Имя выходного файла output.txt
Максимальное время работы на одном тесте 2 секунды
Ограничение по памяти 64 МБ
Не успел Вася отойти от одной легенды, как попалась ему книга о другой. В ней речь шла о великом полководце и его мудром советнике.
Однажды дальняя провинция подняла мятеж, и этот полководец был отправлен туда для подавления восстания. После сокрушительного разгрома он решил наказать мятежников. Для этого он приказал построить их всех в ряд, пронумеровать каждого по порядку и казнить каждого S-го начиная с F-го. Всего должно было быть казнено C человек.
Советник решил, что это наказание слишком суровое, и попытался уговорить полководца отменить свой приказ. На это полководец ответил: "Ладно, так и быть, я пощажу некоторых мятежников, но для этого тебе нужно придумать последовательность равноотстоящих целочисленных номеров, чтобы шли они с шагом больше чем 1 и чтобы шаг не равнялся S. Тогда каждого приговоренного человека, чей номер будет в твоей последовательности, я помилую." Думал советник всю ночь до рассвета, как спасти как можно больше людей, и придумал. Подсчитайте, сколько людей он смог спасти.
Формат входных данных:
В первой строке входного файла заданы три целых числа F, C и S (0 ≤ F ≤ 109, 1 ≤ C ≤ 109, 2 ≤ S ≤ 109) — номер первого человека, количество людей и шаг.
Формат выходных данных:
В выходной файл выведите, какое количество людей он смог спасти.
Пример
input.txt output.txt
1 4 2 2
3 2 4 2

Имя входного файла input.txt
Имя выходного файла output.txt
Максимальное время работы на одном тесте 2 секунды
Ограничение по памяти 64 МБ
Уже не первый год Вася разрабатывает свой собственный файловый менеджер FullCommander. Сегодня он решил добавить новую функциональность — групповое переименование файлов. Пользователь выбирает все файлы в текущей директории и некоторым образом задает новые имена для них. После этого программа самостоятельно переименовывает эти файлы. За один раз эта программа должна выбрать какой-то файл и переименовать его. В любой момент времени в папке не может содержаться два файла с одинаковым именем, даже если буквы в именах файлов разного регистра (это не позволяет делать его операционная система).
Вася долго мучился и все-таки написал эту программу. Причем она была написана наиболее оптимальным образом так, чтобы операций переименования было как можно меньше. В процессе работы программа выводит на экран, сколько переименовано файлов на текущий момент. Но тут Вася понял, что это не информативно, и решил выводить информацию о процессе переименования в процентах. Но для этого ему нужно знать общее количество переименований, которое потребуется программе. Вася уже слишком устал и не в силах написать еще одну программу. Помогите Васе подсчитать наименьшее количество переименований, которое потребуется выполнить программе.
Формат входных данных:
В первой строке входного файла задано натуральное число N, не превосходящее 100 000 — количество файлов в текущей директории. В каждой из последующих N строк через пробел записаны исходное и конечное имя файла.
Имя файла представляет собой строку, состоящую из строчных букв английского алфавита и одной точки, отделяющей имя файла от его расширения. Строка, предшествующая точке, не пуста и имеет длину не более 8 символов, а строка после точки также не пуста и имеет длину не более 3 символов. Гарантируется, что входные данные корректны и решение существует.
Формат выходных данных:
В выходной файл выведите, какое наименьшее количество переименований потребуется выполнить программе.
Пример
input.txt output.txt
2
task1.cpp task3.cpp
task2.pas task4.pas 2
2
solution.pas solution.dpr
solution.dpr solution.pas 3