Хотелось бы узнать как решаются некоторые из задач. Олимпиада прошла, помогите пожалуйста. Задачи B и C. Условия задач под катом .
Воздушные шарики(Задача B)
Ограничение по времени 1 сек.
Ограничение по памяти 64 Мб.
У Маши день рождения. Паша решил сделать ей сюрприз и привязал в ряд N шариков. Каждый шарик в ряду либо красный, либо зеленый, либо синий. Увидев шарики, Маша очень обрадовалась, но не самому подарку, а тому, что придумала для себя новую головоломку. Она пронумеровала все шарики натуральными числами от 1 до N слева направо. Ей стало интересно, сколько существует таких пар чисел (L, R), что 1 ≤ L < R ≤ N и на отрезке от L до R (включительно) красных, синих и зеленых шариков поровну. При достаточно больших значениях N Маше сложно справиться с такой задачей. Поэтому она обратилась за помощью к Вам. Ваша задача – написать программу, которая посчитает количество таких пар за нее.
Входные данные
В первой строке входных данных находятся целое число N (3 ≤ N ≤ 105). Во второй строке входных данных находится строка из N символов, i-ый символ равен «R», если i-ый шарик – красный, «G» – если зеленый, «B» – если синий.
Выходные данные
В единственной строке выходных данных выведите единственное целое неотрицательное число – ответ на поставленную задачу.
Понять и простить(Задача C)
Ограничение по времени 1 сек.
Ограничение по памяти 64 Мб.
Дима учится в школе, в которой сегодня произошло достаточно неприятное происшествие. В очередной раз кто-то разбил стекло в одном из учебных классов. Все учителя школы возмущены. На педсовете было принято решение найти и наказать виновного на этот раз. Диме, как одному из лучших учащихся старших классов, поручили важное задание – найти виновника. Задача не из простых, но Диме повезло найти свидетеля этого происшествия, который готов ответить на любые вопросы. За каждый ответ на вопрос свидетель потребовал платить ему по рублю. Дима не мог не оправдать доверия учителей, а потому согласился. Дима заранее определил N подозреваемых в совершении такого злодеяния. Он также подготовил M вопросов, которые он может задавать свидетелю. Свидетель может отвечать на каждый из них либо «Да», либо «Нет». Для каждого вопроса известно, кто из подозреваемых невиновен в случае ответа «Да», а кто не виновен в случае ответа «Нет». Чтобы заплатить как можно меньше денег, Дима хочет задать как можно меньше вопросов. Причем Дима заранее не знает, как ответит ему свидетель, а потому он хочет знать минимальное количество вопросов, которое ему придется задать в худшем случае, если он будет действовать оптимально. Напишите программу, которая определит это количество. Стоит отметить, что свидетель всегда говорит правду (ему не нужны лишние проблемы) и знает ответы на все M вопросов. Также среди N подозреваемых гарантированно есть виновник происшествия.
Входные данные
В первой строке входных данных находятся два целых числа N и M, разделенных одним пробелом (2 ≤ N ≤ 20, 1 ≤ M ≤ 50). Далее во входных данных заданы N строк, каждая из которых описывает очередного подозреваемого и состоит из M символов. На j-ой позиции i-ой строки стоит символ «Y», если из ответа «Да» на j-ый вопрос следует, что i-ый подозреваемый невиновен. Если из ответа «Нет» на j-ый вопрос следует, что i-ый подозреваемый невиновен, то на j-ой позиции i-ой строки находится символ «N». Гарантируется, что строки для всех подозреваемых различны.
Выходные данные
В единственной строке выходных данных выведите единственное целое положительное число – ответ на поставленную задачу.
Спасибо за внимание.
Ух ты! Мои задачи уже публикуют на Codeforces. После второго раунда VK Cup опубликую разборы этих задач именно тут.
Вообще, конечно, я не могу понять смысла данного поста. Завтра Вы окажетесь на онсайте, где буду присутствовать я лично и на пальцах смогу рассказать решение любой из своих задач.
Идея задачи B:
Будем использовать идею частичных сумм. Для каждой позиции будем хранить тройку вида [SumRed, SumGreen, SumBlue], причем будем ее нормализовать так, чтобы минимум из трех элементов был равен нулю. Теперь для каждой такой тройки в массиве частичных сумм надо найти сколько таких же троек находится слева от нее. Можно просто отсортировать тройки и пройтись за линию для поиска одинаковых. Если есть K одинаковых троек, то добавим K(K-1)/2 в ответу.
Идея задачи C:
Будем использовать ДП по подмаскам. Маска задает студентов, которые еще находятся под подозрением. Переберем для каждой маски все вопросы, которые разбивают ее на две подмаски и рекурсивно решаем задачу для этих двух подмасок, добавив к наибольшему из этих двух решений единицу, мы получаем значение для текущего состояния. Заходила какая-то лютая жадность, на разбор которой у меня просто не было времени.
Спасибо большое. Ночью прочитал, осилил только C, с утра разобрался с B. Только получилось, что прибавляем K*(K-1)/2
Да, правильно. Молодец, что разобрался. Действительно, K(K — 1)/2. Просто у меня вчера был день программирования — внутривуз + подготовка школьного онсайта + VK Cup. Как результат — никакой внимательности к концу дня.
Может, пора остановить время в таблице?
До конца олимпиады осталось: -4 мин.
Задачи очного тура можно где-то посмотреть?
Да, по окончании очного тура можно будет. Школьники — народ хитрый, они быстро попросят помощи, если им дать ссылку на pdf с условиями. Да и задачи там очень простые. Вряд ли участнику первого дивизиона они покажутся интересными.
Окей, дождусь окончания :)
Участники видят результаты тестирования прямо во время тура?
Да. Более того, на последний час только они будут видеть таблицу замороженную с вопросиками на посланных задачах :)
А "болельщики" типа меня тоже будут видеть замороженную?
Во внутреннем интерфейсе таблица будет отключена. А вот эта вполне будет себе работать.
Вот тут класснее выглядит :)
Та версия, на которую я дал ссылку, предназначена для проектора. Поэтому у нее видок так себе. На проекторе смотрится, кстати, вполне себе неплохо.
А может вы тренировку на CF сделаете на этих задачах?
На этих задачах даже стыдно делать тренировку :)
Да ладно тебе :)
Уверен, что участникам div 2 она будет интересна, а участникам div 1 — просто порция фана.
P.S. Посылок как-то сильно много стало висеть.