Блог пользователя Seyaua

Автор Seyaua, 10 лет назад, перевод, По-русски

Привет, Codeforces!

Я рад анонсировать, что компания Rocket Fuel Inc. снова будет проводить соревнование Rockethon! Контест подготовили сотрудники компании Эльдар Богданов, Антон Ломонос, Лаша Лакирбая, Александр Рафф, Никил Гоял и я, Евгений Соболев. Мы надеемся, что каждый из вас найдет для себя интересные задачи на контесте и от решения этих задач вы получите не меньше удовольствия, чем получили мы от их подготовки. Как и в прошлом году, лучшие участники получат ценные призы и футболки. Помимо этого, Rocket Fuel заинтересован в рекрутинге людей после соревнования, поэтому, пожалуйста, заполните простую форму при регистрации.

О Rocket Fuel

Rocket Fuel is building technology platform to do automatic targeting and optimization of ads across all channels — display, video, mobile and social. Our pitch to advertisers is very simple "If you can measure metrics of success of your campaign, we can optimize". We run campaigns for many large advertisers and our clients include many top companies within the following industries: autos, airlines, commercial banks, telecom, food services, insurance, etc. Examples include BMW, Pizza Hut, Brooks Running Shoes and many more!

We buy all our inventory through real time bidding on ad exchanges like Google and Yahoo. Ad exchanges are similar to stock exchanges except the commodity being traded is ad slots on web pages. Our serving systems currently process over 60B bid requests/ day with a response time requirement of 100ms. Our data platform has 64 PBs data that is used for analytics as well as modeling.

Our engineering team is still small (~150) enough for any one person like yourself to make a huge impact. The team represents many top schools in US and outside — Stanford, Carnegie Mellon, MIT, Wisconsin-Madison, IIT (India), Tsinghua (China).

Rocket Fuel has been named #4 on Forbes Most Promising Companies in America List in 2013 and #1 Fastest Growing Company in North America on Deloitte’s 2013 Tech Fast 500 and our CEO George John was recently named “Most Admired CEO” by the SF Business Times in 2014.

Мои впечатления

Около года назад я зашел на Codeforces и увидел объявление о Rockethon 2014. Моей первой мыслью было: "Круто! Еще одно соревнование от крупной компании!" Я поучаствовал, выступил достаточно неплохо, после чего со мной связались рекрутеры Rocket Fuel и назначили несколько собеседований. Я прошел собеседования и теперь я здесь, в Rocket Fuel.

Работа в Rocket Fuel — это отличная возможность изучить продвинутые вещи в software engineering, так как вокруг работают много умных людей, которые всегда готовы делиться своими знаниями. Конечно, наша деятельность не ограничивается только лишь написанием кода — мы играем в баскетбол, футбол, настольный теннис. Я приглашаю каждого из вас принять участие в соревновании и буду рад услышать если вы задумываетесь о трудоустройстве в Rocket Fuel.

Обзор соревнования

Контест начнется 7-го февраля в 20:00 МСК.

Продолжительность контеста — 3 часа.

Тестирование посылок будет производиться сразу же после их отправления и вердикты тестирования будут немедленно показаны авторам посылок.

В контесте будет 7 задач, каждая из которых может иметь от одной до трех подзадач. Каждая подзадача будет стоить некоторое фиксированное число баллов. Если несколько участников наберут одинаковое число баллов, выше будет стоять тот участник у которого будет меньше штрафное время, вычисляемое аналогично ACM-системе.

Призы

Три лучших участника получат следующие призы:

1) IPhone 6 (16 Gb)

2) Участник может выбрать Apple Watch или Samsung Gear S

3) Участник может выбрать Apple Watch или Samsung Gear S

Лучшие 150 участников получат футбоолки Rockethon с оригинальным дизайном соревнования.

Если вы не можете принять участие в соревновании, но заинтересованы в трудоустройстве в Rocket Fuel, мы будем обрабатывать резюме отправленные через специальную форму.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +607
  • Проголосовать: не нравится

Автор Seyaua, 11 лет назад, По-русски

Всем привет!

Приглашаю всех принять участие в контесте 101 Hack March. Ссылка на время старта в разных регионах. В контесте будет пять задач на два часа. Автором задач являюсь я и, на мой взгляд, задачи очень интересные.

Внимательные люди могут заметить, что за полчаса до этого раунда начнется TopCoder SRM 614. Чтобы завлечь Вас поучаствовать в контесте именно на HackerRank, хочу отметить, что топ-10 участников получат футболки! В чем участвовать, в SRM-е или в 101 Hack March, решать Вам, однако, SRM-ов нынче по четыре в месяц, а на HackerRank-е есть шанс выиграть эксклюзивную футболку!

Повторюсь, на мой взгляд, задачи для раунда отличные, поэтому очень не хочется, чтобы они остались нерешенными :)

Заранее благодарю всех тех, кто примет участие в 101 Hack March!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +64
  • Проголосовать: не нравится

Автор Seyaua, 11 лет назад, По-русски

Задача A. Утренний бег

В задаче требовалось найти математическое ожидание количества встреч между бегунами. Как это делать? Для начала, вспомним, что математическое ожидание линейно, поэтому исходная задача эквивалентна следующей: найти сумму математического ожидания количества встреч между каждой парой бегунов. Будем решать задачу именно в этой формулировке. Сделаем несколько наблюдений:

  1. Пусть расстояние между двумя фиксированными бегунами ровно x и они бегут навстречу друг другу бесконечно (вероятность того, что они бегут навстречу, как нетрудно видеть, равняется 0.5·0.5 = 0.25). Тогда первая встреча произойдет в момент времени , следующая — , следующая — и так далее.

  2. Пусть каждый из бегунов бежал ровно l единиц времени. Тогда, если два бегуна встречаются, то они встречаются ровно 2 раза. Вероятность того, что два бегуна встретятся составляет 0.5, так как в двух случаях из четырех они бегут навстречу друг другу, а в оставшихся двух случаях бегут в одном направлении.

На основании этих наблюдений будем строить решение. Для начала разобьем t как t = k·l + p, где 0 ≤ p < l. Тогда, каждый из бегунов пробежит ровно k полных кругов. Что это означает? Так как всего пар бегунов ровно , то за k кругов в каждой из пар с вероятностью 0.5 произойдет ровно 2k встреч. Значит, к ответу нужно добавить .

Теперь как-то нужно обработать оставшиеся p секунд бега. Предположим, что расстояние между двумя бегунами ровно x и они бегут это расстояние навстречу друг другу. Тогда, между ними произойдет встреча, если , или x ≤ 2t. Между ними произойдет вторая встреча, если , или x ≤ 2t - l. Больше двух встреч произойти не может, так как p < l.

Зафиксируем какого-нибудь бегуна, тогда с помощью двоичного поиска мы можем найти количество бегунов, которые находятся на расстоянии не более x от данного. Выберем границу x как x = 2t, и тогда количество бегунов на расстоянии не более x будет означать количество бегунов, которые встретятся с зафиксированным. Если же мы выберем x = 2t - l, то сможем найти количество бегунов, с которыми произойдет вторая встреча. Умножаем полученные количества на 0.25 — вероятность встречи бегунов, и добавляем к ответу.

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

Задача B. Контекстная реклама

В задаче требовалось найти максимальное количество слов, которое можно разместить в блоке размера r × c. Решим сначала следующую задачу: какое максимальное количество подряд идущих слов поместится в строке длины c, если первое слово имеет индекс i. Такую задачу можно решать двоичным поиском, или двигая указатель. Теперь создадим граф, где вершинами будут слова, а ориентированные ребра будут соединять вершины i и j, если слова с i по j - 1 помещаются в одну строку длины c, а слова с i по j уже не помещаются. Весом ребра будет величина j - i. Тогда исходную задачу можно переформулировать в терминах данного графа: требуется найти путь длины k, который имеет наибольший вес. Такую задачу можно решать со сложностью используя метод двоичного подъема, или за O(n) при помощи поиска в глубину.

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

Задача C. Память для массивов

Здесь нужно было найти максимальное количество массивов, которое можно разместить в имеющейся памяти. Для начала отметим следующее: пусть ответ на задачу — это число k, тогда одним из оптимальных решений будет размещение k самых маленьких по размеру массивов в памяти. Без ограничения общности, будем считать, что у нас есть массивы размера 1 и мы хотим их разместить, при этом, разместить их как можно больше. Тогда, если у нас есть участки памяти нечетного размера, то при размещении массива размера 1 на таком участке, мы получим участок памяти четного размера. С другой стороны, если размещать на участке массивы другого размера, то четность не поменяется, и если на участке не будет размещено ни одного массива размера 1, то в самом конце в нем будет хотя бы одна свободная ячейка. Значит, выгодно размещать массивы размера 1 на участках памяти нечетного размера. Сделаем это, пока можем. Возможны три ситуации:

  1. У нас закончились участки памяти нечетного размера.

  2. У нас закончились массивы размера 1.

  3. У нас закончились и участки памяти нечетного размера и массивы размера 1.

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

Во втором случае, если мы сразу разделим все имеющиеся числа целочисленно на 2, и решим изначальную задачу, то ответ мы не ухудшим.

Третий случай аналогичен второму.

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

Сложность данного решения составляет .

Задача D. Теннисные ракетки

Участникам требовалось найти количество тупоугольных треугольников на данных вершинах, удовлетворяющих некоторым условиям. Сразу отметим, что авторское решение имеет сложность O(n2), но имеет ряд оптимизаций, благодаря чему решение укладывается в TL с большим запасом.

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

Так как каждая сторона симметрична, то можем рассматривать лишь половину стороны, а после этого умножить ответ на 2.

Введем координаты, так что вершина A треугольника имеет координаты (0,0). Вершина B (0,) и C(2,0). Тогда найдем координаты каждой из точек на сторонах и выпишем теорему косинусов. Получим некое соотношение, которое гарантирует нам, что треугольник будет тупоугольным. Один из возможных его видов таков: Если 1 ≤ i, j, k ≤ n — номера точек зафиксированных на сторонах, то треугольник тупоугольный тогда и только тогда, когда: f(i, j, k) = 2i2 - i(n + 1) + 2j(n + 1) - ij - k(i + j) < 0. Заметим, что возрастает, поэтому можем использовать метод двигающегося указателя для перебора k. Тогда просто переберем i от m + 1 до , затем j от m + 1 до тех пор, пока верхняя граница для k не превосходит n - m + 1 и будем суммировать результаты.

Отметим, что все результаты нужно делать в типе int, что существенно ускоряет решение.

Задача E. Овечки

Эту задачу предлагается решать жадно. Будем следовать следующему алгоритму. Создадим для каждого отрезка 2 пометки Positionv и MaximalPositionv.

Positionv — соответствует позиции v в искомой перестановке.

MaximalPositionv — соответствует максимальной допустимой позиции v в текущий. момент.

Пусть у нас также имеется счетчик count изначально равный 0 и множество необработанных вершин S. Будем действовать по следующему алгоритму.

  1. Двоичным поиском ищем минимальное возможное расстояние между самыми удаленными соединенными овцами. Для фиксированного расстояния K проверяем существует ли перестановка.

  2. Отсортируем все отрезки по возрастанию ri.

  3. Positioni = 0, 1 ≤ i ≤ n, MaximalPositioni = n, 1 ≤ i ≤ n, current = 1, count = 0.

  4. Выполнить count = count + 1, Positioncurrent = count, удаляем current из S, если S — пустое, то требуемая перестановка найдена.

  5. Перебираем все отрезки, которые соединены с current, и обновляем MaximalPositionv = min(MaximalPositionv, Positioncurrent + K)

  6. Строим множества S(count, j) = {v|MaximalPositionv ≤ count + j}. Если для всех j ≥ K - count + 1 выполнено |S(count, j)| ≤ j то переходим к шагу 7, иначе выводим, что искомой перестановки не существует.

  7. Ищем минимальное j такое что |S(count, j)| = j. Выбираем оттуда вершину с наименьшим ri и берем ее в качестве нового значения current, переходим к шагу 4.

Сначала обоснуем время работы представленного алгоритма. Зафиксируем расстояние K (всего будет итераций с фиксированным K).

Заметим, что шаги с 4 по 7 в худшем случае выполняются ровно n раз (каждый раз размер множества S уменьшается на 1). Каждый из шагов можно реализовать так, чтобы он выполнялся за O(n). Самый сложный шаг — это шаг 6. Но заметим, что нам не требуется явно строить эти множества, достаточно знать лишь их размеры. А это мы можем сделать за линейное время, просто посчитав сколько существует таких элементов, что MaximalPositionv = i. Обозначим это число через Ci — тогда размер множества S(count, j) равен C1 + C2 + ... + Ccount + j, что легко подсчитать при помощи массива частичных сумм.

Обоснуем теперь корректность алгоритма. Если алгоритм расставил позиции для всех вершин, то очевидно, что имеет требуемую перестановку. Предположим, что алгоритм заканчивает свое выполнение до того, как мы расставили все позиции, покажем, что тогда не существует искомой перестановки. Есть алгоритм закончил свое выполнение, это означает, что для некоторого count (рассмотрим найменьшее такое count), что есть такое j0, что |S(count, j0)| > j0 на этом шаге. Покажем, что тогда |S(count, k)| > k. Докажем это от противного. Предположим, что это не так. Из определения count имеем |S(count - 1, j)| ≤ j для всех j ≥ k - count + 2. Тогда |S(count, j)| = |S(count - 1, j + 1)| - 1 ≤ j для всех j ≤ k - 1. При этом, S(count, j) = S(count, k) для k ≤ j < n - count = |S(count, j)| = |S(count, k)| ≤ j. В итоге |S(count, n - count)| = n - count. Тогда |S(count, j)| ≤ j для всех j, следовательно имеем противоречие. Значит, алгоритм преращает свою работу на шаге 6, |S(count, k)| > k. Это означает, что существует как минимум k + 1 вершина, которая до сих пор не имеет назначенной позиции после вершины, которая была отмечена как count. Значит, одна из вершин в S(count, k) должна быть с Position как минимум count + k + 1. Но все вершины в S(count, k) соединены с как минимум одной вeршиной с Position ≤ count. Следовательно, получаем, что искомомй перестановки не существует.

Разбор задач был подготовлен sdya и Seyaua.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +43
  • Проголосовать: не нравится

Автор Seyaua, 12 лет назад, перевод, По-русски

A Div 2

Если aj делится на ai, то тогда ai ≤ aj. Тогда число, на которое будут делиться все остальные числа будет не более чем любое выбранное число. То есть единственный возможный кандидат — это минимум в массиве. Поэтому просто проверим, что все элементы массива делятся на минимальный элемент.

B Div 2

Легко видеть, что Ксюша не сможет закончить ее путешествие, если существует последовательность подряд идущих # длиное более чем k.

C Div 2 / A Div 1

Первое наблюдение: мы не будем волноваться о том, как выглядят строки на самом деле, вся информация, которая нам нужна — это количество пар-символов вида: {0, 0}, {0, 1}, {1, 0}, {1, 1}. Посчитаем эти количества и будем следовать следующему жадному алгоритму:

Для первого игрока: будем брать сначала {1, 1}, если их нет, то {1,0}. Если их нет, то {0, 1} и, в последнюю очередь, будем брать {0, 0}.

Для второго игрока похожая стратегия: сначала {1, 1}, потом {0, 1}, потом {1, 0} и, в последнюю очередь, {0, 0}.

После этого сравним у кого получилось больше единичек.

D Div 2 / B Div 1

Любой путь из верхней левой клетки в правую нижнюю состоит ровно из n + m - 1 клеток. И все они должны быть покрашены в разные цвета. Значит n + m - 1 ≤ k. Исходя из маленьких ограничений на k можно предположить, что брут-форс будет работать. Единственная оптимизация для получения действительно правильного решения — это некоторая канонизация раскрасок. Будем идти по всем клеткам в некотором порядке и красить их согласно следующим условиям. Если i > j, тогда цвет i встречается позже цвета j. После такого перебора мы получим примерно миллион различных шаблонов для максимального теста.

Далее, просто будем сопоставлять уже покрашенные клетки с каждым шаблоном и считать, сколько различных перестановок цветов подходят к данному шаблону.

E Div 2 / C Div 1

После прочтения условия, можно понять, что все, что нам нужно — это посчитать количество решений уравнения (a + b + c)3 - a3 - b3 - c3 = n в положительных целых числах.

Ключевое наблюдение это: 3(a + b)(a + c)(b + c) = (a + b + c)3 - a3 - b3 - c3, после чего мы можем просто вычислять все делители числа и идти по всем делителям x = a + b, таким что ? далее будем идти по делителям y = (a + c) ≥ x, где и в конце будем вычислять z = (b + c), такое что .

После этого, решим систему a + b = x, a + c = y, b + c = z и добавим количество подходящих решений к ответу.

D Div 1

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

Для каждого x определим yleft, yright таким образом, что все точки (x, y), где yleft ≤ y ≤ yright лежат внутри многоугольника и отрезок [yleft, yright] максимально возможный.

Теперь будем считать, что мы имеем a1, a2, ..., ak различных точек для каждого фиксированного x (a1 соответствует x =  - 106, a2 соответствует x =  - 106 + 1 и так далее).

Теперь требуемый ответ это a2a1 + a3(a2 + 22a1) + a4(a3 + 22a2 + 32a1) + ...

Можно заметить, что

(a2 + 22a1) - a1 = a2 + 3a1,

(a3 + 22a2 + 32a1) - (a2 + 22a1) = a3 + 3a2 + 5a1,

и так далее.

Поэтому достаточно предпросчитать частичные суммы вида a2 + 3a1, a3 + 3a2 + 5a1, a4 + 3a3 + 5a2 + 7a1 (разность между двумя соседними суммами составляет 2(ai + ... + a1), поэтому мы можем делать это за O(k)).

После предпросчета достаточно сложить полученные результаты.

E Div 1

Будем считать что у нас есть структура данных, которая позволяет осуществлять следующие операции:

  • добавить точку (x, y) в структуру;

  • сдвинуть все точки структуры на вектор (dx, dy);

  • узнать как много точек (x,y), удовлетворяющих x ≤ xbound, y ≤ ybound;

  • получить все элементы, которые на данный момент находятся в структуре;

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

ОБъясним, как нужно обновлять структуры. Мы будем обрабатывать все вершины в порядке обхода в глубине, и если мы находимся в листе, то мы будем создавать структуру с единственным элементом (0, 0).

В противном же случае, мы будем сортировать структуры сыновей по их размеру в убывающем порядке и будем присваивать указатель наибольшей структуры указателю на текущую вершину (здесь нужно не забыть сдвигать структуру на (1, вес ребра)).

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

  • Сдвинем структуру на (1, вес ребра);

  • Возьмем все элементы структуры;

  • Для каждого элемента (x, y) ответим на запрос xbound = L - x, ybound = W - y (используем родительскую структуру);

  • Добавим элементы по одному в структуру;

После этого ответим на запрос xbound = L, ybound = W и добавим элемент (0, 0).

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

Осталось только объяснить, как создать нужную нам структуру данных.

Существует несколько способов сделать это, один из них:

  • Будем иметь маленькие подструктуры у которых размеры являются степенями двойки;

  • Каждая структура — это двумерное дерево отрезков;

  • Мы можем добавлять элемент следующим образом: если нет подструктуры размера 1, тогда создадим ее, иначе же возьмем все структуры размерами 1, 2, 4, ..., 2k и перестроим в структуру размера 2k + 1.

  • Сдвиг: достаточно помнить вектор сдвига для каждой подструктуры;

  • Ответ на запрос: идем по подструктурам и суммируем результаты.

Разбор задач был подготовлен sdya и Seyaua

Полный текст и комментарии »

  • Проголосовать: нравится
  • +62
  • Проголосовать: не нравится

Автор Seyaua, 12 лет назад, По-русски

Всем привет!

Сегодня состоится второй раунд Всероссийского Открытого Чемпионата по программированию "КРОК-2013". Раунд для вас готовили: sdya, Seyaua, Gerald и, как обычно, задачи на английский переводила Delinur.

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

Официальным участникам напоминаем, что:

  • Все участники чемпионата должны быть не моложе 18 лет на момент регистрации
  • Финал чемпионата состоится 16 и 17 мая в Москве в офисе компании КРОК (50 участников)
  • Проживание во время финала будет оплачено компанией КРОК
  • Для граждан Российской Федерации: организаторы покроют транспортные расходы по территории РФ, транспортные расходы не по территории РФ — по согласованию (возможно, частично)
  • Финалисты должны подтвердить свое участие до 2 мая

И небольшой бонус: лучшие 200 официальных участников чемпионата получат футболки!

Желаем всем получить удовольствие от решения задач ну и, конечно, удачи!

UPD: Разбалловка по задачам сегодня будет немножко отличаться от стандартной: 500-1500-1500-2000-2500 для первого дивизиона и 500-1000-1500-2500-2500 для второго.

UPD2: Мы приносим свои извинения за технические неполадки во время раунда. Посовещавшись, мы решили, что соревнование должно быть рейтинговым. А результаты соревнования будут учитываться в отборе на финал чемпионата КРОК.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +108
  • Проголосовать: не нравится

Автор Seyaua, 13 лет назад, По-русски
В общем, судя по правилам, и куда более логично, надо писать свои жалобы не на Codeforces, а Contest Managerу финала. Можно прочитать об этом здесь.

При этом, чтобы каждый, кто считает, что результаты необъективные написал свою апелляцию. Апелляции должны быть составлены каждой командой независимо, а не по шаблону.

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

  1. Несмотря на декларирование "двух сайтов", тестирование решений происходило только на сервере PC^2 в Бухаресте. В Винницу румынские организаторы тесты не отправили, несмотря на просьбу от винницких организаторов. Команды Винницы при этом работали не напрямую через Интернет, а через промежуточный сервер PC^2.
  2. В интервале с 20-й по 30-ю минуты соревнований произошла перезагрузка сервера в Бухаресте, при которой была утеряна информация об отправленных к тому времени решениях. Именно этим объясняется сдача задач на нулевой-третьей минутах.
  3. На официальном сайте таблица результатов отображалась внутренними кодами Team XX, при этом представители жюри в Бухаресте не предоставляли в Винницу информации по поводу соответствия бухарестских команд своим номерам; только к середине контеста путём долгих уговоров удалось получить id четырёх украинских команд, участвовавших из Бухареста. Информация о соответствии id остальных команд была предоставлена только в конце контеста. Таким образом, возможность наблюдения за результатами - даже через альтернативную таблицу - фактически отсутствовала.
  4. В процессе проведения соревнований были пересужены несколько задач, причём задача J пересуживалась ближе к концу соревнований ("заморозке"). По некоторым задачам было объявлено, что тесты не соответствовали формату, описанному в описании входного файла (вместо пересуживания).
  5. В течение контеста сервер не был доступен для сдачи задач как командами Бухареста, так и командами Винницы  в течение существенных периодов времени.
  6. Где-то в районе 4 часов после рестарта контеста (4 часа времени таблицы) связь сервера в Виннице с сервером в Бухаресте была нарушена, в связи с чем решения участвовавших из Винницы команд не уходили на центральный сервер в Бухаресте. Переданные во время контеста организаторам полуфинала в Виннице решения были позднее отправлены в Бухарест, но представители жюри отказались тестировать данные решения, несмотря на то, что ситуация являлась форс-мажорной. Таким образом, для участников полуфинала, находившихся в Виннице, контест неожиданно оказался на 30 минут короче.
Если вышеизложенные факты верны, то получаем, что по вине румынской стороны результаты SEERC-2011 не являются достоверными, так как получены с грубыми нарушениями правил, при этом из-за пункта 6) команды были в неравном положении. В любом регулярном соревновании после таких нарушений следует объявление раунда unrated или как минимум судейское решение о разделении результатов.

Также обращаем внимание, что по имеющимся данным восстановление штрафного времени, полученного участниками, невозможно  в принципе (в силу пунктов 1 и 5).

Полный текст и комментарии »

  • Проголосовать: нравится
  • +205
  • Проголосовать: не нравится

Автор Seyaua, 13 лет назад, По-русски

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

Дивизион 2, задача А. Петя и строки

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

 

Дивизион 2, задача B. Петя и квадрат

Оказывается, что если мы хотим разделить квадрат на две равные части, то линия разреза должна проходить через центр квадрата. Отсюда становится понятно, что если отмеченная клетка содержит центр квадрата, то ломаную провести невозможно и нужно вывести NO, иначе вывести YES. Получаем код, которой решает данную задачу:

scanf("%d%d%d", &n, &x, &y);

n /= 2;

if ((x == n || x == n + 1) && (y == n || y == n + 1)) printf("NO\n"); else printf("YES\n");

 

Дивизион 2, задача С. Петя и неравенства (Дивизион 1, задача А)

Нетрудно видеть, что максимум суммы квадратов достигается, когда все числа, кроме одного равны 1. Теперь достаточно проверить, можем ли мы из заданного y набрать n положительных целых чисел и если можем, то проверить, что x ≤ 1 + 1 + ... + (y - (n - 1))2.

 

Дивизион 2, задача D. Петя и делители (Дивизион 1, задача B)

Заведем массив used, такой, что в used[j] хранится номер последнего числа во входных данных, у которого есть делитель j. Тогда для каждого запроса будем последовательно перебирать делители числа xi и для каждого делителя k числа xi будем проверять является ли он «уникальным». После этого обновим пометку для делителя k в массиве used.

 

Дивизион 2, задача E. Петя и пауки (Дивизион 1, задача С)

Данная задача подразумевала множество решений. Следует отметить, что количество входных данных не так велико, поэтому можно было попытаться вручную разобрать все возможные входные данные. Можно было написать перебор, который при нужных отсечениях можно было сдать даже без предпросчета ответов. Однако большинство решений участников все же содержало в себе динамику по профилю. Здесь я приведу решение пользователя Zlobober.

Будем считать не максимальное количество оставшихся клеток, а минимальное количество центров, в которые могут сбежаться все пауки. Повернём доску, чтобы количество строк было не больше шести.

Пусть D[k][pmsk][msk] - это минимальное количество центров, достаточное, чтобы собрать всех пауков с первых k столбцов, причём k-ый столбец имеет маску pmsk, а k + 1-ый - msk. Тогда за переход мы перебираем маску tmsk k - 1-ого столбца, и среди тех, для которых k-ый столбец может целиком разбежаться по центрам, выбираем тот, для которого D[k - 1][tmsk][pmsk] минимально.

Получается решение за O(n*23m), где n > m.

 

Дивизион 1, задача Д. Петя и раскраски

Заметим, что если m = 1, то ответ kn, так как допустимы все возможные раскраски.

Теперь m > 1. Рассмотрим первый столбец доски (проведем вертикальную прямую справа от первого столбца). Пусть в нем x различных цветов. Тогда в оставшихся столбцах тоже x различных цветов по условию. Теперь если мы сдвинем нашу вертикальную прямую на 1 вправо, то количество цветов в левой части не уменьшится, а в правой не увеличится. Повторяя сдвиги, можем сделать вывод, что опять в левой части будет x различных цветов и в правой тоже x. Теперь мы получаем, что в крайних столбцах доски ровно по x различных цветов. Нетрудно видеть, что в остальных столбцах доски должны встречаться только те цвета, которые встречаются в пересечении цветов крайних столбцов доски.

Будем последовательно перебирать два числа x и y, где x - количество используемых цветов в каждом из крайних столбцов, y - количество общих цветов в крайних столбцах. При этом ясно, что на x и y накладываются некоторые ограничения в зависимости от размера доски.  Будем считать ответ для каждой такой пары, а затем все их просуммируем. Тогда для каждой пары (x,y) имеем, что надо сначала выбрать (2x-y) цветов из k данных цветов, которые мы будем использовать при раскраске. Поэтому ответ для пары нужно сразу умножить на C(k,2x-y). Далее, выберем (x-y) уникальных цветов, которые будут использоваться в первом столбце. Ответ умножается еще на C(2x-y,x-y). Выбирая (x-y) уникальных цветов для последнего столбца, имеем еще одно умножение ответа на C(x,x-y). Теперь надо знать, сколько существует способов раскрасить n клеток в x цветов. Это несложная динамика (при этом цвета учитываются лексикографически, что означает, что если на доске есть цвета a и b, при этом a<b, то цвет a встречается раньше чем b), которая пересчитывается по формуле: d[i][j]=j*d[i-1][j]+d[i-1][j-1]. Домножаем ответ для пары на d[n][x] (раскрашиваем первый столбец) и потом еще раз на d[n][x] (раскрашиваем последний столбец). После этого в каждом из крайних столбцов можно сделать перестановку цветов, поэтому нужно ответ умножить на (x!)2. Теперь осталось домножить ответ на yn(m-2), так как цвета в средних столбиках могут быть любыми из пересечения.

Можно привести простой код, который проверяет нужные нам пары:

long long ans=0;

     

for (int y=0; y<=n; y++){

      long long cur=powmod(y,n*(m-2));

      for (int x=y; x<=n; x++)

      if (2*x-y<=k)

      {

            long long tek=cnk[2*x-y];

            tek*=cnn[2*x-y][x-y], tek%=mod;

            tek*=cnn[x][x-y], tek%=mod;

            tek*=d[n][x], tek%=mod;

            tek*=d[n][x], tek%=mod;

            tek*=f[x], tek%=mod;

            tek*=f[x], tek%=mod;

            tek*=cur;

            ans+=tek;

            ans%=mod;

      }

}

cout<<ans<<endl;

Здесь, cnk[i] – это предпросчитанное C(k,i), cnn[a][b] – C(a,b), d[n][x] – динамика как в разборе, f[x] – x!.

Заметим, что у некоторых участников возникли проблемы с тайм лимитом, однако если аккуратно предпросчитать все C(k,i) и помнить, что нам никогда не понадобится более чем 2000 цветов из предложенных 1000000, то проблем со временем быть не должно. Следует отметить, что авторское решение работало менее 200 мс, при предложенном тайм лимите в 5 секунд.

 Дивизион 1, задача E. Петя и прямоугольник

Обозначим длину максимального пути через S. Оценим число S, исходя из ограничений задачи. Раскрасим нашу доску в шахматную раскраску. Тогда получим, что любые две соседние клетки в максимальном пути имеют разный цвет. Из этого уже можем сделать какие-то ограничения на S. Действительно, к примеру, если у нас на доске получилось всего 4 белых клетки и 5 черных, при этом стартовая клетка белая и конечная белая, то очевидным образом длина пути не превосходит 7, так как белые и черные клетки должны чередоваться в пути. Таким образом, можем написать несложную функцию, которая считает максимальное теоретически возможное значение S (n, m – размеры доски, (sx, sy) – стартовая клетка, (fx, fy) – конечная клетка).

int fnd_ans(int n,int m,int sx,int sy,int fx,int fy){

      int col1=((sx+sy+1)%2); //цвет стартовой клетки

      int col2=((fx+fy+1)%2); //цвет конечной клетки

 

      int cntb=(n*m+1)/2; //количество черных клеток на доске

      int cntw=(n*m)/2; //количество белых клеток на доске

 

      //разбор случаев для нахождения ответов

      if (col1==1&&col2==1)

            return cntb*2-1;

      if (col1==1&&col2==0)

            return cntw*2;

      if (col1==0&&col2==1)

            return cntw*2;

      if (col1==0&&col2==0)

            return 2*cntw-1;

}

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

 

Разобьем доску на 5 частей, как показано на левом рисунке. При этом пока будем считать, что конфигурация начальной и конечной клеток будет именно такой. Тогда в каждой из частей попробуем построить самый длинный путь, проходящий именно в этой части. При этом для части 1 будем строить путь из правой верхней клетки в левую верхнюю. Для части 2 из левой нижней в правую верхнюю. Для части 3 из левой верхней в правую нижнюю, для части 4 из правой верхней в левую нижнюю и для части 5 из правой нижней в правую верхнюю. Пути, которые мы ищем в каждой части могут немножко меняться для других досок, однако при этом общая структура в целом сохраняется. После этого, видим, что у всех 5 частей всего 2 различных вида путей с учетом поворотов – из верхнего левого угла в правый нижний и из верхнего левого в правый верхний. Теперь можем сформулировать алгоритм.

1)     Делим доску на части

2)     В каждой из частей ищем длиннейший путь

3)     Проверяем подходит ли найденный путь под оптимальный ответ

4)     Поворачиваем/переворачиваем доску и переходим к шагу 1.

 

Осталось только понять, как решать задачу для поиска пути между углами частей. Это делается довольно просто, последовательным обходом по строкам/столбцам доски.

Данное решение проходит стресс-тест для всех досок с 4<=n,m<=20. Так как для таких досок рассматриваются все возможные варианты четности сторон каждой из частей, на которые делится вся доска, то можно сделать вывод, что решение работает для любых досок. Итоговая сложность -  O(n*m).

Полный текст и комментарии »

Разбор задач Codeforces Beta Round 85 (Div. 1 Only)
Разбор задач Codeforces Beta Round 85 (Div. 2 Only)
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор Seyaua, 13 лет назад, перевод, По-русски
Привет всем из солнечного Петрозаводска!

Сегодня я и мой брат sdya подготовили для вас несколько интересных задач. Из-за плотного графика на петрозаводских сборах, особенно из-за рафтинга и просмотра аниме ночами напролет, у нас было немного времени на написание длинных условий задач. Так что наслаждайтесь короткими условиями и изобретайте легенды на ваше усмотрение :)

Удачи всем!

Контест завершен! Поздравляю победителей!

Division 1:
  1. dolphinigle
  2. ilyakor
  3. marek.cygan
Division 2:
  1. wuzhengkai
  2. jayi
  3. superpear
Опубликован разбор.

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор Seyaua, 14 лет назад, По-русски

Здесь приводится разбор всех задач прошедшего раунда. Вопросы и предложения задавайте в комментариях. Отдельное спасибо пользователю sdya за подготовку разборов задач D и E, которые я использовал в качестве авторского разбора.

Задача А

В данной задаче нужно уметь проверять всего четыре условия:
1) помещается ли N в тип byte

2) помещается ли N в тип short

3) помещается ли N в тип int

4) помещается ли N в тип long

Именно в таком порядке и нужно проверить эти условия. Если все они неверны – то ответ BigInteger.

Как проще всего проверить условия 1) – 4)? Проще всего хранить числа в виде строк и написать функцию сравнения двух строк как чисел. В Java можно было пользоваться встроенным типом BigInteger.

 

Задача B

Тут нужно перебрать все возможные позиции для создания искусственного дождя, посмотреть сколько в каждом из случаев получается участков, содержащих воду и выбрать среди всех возможных вариантов максимальный. При этом подсчитывать ответ для текущей позиции будем, просто расходясь вправо и влево от текущей позиции. Итоговая сложность O(N^2).


Задача C

Понятно, что максимальное число файлов и максимальное число подпапок будет в каких-то из папок, находящихся непосредственно в корне каких-то дисков. Рассмотрим, чем характеризуется файл и чем характеризуется подпапка. Файл характеризуется путем, который записан в условии, а папка характеризуется частью пути до нее. То есть, к примеру, если есть путь: C:\folder1\folder2\1.txt, то отсюда нам надо выделить две папки и один файл, чтобы получить выражение для каждой из папок в данном пути и для файла. Имеем, что первой папке соответствует путь C:\folder1\, второй папке C:\folder1\folder2\, и файлу соответствует C:\folder1\folder2\1.txt. После того, как мы разделим так каждую строку из входных данных, у нас получится набор путей к папкам и отдельно набор путей к файлам. Решим задачу сначала для подпапок. Для этого соберем все пути к папкам, которые мы получили в результате предыдущей операции. Понятно, что некоторые пути могут встречаться там несколько раз. Отсортируем этот массив. Прежде чем удалить из него повторения, заметим, что ими можно воспользоваться для подсчета ответа по файлам. Для этого просто подсчитаем какая из строк встречается больше всего раз – это и будет ответом по файлам (подумайте почему). После, нужно удалить повторения – это можно сделать, отсортировав все строки-пути и пройдя один раз по полученному массиву. Теперь у нас остался отсортированный массив путей, без повторений. Пусть наш массив будет s. Будем идти по массиву и искать строку, в которой ровно два обратных слеша – это будет означать, что мы нашли папку, которая находится в корне какого-то диска. Пусть индекс этой строки в массиве k. Тогда рассмотрим все строки, начиная с k+1 по k+l, такие, что они содержат строку s[k] как подстроку, начиная с стартовой позиции. А s[k+l+1] уже не содержит. То есть, имеется в виду, что если s[k]=X:\folder1\, то все подпапки этой папки будут иметь вид X:\folder1\... И естественно они и только они содержат s[k] как подстроку, при этом начиная с начала (выделено жирным).

Тогда, мы получим, что у папки X:<span lang="EN-US">folder1\ будет ровно l подпапок. Аналогично, пройдя так до конца массива, мы найдем ответ по максимальному количеству вложенных подпапок. Также можно было решать эту задачу используя set, или map вместо сортировки.


Задача D

Выберем N различных простых чисел: p1, p2, …, pn. Пусть A=p1*p2*...*pn. Тогда, нетрудно видеть, что в качестве ответа подходят следующие числа: A/p1, A/p2, …, A/pn. Единственный особый случай, это N=2. Здесь ответа не существует.

Следует заметить, что для такого решения этой задачи нужна длинная арифметика, при этом из операций нужно лишь умножение (A/pi=p1*…*p(i-1)*p(i+1)*…*pn). Если выбрать в качестве p1, …, pn первые n простых чисел, то самое большое из чисел в ответе на n=100, будет содержать меньше 300 знаков.

 

Однако существует еще решение. Рассмотрим ответ для N=3 – 15, 10, 6. Тогда, для произвольного N>3 подходят следующие числа: 15, 10, 6, 15*2, 15*3, …, 15*(N-2).

Задача E

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

D1=a1-b1,

D2=(a1+a2)-(b1+b2),

D3=(a1+a2+a3)-(b1+b2+b3),

Dn=(a1+a2+…+an)-(b1+b2+…+bn);

Очевидно, что если какое-то из чисел Di меньше нуля, то от первой станции машина не сможет проехать круг против часовой стрелки. Также рассмотрим число D=min(Di) – оно нам пригодится в дальнейшем решении. Очевидно, если D<0, то первая станция не может быть стартовой. Таким образом, за время O(N) мы умеем проверять, может ли первая станция быть стартовой. Покажем теперь, как проверить за O(1), может ли быть вторая станция стартовой. Для этого рассмотрим числа:

E1=D1-(a1-b1),

E2=D2-(a1-b1),

En=Dn-(a1-b1).

Распишем эти числа в более развернутом виде:

E1=(a1-b1)-(a1-b1)=0=(a2+a3+…+an+a1)-(b2+b3+…+bn+b1) – так как сумма всех ai равна сумме всех bi по условию.

E2=(a1+a2)-(b1+b2)-(a1-b1)=a2-b2

E3=(a1+a2+a3)-(b1+b2+b3)-(a1-b1)=(a2+a3)-(b2+b3)

En=(a1+a2+…+an)-(b1+b2+…+bn)-(a1-b1)=(a2+…+an)-(b2+…+bn)

Но, мы видим, что числа E1 для второй станции имеют тот же смысл, что и числа D1 для первой станции. Поэтому достаточно лишь проверить условие min(Ei)>=0. Но как это быстро проверить? У нас есть числа Di и из всех их вычитается одинаковое число => если минимум среди Di было число Dk, то среди Ei минимумом будет число Ek=Dk-(a1-b1). Таким образом, на то, чтобы проверить подходит ли в качестве ответа вторая станция – нам уже нужно O(1) операций. Аналогичным образом, зная минимум для второй станции мы проверим, подходит ли к ответу третья станция и так далее. После этого нужно не забыть решить задачу в обратном направлении, когда машина двигается по часовой стрелке.

Полный текст и комментарии »

Разбор задач Codeforces Beta Round 61 (Div. 2)
  • Проголосовать: нравится
  • +57
  • Проголосовать: не нравится

Автор Seyaua, 14 лет назад, По-русски
Здравствуйте!

Приглашаю всех принять участие в знаменательном раунде! Сегодня будет первый за всю историю Codeforces раунд для второго дивизиона, когда в конкурсе будут участвовать синие участники!

Сегодня авторами задач являюсь я и sdya
Выражаю благодарность всем тем, кто помогал готовить раунд, то есть Артему Рахову, Марии Беловой, Дмитрию Матову.

Всем удачи!

UPD #1: ссылка на разбор.

UPD #2: Поздравляем победителя второго дивизиона Kepnu4, а также победителя среди внеконкурсных участников и среди всех участников cerealguy!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +115
  • Проголосовать: не нравится

Автор Seyaua, 14 лет назад, По-русски
Задача A. Определите цвет

Здесь все понятно. Достаточно рассмотреть несколько случаев. Первый — когда расстояние от 
точки до начала координат — целое число, тогда ответ black. В противном случае, пусть d 
- это расстояние от нашей точки до начала координат. Тогда будем работать с [d]. Теперь 
осталось два случая: 1) если наша точка лежит в 1-ой, или 3-ей четверти; 2) точка лежит во 
2-ой, либо 4-ой четверти. В случае 1) имеем, если [d] нечетно, то ответ white, иначе 
black; в случае 2) если [d] четно, то ответ white, иначе black. Подразумевается, что 
[d] — целая часть d.

Задача B. Перекрашивания

Первое, что надо заметить, так это то, что на i-ом шаге все перекрашенные клетки будут 
лежать в прямоугольнике с вершинами в клетках (i,i), (n-i,m-i) (если считать, что (1,1) - 
левая верхняя клетка, а (n,m) — правая нижняя). Тогда отсюда уже следует решение: нужно 
подсчитать количество клеток такого типа, что минимальное расстояние до стороны в точности 
равняется x. То есть для клетки (a,b) должно выполняться 
min(min(a, b), min(n - a + 1, m - b + 1)) = x.

Задача C. Берляндская площадь

Идейно эта задача не очень сложная, но было много хитрых случаев. Авторское решение предполагало следующую идею. Сначала заметим, что наше множество окружностей на плоскости может быть несвязным. Тут есть два случая, когда есть хотя бы одна точка пересечения окружностей и когда нет ни одной. Если их нет, то ответ N+M+1. Иначе, если есть хотя бы одна точка пересечения, то мы можем удалить некоторые окружности таким образом, чтобы оставшаяся фигура из окружностей была связной. Тогда для этой фигуры можно применить формулу Эйлера. Таким образом, нам здесь нужно посчитать количество точек пересечения и количество дуг-ребер. Нетрудно видеть, что каждая точка пересечения добавляет две дуги. Таким образом, мы можем найти количество частей, на которые разделилась плоскость без удаленных окружностей. Теперь достаточно заметить, что каждая удаленная окружность добавляет ровно 1 к ответу. Весь вопрос в том, чтобы посчитать, сколько точек пересечения. Это можно сделать за O(N+M), если считать для каждой окружности, точки пересечения, которые принадлежат ей. Для этого достаточно заметить, что все окружности, с которыми наша окружность пересекается будут иметь радиусы l, l+1, ..., r. Также, с некоторыми из этих окружностей наша окружность будет иметь не две точки пересечения а одну. Это необходимо учесть в решении. После этого остается лишь аккуратно реализовать эту идею. 

Задача D. Интересная последовательность

Здесь нужно было погенерировать разные последовательности, которые могут получаться и внимательно смотреть на полученные значения. Основное наблюдение, это то, что каждое из чисел, которые встречаются в последовательности имеет вид 12k + 12m, при этом это число может встречаться лишь на позиции (k + m + 1). Теперь, когда известен общий вид, можно по методу математической индукции доказать, что на x-ой позиции могут встречаться все числа вида 12k + 12m, такие что, k + m + 1 = x. После этого можно было реализовать простое в написании решение за O(N3), где N — длина входного числа. Для этого перебираем все x от 1 до 600 и проверяем, существуют ли такие k и m, что k + m + 1 = x и 12k + 12m = A. Но также есть и решение со сложностью O(N2).

Задача E. Таблица из чисел

Первое, что должно было броситься в глаза, это то, что клеток, изначально не пустых — совсем мало. Из ограничений следует, что всегда есть пустая строка либо пустой столбец. Без ограничений общности можем считать, что у нас есть пустая строка и она последняя. Тогда выберем какой-либо столбец (к примеру, последний) и зафиксируем его одновременно с пустой строкой. Тогда по оставшейся таблице размера (n - 1) × (m - 1) клетки в последнем столбце и в последней строке заполняются однозначно. Но есть одно замечание, в последнем столбце уже стоят какие-то числа. Тогда нам надо для каждой строки, кроме последней подсчитать, сколько существует вариантов этой строки, таких, что произведение чисел в этой строке равно -1. В авторском решении, эта часть считалась при помощи динамического программирования. После этого нужно перемножить полученные ответы для каждой строки. Тогда ответ на задачу — это полученное произведение, либо 0 — если сумма n + m нечетна.


Разбор задач был подготовлен мной и sdya

Полный текст и комментарии »

Разбор задач Codeforces Beta Round 39
  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

Автор Seyaua, 14 лет назад, По-русски
Приглашаю всех принять участие в очередном раунде на Codeforces!

В этот раз авторами задач будем я и sdya. Немного о нас: мы учимся на втором курсе механико-математического факультета Харьковского национального университета им. В. Н. Каразина. И для тех, кто не знает - мы братья-близнецы. Программированием начали заниматься в конце 10 класса, то есть примерно 2,5 года назад. Никаких масштабных достижений в программировании у нас пока нет, но мы надеемся, что все еще впереди :)

Хочется сказать спасибо Артему Рахову, который помогал нам готовить этот контест, и Марие Беловой, которая перевела условия задач на английский язык. 

Желаем всем удачи в предстоящем раунде, надеемся, что задачи покажутся Вам интересными!

UPD: Контест завершен, поздравляeм Геннадия Короткевича, который стал победителем этого раунда. 

Ссылка на результаты и на разбор задач.


Полный текст и комментарии »

  • Проголосовать: нравится
  • +66
  • Проголосовать: не нравится