Сегодня состоялось открытое первенство ЮУрГУ по программированию. Рая «Stigler», Женя «CKopnuOH» и я «Я» составляли дружную команду хакеров. Специально обученный человек прочитал наши фамилии и объявил, что нам дорога к рабочему месту №25. Нужно было придумать название команде; здесь Женя порулил, предложив название «Команда ПК №25».

Потом мы отлично пописали программы на Паскале, несмотря на Раины попытки запустить Си. Из 8 задач мы решили 3. Из команд так 60 мы заняли 21-е место. Учитывая то, что мы туда шли вообще просто так (пообщаться), результат неплохой.

Задание №4 — написать парсер-преобразователь из одного XML-формата в другой. Основная задача — заменить непарные теги (<tag/>) парными (<tag></tag>), а атрибуты (<tag attr="value" />) убрать и сделать вложенными тегами (<tag><attr>value</attr></tag>). Естественно, какие-то тэги могут оказаться парными и при этом с атрибутами. Внутри парных тэгов мог оказаться какой-то текст, в том числе и вложенные тэги.

Исходный файл может быть форматирован сколь угодно безобразно. На выходе должна получиться конфетка. Пробелы, переносы и табуляция внутри текста и значений атрибутов должны быть сохранены, а вне их — заменены на один пробел. Напоминает, полную задницу, не так ли? Не напоминает? В Паскале нет регэкспов. Теперь напомнинает? То-то.

Кроме нашей команды парсер сделала еще только одна. И снова у меня появился повод считать себя крутым. Я крутой.

(Здесь я, кстати, выражаю благодарность Шурику Бабаеву за пропаганду автоматного программирования. Сильно помогло)

За полчаса до конца Рая сгенерировала алгоритм решения одной задачи на поиск площади геометрической фигуры, образованной пересечением окружности и квадрата (параметры задаются тестером). Мы так и не успели его реализовать. Жалко. Сергей «SauroN» (был в другой команде) решил эту задачу методом Монте-Карло за первые 8 минут олимпиады. Гад! Так не честно! (Смайлик.) И снова у меня появился повод считать его крутым. Сергей — крутой.

В общем, было интересно.

Слабомонотонной будем называть последовательность, которая либо не возрастает, либо не убывает. Например, 000, 111, 100 — слабомонотонные последовательности, а 101 или 010 — уже нет. Матрица называется фиолетовой, если каждая её строка и каждый её столбец представляют собой слабомонотонную последовательность. Рассмотрим двоичные матрицы, то есть такие, у которых элементы — 0 или 1.

Сколько бывает двоичных фиолетовых матриц M×N (нужно выразить через M и N)?

Дано две веревки и зажигалка. Известно, что одна сгорает за час, другая за полчаса. При этом вполне возможно, что горят они неравномерно. Задача: засечь 45 минут.

Пост утверждает, что всякая вычислимая функция вычислима по Посту, т. е. с помощью машины Поста.

Как бы это доказать? Не знаю даже как подступиться. Достаточно ли доказать, что можно сложить, вычесть, умножить и разделить, а потом сказать, что всякие там функции можно разложить в ряд? Или есть какие-то еще загвоздки? Кстати, как разделить? Что делать с дробями?

На Первом канале показывают какую-то толпу супер-мега юмористов (аншлаг или что там), а на Культуре в это же время — Жванецкого. Ну, то есть, Первый — количеством, а Культура — качеством.

Илья Бирман, специально для...

Михаил Ефимович Фрадков, премьер-министр Российской Федерации. Зачем? Я вот как думаю:

До того, как Путин отправил Касьянова в отставку, темой дня были выборы. Те, кому не совсем пофигу, стали смотреть, что за кандидатов раздают, думать. А тут — бах — Касьянова в отставку. И все теперь говорят только про Фрадкова. И тут же ощущение выборов пропало. Мне совсем не пофигу, но я не знаю кандидатов в президенты, кроме Путина и Хакамады. Про выборы никто не говорит (не считая роликов «что такое президент России»). Я думаю, Путин просто хотел отвлечь людей от выборов, чтобы когда они вдруг неожиданно наступят (ой, 14 марта!), все пошли голосовать «за Путина, ведь вроде при нём было не так плохо, а кто такие остальные — мы не знаем, так что голосовать за них не будем, чтобы не стало хуже».

(На самом деле, я вычитал задачу про тюремщика, решил её, рассказал Смирнову, он вспомнил задачу про короля, опубликовал её, потом я опубликовал эту, потом вроде бы решил смирновскую про короля, но Смирнов, гад, пропал куда-то и не говорит, правильно я решил или нет.)

Я как человек, которому до всего нужно докопаться, вот чего подумал. Если Duracell мощнее обычных батареек, то, согласно P=UI, или (а) они дают более высокое напряжение, или (б) более высокий ток. В обоих случаях питаемый ими прибор легко может сгореть.

Вывод: не пользуйтесь батарейками Duracell.

Тюремщик встречает 23 новых заключенных и говорит:

Сегодня вы можете встретиться и выработать стратегию, но после этого вы будете изолированы в своих камерах и не сможете общаться.

В тюрьме есть комната с двумя выключателями «А» и «Б», каждый из которых может быть либо включен, либо выключен. В каком они сейчас положении я вам не скажу. Выключатели ни к чему не подключены. С завтрашнего дня я начну время от времени, когда мне этого захочется, брать одного из вас и приводить в эту комнату. Он должен будет выбрать один из выключателей, включить его, если он был выключен или выключить, если он был включен. Потом я отведу его назад в камеру. Никто кроме вас не будет входить в эту комнату и изменять положение выключателей.

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

В любой момент любой из вас может объявить: «Каждый из нас уже побывал в комнате с выключателями». Если он будет прав (каждого из вас я действительно хотя бы один раз туда к этому времени свожу), тогда вы все будете освобождены. В противном случае (кто-то так и не был в комнате) все вы останетесь здесь навсегда, без шансов на освобождение.

Посоветуйте заключенным, как гарантированно обеспечить своё освобождение.

(Своровано из Ponder This. Я решил. Оказывается, не так-то уж и трудно.)