Месяц: Май 2012

Пью третий кофе, ну никак, не могу проснуться. Зато сработало как, как только я его на себя вылил!..

Кстати, специалисты, а объясните, а почему в катушке электромагнитный фон в городах навести небольшой ток может (те же детекторные приемники), а накапливать его (пусть даже очень медленно) нельзя? Или можно?

После обновления iOS на 5.1.1, айпад, похоже, подумал, “а как же я”, и уперся работать с мобильным интернетом. После секса с настроками и симкой, а также впитывания чужого опыта, нашлось решение: Спасла замена симки на новую. Если кто еще не обновился – будьте готовы к таким сюрпризам.

Не понимаю, почему при том, что абсолютно во всех ресторанах кормят в кредит по доверию анонимных людей, заправки в России до сих пор (кроме ВР) ре уют денег вперед. Ну уедет один, не заплатив – видео и заяву ментам, плюс копейка к цене за литр и проблем нет.

Прошлогодний победитель RCC Петр Митричев пока на 126-м месте. Пожелаем ему удачи! Еще есть целых 15 минут)

Задача №5, “Этикетка”. Только что ее решил Епифанов Кирилл, тем самым взяв первое место в квалификации (решил все задачи быстрее остальных). Вот ее постановка:

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

Проблема заключалась в том, что эта цивилизация не пользовалась знаком переноса. Как только строка заканчивалась, чтение просто продолжалось со следующей строки. При расшифровке книг это не доставляло никаких неудобств, однако у этикетки есть существенное отличие от книги — этикетка наклеивалась на бутылку так, что получался цельный цилиндр, на котором по кругу был написан текст. При чтении текста следовало начать читать первую строку от места склейки, после достижения места склейки перейти на вторую строку, после этого на третью и так далее. Но ученым пока не удается определить место, где этикетка была склеена! Так что вместо текста пока имеется только набор строк одинаковой длины k, состоящих из букв и символов «.», которые использовались этой цивилизацией вместо пробелов.

К счастью, кроме самой этикетки имеется словарь, в котором перечислены все возможные слова, которые использовались этой цивилизацией. Теперь по этим данным вам необходимо определить, сколько существует вариантов местонахождения склейки. Более формально, вам необходимо определить, сколько существует неотрицательных значений t < k таких, что конкатенация всех данных вам строк, циклически сдвинутых влево на t символов, представляет собой набор слов из словаря, разделенных одним или несколькими символами «.». Кроме этого, вам необходимо также вывести все эти значения t.

Входные данные имеют следующий формат.

Первая строка содержит одно целое число m (1 ≤ m ≤ 2000) — количество слов в словаре. Следующие m строк содержат слова из словаря. Все слова различны, состоят только из строчных букв латинского алфавита, длина каждого слова не превышает 2000 символов.

Следующая строка содержит одно целое число n (1 ≤ n ≤ 2000) — количество строк, написанных на этикетке. Следующие n строк содержат слова строки, написанные на этикетке. Все эти строки состоят только из строчных букв латинского алфавита и символов «.». Длина всех строк одинакова и не превышает 2000 символов. Гарантируется, что в каждой строке содержится хотя бы один символ «.».

Выводить нужно в таком формате: В первой строке – одно целое число — количество значений t. В следующей строке – сами эти значения, разделенные пробелами и упорядоченные по возрастанию.

Например, при входных данных

2

uu

u

5

.uu..uu

.uu…u

…uu.u

.u.u.uu

uuu.uu.

нужно выводить

2

1 2

»

Задача №5, Джавайское оружие. Первым решил Кирилл Веденский на 24-й минуте. Вот ее задача:

«С древности у каждого джавая был набор из трех видов оружия: лазерный меч, лазерная сабля и лазерный ножик для намазывания масла на хлеб (вдруг джавай проголодается).

Но так как это оружие джавайское, а не простое, на длины входящих в набор предметов накладывались следующие ограничения:

* Длина ножика — d1, длина сабли — d2, длина меча — d3 должны быть простыми числами;

* d1 ≤ d2 ≤ d3;

* (d1 + d2)^2 − 1 делится на d3;

* (d2 + d3)^2 − 1 делится на d1;

* (d3 + d1)^2 − 1 делится на d2.

Компания “Dart Generics Industries” продает любой набор джавайского оружия по его номеру в лексикографическом порядке. А именно, упорядочим все джавайские наборы по неубыванию d1, при равном d1 по неубыванию d2, а при равных d1 и d2 по возрастанию d3 и пронумеруем их в этом порядке от 1 до бесконечности. Тогда по заданному k можно купить k-й набор в этом порядке.

Джавай Anykey хочет купить k-й набор. Подскажите ему размеры его оружия.

Первая строка содержит одно целое число k (1 ≤ k ≤ 60000).

Нужно вывести три упорядоченных по неубыванию размера оружий, входящих в k-й комлект.

К примеру, при входных данных

1

нужно выводить

2 2 3

»

В 1-й квалификации RCC участвуют !2000 сабмитов. Решивших хотя бы одну задачу уже >600. #rcc12 #mailru

Хотя бы одну задачу Russian Code Cup сдали 553 человека (за 51 минуту турнира). Уже есть решение четырех задач от Епифанова Владислава. Принимают участие не меньше полутра тысяч человек.

Задача №3, тоже посложнее, «Война». Решена правильно Капуном Евгением на 16-й минуте.

«На одну маленькую нефтеносную страну было совершено нападение высокотехнологичной армии другой враждебной страны. Для защиты была мобилизована армия, состоящая из n солдат. Перед началом решающего боя все n солдат выстроились в шеренгу перед генералом. Он всегда считал, что все солдаты в его войске одинакового роста, однако это оказалось не так. Генерал понял, что такая армия малоэффективна, и решил разбить ее на подразделения. Под подразделениями генерал подразумевал непустые группы солдат, стоящих друг за другом в шеренге. Также генерал решил ввести понятие “мощность подразделения”, которое определялось как:

* количество солдат в подразделении, если в шеренге они стоят в порядке невозрастания или неубывания их роста;

* 0 в противном случае.

Также генерал решил, что мощность армии равна произведению мощностей всех подразделений.

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

Первая строка содержит целое число n (1 ≤ n ≤ 50000)— количество солдат. В следующей строке содержится n целых чисел ai (0 ≤ ai ≤ 109) — рост i-го солдата.

В первой строке выведете число k — количество подразделений, на которое генералу следует раздить шеренгу. Во второй строке следует вывести k чисел bi — номер в шеренге самого правого солдата в i-м подразделении. Числа надо вывести в порядке возрастания. Если существует несколько разбиений, то можно вывести любое разбиение.

Например, при следующих входных данных

5

1 2 3 5 4

нужно выводить

2

3 5

»