Интересные ресурсы для изучения английского языка

В очередной раз напишу некоторые найденные мной интересные ресурсы для изучения английского языка.

Читать дальше

Театр "У Моста" приглашает на премьеру трагикомедии "На дне"

Театр «У Моста» приглашает на премьеру трагикомедии «На дне», М.Горький!

4, 5, 9, 10, 12 мая в 18-00 и 13 мая в 19-00.

Признанный мастер мистических постановок Сергей Федотов представляет трагикомедию «На дне». Парадоксы и мистика горьковской ночлежки, фарс и потусторонние силы, отчаянная любовь и борьба за невозможное счастье – в новом спектакле театра «у Моста»!

Читать дальше

Конференция по психологии и педагогике

22 марта в 8:30 в 415 аудитории экономического факультета ПГСХА состоялась конференция по психологии и педагогике у студентов III курса факультета Прикладной информатики. Темой конференции стала “Современная парадигма образования”. Специально приглашенный гость конференции — Виктория Валентиновна Неклюдова.

Читать дальше

Ненормальное программирование (серия 3). Не такое уж и простое это простое число

Простые числа (2, 3, 5, 7, 11, 13...)

Достаточно часто при решении задач приходится сталкиваться с нахождением простых чисел. Сегодня мы рассмотрим несколько способов, которыми можно решить данную проблему. Если заинтересовало — пожалуйте под кат.

Читать дальше

Олимпиада по программированию (26.05.2012)

Как и обещал, выкладываю текст задач с олимпиады. Если кому-то нужны задачи в печатном виде — обращайтесь, распечатаю.

А. Веселый забор
Первые две недели своих каникул Вася решил провести в деревне. Но первые же полчаса, проведенные там, разочаровали его. Еще бы! В этой глуши нет даже GPRS. Тогда он решил заняться чем-то полезным. Например, покрасить забор, ведь, как известно из творчества, Марка Твена покраска забора — процесс очень увлекательный. Однако надо думать не только о самом процессе покраски, но и о том, что получится в результате, поэтому Вася задумался о том, как же сделать так, чтобы получившийся в итоге раскраски забор был наиболее веселым. Для этого Вася решил покрасить забор в разные цвета. Забор состоит из n досок и представляет собой замкнутую окружность. В распоряжении Васи находится k красок различных цветов. Одну доску разрешается красить только в один цвет.
Каждый цвет имеет свою степень веселости. Кроме того для всех пар цветов также определена степень взаимной веселости. Степень веселости всего забора определяется как сумма степеней веселости всех досок и сумма степеней взаимной веселости всех соседних досок забора. Определите, какой наибольшей степенью веселости может обладать забор.

Формат входных данных
В первой строке заданы 2 целых числа n и k (1 <= n,k <= 100). Во второй строке дано k чисел — степени веселости красок. В последующих k строках заданы по k чисел, описывающие степень взаимной веселости всех пар досок.

Формат выходных данных
На выходе должно быть единственное число — максимальная степень веселости забора.

Пример
Ввод 1
4 3
5 3 4
1 2 7
2 3 4
7 4 2
Вывод 1
46

Ввод 2
5 4
3 7 5 6
1 5 2 8
5 1 10 4
2 10 1 9
8 4 9 1
Вывод 2
73
В. Новые правила
Прошел один день в деревне, забор покрашен, больше дел нет. И даже в шахматы поиграть не с кем. Тогда Вася начал думать, как можно модифицировать правила шахмат, чтоб, вернувшись домой, можно было сыграть с друзьями во что-то новое. И первое, что в такой ситуации приходит в голову — это изменение ходов фигур. Вася решил изменить правила перемещения для слонов и ладьей.
Напомним ходы этих фигур в классическом варианте шахмат. Слон может перемещаться на любое количество полей по диагонали. Ладья может перемещаться на любое количество полей по вертикали и горизонтали.
Классические перемещения Вася решил не трогать, но добавить к ним немного своего. Так, слон теперь может перемещаться на 1 поле по вертикали и горизонтали, а ладья — на 1 поле по диагонали.
После модификации правил интересно расставить фигуры на доску и посмотреть, сколько же сейчас фигур находится под боем. А сможете ли вы решить эту задачу?
Кроме того, Вася решил немного изменить размеры поля.

Формат входных данных
В первой строке дано число n (1 <= n <= 1000) — размер стороны шахматного поля.
Во второй строке дано число m (1 <= m <= 100) — количество слонов на поле.
В последующих m строках записаны по паре чисел — координаты слонов.
В m+3 строке дано число k (1 <= k <= 100) — количество ладьей на поле.
В последующих k строках записаны по паре чисел — координаты ладьей.

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

Пример
Ввод 1
6
2
5 1
3 5
3
1 1
5 2
4 6
Вывод 1
4

Ввод 2
6
2
3 1
6 6
2
1 1
2 5
Вывод 2
2
С. Письмо
Васе не терпится рассказать о придуманных им шахматных фигурах своему другу, так что он решил написать об этом ему в письме (да, это то самое классическое письмо, которое пишут на бумаге, ведь в Интернет Вася никак не может выйти). Но он боится, что на почте могут вскрыть конверт, прочитать письмо и украсть его идею. Поэтому он решил прибегнуть к шифрованию с помощью шифровальной решетки.
Шифровальной решёткой называется бумажный квадрат размера n х n клеток, в котором вырезаны (n^2)/4 клетки-окошка. Наложив решётку на листок бумаги, имеющий такой же размер, Вася пишет в её окошках первые (n^2)/4 символа письма. После этого он поворачивает решётку по часовой стрелке на 90 градусов. При таком расположении все ранее написанные буквы оказываются под решёткой, а в окошках появляется чистая бумага. Он записывает в окошках следующие (n^2)/4 символа письма, после чего вновь поворачивает решётку на 90 градусов. Записав очередные (n^2)/4 символа, Вася делает ещё один поворот решётки и после этого пишет последние (n^2)/4 символа письма.
Однако Вася очень не любит рукописные тексты, поэтому он хочет написать письмо на компьютере и распечатать его (к счастью, все необходимое для этого он привез с собой). Но шифровать текст описанным выше способом на компьютере вручную не очень удобно, так что на ваши плечи возлагается задача написания программы, которая зашифрует текст письма.

Формат входных данных
Первая строка входных данных состоит из n^2 (n <= 100, n — четное) символов и является строкой, которую необходимо зашифровать. Данная строка состоит только из строчных латинских символов. В последующих n строка идет по n символов — описание решетки. Символ «.» означает, что на данной позиции находится бумага, символ «#» говорит о том, что на данной позиции находится окошко.

Формат выходных данных
На выходе должно быть n строк по n символов — результат работы алгоритма шифрования.

Пример
Ввод
thisissimpletext
#...
.#.#
....
.#..
Вывод
ttmi
shsi
pelx
tsie
D. OCR
Вася получил ответ на свое письмо (да, в стране, где происходят действия, почта работает очень оперативно). Но, о, УЖАС! Это письмо оказалось рукописным. Теперь он хочет распознать текст этого письма, чтобы спокойно прочитать текст на компьютере.
К счастью, у Васи есть образцы всех букв, а друг Васи, приславший ему письмо, обладает очень хорошим почерком.

Формат входных данных
Первая строка содержит 2 числа h и w (1 <= h,w <= 10) — высота и ширина каждой буквы. Вторая строка содержит число n (1 <= n <= 26) — количество букв в алфавите. Далее идет описание букв в следующем формате. Сначала задан единственный символ — строчная буква латинского алфавита. Потом идут h строк по w символов, описывающих данную букву (символ «.» означает пустое место, символ «#» означает, что в данном месте есть чернила). В последующих h строках идет текст письма, состоящий из символов «.» и «#». Между соседними буквами может быть любое количество символов «.». Гарантируется, что текст может быть распознан однозначно.

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

Пример
Ввод 1
5 5
3
o
.###.
#...#
#...#
#...#
.###.
c
.###.
#....
#....
#....
.###.
r
####.
#...#
####.
#.#..
#..#.
.###....###....####.
#...#..#.......#...#
#...#..#.......####.
#...#..#.......#.#..
.###....###....#..#.
Вывод 1
ocr

Ввод 2
5 5
5
i
.###.
..#..
..#..
..#..
.###.
p
####.
#...#
####.
#....
#....
e
#####
#....
###..
#....
#####
r
####.
#...#
####.
#.#..
#..#.
m
#...#
##.##
#.#.#
#...#
#...#
..####....#####....####...#...#
..#...#...#........#...#..##.##
..####....###......####...#.#.#
..#.......#........#.#....#...#
..#.......#####....#..#...#...#
Вывод 2
perm
Е. Белочка и орешки
Прошла неделя в деревне. Вася уже начинает втягиваться в эту жизнь. Прогулки по лесу и наблюдение за белочками стали для него обычным делом.
Белочка живет в дупле дерева. Дерево находится в лесу. Лес содержит непроходимые препятствия. Также по лесу разбросаны орешки. Белочка не может нести больше одного орешка за раз.
За какое минимальное количество ходов белочка может собрать все орешки?
В начальный момент белочка находится в дупле.

Формат входных данных
В первой строке даны 2 числа n и m (1 <= n,m <= 100) — высота и ширина поля. Следующие n строк содержат по m символов — описание поля в следующем формате.
«.» — пустая клетка
«#» — непроходимое препятствие
«&» — дерево с дуплом белочки
«@» — орешек
Гарантируется, что символ «&» встречается только один раз.

Формат выходных данных
Выведите единственное число — количество ходов, которое потребуется белочке, чтобы собрать все орешки. Если все орешки собрать невозможно выведите -1.

Пример
Ввод 1
6 8
.@......
.....##@
.##@...#
..#.#.#.
.&#...#.
.......@
Вывод 1
64

Ввод 2
4 4
...@
###.
@.#.
.&#.
Вывод 2
-1
F. Велосипед и старая карта
Однажды вечером, когда Васе в очередной раз стало невыносимо скучно, он изучал весь хлам, который собран на чердаке дома. И внезапно он нашел свой старый велосипед, а вместе с велосипедом была и карта. Вася вспомнил, что когда-то давно он любил кататься до деревни Y, находя при этом каждый раз новые пути до нее. Он решил вспомнить те пути, по которым он ездил, но его очень сильно сбивают пункты, которые не лежат ни на одном пути до деревни Y. Вася хочет, чтобы вы помогли исключить ему эти пункты. Известно, что в стране, в которой Вася живет, по дорогам можно передвигаться только в одном заданном направлении.

Формат входных данных
В первой строке заданы 2 числа n и m (1 <= n <= 1000, 1 <= m <= n*(n-1)) — количество пунктов на карте и количество дорог.
В последующих m строках следует по два числа a и b, что означает, что из пункта a существует дорога в пункт b.
Следует считать, что Вася находится в пункте с номером 1, а деревня Y является пунктом номер n.

Формат выходных данных
В первой строке выведите количество пунктов, которые принадлежат хотя бы одному пути до деревни Y. Во второй строке перечислите эти пункты порядке возрастания их номеров через пробел.

Пример
Ввод 1
7 8
1 2
1 3
1 4
2 5
3 7
4 7
5 2
6 7
Вывод 1
4
1 3 4 7

Ввод 2
8 9
1 2
1 3
2 4
3 8
4 8
5 8
5 7
6 5
7 6
Вывод 2
5
1 2 3 4 8
G. Энергетическая ценность
Вася решил в очередной раз съездить до деревни Y. Но путь до нее не простой, поэтому Васе необходимо запастись едой. При этом Вася знает, что, если его груз станет тяжелее Wmax кг, ему будет ехать очень не комфортно, и он не получит никакого удовольствия от этой поездки.
Открыв холодильник, Вася увидел там много еды, для которой известна ее энергетическая ценность и вес. Помогите Васе выбрать, что брать с собой так, чтобы суммарная энергетическая ценность еды была максимальна.

Формат входных данных
В первой строке даны два числа вещественное Wmax — максимальный вес груза Васи (1 <= Wmax <= 1000 и целое n (1 <= n <= 15) — количество единиц еды, которая есть в холодильнике. В последующих n строках даны по 2 числа целое c и вещественное w (1 <= c <= 1000, 1 <= w <= 1000) — энергетическая ценность и вес текущей единицы еды соответственно.
Все вещественные числа в задаче даны с точностью 10^-2.

Формат выходных данных
Выведите максимальную возможную энергетическую ценность.

Пример
Ввод 1
10.00 4
3 5.00
6 7.00
2 4.00
1 1.00
Вывод 1
7

Ввод 2
23.70 6
10 15.80
5 3.70
23 7.70
13 10.10
8 4.30
20 17.70
Вывод 2
44
H. Хэш-функция
Коротая последние дни в деревне, Вася заинтересовался проблемой хэширования информации и придумал свою хэш-функцию. Нам про эту функцию известно лишь то, что в результате ее работы получается число в интервале [1;n]. Также известно, что необходимо будет обрабатывать k записей. Посчитайте вероятность того, что хотя бы 2 записи будут обладать одинаковым хэшем.

Примечание
Обратите внимание, что десятичным разделителем должен быть символ «.». Убедитесь, что используемый вами язык программирования при форматированном выводе не подставляет в качестве десятичного разделителя «,».

Формат входных данных
В единственной строке заданы 2 целых числа (1 <= n,k <= 10000).

Формат выходных данных
Выведите единственное число — ответ на задачу с погрешностью не более 10^-6.

Пример
Ввод 1
100 20
Вывод 1
0.8696005

Ввод 2
100 10
Вывод 2
0.3718435
I. Теория чисел
Пока Вася придумывал хэш-функцию, он изучил немало литературы по теории чисел, и его очень заинтересовала бинарная проблема Гольдбаха. Эта проблема имеет следующее утверждение:
«Любое чётное число, начиная с 4, можно представить в виде суммы двух простых чисел»
Теперь Вася хочет убедиться в том, что это действительно так хотя бы для не очень больших чисел.

Формат входных данных
В первой строке входного файла задано число t (1 <= t <= 10) — количество запросов. В последующих t строках перечислены запросы. Каждый запрос содержит единственное четное число x (4 <= x <= 1000000).

Формат выходных данных
На каждый запрос необходимо вывести 2 простых числа a и b таких, что a+b=x. Если возможны несколько ответов, выведите любой.

Пример
Ввод 1
3
4
6
8
Вывод 1
2 2
3 3
3 5

Ввод 2
4
18
26
36
30
Вывод 2
5 13
3 23
5 31
7 23
J. Шарики во сне
Каникулы закончились. Завтра Васе надо идти на занятия. И почему-то накануне первого учебного дня Вася видит странный сон, и снятся ему шарики, которые катятся по столу.
Шарики катятся вдоль одной прямой со скоростью 1 см/сек. Если два шарика сталкиваются, то они меняют направление своего движения на противоположное. Вася смог точно определить положения шариков, а также ширину стола, но он никак не может понять в какую сторону, какой шарик катится. Также Вася осознал, что как только последний шарик упадет со стола, зазвенит будильник, и Васе придется просыпаться.
Определите максимальное возможное время в секундах, в течение которого Вася может еще поспать.
Радиусом шариков следует пренебречь.

Формат входных данных
Первая строка содержит 2 целых числа l и n (2 <= l,n <= 1000000) — длина стола и количество шариков соответственно.
Вторая строка содержит n целых чисел — координаты шариков. Каждая координата принадлежит интервалу (0,l).
Все координаты заданы в сантиметрах.

Формат выходных данных
Выведите единственное число — ответ на задачу.

Пример
Ввод 1
10 3
2 6 7
Вывод 1
8

Ввод 2
214 7
11 12 7 13 176 23 191
Вывод 2
207

Thoughts Cloud

Thoughts Cloud
Я уже как-то говорил о своем проекте под названием Thoughts Cloud, по крайней мере, на последней конференции… Хотите узнать о нем чуть подробнее? — Пожалуйте под кат.

Читать дальше

Встреча 23.04.2012

Дабы разгрузить немного основной топик давайте в этом топике обсуждать решения задач со встречи 23.04.2012.

Читать дальше