Codeforces: изменение подсчёта рейтинга для новых аккаунтов Всем привет. В ближайшие дни я закончу реализацию небольших изменений подсчета рейтинга для новых аккаунтов. Вот основные нововведения. * Рейтинг нового аккаунта будет равен $0$ для отображения (но будет равен $1400$ при подсчете изменений рейтинга). * Допустим, после первого раунда участник на основании своих результатов получил $d_1$ единиц рейтинга (помните, что его рейтинг считался равным $1400$ при таких расчетах), то в отображении рейтинга после этого раунда будет отображен $500+d_1$. Таким образом, после первого участия рейтинг наверняка увеличится с $0$ до значения в районе $500$ (плюс-минус $300$ примерно). * Таким образом, перед вторым участием отображаемый рейтинг равен $500+d_1$, а рейтинг для подсчета изменений $1400+d_1$. Допустим, новое изменение будет равно $d_2$, тогда отображаемый рейтинг станет равен $500+d_1+350+d_2$. * Таким образом, перед третьим участием отображаемый рейтинг равен $500+d_1+350+d_2$, а рейтинг для подсчета изменений $1400+d_1+d_2$. Допуст...

Full text and comments »

Трансляции на Codeforces Всем привет! Сегодня на Codeforces появилась поддержка трансляций (стримов)! Спасибо Геннадию [user:tourist,2020-10-21] Короткевичу за отличную идею! Поддерживаются две популярные платформы — Twitch и YouTube. Пока возможность добавлять трансляции на Codeforces открыта красным участникам и по индивидуальным приглашениям. Позднее, мы, возможно, откроем эту возможность большему числу пользователей. Идея состоит в том, чтобы стримеры могли анонсировать свои трансляции на аудиторию Codeforces. Для этого трансляцию нужно добавить на сайт, используя специальный раздел в профиле. Обратите внимание, что при добавлении Twitch-трансляции вам надо указать просто URL вашего канала, а при добавлении YouTube-трансляции — её уникальную короткую ссылку (ссылку на видео youtu.be/…). Незадолго до старта трансляции в сайдбаре справа появится уведомление о предстоящей трансляции, которое будут видеть все посетители сайта. Если вы указали название трансляции только на русском язы...

Full text and comments »

Codeforces: серия обновлений (рейтинг, раунды) <img src="/predownloaded/21/a3/21a33b497ee8a34a678befc3f79745eb69a9cf07.png" style="float:right; margin: 0 1em 1em 1em;"/> Привет, Codeforces! Настало время новостей. Надеюсь, вам понравится! * Мы немного опускаем границу рейтинга для оранжевых участников. Таким образом, теперь оранжевый рейтинг (и звание _мастер_) будет начинаться от 2100 единиц рейтинга. * Нижняя граница рейтинга для _легендарных гроссмейстеров_ увеличена до 3000 единиц рейтинга. Таким образом, прямо сейчас в сообществе 14 участников соответствуют этому требованию. Настоящие легенды! * Для раундов серии «только для Div. 2» увеличена верхняя граница рейтинга для официального участия. Теперь все, чей рейтинг менее 2100 (то есть до _кандидатов в мастера_ включительно) смогут зарегистрироваться на такие раунды для участия в конкурсе, их рейтинг будет обновлён по результатам раунда. Мы не планируем повышать сложность Div. 2 раундов. Практика показывает, что задачи таких раундов и сейчас интересны и полезны ...

Full text and comments »

Новое на Codeforces: возможность переписать условие в мэшапе Привет, Codeforces! Есть кое-что новое. Кажется, теперь переиспользовать задачи с раундов в учебных и прочих целях станет проще. Как вы знаете, <a href="https://codeforces.me/blog/entry/10099">в мэшапы</a> можно добавлять задачи с прошедших раундов Codeforces просто по их кодам вида <code>1234D</code> (айдишник контеста + буква задачи). Я сам регулярно этим пользовался, когда преподавал в Саратовском университете &mdash; очень удобно было так делать тренировки: задачи ожидаемой сложности и тематики, есть русское и английское условия, можно посмотреть разбор и множество решений. Почти всюду очень сильные тесты по причине поддержки взломов и довзламывания, задачи хорошо подготовлены. Кроме того, с помощью <a href="https://codeforces.me/blog/entry/21912">списков пользователей</a> можно для группы учащихся легко подобрать задачи, которые они не решали. <img src="/predownloaded/ac/ae/acae3c9dda56f3fd7a480ec96ed717dd5ca18f49.png" style="float:right; margin: 0 1em 1em 1em; width:60...

Full text and comments »

Good Bye 2019 Снова привет, Codeforces! Мы ради пригласить вас на <s>Mathforces</s> <s>Thinkforces</s> [Good Bye 2019](https://codeforces.me/contests/1270), который пройдет [contest_time:1270]. Немного информации о раунде: <ul> <li>Рейтинговый для всех участников!</li> <li>3 часа!</li> <li> <strong> Никаких подзадач! </strong> </li> <li> В раунде будет <strong> интерактивная задача </strong>. Вы можете ознакомиться с руководством по интерактивным задачам [здесь](https://codeforces.me/blog/entry/45307)</li> <li> Разбор будет опубликован сразу после окончания системного тестирования </li> </ul> Все задачи в этом раунде были приготовлены нами, [user:antontrygubO_o,2019-12-28] и [user:kefaa2,2019-12-28]. Мы долго работали над эти раундом и постарались сделать все задачи очень интересными. Надеемся, вам понравится раунд! Мы бы хотели поблагодарить: <ul> <li> [user:arsijo,2019-12-24] за координацию раунда </li> <li> [user:GandalfTheGrey,2019-12-24] за идею решени...

Full text and comments »

Code Weekend #1 <div align="right" margin="20px"> <img align="right" src="/predownloaded/72/f1/72f1f31badb1452243838a0fc2553c04accff164.jpeg" alt="logo" width="300px" height="300px" margin="20px"/></div> Всем привет! Мы, команда [RGBTeam](https://clist.by/team/Romka,tourist,%E2%88%A83886090/) ([user:qwerty787788,2024-05-21], [user:Romka,2024-05-21] и [user:tourist,2024-05-21]) очень любим эвристические соревнования по программированию и очень грустим из-за того, что с каждым годом их становится всё меньше и меньше. И вот, как-то однажды мы подумали, что хватит это терпеть, и решили организовать своё соревнование :) Несмотря на то, что часто такие идеи остаются лишь идеями, в этот раз мы были полны решимости довести дело до конца и сейчас хотим пригласить вас всех поучаствовать в первом и, хочется надеяться, не последнем **[Code Weekend #1!](https://codeweekend.dev)** Соревнование пройдёт в формате, довольно близком к ICFPC/Hashcode &mdash; будет дана одна задача и несколько десятков тестов к н...

Full text and comments »

Codeforces: Итоги 2017 <img src="/predownloaded/e4/09/e40915ee54c5991b91098756a90270d94be893b3.jpg"/> С Новым годом, Codeforces! Спешу пожелать всей аудитории (и мне в том числе) работающих программ, внезапных озарений, красивых идей и интересных задач! Я надеюсь, что вы встретили новый год так же весело, как и я. Успели выспаться после новогодней ночи? В этом году традиционный пост подведения итогов прошедшего года я сел писать только 1-го января 2018-го. Надеюсь, мне не придется теперь весь год подводить итоги. Этот пост важен для меня, так как он подводит черту всей работе, которая проделана командой Codeforces и всем сообществом в 2017-м году. Огромное спасибо команде: все перечисленные ниже достижения &mdash; результат общих трудов и усилий. Мы отлично поработали! Сообщество должно знать своих героев. В 2017-м году в развитии проекта принимали участие: [user:MikeMirzayanov,2018-01-01], [user:KAN,2018-01-01] (координатор задач), [user:gritukan,2018-01-01] (второй координатор задач), [user:ne...

Full text and comments »

Codeforces: подводим итоги 2016-го года <center> <img src="http://assets.codeforces.com/images/Happy-New-Year-HD-Wallpapers.jpg"/> </center> Как-то так получается, что лично для меня каждый следующий Новый год значит всё больше. Это отличный повод подвести итоги, перехватить воздух, пережить своеобразный катарсис. Это редкая возможность побыть с семьей, нарядиться в Деда Мороза и просто повеселиться. Еще праздники дарят мне четкий критерий того, что я занимаюсь правильным для себя делом. Если в праздники я начинаю думать об этом деле, вспоминать какие-то отложенные идеи, горю желанием реализовать что-то новое. Значит это оно. Твоё. Настоящее. И вот уже который год я под самый Новый год и сразу после него коммичу в Codeforces новое, вникаю в новую технологию или просто вношу мелкую правку в testlib. Надо мной в этот момент не стоят никакие сроки, не давят обязательства. Просто именно сейчас, в 3 часа ночи я не могу оторваться от того, чтобы сделать что-то новенькое. Хочется воспользоваться моментом и реализовать то, ч...

Full text and comments »

Как провести Div 1 или Div 2 раунд на Codeforces Как вы наверняка знаете, большинство раундов на Codeforces созданы активными участниками нашего сообщества. Мы очень благодарны талантливым авторам со всего мира за то, что они знакомят десятки тысяч участников наших соревнований со своими идеями, предоставляя возможность учиться и получать удовольствие от решения задач как новичкам, так и лучшим в мире спортивным программистам. Этот пост расскажет, как стать автором задач и провести раунд на Codeforces. ## Кто может стать автором Обычно авторами наиболее интересных и качественных задач являются опытные участники. Так как наши ресурсы по обработке предложений задач ограничены, то с 1-го января 2021, для предложения своих задач вы должны удовлетворять следующим условиям: - рейтинг &mdash; 2100 или выше, или - уже был автором. В будущем ограничения могут быть изменены, пост будет обновлен. Если вы уже открыли ваш раунд для ревью, то он будет рассмотрен независимо от действующих ограничений, не волнуйтесь. Если вы не подхо...

Full text and comments »

Петиция по поводу флага Беларуси Привет всем беларусам, которые активно, или не очень, участвуют в жизни замечательного сообщества Codeforces. Хотелось бы заручиться вашей поддержкой в том, чтобы инициировать смену флага Беларуси на данном ресурсе на исторический [бело-красно-белый флаг](https://ru.wikipedia.org/wiki/%D0%91%D0%B5%D0%BB%D0%BE-%D0%BA%D1%80%D0%B0%D1%81%D0%BD%D0%BE-%D0%B1%D0%B5%D0%BB%D1%8B%D0%B9_%D1%84%D0%BB%D0%B0%D0%B3), потому что государственный флаг Республики Беларусь стал стойко ассоциироваться с преступлениями против человечности, с той жестокостью, пытками, зверствами, нарушениями прав человека, которые, к сожалению, стали обыденностью в последние месяцы в нашей прекрасной стране. <html> <body> <img src="https://upload.wikimedia.org/wikipedia/commons/thumb/5/50/Flag_of_Belarus_%281918%2C_1991%E2%80%931995%29.svg/500px-Flag_of_Belarus_%281918%2C_1991%E2%80%931995%29.svg.png" style="display: block; width:30%; margin: 0 auto; border: 1px solid black"> </body> </html> Вне публичной ...

Full text and comments »

Codeforces Round #741. Как развлекается автор контеста. Привет, Codeforces! Не так давно прошел мой второй раунд, Codeforces #741 (Div. 2). Перед его началом, я задумался: ведь наверняка на моем раунде, как и на любом другом, процветает читерство? И я решил сделать кое-что необычное. Как известно из [одного блога о читерах](https://codeforces.me/blog/entry/93893), искать telegram/youtube каналы с читерами не составляет никакого труда. И я решил найти парочку и вступить в них... Итак, первая telegram-группа, которую я нашел, это [ссылки пока нет]. В ней было не так много читеров, но все же они были, вот пример: <spoiler summary="Картинка"> <a href="https://imgbb.com/"><img src="https://i.ibb.co/kJqMzMS/pic1.png" alt="pic1" border="0"></a> </spoiler> Я вступил в эту telegram-группу, и состоялся содержательный диалог примерно такого плана: <spoiler summary="Картинка"> <a href="https://ibb.co/1mC2csG"><img src="https://i.ibb.co/VqFB6HY/pic2.png" alt="pic2" border="0"></a> </spoiler> Это может показаться невероятным, но ...

Full text and comments »

О раунде 382 Добрый день! Спешу поделиться своими мыслями о недавно прошедшем раунде 382. Конечно, получилось так себе и расстроен не только я, но и координатор раунда Глеб [user:GlebsHP,2016-11-28] Евстропов. В данном раунде основной негатив вызвали две задачи: задача [problem:735D] и задача [problem:735C]. Касательно [problem:735D] я не вполне разделяю критического отношения к этой задаче. В самом деле, для ее решения неплохо было иметь представление о <a href="https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D0%93%D0%BE%D0%BB%D1%8C%D0%B4%D0%B1%D0%B0%D1%85%D0%B0">проблеме Гольдбаха</a>, да и вообще о <a href="https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B8_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%8B%D1%85_%D1%87%D0%B8%D1%81%D0%B5%D0%BB">распределении простых чисел</a>. Эти факты являются средне-популярными в среде спортивного программирования (нельзя ...

Full text and comments »

Codeforces Round #672 (Div. 2) Привет, Codeforces! Я очень рад пригласить вас на [Codeforces Round #672 (Div. 2)](https://codeforces.me/contest/1420), который пройдет в [contest_time:1420]. <b>Этот раунд будет рейтинговым для участников, чей рейтинг ниже 2100.</b> Все задачи придумал я, но с двумя последними задачами очень помог [user:gepardo,2020-09-22], без него этих задач могло бы и не быть. Мои благодарности: - [user:antontrygubO_o,2020-09-22] за координацию раунда. Именно благодаря такой отличной координации в соревновании остались только хорошие задачи. Спасибо! - [user:gepardo,2020-09-22] сделал много чего, без него этого соревнования просто не было бы! Он не только помог с двумя последними задачами, но и помогал мне разбираться, как правильно делать задачи на Codeforces. Спасибо! - [user:EIK,2020-09-22] это тот человек, без которого я бы вообще не попал в спортивное программирование — мой учитель информатики. Спасибо! - [user:programmer228,2020-09-22], [user:Hacktafly,2020-09-22], [user...

Full text and comments »

Новинка: учебные раунды на Codeforces! Всем привет! Во-первых, приглашаю вас принять участие в неофициальном тестовом раунде [contest:597]. Дело в том, что команда Codeforces внесла множественные изменения в платформу (о чем чуть позже), и все мы хотим быть уверенными, что основная функциональность осталась без изменений. Этот раунд будет иметь сокращенную длительность 1.5 часа, состоять из 3 (может, и 4) задач, которые вы могли уже где-то и видеть ранее. Цель его &mdash; с одной стороны, протестировать систему, а с другой &mdash; скрасить вечер среды. Конечно, раунд будет нерейтинговым. Теперь самое главное. В ближайшую пятницу (да, 13-го ноября) Codeforces стартует еще одну линейку раундов. Мы назвали их учебными раундами (Educational Rounds). На примере моих студентов в Центре олимпиадной подготовки программистов Саратовского государственного университета (ЦОПП-СГУ) я регулярно замечаю, что даже те из них, кто имеет заметный прогресс в результатах на раундах, зачастую имеют неширокий кругозор в плане стандартных те...

Full text and comments »

[Tutorial] Пересечение матроидов простыми словами **[This article is also available in [English](https://codeforces.me/blog/entry/69287?locale=en)]** Привет, CodeForces. Я думаю, что матроиды &mdash; это прекрасные и очень мощные структуры, однако, не настолько хорошо известные в спортивном программировании. Я познакомился с матроидами на Зимних Петрозаводских Сборах 2019. Там была задача, которая очевидно не решалась обычными способами, известными мне тогда. Разбор этой задачи состоял буквально из трех слов “just matroid intersection”. Тогда мне потребовалось больше двух дней дорешивания чтоб найти всю необходимую информацию и детали и написать решение, которое получает Accepted. И намного больше времени мне потребовалось чтобы понять почему это действительно работает и как именно это работает. (Я до сих пор сомневаюсь в некоторых деталях.) Конечно, совершенно не трудно нагуглить все необходимые определения и статьи, связанные с этой темой, но мне кажется, что все они больше сконцентрированы на математической теории, с...

Full text and comments »

Общие идеи Всем привет! Любители ли вы задачи, которые расчитаны на Ad Hoc решение? Я &mdash; терпеть не могу! Поэтому я решил сделать подборку идей, которые могут быть применены к достаточно большому классу задач. Добавляйте ещё, если о чём-то забыл. :) [cut]<br> **1. Слияние множеств за $O(n\log{n})$ амортизированно.** Если у нас есть некоторые множества, которые нам потом нужно будет соединять, поддерживая промежуточные результаты, то можно делать это в лоб, всегда добавляя меньшее множество к большему. Таким образом, каждый элемент будет перенесён в какое-то другое множество не более, чем $O(\log{n})$ раз, так как новое множество для него каждый раз будет увеличиваться хотя бы в два раза. На этом, в частности, основана одна из версий общеизвестного _DSU_. Из применений &mdash; можно сливать множества внутри обхода дерева в глубину и таким образом можно для каждой вершины в какой-то момент времени подержать в руках множество всех элементов её поддерева. **2. Подвохи в задачах. Час...

Full text and comments »

Как придумывать решения задач: приемы Работая со студентами, я часто сталкиваюсь с тем, что если задача не кажется им понятной с первого взгляда, то они и не могут ее решить. В самом деле, всегда рассказывают конкретные методы и приемы, но не то, как надо думать, чтобы применить их. В этой заметке я попробую обобщить мой опыт решения задач на соревнованиях по программированию. Впрочем, некоторые советы будут применимы и для олимпиад по математике или первых шагов в научной работе. Итак, вы прочли задачу и не знаете как ее решать. Попробуйте следующие приемы, зачастую какой-то из них может помочь. ##### Прием 1: "Вспомнить всё" Попробуйте вспомнить какие-то похожие задачи, которые вам приходилось решать. Очень многие задачи не несут в себе совсем уж оригинальной идеи и, вероятно, опыт решения подобной задачи может быть использован для решения этой. ##### Прием 2: "От частного к общему" Представьте, что вы нашли решение задачи (ура!) Рассмотрите какой-то частный случай задачи. К нему, конечно, может быть при...

Full text and comments »

Для авторов контестов: новый порядок подачи заявок <i>В 2021-м году некоторые детали, в том числе требования к авторам были изменены. Подробности прочтите здесь <a href="https://codeforces.me/blog/entry/85259">https://codeforces.me/blog/entry/85259</a>.</i> Привет, Codeforces! Новый год приносит изменения в состав команды Codeforces. <a href="/blog/entry/49466">Как вы уже, наверное, знаете</a> [user:GlebsHP,2017-01-04] завершил свою работу в качестве главного координатора Codeforces. Глеб, спасибо большое! Ты сделал отличную работу, помог провести большое количество интересных раундов. Ты настоящий профессионал, интересный человек, у тебя безупречный вкус к задачам, и сам ты зарекомендовал себя ярким и талантливым автором. Спасибо, что ты был с нами! Надеюсь еще не раз увидеть твои задачи на Codeforces! На смену Глебу пришел Николай [user:KAN,2017-01-04] Калинин. Он тоже опытнейший участник, уже провел в качестве координатора несколько раундов. Николай серьезно занимается программированием с седьмого класса (12 лет). Его о...

Full text and comments »

Educational Codeforces Round 100 [рейтинговый для Div. 2] Привет, Codeforces! В [contest_time:1463] состоится [contest:1463]. Продолжается серия образовательных раундов в рамках инициативы [Harbour.Space University](https://harbour.space/)! Подробности о сотрудничестве [Harbour.Space University](https://harbour.space/) и Codeforces можно прочитать <a href="http://codeforces.me/blog/entry/51208">в посте</a>. Этот раунд будет **рейтинговым для участников с рейтингом менее 2100**. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования. Вам будет предложено **6 или 7 задач на 2 часа**. Мы надеемся, что вам они покажутся интересными. Задачи вместе со мной придумывали и готовили Роман [...

Full text and comments »

Codeforces Round #270 Хотите выиграть футболу? Или узнать как придумывать задачи для соревнований по программированию? А как насчет порешать 7 задач за два с половиной часа? Если ответ хотя бы на один вопрос из перечисленных выше -- да, тогда Codeforces Round #270 непременно для вас. Раунд был разработан мной в Калифорнии, и приготовлен в системе Polygon (оригинал: designed by me in California, assembled in polygon). Спасибо [user:MikeMirzayanov,2014-09-28] за прекрасную систему и [user:Gerald,2014-09-28] за помощь в организации и тестирование раунда. Раунд стартует [в обычное время в воскресенье](http://www.timeanddate.com/worldclock/fixedtime.html?day=28&month=9&year=2014&hour=19&min=30&sec=0&p1=166), не упустите возможность посоревноваться! Организаторы **<a href="/blog/entry/13929">Marathon24</a>** решили сделать подарок лучшим участникам раунда! Лучшие 25 участников получат специальные футболки от Marathon24! Большое им спасибо! <center> <img src="http://www.elmostshirts.com/images/tshirts.jp...

Full text and comments »

Codeforces Month of Blog Posts Pt. II (Выиграйте $800+!) **TL;DR: Опубликуйте интересный блог на Codeforces до 15 октября и выиграйте $800+1!** **UPD: Мы решили продлить конкурс до 15 ноября!** _Этот блог вдохновлен [месяцем блогов на Codeforces](https://codeforces.me/blog/entry/110840) от [user:peltorator,2024-09-25]._ Привет всем! Прошлый конкурс помог мне тогда, когда я больше всего в этом нуждался. Так что теперь я хочу отплатить сообществу обратно &mdash; организовать Codeforces Month Of Blog Posts еще раз! ### Вступление Мое мнение о блогах совпадает с мнением peltorator'а &mdash; я большой фанат Codeforces, он почти что заменяет мне социальные сети, а блоги &mdash; одна из лучших его частей! Многие люди ждут лучшего времени для публикации своих блогов, откладывают его на потом &mdash; теперь это время пришло! ### Правила и сроки Правила просты: **1. Опубликуйте что-нибудь на Codeforces **(с переводом на английский язык)** не ранее 10 сентября (00:02 UTC) 2024 года.** Мы ищем новые идеи / новые взгляды на темы,...

Full text and comments »

Куда развлечения завели автора контеста. Обманываем читеров. Привет, Codeforces! Месяц назад я написал [свой блог о читерах](https://codeforces.me/blog/entry/94300). Под тем блогом скопилось ряд предложений, да и у меня накопился ряд интересных идей, которые можно было бы применить для саботажа в группе читеров. Стоит отметить, что я часто видел комментарии по типу: <spoiler summary="Картинки"> <a href="https://imgbb.com/"><img src="https://i.ibb.co/r65zfTL/cheat1.png" alt="pic1" border="0"></a> <a href="https://imgbb.com/"><img src="https://i.ibb.co/Yh6ZfY8/cheat2.png" alt="pic2" border="0"></a> </spoiler> Ну, делать то, что предложил [user:Ari,2021-09-28] я не очень хотел, а вот проверить, что будет, если послать неверные решения, стоило. Перед этим я спросил у одного пользователя, что будет, если читерам послать неверные решения. На что он сказал, что его знакомые уже так делали, но их быстро разоблачали. Я задумался: а можно ли водить читеров за нос, оставаясь непойманным? Но для этой проверки мне нужно было кое-что сделать. ...

Full text and comments »

Похоже, против LLM-читинга мы смотрим не на то ### 1. Что именно за проблема Во время раундов появилась конкретная схема: участник получает у LLM готовый код и просто отправляет его, почти не понимая. Это не всегда ловится плагиатом: человек может изменить переменные, поменять местами некоторые части кода. ### 2. Идея #### Xeppelin — open-source tool, изначально сделанный для ICPC, который: - запускается локально перед контестом - логирует изменения файлов в рабочей директории - сохраняет таймлайн разработки (когда и как менялся код) - не записывает экран, клавиатуру, сеть или вкладки - после контеста строит визуализацию активности #### [Это не мой tool, но вы можете найти его тут](https://github.com/KiK0S/xeppelin) ### 3. Что именно предлагается для Codeforces (реализация, не идея) Предложение — использовать Xeppelin как внешний источник поведенческих данных, без вмешательства в CF-инфраструктуру. Поток работы: 1. Участник запускает Xeppelin перед раундом 2. Решает задачи как обычно (локально, в ...

Full text and comments »

Codeforces Round #539 (Div. 1, Div. 2) Доброго времени суток, Codeforces! Представляю вашему вниманию [Codeforces Round #539](https://codeforces.me/contests/1109,1113), который пройдет в эту [субботу, 16 февраля 2019 г. в 19:35](https://www.timeanddate.com/worldclock/fixedtime.html?day=16&month=2&year=2019&hour=19&min=35&sec=0&p1=166). Раунд будет **рейтинговым** для обоих дивизионов. Авторы задач: [user:markysha,2019-02-14], [user:xolm,2019-02-14], [user:aleex,2019-02-14]. Это наш первый раунд на Codeforces, и, надеюсь, не последний :) Выражаем благодарность всем кто помог в подготовке задач: - Нашему координатору [user:arsijo,2019-02-14] за помощь во всем - Большое спасибо [user:kefaa2,2019-02-14], [user:GandalfTheGrey,2019-02-14], [user:sharepoLOVEDDD,2019-02-14], [user:austrian_artist,2019-02-14], [user:Adalbert,2019-02-14], [user:StasyaCat,2019-02-14], [user:Fekete,2019-02-14] и [user:Daryusz,2019-02-14] за прорешивание задач (да, да к тестированию мы подошли основательно :)) - [user:gepardo,2019-02...

Full text and comments »

Codeforces Round #764 (Div. 3) Привет! В [contest_time:1624] начнётся [contest:1624] — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 7-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса. Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза **открытых взломов**. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста. Вам будет предложено **7-8 задач** и **2 часа 15 минут** на их решение. Одна из задач интерактивная. Не забудьте прочитать [инструкцию по интерактивным задачам](https://codeforces.me/blog/entry/45307). **Штраф** за неверную попытку в этом раунде будет равняться **10 минутам**. [Напоминаем](https://codefo...

Full text and comments »

Разбор Codeforces Round #770 (Div. 2) Спасибо за участие, надеемся, что вам понравились задачи! Также мы просим вас оценить каждую из задач раунда в соответствующем спойлере, чтобы улучшить качество будущих соревнований. Все задачи были подготовлены [user:Alexdat2000,2022-02-02] при помощи соавторов. [Почему AI не участвовал](https://codeforces.me/blog/entry/99579?#comment-884764) [problem:1634A]<br> Идея: [user:sevlll777,2022-02-02] <div class="spoiler"> <b class="spoiler-title">Подсказка 1</b> <div class="spoiler-content" style="display: none;"> Каким свойством будет обладать строка после первой операции (независимо от типа операции)? </div></div> <div class="spoiler"> <b class="spoiler-title">Подсказка 2</b> <div class="spoiler-content" style="display: none;"> Что произойдет, если применить операцию к палиндрому? </div></div> <div class="spoiler"> <b class="spoiler-title">Разбор</b> <div class="spoiler-content" style="display: none;"> [tutorial:1634A]</div></div> <spoiler summary="Решение"> ...

Full text and comments »

Разбор Educational Codeforces Round 87 [problem:1354A] Идея: [user:BledDest,2020-05-18] <spoiler summary="Разбор"> [tutorial:1354A] </spoiler> <spoiler summary="Решение (pikmike)"> ~~~~~ t = int(input()) for _ in range(t): a, b, c, d = map(int, input().split()) if b >= a: print(b) continue if c <= d: print(-1) continue a -= b dif = c - d print(b + (a + dif - 1) // dif * c) ~~~~~ </spoiler> [problem:1354B] Идея: [user:BledDest,2020-05-18] <spoiler summary="Разбор"> [tutorial:1354B] </spoiler> <spoiler summary="Решение (BledDest)"> ~~~~~ #include<bits/stdc++.h> using namespace std; char buf[200043]; int main() { int t; scanf("%d", &t); for(int i = 0; i < t; i++) { scanf("%s", buf); string s = buf; int ans = int(1e9); int n = s.size(); vector<pair<char, int> > c; for(auto x : s) { if(c.empty() || c.back().first != x) c.push_back(make_pair(x, 1)); else c.back().second++; } int m = c.size(); for(int i...

Full text and comments »

Codeforces Round #656 (Div. 3) &lt;too-old-joke-about-copy-paste&gt; Привет! В [contest_time:1385] начнётся [contest:1385] &mdash; очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач (или 8), которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса. Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты &mdash; так же как и вы буду расстроен, если у многих попадают решения после окончания контеста. Вам будет предложено 6 или 7 (или 8) задач и 2 часа на их решение. **Штраф** за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться **10 минутам**. [Напоминаем](/blog/entry/59228), что в таблицу официальных результатов попадут тол...

Full text and comments »

Jngen: универсальный генератор тестов Два года назад я [вкидывал](http://codeforces.me/blog/entry/20108) в сообщество идею о библиотеке, которая умеет генерировать разные клёвые тесты. Я долго крутил идею в голове и наконец попытался что-то написать. Реализовано пока далеко не всё из того, что хочется, но то, что уже есть, я активно использую в своих задачах. Итак, встречайте: https://github.com/ifsmirnov/jngen. Саму библиотеку (точнее, единственный хедер jngen.h) можно скачать [тут](https://raw.githubusercontent.com/ifsmirnov/jngen/master/jngen.h). Jngen умеет работать с массивами, деревьями и графами, а также генерировать немного строк и геометрии. Есть парсер опций командной строки и клёвая SVG-рисовалка. Можно делать, например, так. ~~~~~ cout << Array::id(10).shuffled().add1() << endl; // permutation of elements from 1 to 10 cout << Tree::random(100000, 20) << endl; // "long" tree with elongation 20 pair<string, string> test = rnds.antiHash({{mod1, base1}, {mod2, base2}}, "a-z", 10000); // should be s...

Full text and comments »

Codeforces Round #461 (Div. 2) _Привет, Codeforces! Давно не виделись :D_ Codeforces Round #461 состоится [в среду в 20:15 по московскому времени](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Codeforces+Round+%23461+%28Div.+2%29&iso=20180207T2015&p1=352&ah=2). Обратите внимание, что раунд чуть позже, чем обычно. Раунд будет **рейтинговым** для участников из второго дивизиона. Первый дивизион тоже приветствуется, но вне конкурса :) Спасибо Коле ([user:KAN, 2018-02-04]) за координацию раунда, Грише ([user:gritukan, 2018-02-04]), Олегу ([user:x3n, 2018-02-04]), АмирРезе ([user:Arpa, 2018-02-04]) и Сене ([user:senek_k, 2018-02-04]) за тестирование и, конечно, Майку ([user:MikeMirzayanov, 2018-01-01]) за Codeforces и Polygon. Отдельная благодарность отправляется Диме ([user:mitterr1999, 2018-02-04]) и Камилю ([user:pseuda, 2018-02-04]) за идею одной из задач. В этом раунде вы будете помогать игривому монстрику Импу. Не пугайтесь, условия будут короткими! ![ ](https://vk.com/images/stickers/2...

Full text and comments »

Codeforces Round #925 (Div. 3) Привет! В [contest_time:1931] начнётся [contest:1931] — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса. Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза **открытых взломов**. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста. Вам будет предложено **7 задач** и **2 часа 15 минут** на их решение. **Штраф** за неверную попытку в этом раунде будет равняться **10 минутам**. [Напоминаем](https://codeforces.me/blog/entry/59228), что в таблицу официальных результатов попадут только _достоверные участники третьего дивизиона_. Как напи...

Full text and comments »

Разбор Educational Codeforces Round 95 [problem:1418A] Идея: [user:vovuh,2020-09-15] <spoiler summary="Разбор"> [tutorial:1418A] </spoiler> <spoiler summary="Решение (vovuh)"> ~~~~~ for i in range(int(input())): x, y, k = map(int, input().split()) print(((y + 1) * k - 1 + x - 2) // (x - 1) + k) ~~~~~ </spoiler> [problem:1418B] Идея: [user:BledDest,2020-09-15] <spoiler summary="Разбор"> [tutorial:1418B] </spoiler> <spoiler summary="Решение (Ne0n25)"> ~~~~~ #include <bits/stdc++.h> using namespace std; #define sz(a) int((a).size()) #define forn(i, n) for (int i = 0; i < int(n); ++i) void solve() { int n; cin >> n; vector<int> a(n), b(n), c; forn(i, n) cin >> a[i]; forn(i, n) cin >> b[i]; forn(i, n) if (!b[i]) c.push_back(a[i]); sort(c.rbegin(), c.rend()); int j = 0; forn(i, n) { if (b[i]) cout << a[i] << ' '; else cout << c[j++] << ' '; } cout << '\n'; } int main() { int T; c...

Full text and comments »

Codeforces Round #653 (Div. 3) &lt;almost-copy-pasted-part&gt; Привет! В [contest_time:1374] начнётся [contest:1374] &mdash; очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач (или 8), которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса. Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты &mdash; так же как и вы буду расстроен, если у многих попадают решения после окончания контеста. Вам будет предложено 6 или 7 (или 8) задач и 2 часа на их решение. **Штраф** за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться **10 минутам**. [Напоминаем](/blog/entry/59228), что в таблицу официальных результатов попадут только <i...

Full text and comments »

Codeforces Round #295: разбор (теперь с бонусами!) Мы хотели бы также поблагодарить тестеров задач этого раунда и олимпиады ЗКШ: [user:alger95,2015-03-02], [user:thefacetakt,2015-03-02], [user:adamant,2015-03-02], [user:dragonic,2015-03-02], [user:Who179,2015-03-02], [user:ASverdlov,2015-03-02]. Пожалуйста, пишите в комментариях о найденных ошибках. **UPD**: я вспомнил, что забыл написать регулярные бонусные челленджи. Так что вот, пожалуйста. [problem:520A] Идея:[user:Endagorion,2015-03-02] Подготовка:[user:Endagorion,2015-03-02] Чтобы проверить, что все буквы присутствуют, заведем массив длины 26 и для каждой буквы поставим в соответствующую ячейку единичку. В конце надо проверить, что все 26 единичек на месте. Решение работает за $O(n)$. Также надо не забыть перевести все буквы к нижнему регистру (или наоборот, все буквы к верхнему). Чтобы перевести буквы в нижний регистр, можно использовать встроенные функции, например, `tolower` в Python. Также можно пользоваться тем, что буквы от `a` до `z` идут подряд по их ...

Full text and comments »

Codeforces Global Round 16 Editorial Мы надеемся, что вам понравился контест. Сразу к разбору: <spoiler summary="A: Максимизация медианы"> [problem:1566A] <spoiler summary="Первое решение"> <spoiler summary="Подсказка 1"> Какие числа меньше медианы нужно брать? </spoiler> <spoiler summary="Подсказка 2"> Какие числа больше медианы нужно брать? </spoiler> <spoiler summary="Подсказка 3"> Жадный алгоритм. </spoiler> <spoiler summary="Разбор"> Будем рассматривать искомый массив из $n$ чисел в порядке неубывания. Заметим, что числа до медианы можно сделать равными нулю, после чего останется $m = \lfloor {\frac{n}{2}} \rfloor + 1$ чисел, сумма которых должна быть равна $s$, причём минимальное из них (то есть медиана) должно быть максимально. Чтобы этого добиться, достаточно сначала сделать эти числа равными $\lfloor {\frac{s}{m}} \rfloor$, а потом добавить к последнему числу то, что осталось от $s$, то есть $s \bmod m$. Нетрудно убедиться, что такой массив удовлетворяет всем условиям, причём сделать ...

Full text and comments »

Разбор Educational Codeforces Round 70 [problem:1202A] Идея: [user:adedalic,2019-08-08] <spoiler summary="Разбор"> [tutorial:1202A] </spoiler> <spoiler summary="Решение (adedalic)"> ~~~~~ fun main(args: Array<String>) { val T = readLine()!!.toInt() for (tc in 1..T) { val x = readLine()!!.reversed() val y = readLine()!!.reversed() val posY = y.indexOf('1') val posX = x.indexOf('1', posY) println(posX - posY) } } ~~~~~ </spoiler> [problem:1202B] Идея: [user:adedalic,2019-08-08] <spoiler summary="Разбор"> [tutorial:1202B] </spoiler> <spoiler summary="Решение (adedalic)"> ~~~~~ const val INF = 1e9.toInt() fun main(args: Array<String>) { val s = readLine()!!.map { it - '0' } val cf = Array(10) {Array(10) {0}} for (i in 1 until s.size) cf[s[i - 1]][s[i]]++ for (x in 0..9) { for (y in 0..9) { val ds = Array(10) {Array(10) {INF + 7}} for (v in 0..9) { ...

Full text and comments »

Codeforces Round #708 Editorial Нам очень жаль, что раунд пришлось сделать нерейтинговым. Мы в очередной раз приносим свои извинения и надеемся, что вам понравились задачи! [problem:1497A] Идея: [user:shishin,2021-03-14] <spoiler summary="Разбор"> [tutorial:1497A] </spoiler> <spoiler summary="Реализация"> ~~~~~ // один манул #include <bits/stdc++.h> using namespace std; int main() { int T; cin >> T; while (T --> 0) { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; sort(a.begin(), a.end()); vector<int> b; for (int i = 0; i < n; i++) { if (i == 0 || a[i] != a[i - 1]) { b.emplace_back(a[i]); } } for (int i = 0; i < n; i++) { if (i > 0 && a[i] == a[i - 1]) { b.emplace_back(a[i]); } } for (auto x : b) cout << x << ' '; cout << '\n'; } return 0; cout << "...

Full text and comments »

Codeforces Round #673 **Ас-саляму алейкум**, Codeforces! (Мир вам, Codeforces!) Мы рады пригласить вас на [contest:1416] и [contest:1417], который пройдет в **[contest_time:1416]** (Обратите внимание, что время **позже**, чем обычно). Раунд будет **рейтинговым** для обоих дивизионов. Участникам обоих дивизионов будет предложено шесть задач и два часа на их решение. Задачи были придуманы [user:RedDreamer,2020-08-05], [user:BThero,2020-08-05] и мною [user:DimmyT,2020-09-25]. Мы очень благодарны следующим людям, которые помогли в подготовке раунда: - Огромное спасибо [user:BledDest,2020-08-05] за блестящую координацию нашего раунда. - Cпасибо [user:adedalic,2020-08-28], [user:kdjonty31,2020-08-28], [user:PM11,2020-08-28], [user:namanbansal013,2020-08-28], [user:RockyB,2020-08-28], [user:postscript,2020-08-28], [user:saurabhshadow,2020-08-28], [user:morzer,2020-08-28], [user:Mohamed.Sobhy,2020-08-28], [user:growup974,2020-08-28], [user:hugopm,2020-08-28], [user:Tlatoani,2020-08-28], [user:dorij...

Full text and comments »

Codeforces Round #479 (Div. 3) Привет! [6 мая (воскресенье) в 17:05 (Московское время)](http://www.timeanddate.com/worldclock/fixedtime.html?day=6&month=5&year=2018&hour=17&min=5&sec=0&p1=166) начнётся [contest:977] — первый в истории Codeforces раунд для третьего дивизиона. В этом раунде будет 6 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Наверное, участникам из первого дивизиона они будут совсем не интересны, а для 1600-1899 покажутся простыми. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса. Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты &mdash; так же как и вы буду расстроен, если у многих попадают решения после окончания контеста. [Напоминаем](/blog/entry/59228), что в таблицу официальных результатов поп...

Full text and comments »

Codeforces Round #661 (Div. 3) Привет! В [contest_time:1399] начнётся [contest:1399] &mdash; очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач (или 8), которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса. Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты &mdash; так же как и вы буду расстроен, если у многих попадают решения после окончания контеста. Вам будет предложено 6 или 7 (или 8) задач и 2 часа на их решение. **Штраф** за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться **10 минутам**. [Напоминаем](/blog/entry/59228), что в таблицу официальных результатов попадут только <i>достоверные участники третьего див...

Full text and comments »

Разбор Educational Codeforces Round 133 [problem:1716A] Идея: [user:vovuh,2022-08-05] <spoiler summary="Разбор"> [tutorial:1716A] </spoiler> <spoiler summary="Решение (vovuh)"> ~~~~~ for _ in range(int(input())): n = int(input()) print(1 + (n == 1) if n <= 3 else (n + 2) // 3) ~~~~~ </spoiler> [problem:1716B] Идея: [user:BledDest,2022-08-05] <spoiler summary="Разбор"> [tutorial:1716B] </spoiler> <spoiler summary="Решение (awoo)"> ~~~~~ for _ in range(int(input())): n = int(input()) p = [i + 1 for i in range(n)] print(n) for i in range(n): print(*p) if i < n - 1: p[i], p[i + 1] = p[i + 1], p[i] ~~~~~ </spoiler> [problem:1716C] Идея: [user:BledDest,2022-08-05] <spoiler summary="Разбор"> [tutorial:1716C] </spoiler> <spoiler summary="Решение (awoo)"> ~~~~~ INF = 2 * 10**9 for _ in range(int(input())): m = int(input()) a = [[int(x) for x in input().split()] for i in range(2)] su = [[-INF for j in range(m + 1)] for i in range(2)] for ...

Full text and comments »

Разбор Educational Codeforces Round 91 [problem:1380A] Идея: [user:BledDest,2020-07-12] <spoiler summary="Разбор"> [tutorial:1380A] </spoiler> <spoiler summary="Решение (Ne0n25)"> ~~~~~ #include <bits/stdc++.h> using namespace std; const int N = 1000; int n; int a[N]; void solve() { cin >> n; for (int i = 0; i < n; ++i) cin >> a[i]; for (int i = 1; i < n - 1; ++i) { if (a[i] > a[i - 1] && a[i] > a[i + 1]) { cout << "YES" << endl; cout << i << ' ' << i + 1 << ' ' << i + 2 << endl; return; } } cout << "NO" << endl; } int main() { int T; cin >> T; while (T--) solve(); } ~~~~~ </spoiler> [problem:1380B] Идея: [user:adedalic,2020-07-12] <spoiler summary="Разбор"> [tutorial:1380B] </spoiler> <spoiler summary="Решение (adedalic)"> ~~~~~ fun main() { val winBy = mapOf('R' to 'P', 'S' to 'R', 'P' to 'S') repeat(readLine()!!.toInt()) { val s = readLine()!! val maxCnt = s.groupingBy { it }.eachCount().maxBy { it.v...

Full text and comments »

Разбор Educational Codeforces Round 92 [problem:1389A] Идея: [user:BledDest,2020-07-30] <spoiler summary="Разбор"> [tutorial:1389A] </spoiler> <spoiler summary="Решение (BledDest)"> ~~~~~ t = int(input()) for i in range(t): l, r = map(int, input().split()) if l * 2 > r: print(-1, -1) else: print(l, l * 2) ~~~~~ </spoiler> [problem:1389B] Идея: [user:Roms,2020-07-30] <spoiler summary="Разбор"> [tutorial:1389B] </spoiler> <spoiler summary="Решение 1 (pikmike)"> ~~~~~ for _ in range(int(input())): n, k, z = map(int, input().split()) a = [int(x) for x in input().split()] ans = 0 s = 0 mx = 0 for t in range(z + 1): pos = k - 2 * t if pos < 0: continue mx = 0 s = 0 for i in range(pos + 1): if i < n - 1: mx = max(mx, a[i] + a[i + 1]) s += a[i] ans = max(ans, s + mx * t) print(ans) ~~~~~ </spoiler> <spoiler summary="Решение 2 (pikmike)"> ~~~~~ for _ in range(int(input())): n, k, z = map(int, input()...

Full text and comments »

Разбор Educational Codeforces Round 101 [problem:1469A] Идея: [user:BledDest,2020-12-29] <spoiler summary="Разбор"> [tutorial:1469A] </spoiler> <spoiler summary="Решение 1 (BledDest)"> ~~~~~ t = int(input()) for i in range(t): s = input() if len(s) % 2 == 0 and s[0] != ')' and s[-1] != '(': print('YES') else: print('NO') ~~~~~ </spoiler> <spoiler summary="Решение 2 (BledDest)"> ~~~~~ t = int(input()) for i in range(t): s = input() n = len(s) a = [s[i] for i in range(n)] cnt = n // 2 - 1 for j in range(n): if a[j] == '?': if cnt > 0: cnt -= 1 a[j] = '(' else: a[j] = ')' bal = 0 minbal = 0 for j in range(n): if a[j] == '(': bal += 1 else: bal -= 1 minbal = min(bal, minbal) print('YES' if bal == 0 and minbal >= 0 else 'NO') ~~~~~ </spoiler> [problem:1469B] Идея: [user:BledDest...

Full text and comments »

Разбор Educational Codeforces Round 180 [problem:2112A] Идея: [user:BledDest,2025-06-24] <spoiler summary="Разбор"> [tutorial:2112A] </spoiler> <spoiler summary="Решение (Neon)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { int a, x, y; cin >> a >> x >> y; cout << ((a < x) == (a < y) ? "YES" : "NO") << '\n'; } } ~~~~~ </spoiler> [problem:2112B] Идея: [user:BledDest,2025-06-24] <spoiler summary="Разбор"> [tutorial:2112B] </spoiler> <spoiler summary="Решение (adedalic)"> ~~~~~ #include<bits/stdc++.h> using namespace std; void solve() { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 1; i < n; i++) { if (abs(a[i - 1] - a[i]) <= 1) { cout << 0 << endl; return; } } for (int i = 1; i + 1 < n; i++) { if (a[i - 1] < a[i] && a[i] > a[i + 1]) { cout << 1 << endl; return; } if (a[i - 1] > a[i] && a[i] < a[i + 1]) { ...

Full text and comments »

Яндекс.Алгоритм 2017, третий отборочный раунд: разбор (с челленджами и свистелками) На этот раз я решил попробовать писать разбор в спойлерах, как уже делал кое-кто из авторов. Буду рад вашим комментариям о том, стало ли лучше. #### Задача A. Сдвиги Темы: динамическое программирование. Общий комментарий: это первая среди "сложных" задач контеста. В ней можно помочь хорошее знакомство со стандартными задачами на ДП, но довести решение до финального правильного вида все равно непросто. Решение: пускай мы можем сдвигать не только вправо, но и влево. <spoiler summary="Как решать такую задачу?"> Прежде всего заметим, что сделать сдвиг -- это то же самое, что переместить какой-то символ в другое место. Ясно, что никакой символ не надо двигать больше одного раза, поскольку вместо этого можно сразу поставить его на финальное место и не тратить действия. Кроме того, очевидно, что сдвиги не меняют количество вхождений каждого символа в строку, поэтому в обеих строках посимвольные вхождения должны совпадать. Посмотрим теперь на символы исходной строки, котор...

Full text and comments »

Разбор Educational Codeforces Round 94 [problem:1400A] Идея: [user:BledDest,2020-08-26] <spoiler summary="Разбор"> [tutorial:1400A] </spoiler> <spoiler summary="Решение (adedalic)"> ~~~~~ fun main() { repeat(readLine()!!.toInt()) { val n = readLine()!!.toInt() val c = readLine()!!.groupingBy { it }.eachCount().maxBy { it.value }!!.key println(c.toString().repeat(n)) } } ~~~~~ </spoiler> [problem:1400B] Идея: [user:adedalic,2020-08-26] <spoiler summary="Разбор"> [tutorial:1400B] </spoiler> <spoiler summary="Решение (adedalic)"> ~~~~~ fun main() { repeat(readLine()!!.toInt()) { val (p, f) = readLine()!!.split(' ').map { it.toInt() } var (cntS, cntW) = readLine()!!.split(' ').map { it.toInt() } var (s, w) = readLine()!!.split(' ').map { it.toInt() } if (s > w) { s = w.also { w = s } cntS = cntW.also { cntW = cntS } } var ans = 0 for (s1 in 0..minOf(...

Full text and comments »

Codeforces Round #686 (Div. 3) Привет! В [contest_time:1454] начнётся [contest:1454] &mdash; очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач (или 8), которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса. Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты &mdash; так же как и вы буду расстроен, если у многих попадают решения после окончания контеста. Вам будет предложено 6 или 7 (или 8) задач и 2 часа на их решение. **Штраф** за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться **10 минутам**. [Напоминаем](/blog/entry/59228), что в таблицу официальных результатов попадут только <i>достоверные участники третьего див...

Full text and comments »

Разбор Educational Codeforces Round 153 [problem:1860A] Идея: [user:BledDest,2023-08-18] <spoiler summary="Разбор"> [tutorial:1860A] </spoiler> <spoiler summary="Решение (Neon)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while (t--) { string s; cin >> s; int n = s.size(); string a, b; for (int i = 0; i < 2 * n; ++i) { a += "()"[i & 1]; b += ")("[i < n]; } if (a.find(s) == string::npos) { cout << "YES\n" << a << '\n'; } else if (b.find(s) == string::npos) { cout << "YES\n" << b << '\n'; } else { cout << "NO\n"; } } } ~~~~~ </spoiler> [problem:1860B] Идея: [user:BledDest,2023-08-18] <spoiler summary="Разбор"> [tutorial:1860B] </spoiler> <spoiler summary="Решение 1 (BledDest)"> ~~~~~ #include<bits/stdc++.h> using namespace std; int main() { int t; cin >> t; for(int i = 0; i < t; i++) { int m, k, a1, ak; cin >> m >> k >> a1 >> ...

Full text and comments »

Разбор Educational Codeforces Round 103 [problem:1476A] Идея: [user:vovuh,2021-01-30] <spoiler summary="Разбор"> [tutorial:1476A] </spoiler> <spoiler summary="Решение (adedalic)"> ~~~~~ #include<bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while(t--) { long long n, k; cin >> n >> k; long long cf = (n + k - 1) / k; k *= cf; cout << (k + n - 1) / n << endl; } return 0; } ~~~~~ </spoiler> [problem:1476B] Идея: [user:adedalic,2021-01-30] <spoiler summary="Разбор"> [tutorial:1476B] </spoiler> <spoiler summary="Решение (adedalic)"> ~~~~~ #include<bits/stdc++.h> using namespace std; typedef long long li; const int INF = int(1e9); int main() { int t; cin >> t; while(t--) { int n, k; cin >> n >> k; vector<int> p(n); for (int i = 0; i < n; i++) cin >> p[i]; li x = 0; li pSum = p[0]; for (int i = 1; i < n; i++) { x = max(x, (100ll * p[i] - k * pSum + k...

Full text and comments »

Быстрое умножение по модулю Рассмотрим такую задачу: даны три целых числа $x$, $y$ и $m$, $0 \leqslant x,y < m < 2^{32}$, найти $xy\bmod m$. По-хорошему хотелось бы просто перемножить эти два числа, а потом применить операцию остатка: ~~~~~ uint32_t prod(const uint32_t x, const uint32_t y, const uint32_t m) { return x * y % m; } ~~~~~ Как вы, возможно, догадываетесь, это решение неверное. Всё дело в том, что в такой процедуре возможно переполнение: операция `x * y` выполняется в типе `uint32_t`, и на самом деле промежуточным результатом выполнения этой операции будет не $xy$, а $xy\bmod2^{32}$. Если после этого взять результат по модулю $m$, он может отличаться от правильного: $$ \left(xy\bmod2^{32}\right)\bmod m\ne xy\bmod m. $$ Выход прост — перемножать необходимо в большем типе: ~~~~~ uint64_t prod_uint64(const uint64_t x, const uint64_t y, const uint64_t m) { return x * y % m; } ~~~~~ Если так делать, то, поскольку $xy<2^{64}$, это произведение точно не переполнится, и после взятия ре...

Full text and comments »

Разбор Educational Codeforces Round 143 [problem:1795A] Идея: [user:BledDest,2023-02-17] <spoiler summary="Разбор"> [tutorial:1795A] </spoiler> <spoiler summary="Решение (Neon) 1"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { auto ok = [](string s) { for (int i = 1; i < (int)s.size(); ++i) if (s[i - 1] == s[i]) return false; return true; }; int t; cin >> t; while (t--) { int n, m; string s, t; cin >> n >> m >> s >> t; bool f = false; for (int x = 0; x < 2; ++x) { string cs = s, ct = t; for (int i = 0; i < n; ++i) { f |= ok(cs) && ok(ct); ct.push_back(cs.back()); cs.pop_back(); } swap(n, m); swap(s, t); } cout << (f ? "YES\n" : "NO\n"); } } ~~~~~ </spoiler> <spoiler summary="Решение (Neon) 2"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { int n, m; string s, t...

Full text and comments »

Разбор Educational Codeforces Round 131 [problem:1701A] Идея: [user:BledDest,2022-07-09] <spoiler summary="Разбор"> [tutorial:1701A] </spoiler> <spoiler summary="Решение (vovuh)"> ~~~~~ for _ in range(int(input())): a = [list(map(int, input().split())) for i in range(2)] cnt = sum([sum(a[i]) for i in range(2)]) if cnt == 0: print(0) elif cnt == 4: print(2) else: print(1) ~~~~~ </spoiler> [problem:1701B] Идея: [user:BledDest,2022-07-09] <spoiler summary="Разбор"> [tutorial:1701B] </spoiler> <spoiler summary="Решение (Neon)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while (t--) { int n; cin >> n; cout << 2 << '\n'; for (int i = 1; i <= n; ++i) if (i % 2 != 0) for (int j = i; j <= n; j *= 2) cout << j << ' '; cout << '\n'; } } ~~~~~ </spoiler> [problem:1701C] Идея: [user:BledDest,2022-07...

Full text and comments »

Разбор Educational Codeforces Round 142 [problem:1792A] Идея: [user:BledDest,2023-01-25] <spoiler summary="Разбор"> [tutorial:1792A] </spoiler> <spoiler summary="Решение (Neon)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { int n; cin >> n; int cnt1 = 0; for (int i = 0; i < n; ++i) { int x; cin >> x; cnt1 += (x == 1); } cout << n - cnt1 / 2 << '\n'; } } ~~~~~ </spoiler> [problem:1792B] Идея: [user:BledDest,2023-01-25] <spoiler summary="Разбор"> [tutorial:1792B] </spoiler> <spoiler summary="Решение (awoo)"> ~~~~~ for _ in range(int(input())): a1, a2, a3, a4 = map(int, input().split()) if a1 == 0: print(1) else: print(a1 + min(a2, a3) * 2 + min(a1 + 1, abs(a2 - a3) + a4)) ~~~~~ </spoiler> [problem:1792C] Идея: [user:BledDest,2023-01-25] <spoiler summary="Разбор"> [tutorial:1792C] </spoiler> <spoiler summary="Решение (Neon...

Full text and comments »

Разбор Educational Codeforces Round 151 [problem:1845A] Идея: [user:BledDest,2023-06-30] <spoiler summary="Разбор"> [tutorial:1845A] </spoiler> <spoiler summary="Решение (awoo)"> ~~~~~ for _ in range(int(input())): n, k, x = map(int, input().split()) if x != 1: print("YES") print(n) print(*([1] * n)) elif k == 1 or (k == 2 and n % 2 == 1): print("NO") else: print("YES") print(n // 2) print(*([3 if n % 2 == 1 else 2] + [2] * (n // 2 - 1))) ~~~~~ </spoiler> [problem:1845B] Идея: [user:adedalic,2023-06-30] <spoiler summary="Разбор"> [tutorial:1845B] </spoiler> <spoiler summary="Решение (adedalic)"> ~~~~~ #include<bits/stdc++.h> using namespace std; #define fore(i, l, r) for(int i = int(l); i < int(r); i++) #define sz(a) int((a).size()) #define x first #define y second typedef long long li; typedef pair<int, int> pt; pt A, B, C; inline bool read() { if(!(cin >> A.x >> A.y)) return false; cin >> B.x >> B.y; cin >> C.x >> C.y; return ...

Full text and comments »

Разбор Educational Codeforces Round 102 [problem:1473A] Идея: [user:BledDest,2021-01-15], [user:adedalic,2021-01-15] <spoiler summary="Разбор"> [tutorial:1473A] </spoiler> <spoiler summary="Решение (Neon)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int tc; cin >> tc; while (tc--) { int n, d; cin >> n >> d; vector<int> a(n); for (int& x : a) cin >> x; sort(a.begin(), a.end()); cout << (a.back() <= d || a[0] + a[1] <= d ? "YES" : "NO") << endl; } } ~~~~~ </spoiler> [problem:1473B] Идея: [user:BledDest,2021-01-15] <spoiler summary="Разбор"> [tutorial:1473B] </spoiler> <spoiler summary="Решение (Neon)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { auto mul = [](string s, int k) -> string { string res = ""; while (k--) res += s; return res; }; int tc; cin >> tc; while (tc--) { string s, t; cin >> s >> t; int n = s.length(), m = t.length(); int ...

Full text and comments »

Разбор Educational Codeforces Round 86 [problem:1342A] Идея: [user:BledDest,2020-04-27] и [user:adedalic,2020-04-27] <spoiler summary="Разбор"> [tutorial:1342A] </spoiler> <spoiler summary="Решение (Roms)"> ~~~~~ for _ in range(int(input())): x, y = map(int, input().split()) a, b = map(int, input().split()) b = min(b, a + a) if x < y: x, y= y, x print(y * b + (x - y) * a) ~~~~~ </spoiler> [problem:1342B] Идея: [user:adedalic,2020-04-27] <spoiler summary="Разбор"> [tutorial:1342B] </spoiler> <spoiler summary="Решение (adedalic)"> ~~~~~ fun main() { val T = readLine()!!.toInt() for (tc in 1..T) { val t = readLine()!! val s = t.toCharArray().distinct().joinToString("").repeat(t.length) println(s) } } ~~~~~ </spoiler> [problem:1342C] Идея: [user:BledDest,2020-04-27] и [user:adedalic,2020-04-27] <spoiler summary="Разбор"> [tutorial:1342C] </spoiler> <spoiler summary="Решение (BledDest)"> ~~...

Full text and comments »

Разбор Educational Codeforces Round 132 [problem:1709A] Идея: [user:BledDest,2022-07-22] <spoiler summary="Разбор"> [tutorial:1709A] </spoiler> <spoiler summary="Решение (awoo)"> ~~~~~ for _ in range(int(input())): x = int(input()) a = [0] + [int(x) for x in input().split()] print("YES" if a[x] != 0 and a[a[x]] != 0 else "NO") ~~~~~ </spoiler> [problem:1709B] Идея: [user:BledDest,2022-07-22] <spoiler summary="Разбор"> [tutorial:1709B] </spoiler> <spoiler summary="Решение (vovuh)"> ~~~~~ n, m = map(int, input().split()) a = list(map(int, input().split())) l = [0] + [max(0, a[i] - a[i + 1]) for i in range(n - 1)] r = [0] + [max(0, a[i] - a[i - 1]) for i in range(1, n)] for i in range(n - 1): l[i + 1] += l[i] r[i + 1] += r[i] for _ in range(m): s, t = map(int, input().split()) if s < t: print(l[t - 1] - l[s - 1]) else: print(r[s - 1] - r[t - 1]) ~~~~~ </spoiler> [problem:1709C] Идея: [user:BledDest,2022-07-22] <spoiler summar...

Full text and comments »

Разбор Educational Codeforces Round 106 [problem:1499A] Идея: [user:adedalic,2021-03-19] <spoiler summary="Разбор"> [tutorial:1499A] </spoiler> <spoiler summary="Решение (adedalic)"> ~~~~~ fun main() { repeat(readLine()!!.toInt()) { val (n, k1, k2) = readLine()!!.split(' ').map { it.toInt() } val (w, b) = readLine()!!.split(' ').map { it.toInt() } if (k1 + k2 >= 2 * w && (n - k1) + (n - k2) >= 2 * b) println("YES") else println("NO") } } ~~~~~ </spoiler> [problem:1499B] Идея: [user:BledDest,2021-03-19] <spoiler summary="Разбор"> [tutorial:1499B] </spoiler> <spoiler summary="Решение (Neon)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { string s; cin >> s; int i = s.find("11"); int j = s.rfind("00"); cout << (i != -1 && j != -1 && i < j ? "NO" : "YES") << endl; } } ~~~~~ </spoiler> [problem:1499C] Идея: [user:aded...

Full text and comments »

Codeforces: Календарь Всем привет! Последним нововведением в Codeforces является внедрение Google календаря, в котором содержится информация о ближайших соревнованиях. Для того, чтобы ознакомиться с ним, перейдите во вкладку <<Календарь>> в верхнем меню.  Соревнования, проводимые у нас на Codeforces добавляются в календарь автоматически. Также можно добавлять соревнования, проводимые других платформах. Эта возможность есть у всех красных пользователей. Кроме того, мы предоставим права на редактирование календаря сотрудникам/энтузиастам других популярных платформ. Во вкладке <<Добавить>> вы можете добавить информацию о предстоящем соревновании. Для этого доступна форма, изображенная ниже.  Добавлять в календарь нужно классические алгоритмические контесты, чья продолжительность не превышает суток. Также нужно, чтобы соревнование было общедоступным, то есть...

Full text and comments »

Разбор Educational Codeforces Round 89 [problem:1366A] Идея: [user:Roms,2020-06-12] <spoiler summary="Разбор"> [tutorial:1366A] </spoiler> <spoiler summary="Решение (Roms)"> ~~~~~ for _ in range(int(input())): l, r = map(int, input().split()) print(min(l, r, (l + r) // 3)) ~~~~~ </spoiler> [problem:1366B] Идея: [user:Roms,2020-06-12] <spoiler summary="Разбор"> [tutorial:1366B] </spoiler> <spoiler summary="Решение (Roms)"> ~~~~~ for _ in range(int(input())): n, x, m = map(int, input().split()) l, r = x, x for _ in range(m): L, R = map(int, input().split()) if max(l, L) <= min(r, R): l = min(l, L) r = max(r, R) print(r - l + 1) ~~~~~ </spoiler> [problem:1366C] Идея: [user:BledDest,2020-06-12] <spoiler summary="Разбор"> [tutorial:1366C] </spoiler> <spoiler summary="Решение (BledDest)"> ~~~~~ #include <bits/stdc++.h> using namespace std; void solve() { int n, m; cin >> n...

Full text and comments »

Разбор Educational Codeforces Round 145 [problem:1809A] Идея: [user:BledDest,2023-03-24] <spoiler summary="Разбор"> [tutorial:1809A] </spoiler> <spoiler summary="Решение (Neon)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int tc; cin >> tc; while (tc--) { string s; cin >> s; vector<int> cnt(10); for (auto c : s) ++cnt[c - '0']; int mx = *max_element(cnt.begin(), cnt.end()); if (mx == 4) cout << -1; else if (mx == 3) cout << 6; else cout << 4; cout << '\n'; } } ~~~~~ </spoiler> [problem:1809B] Идея: [user:BledDest,2023-03-24] <spoiler summary="Разбор"> [tutorial:1809B] </spoiler> <spoiler summary="Решение 1 (adedalic)"> ~~~~~ fun main() { repeat(readln().toInt()) { val n = readln().toLong() var l = (-1).toLong() var r = 1e9.toLong() while (r - l > 1) { val mid = (l + r) / 2 if (mid * mid >= n) ...

Full text and comments »

Разбор Educational Codeforces Round 124 [problem:1651A] Идея: [user:BledDest,2022-03-11] <spoiler summary="Разбор"> [tutorial:1651A] </spoiler> <spoiler summary="Решение (BledDest)"> ~~~~~ t = int(input()) for i in range(t): n = int(input()) print(2 ** n - 1) ~~~~~ </spoiler> [problem:1651B] Идея: [user:adedalic,2022-03-11] <spoiler summary="Разбор"> [tutorial:1651B] </spoiler> <spoiler summary="Решение (awoo)"> ~~~~~ for _ in range(int(input())): n = int(input()) if 3**(n-1) > 10**9: print("NO") else: print("YES") print(*[3**x for x in range(n)]) ~~~~~ </spoiler> [problem:1651C] Идея: [user:adedalic,2022-03-11] <spoiler summary="Разбор"> [tutorial:1651C] </spoiler> <spoiler summary="Решение (adedalic)"> ~~~~~ #include<bits/stdc++.h> using namespace std; #define fore(i, l, r) for(int i = int(l); i < int(r); i++) typedef long long li; const int INF = int(1e9); int n; vector<int> a, b; inline bool read() { if(!(cin >> n)) ...

Full text and comments »

Как тренироваться: почему недостаточно просто решать много задач Привет, Codeforces! Я, как и многие из вас, периодически читаю блоги. В последнее время мое внимание стали привлекать блоги от пользователей с низким рейтингом, которые спрашивают, как им поднять свой рейтинг. Хочу немного рассказать о своем мнении по поводу этих блогов. Итак, что же их себя представляют эти блоги? Обычно это блог с заголовком что-то вроде <b>"Срочно нужна помощь!"</b> или <b>"Как улучшить рейтинг, помогите!"</b> Когда открываешь этот блог, то видишь максимально подробное описание проблемы, например, такое: "я решил уже 500 задач, а улучшения все нет и нет." или "я решил уже 100 задач с рейтингом >= 1500, а мой рейтинг не увеличивается". А в комментариях им обычно пишут "ты недостаточно решал, решай больше" ну или "решай более сложные задачи". <b>На мой взгляд, это неверно, и вводит таких пользователей в заблуждение.</b> Позвольте объяснить, что я имею в виду. Итак, представьте, что вы вообще ничего не знаете ни о спортивном программировнии, ни даже об основах ол...

Full text and comments »

Разбор Educational Codeforces Round 111 [problem:1550A] Идея: [user:BledDest,2021-07-15] <spoiler summary="Разбор"> [tutorial:1550A] </spoiler> <spoiler summary="Решение (BledDest)"> ~~~~~ def maxSum(x): return x ** 2 def getAns(x): res = 1 while maxSum(res) < x: res += 1 return res def main(): t = int(input()) for i in range(t): print(getAns(int(input()))) main() ~~~~~ </spoiler> [problem:1550B] Идея: [user:Neon,2021-07-15] <spoiler summary="Разбор"> [tutorial:1550B] </spoiler> <spoiler summary="Решение (Neon)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { int n, a, b; string s; cin >> n >> a >> b >> s; int m = unique(s.begin(), s.end()) - s.begin(); cout << n * a + max(n * b, (m / 2 + 1) * b) << '\n'; } } ~~~~~ </spoiler> [problem:1550C] Идея: [user:adedalic,2021-07-15] <spoiler summary="Разбор"> [tutorial:1550C] </spoiler> <spoiler summary="Решени...

Full text and comments »

Разбор Educational Codeforces Round 121 [problem:1626A] Идея: [user:BledDest,2022-01-17] <spoiler summary="Разбор"> [tutorial:1626A] </spoiler> <spoiler summary="Решение (awoo)"> ~~~~~ for _ in range(int(input())): print(''.join(sorted(input()))) ~~~~~ </spoiler> [problem:1626B] Идея: [user:BledDest,2022-01-17] <spoiler summary="Разбор"> [tutorial:1626B] </spoiler> <spoiler summary="Решение (awoo)"> ~~~~~ for _ in range(int(input())): x = [ord(c) - ord('0') for c in input()] n = len(x) for i in range(n - 2, -1, -1): if x[i] + x[i + 1] >= 10: x[i + 1] += x[i] - 10 x[i] = 1 break else: x[1] += x[0] x.pop(0) print(''.join([chr(c + ord('0')) for c in x])) ~~~~~ </spoiler> [problem:1626C] Идея: [user:BledDest,2022-01-17] <spoiler summary="Разбор"> [tutorial:1626C] </spoiler> <spoiler summary="Решение (awoo)"> ~~~~~ for _ in range(int(input())): n = int(input()) k = list(map(int, input().split())) h = list(map(...

Full text and comments »

Разбор Educational Codeforces Round 137 [problem:1743A] Идея: [user:fcspartakm,2022-10-18] <spoiler summary="Разбор"> [tutorial:1743A] </spoiler> <spoiler summary="Решение 1 (awoo)"> ~~~~~ for _ in range(int(input())): n = int(input()) a = set(map(int, input().split())) ans = 0 for i in range(10000): num = str(i) num = (4 - len(num)) * '0' + num used = set(num) if len(used) != 2: continue d1 = int(used.pop()) d2 = int(used.pop()) if (not d1 in a) and (not d2 in a) and num.count(num[0]) == 2: ans += 1 print(ans) ~~~~~ </spoiler> <spoiler summary="Решение 2 (fcspartakm)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int n; inline void read() { cin >> n; int x; for (int i = 0; i < n; ++i) cin >> x; } inline int fac(int n) { int res = 1; for (int i = 2; i <= n; i++) { res *= i; } return res; } inline int c(int n, int k) { return fac(n) / fac(k) / fac(n - k); } inline void solve()...

Full text and comments »

Разбор Educational Codeforces Round 186 [problem:2182A] Идея: [user:BledDest,2025-12-30] <spoiler summary="Разбор"> [tutorial:2182A] </spoiler> <spoiler summary="Решение (BledDest)"> ~~~~~ t = int(input()) for i in range(t): n = int(input()) s = input() if '2025' in s and not '2026' in s: print(1) else: print(0) ~~~~~ </spoiler> [problem:2182B] Идея: [user:BledDest,2025-12-30] <spoiler summary="Разбор"> [tutorial:2182B] </spoiler> <spoiler summary="Решение (BledDest)"> ~~~~~ t = int(input()) for i in range(t): a, b = map(int, input().split()) if a < b: a, b = b, a x, y = 0, 0 ans = 0 cur = 1 while True: x, y = y + cur, x if x <= a and y <= b: ans += 1 cur *= 2 else: break print(ans) ~~~~~ </spoiler> [problem:2182C] Идея: [user:Roms,2025-12-30] <spoiler summary="Разбор"> [tutorial:2182C] </spoiler> <spoiler summary="Решение ...

Full text and comments »

Разбор Educational Codeforces Round 90 [problem:1373A] Идея: [user:Roms,2020-06-26] <spoiler summary="Разбор"> [tutorial:1373A] </spoiler> <spoiler summary="Решение (pikmike)"> ~~~~~ for tc in range(int(input())): a, b, c = map(int, input().split()) print(1 if a < c else -1, end=" ") print(b if c < a * b else -1) ~~~~~ </spoiler> [problem:1373B] Идея: [user:Roms,2020-06-26] <spoiler summary="Разбор"> [tutorial:1373B] </spoiler> <spoiler summary="Решение (Roms)"> ~~~~~ for _ in range(int(input())): s = input() print('DA' if min(s.count('0'), s.count('1')) % 2 == 1 else 'NET') ~~~~~ </spoiler> [problem:1373C] Идея: [user:Roms,2020-06-26] <spoiler summary="Разбор"> [tutorial:1373C] </spoiler> <spoiler summary="Решение (Roms)"> ~~~~~ for _ in range(int(input())): s = input() cur, mn, res = 0, 0, len(s) for i in range(len(s)): cur += 1 if s[i] == '+' else -1 if cur < mn: mn = cur res += i + 1 ...

Full text and comments »

Codeforces Round #642 (Div. 3) &lt;almost-copy-pasted-part&gt; Привет! В [contest_time:1353] начнётся [contest:1353] &mdash; очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач (или 8), которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса. Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты &mdash; так же как и вы буду расстроен, если у многих попадают решения после окончания контеста. Вам будет предложено 6 или 7 (или 8) задач и 2 часа на их решение. **Штраф** за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться **10 минутам**. [Напоминаем](/blog/entry/59228), что в таблицу официальных результатов попадут только <i...

Full text and comments »

Global Round 19 Editorial Мы надеемся, что вам понравился контест! Мы рекомендуем вам прочитать разбор, даже если вы решили задачу, возможно вы узнаете что-то новое. [problem:1637A]<br> Идея: [user:__JustMe__,2022-02-12]. <spoiler summary="Подсказка 1"> Что происходит, если массив уже отсортирован? </spoiler> <spoiler summary="Подсказка 2"> Что происходит, если есть такие индексы $i$ и $j$, что $i > j$ и $a_i > a_j$? </spoiler> <spoiler summary="Разбор"> [tutorial:1637A] </spoiler> <spoiler summary="Решение"> ``` #include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; for (int i = 0; i < t; i++) { int n; cin >> n; vector<int> a(n); for (auto& u : a) cin >> u; if (!is_sorted(a.begin(), a.end())) cout << "YES\n"; else cout << "NO\n"; } } ``` </spoiler> [problem:1637B]<br> Идея: [user:__JustMe__,2022-02-12] and [user:Mangooste,2022-02-12]. <spoi...

Full text and comments »

Codeforces Round #765. Один из авторов контеста снова развлекается. Привет, Codeforces! Не так давно прошел Codeforces #765 (Div. 2), и одним из его авторов был я. Когда уже прошел час с начала контеста, я решил вспомнить былое и начать издеваться над читерами. Для этого я решил заглянуть в старые группы с читерами, и посмотреть, как у них проходят дела. Первая группа, в которую я заглянул &mdash; это группа, в которой админ активно борется против читеров. Так вот, там действительно не было читеров на раунде. Считаю, что это успех. Вторая группа, в которую я заглянул &mdash; это группа на 2.5к пользователей. Я решил, что просто зайти туда будет слишком скучно, так что я решил сразу написать, что я автор контеста. Вот реакция пользователей: <spoiler summary="Картинка"> <a href="https://imgbb.com/"><img src="https://i.ibb.co/0Xt07qt/Screenshot-20220112-164100.png" alt="pic1" border="0"></a> </spoiler> Вы представляете?! Я пишу, что я автор контеста, а мне предлагают слить решение на задачу С. Как и в [прошлом блоге](https://codeforces...

Full text and comments »

Разбор Codeforces Round 916 (Div. 3) [problem:1914A] Идея: [user:BledDest,2023-12-20] <spoiler summary="Разбор"> [tutorial:1914A] </spoiler> <spoiler summary="Решение (awoo)"> ~~~~~ for _ in range(int(input())): n = int(input()) s = input() print(sum([s.count(chr(ord('A') + i)) >= i + 1 for i in range(26)])) ~~~~~ </spoiler> [problem:1914B] Идея: [user:Roms,2023-12-20] <spoiler summary="Разбор"> [tutorial:1914B] </spoiler> <spoiler summary="Решение (BledDest)"> ~~~~~ #include<bits/stdc++.h> using namespace std; void solve() { int n, k; cin >> n >> k; vector<int> a(n); for(int i = 0; i < n; i++) a[i] = n - i; reverse(a.end() - k - 1, a.end()); for(int i = 0; i < n; i++) { if(i) cout << " "; cout << a[i]; } cout << endl; } int main() { int t; cin >> t; for(int i = 0; i < t; i++) solve(); return 0; } ~~~~~ </spoiler> [problem:1914C] Идея: [user:Roms,2023-12-20] <spoiler summary="Разбор"> [tutorial:1914C] </sp...

Full text and comments »

Рейтинг Codeforces [обновлен в октябре 2015] Начиная с октября 2015-го года рейтинг на Codeforces считается по открытым формулам, о которых и пойдет здесь речь. Вполне вероятно, что мы будем их слегка менять со временем, что будем отражать в этом посте. Основная концепция используемых формул &mdash; мы расширяем принципы рейтинга Эло для встреч более чем двух участников. Каждый участник характеризуется величиной рейтинга $r_i$ &mdash; целое число (возможно отрицательное). Грубо говоря, чем это значение выше, тем лучше участник выступает в соревнованиях. Рейтинг это подсчитывается/пересчитывается таким образом, чтобы выполнялось равенство: $$P_{i,j}=\frac{1}{1+10^{\frac{r_j-r_i}{400}}},$$ где $P_{i,j}$ вероятность того, что $i$-й участник победит на соревновании $j$-го. Таким образом вероятность победы одного участника над другим определяется только разностью их рейтингов. Например, если разница рейтингов двух участников равна 200, то побеждает сильнейший с вероятностью примерно 0.75. При разнице рейтинга 400 вероятнос...

Full text and comments »

Разбор Educational Codeforces Round 168 [problem:1997A] Идея: [user:BledDest,2024-07-31] <spoiler summary="Разбор"> [tutorial:1997A] </spoiler> <spoiler summary="Решение (BledDest)"> ~~~~~ #include<bits/stdc++.h> using namespace std; void solve() { string s; cin >> s; int n = s.size(); int idx = -1; for(int i = 0; i + 1 < n; i++) if(s[i] == s[i + 1]) idx = i; if(idx == -1) { if(s.back() == 'a') cout << (s + "b") << endl; else cout << (s + "a") << endl; } else { string t = "a"; if(s[idx] == 'a') t = "b"; cout << s.substr(0, idx + 1) + t + s.substr(idx + 1) << endl; } } int main() { int t; cin >> t; for(int i = 0; i < t; i++) solve(); } ~~~~~ </spoiler> [problem:1997B] Идея: [user:BledDest,2024-07-31] <spoiler summary="Разбор"> [tutorial:1997B] </spoiler> <spoiler summary="Решение (Neon)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { int n; cin >...

Full text and comments »

Разбор Educational Codeforces Round 181 [problem:2125A] Идея: [user:FelixArg,2025-07-23] <spoiler summary="Разбор"> [tutorial:2125A] </spoiler> <spoiler summary="Решение (awoo)"> ~~~~~ #include<bits/stdc++.h> using namespace std; int main(){ int tc; cin >> tc; while (tc--){ string s; cin >> s; sort(s.begin(), s.end()); reverse(s.begin(), s.end()); cout << s << '\n'; } } ~~~~~ </spoiler> [problem:2125B] Идея: [user:BledDest,2025-07-23] <spoiler summary="Разбор"> [tutorial:2125B] </spoiler> <spoiler summary="Решение (ifive)"> ~~~~~ from math import gcd for _ in range(int(input())): a, b, k = map(int, input().split()) g = gcd(a, b) print(1 if a // g <= k and b // g <= k else 2) ~~~~~ </spoiler> [problem:2125C] Идея: [user:BledDest,2025-07-23] <spoiler summary="Разбор"> [tutorial:2125C] </spoiler> <spoiler summary="Решение 1 (BledDest)"> ~~~~~ def good(x): return x % 2 > 0 and x %...

Full text and comments »

Codeforces Round #667 (Div. 3) Привет! В [contest_time:1409] начнётся [contest:1409] &mdash; очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач (или 8), которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса. Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты &mdash; так же как и вы буду расстроен, если у многих попадают решения после окончания контеста. Вам будет предложено 6 или 7 (или 8) задач и 2 часа на их решение. **Штраф** за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться **10 минутам**. [Напоминаем](/blog/entry/59228), что в таблицу официальных результатов попадут только <i>достоверные участники третьего див...

Full text and comments »

Разбор Educational Codeforces Round 115 [problem:1598A] Идея: [user:BledDest,2021-10-11] <spoiler summary="Разбор"> [tutorial:1598A] </spoiler> <spoiler summary="Решение (BledDest)"> ~~~~~ def solve(): n = int(input()) s1 = input() s2 = input() bad = False for i in range(n): bad |= s1[i] == '1' and s2[i] == '1' if bad: print('NO') else: print('YES') t = int(input()) for i in range(t): solve() ~~~~~ </spoiler> [problem:1598B] Идея: [user:fcspartakm,2021-10-11] <spoiler summary="Разбор"> [tutorial:1598B] </spoiler> <spoiler summary="Решение (BledDest)"> ~~~~~ t = int(input()) for i in range(t): n = int(input()) a = [[] for i in range(n)] for j in range(n): a[j] = list(map(int, input().split())) ans = False for j in range(5): for k in range(5): if k != j: cnt1 = 0 cnt2 = 0 cntno = 0 for z in range(n): if a[z][j] == 1: ...

Full text and comments »

Разбор Educational Codeforces Round 154 [problem:1861A] Идея: [user:BledDest,2023-09-01] <spoiler summary="Разбор"> [tutorial:1861A] </spoiler> <spoiler summary="Решение (BledDest)"> ~~~~~ #include<bits/stdc++.h> using namespace std; int main() { int t; cin >> t; for(int i = 0; i < t; i++) { string s; cin >> s; if(s.find("1") < s.find("3")) cout << 13; else cout << 31; cout << endl; } } ~~~~~ </spoiler> [problem:1861B] Идея: [user:Roms,2023-09-01] <spoiler summary="Разбор"> [tutorial:1861B] </spoiler> <spoiler summary="Решение (Roms)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; for (int tc = 0; tc < t; ++tc) { string a, b; cin >> a >> b; bool ok = false; for (int i = 0; i + 1 < a.size(); ++i) { if (a[i] == b[i] && a[i] == '0' && a[i + 1] == b[i + 1] && a[i + 1] == '1') { ok = true; } } ...

Full text and comments »

Разбор Educational Codeforces Round 108 [problem:1519A] Идея: [user:adedalic,2021-04-30] <spoiler summary="Разбор"> [tutorial:1519A] </spoiler> <spoiler summary="Решение (adedalic)"> ~~~~~ fun main() { repeat(readLine()!!.toInt()) { val (r, b, d) = readLine()!!.split(' ').map { it.toInt() } println(if (minOf(r, b) * (d + 1).toLong() >= maxOf(r, b)) "YES" else "NO") } } ~~~~~ </spoiler> [problem:1519B] Идея: [user:adedalic,2021-04-30] <spoiler summary="Разбор"> [tutorial:1519B] </spoiler> <spoiler summary="Решение (adedalic)"> ~~~~~ fun main() { repeat(readLine()!!.toInt()) { val (n, m, k) = readLine()!!.split(' ').map { it.toInt() } println(if (n * m - 1 == k) "YES" else "NO") } } ~~~~~ </spoiler> [problem:1519C] Идея: [user:BledDest,2021-04-30] <spoiler summary="Разбор"> [tutorial:1519C] </spoiler> <spoiler summary="Решение (awoo)"> ~~~~~ #include <bits/stdc++.h> #define forn(i, n) for (int i = 0; i < int(...

Full text and comments »

Разбор Educational Codeforces Round 77 [problem:1260A] Идея: [user:adedalic,2019-11-28] <spoiler summary="Разбор"> [tutorial:1260A] </spoiler> <spoiler summary="Решение (adedalic)"> ~~~~~ #include<bits/stdc++.h> using namespace std; int c, sum; inline bool read() { if(!(cin >> c >> sum)) return false; return true; } inline void solve() { int d = sum / c; int rem = sum % c; cout << rem * (d + 1) * (d + 1) + (c - rem) * d * d << endl; } int main() { #ifdef _DEBUG freopen("input.txt", "r", stdin); #endif int n; cin >> n; while(n--) { read(); solve(); } return 0; } ~~~~~ </spoiler> [problem:1260B] Идея: [user:Roms,2019-11-28] <spoiler summary="Разбор"> [tutorial:1260B] </spoiler> <spoiler summary="Решение (Roms)"> ~~~~~ for t in range(int(input())): a, b = map(int, input().split()) if a > b: a, b = b, a print ('YES' if ( ((a + b) % 3) == 0 and a * 2 >= b) else 'NO') ~~~~~ </spoiler> [problem:1260C] Идея: [user:adedalic,201...

Full text and comments »

Codeforces Round #634 (Div. 3) &lt;almost-copy-pasted-part&gt; Привет! В [contest_time:1335] начнётся [contest:1335] &mdash; очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач (или 8), которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса. Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты &mdash; так же как и вы буду расстроен, если у многих попадают решения после окончания контеста. Вам будет предложено 6 или 7 (или 8) задач и 2 часа на их решение. **Штраф** за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться **10 минутам**. [Напоминаем](/blog/entry/59228), что в таблицу официальных результатов попадут только <i...

Full text and comments »

Codeforces Round #265: разбор Я скоро засабмичу свои решения и положу здесь ссылки. В некоторых разборах приведены дополнительные челленджи, над которыми можно поломать голову. Делитесь идеями в комментариях. =) [problem:465A] Если прибавить к числу 1, его двоичная запись поведет себя понятным образом: все младшие единицы превратятся в нули, а следующий за ними ноль станет единицей. Найдем длину максимального суффикса из единиц, пусть она равна $l$. Тогда ответ равен $l+1$, кроме случая, когда вся строка состоит из единиц, тогда ответ $l$. Забавно, что в задаче div1E тоже приходится думать о том, что будет, если прибавить к числу 1. =) [problem:465B] Наилучшая стратегия такова: для каждого непрерывного отрезка из непрочитанных писем откроем первое письмо, пролистаем до последнего в том же отрезке, если есть еще непрочитанные письма, вернемся к списку. Легко показать, что лучше мы сделать не сможем: для выбранного отрезка посмотрим на момент, когда мы прочитаем последнее письмо из него. Если мы ...

Full text and comments »

Educational Codeforces Round #1 Привет, Codeforces! [13 ноября 2015 года в 18:00 MSK](http://www.timeanddate.com/worldclock/fixedtime.html?msg=Educational+Codeforces+Round+%231&iso=20151113T1500) состоится первый учебный раунд Educational Codeforces Round #1 для участников из первого и второго дивизионов. Учебные раунды Codefores &mdash; это новый формат соревнований основной целью, которого является помощь в развитии у участников базовых (и не только) навыков и знаний, которые необходимы при решении олимпиадных задач по программированию. В учебных раундах вы встретите не только старые добрые идеи и алгоритмы, которые многие знают, но также и некоторые расширенные темы, которые неизвестны многим участникам, в том числе и из первого дивизиона. Сложность задач будет сравнима с обычными раундами для участников из второго дивизиона, хотя многое может пригодиться и участникам из первого дивизиона. На мой взгляд первый раунд получился несколько проще того на что мы ориентировались. Учебные раунды будут нерейтингов...

Full text and comments »

Разбор Educational Codeforces Round 81 [problem:1295A] Идея: [user:adedalic,2020-01-30] <spoiler summary="Разбор"> [tutorial:1295A] </spoiler> <spoiler summary="Решение (BledDest)"> ~~~~~ t = int(input()) for i in range(t): n = int(input()) if(n % 2 == 1): print(7, end='') n -= 3 while(n > 0): print(1, end='') n -= 2 print() ~~~~~ </spoiler> [problem:1295B] Идея: [user:Roms,2020-01-30] <spoiler summary="Разбор"> [tutorial:1295B] </spoiler> <spoiler summary="Решение (adedalic)"> ~~~~~ #include<bits/stdc++.h> using namespace std; typedef long long li; int n, x; string s; inline bool read() { if(!(cin >> n >> x >> s)) return false; return true; } inline void solve() { int ans = 0; bool infAns = false; int cntZeros = (int)count(s.begin(), s.end(), '0'); int total = cntZeros - (n - cntZeros); int bal = 0; for(int i = 0; i < n; i++) { if(total == 0) { if(bal == x) infAns = true; ...

Full text and comments »

Разбор Educational Codeforces Round 161 [problem:1922A] Идея: [user:Roms,2024-01-19] <spoiler summary="Разбор"> [tutorial:1922A] </spoiler> <spoiler summary="Решение (awoo)"> ~~~~~ for _ in range(int(input())): n = int(input()) a = input() b = input() c = input() print("YES" if any([a[i] != c[i] and b[i] != c[i] for i in range(n)]) else "NO") ~~~~~ </spoiler> [problem:1922B] Идея: [user:Roms,2024-01-19] <spoiler summary="Разбор"> [tutorial:1922B] </spoiler> <spoiler summary="Решение (Roms)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int t; int main() { cin >> t; for (int tc = 0; tc < t; ++tc) { int n; cin >> n; map<int, int> numOfLens; for (int i = 0; i < n; ++i){ int x; cin >> x; ++numOfLens[x]; } long long res = 0; int sum = 0; for (auto it : numOfLens) { long long cnt = it.second; if(cnt >= 3) ...

Full text and comments »

Разбор Educational Codeforces Round 164 [problem:1954A] Идея: [user:BledDest,2024-04-13] <spoiler summary="Разбор"> [tutorial:1954A] </spoiler> <spoiler summary="Решение (BledDest)"> ~~~~~ t = int(input()) for i in range(t): n, m, k = map(int, input().split()) max_color = (n + m - 1) / m if max_color + k >= n: print('NO') else: print('YES') ~~~~~ </spoiler> [problem:1954B] Идея: [user:BledDest,2024-04-13] <spoiler summary="Разбор"> [tutorial:1954B] </spoiler> <spoiler summary="Решение (awoo)"> ~~~~~ for _ in range(int(input())): n = int(input()) a = list(map(int, input().split())) lst = -1 ans = n for i in range(n): if a[i] != a[0]: ans = min(ans, i - lst - 1) lst = i ans = min(ans, n - lst - 1) if ans == n: print(-1) else: print(ans) ~~~~~ </spoiler> [problem:1954C] Идея: [user:BledDest,2024-04-13] <spoiler summary="Разбор"> [tutorial:1954C] <...

Full text and comments »

Разбор Educational Codeforces Round 178 [problem:2104A] Идея: [user:fcspartakm,2025-04-29] <spoiler summary="Разбор"> [tutorial:2104A] </spoiler> <spoiler summary="Решение (awoo)"> ~~~~~ for _ in range(int(input())): a, b, c = map(int, input().split()) if (a + b + c) % 3 != 0: print("NO") continue x = (a + b + c) // 3 print("YES" if b <= x else "NO") ~~~~~ </spoiler> [problem:2104B] Идея: [user:BledDest,2025-04-29] <spoiler summary="Разбор"> [tutorial:2104B] </spoiler> <spoiler summary="Решение (BledDest)"> ~~~~~ #include<bits/stdc++.h> using namespace std; int main() { int t; cin >> t; for(int i = 0; i < t; i++) { int n; cin >> n; vector<int> a(n); for(int j = 0; j < n; j++) cin >> a[j]; vector<int> pmax(n + 1); vector<long long> psum(n + 1); for(int j = 0; j < n; j++) { pmax[j + 1] = max(pmax[j], a[j]); psum[j + 1] = psum[j]...

Full text and comments »

Разбор Educational Codeforces Round 72 [problem:1217A] <spoiler summary="Разбор"> [tutorial:1217A] </spoiler> <spoiler summary="Решение (adedalic)"> ~~~~~ fun main() { val t = readLine()!!.toInt() for (ct in 1..t) { val (str, int, exp) = readLine()!!.split(' ').map { it.toInt() } val minAddStr = maxOf(0, (exp + int - str + 2) / 2) println(maxOf(exp - minAddStr + 1, 0)) } } ~~~~~ </spoiler> [problem:1217B] Идея: [user:Roms,2019-09-06] <spoiler summary="Разбор"> [tutorial:1217B] </spoiler> <spoiler summary="Решение (Roms)"> ~~~~~ #include <bits/stdc++.h> using namespace std; const int N = 105; int t; int n, m; int d[N], h[N]; int main() { cin >> t; for(int tc = 0; tc < t; ++tc){ cin >> n >> m; int maxDH = -2e9; for(int i = 0; i < n; ++i){ cin >> d[i] >> h[i]; maxDH = max(maxDH, d[i] - h[i]); } int res = 1; int maxD = *max_element(d, d + n); m -= maxD; if(m > 0){ if(maxDH <= 0) res = -1; e...

Full text and comments »

Разбор Educational Codeforces Round 88 [problem:1359A] Идея: [user:BledDest,2020-05-29] <spoiler summary="Разбор"> [tutorial:1359A] </spoiler> <spoiler summary="Решение 1 (BledDest)"> ~~~~~ t = int(input()) for i in range(t): n, m, k = map(int, input().split()) d = n // k a1 = min(m, d) a2 = (m - a1 + k - 2) // (k - 1) print(a1 - a2) ~~~~~ </spoiler> <spoiler summary="Решение 2 (BledDest)"> ~~~~~ t = int(input()) for i in range(t): n, m, k = map(int, input().split()) ans = 0 d = n // k for a1 in range(m + 1): for a2 in range(a1 + 1): if(a1 > d): continue if(a1 + a2 > m): continue if(a1 + (k - 1) * a2 < m): continue ans = max(ans, a1 - a2) print(ans) ~~~~~ </spoiler> [problem:1359B] Идея: [user:BledDest,2020-05-29] <spoiler summary="Разбор"> [tutorial:1359B] </spoiler> <spoiler summary="Решение (pikmike)"> ~~~~~ ...

Full text and comments »

Разбор Educational Codeforces Round 171 [problem:2026A] Идея: [user:adedalic,2024-10-29] <spoiler summary="Разбор"> [tutorial:2026A] </spoiler> <spoiler summary="Решение (adedalic)"> ~~~~~ #include<bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { int X, Y, K; cin >> X >> Y >> K; int M = min(X, Y); cout << "0 0 " << M << " " << M << endl; cout << "0 " << M << " " << M << " 0" << endl; } } ~~~~~ </spoiler> [problem:2026B] Идея: [user:BledDest,2024-10-29] <spoiler summary="Разбор"> [tutorial:2026B] </spoiler> <spoiler summary="Решение (Neon)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { int n; cin >> n; vector<long long> a(n); for (auto& x : a) cin >> x; long long ans = 1e18; auto upd = [&](vector<long long> a) { sort(a.begin(), a.end()); for (int i = 1; i < (int)a.size(); ++i) if (a[i - 1] == a[i]) ret...

Full text and comments »

Разбор Educational Codeforces Round 148 [problem:1832A] Идея: [user:BledDest,2023-05-13] <spoiler summary="Разбор"> [tutorial:1832A] </spoiler> <spoiler summary="Решение (Neon)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { string s; cin >> s; s = s.substr(0, s.size() / 2); int k = unique(s.begin(), s.end()) - s.begin(); cout << (k == 1 ? "NO" : "YES") << '\n'; } } ~~~~~ </spoiler> [problem:1832B] Идея: [user:BledDest,2023-05-13] <spoiler summary="Разбор"> [tutorial:1832B] </spoiler> <spoiler summary="Решение (awoo)"> ~~~~~ for _ in range(int(input())): n, k = map(int, input().split()) a = sorted(list(map(int, input().split()))) ans = 0 pr = [0] * (n + 1) for i in range(n): pr[i + 1] = pr[i] + a[i] for i in range(k + 1): ans = max(ans, pr[n - (k - i)] - pr[2 * i]) print(ans) ~~~~~ </spoiler> [problem:1832C] Идея: [user:BledDest,2023-05-13] <spoiler summary="Раз...

Full text and comments »

Разбор Educational Codeforces Round 93 [problem:1398A] Идея: [user:Roms,2020-08-15] <spoiler summary="Разбор"> [tutorial:1398A] </spoiler> <spoiler summary="Решение (Roms)"> ~~~~~ for _ in range(int(input())): n = int(input()) a = list(map(int, input().split())) if a[0] + a[1] > a[-1]: print(-1) else: print(1, 2, n) ~~~~~ </spoiler> [problem:1398B] Идея: [user:BledDest,2020-08-15] <spoiler summary="Разбор"> [tutorial:1398B] </spoiler> <spoiler summary="Решение (Ne0n25)"> ~~~~~ #include <bits/stdc++.h> using namespace std; #define sz(a) int((a).size()) #define forn(i, n) for (int i = 0; i < int(n); ++i) void solve() { string s; cin >> s; vector<int> a; forn(i, sz(s)) if (s[i] == '1') { int j = i; while (j + 1 < sz(s) && s[j + 1] == '1') ++j; a.push_back(j - i + 1); i = j; } sort(a.rbegin(), a.rend()); int ans = 0; for (int i = 0; i < sz(a); i += 2) ans += a[i]; cout << ans << endl; } int main() { in...

Full text and comments »

Разбор Educational Codeforces Round 170 [problem:2025A] Идея: [user:BledDest,2024-10-15] <spoiler summary="Разбор"> [tutorial:2025A] </spoiler> <spoiler summary="Решение (BledDest)"> ~~~~~ for _ in range(int(input())): s = input() t = input() lcp = 0 n = len(s) m = len(t) for i in range(1, min(n, m) + 1): if s[:i] == t[:i]: lcp = i print(n + m - max(lcp, 1) + 1) ~~~~~ </spoiler> [problem:2025B] Идея: [user:adedalic,2024-10-15] <spoiler summary="Разбор"> [tutorial:2025B] </spoiler> <spoiler summary="Решение (adedalic)"> ~~~~~ #include<bits/stdc++.h> using namespace std; const int MOD = int(1e9) + 7; int main() { int t; cin >> t; vector<int> ks(t); for (int _ = 0; _ < 2; _++) for (int i = 0; i < t; i++) cin >> ks[i]; vector<int> ans(1 + *max_element(ks.begin(), ks.end()), 1); for (int i = 1; i < (int)ans.size(); i++) ans[i] = (2LL * ans[i - 1]) % MOD; for (int k : ks) cout << ans[k] << '\n'; return 0; } ~~~~~ </spoiler> ...

Full text and comments »

Разбор Educational Codeforces Round 166 [problem:1976A] Идея: [user:BledDest,2024-05-31] <spoiler summary="Разбор"> [tutorial:1976A] </spoiler> <spoiler summary="Решение (awoo)"> ~~~~~ for _ in range(int(input())): n = int(input()) s = input() print("YES" if list(s) == sorted(s) else "NO") ~~~~~ </spoiler> [problem:1976B] Идея: [user:BledDest,2024-05-31] <spoiler summary="Разбор"> [tutorial:1976B] </spoiler> <spoiler summary="Решение (Neon)"> ~~~~~ #include <bits/stdc++.h> using namespace std; using li = long long; int main() { int t; cin >> t; while (t--) { int n; cin >> n; vector<li> a(n), b(n + 1); for (auto& x : a) cin >> x; for (auto& x : b) cin >> x; li sum = 0, ext = 1e18; for (int i = 0; i < n; ++i) { sum += abs(a[i] - b[i]); ext = min(ext, abs(a[i] - b[n])); ext = min(ext, abs(b[i] - b[n])); if (min(a[i], b[i]) <= b[n] && b[n] <= max(a[i], b[i])) ext = 0; } cout << sum + e...

Full text and comments »

Разбор Educational Codeforces Round 104 [problem:1487A] Идея: [user:BledDest,2021-02-16] <spoiler summary="Разбор"> [tutorial:1487A] </spoiler> <spoiler summary="Решение (Neon)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { int n; cin >> n; vector<int> a(n); for (int& x : a) cin >> x; cout << n - count(a.begin(), a.end(), *min_element(a.begin(), a.end())) << endl; } } ~~~~~ </spoiler> [problem:1487B] Идея: [user:adedalic,2021-02-16] <spoiler summary="Разбор"> [tutorial:1487B] </spoiler> <spoiler summary="Решение (adedalic)"> ~~~~~ fun main() { repeat(readLine()!!.toInt()) { var (n, k) = readLine()!!.split(' ').map { it.toInt() } k-- val floor = n / 2 println((k + (n % 2) * k / floor) % n + 1) } } ~~~~~ </spoiler> [problem:1487C] Идея: [user:BledDest,2021-02-16] <spoiler summary="Разбор"> [tutorial:1487C] </spoiler> <spoiler summary...

Full text and comments »

Разбор Educational Codeforces Round 120 [problem:1622A] Идея: [user:BledDest,2021-12-28] <spoiler summary="Разбор"> [tutorial:1622A] </spoiler> <spoiler summary="Решение (Neon)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { vector<int> l(3); for (int i = 0; i < 3; ++i) cin >> l[i]; bool ok = false; for (int i = 0; i < 3; ++i) ok |= l[i] == l[(i + 1) % 3] + l[(i + 2) % 3]; for (int i = 0; i < 3; ++i) if (l[i] % 2 == 0) ok |= l[(i + 1) % 3] == l[(i + 2) % 3]; cout << (ok ? "YES\n" : "NO\n"); } } ~~~~~ </spoiler> [problem:1622B] Идея: [user:adedalic,2021-12-28] <spoiler summary="Разбор"> [tutorial:1622B] </spoiler> <spoiler summary="Решение (awoo)"> ~~~~~ for _ in range(int(input())): n = int(input()) p = [int(x) for x in input().split()] s = input() l = sorted([[s[i], p[i], i] for i in range(n)]) q = [-1 for i in range(n)] for i in range(n): q[l[i][2]] = i...

Full text and comments »

Разбор Educational Codeforces Round 192 [problem:2242A] Идея: [user:BledDest,2026-07-07] <spoiler summary="Разбор"> [tutorial:2242A] </spoiler> <spoiler summary="Решение (BledDest)"> ~~~~~ t = int(input()) for i in range(t): k = int(input()) a = list(map(int, input().split())) if max(a) > 2 or a.count(2) > 1: print('YES') else: print('NO') ~~~~~ </spoiler> [problem:2242B] Идея: [user:FelixArg,2026-07-07] <spoiler summary="Разбор"> [tutorial:2242B] </spoiler> <spoiler summary="Решение (FelixArg)"> ~~~~~ #include <bits/stdc++.h> using namespace std; const int INF = 1'000'000'007; void solve() { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++){ cin >> a[i]; } vector<int> pref1(n + 1); vector<int> pref2(n + 1); for (int i = 0; i < n; i++){ pref1[i + 1] = pref1[i] + (a[i] == 1 ? 1 : -1); pref2[i + 1] = pref2[i] + (a[i] == 3 ? -1 : 1); } int mn = INF; for (int i = 1; i < n; i++){ if (pr...

Full text and comments »

Разбор Educational Codeforces Round 127 [problem:1671A] Идея: [user:BledDest,2022-04-23] <spoiler summary="Разбор"> [tutorial:1671A] </spoiler> <spoiler summary="Решение (BledDest)"> ~~~~~ t = int(input()) for i in range(t): s = input() ans = True n = len(s) for j in range(n): if (j == 0 or s[j] != s[j - 1]) and (j == n - 1 or s[j] != s[j + 1]): ans = False print('YES' if ans else 'NO') ~~~~~ </spoiler> [problem:1671B] Идея: [user:vovuh,2022-04-23] <spoiler summary="Разбор"> [tutorial:1671B] </spoiler> <spoiler summary="Решение (vovuh)"> ~~~~~ for i in range(int(input())): n = int(input()) x = list(map(int, input().split())) print('YES' if x[-1] - x[0] - n + 1 <= 2 else 'NO') ~~~~~ </spoiler> [problem:1671C] Идея: [user:vovuh,2022-04-23] и [user:BledDest,2022-04-23] <spoiler summary="Разбор"> [tutorial:1671C] </spoiler> <spoiler summary="Решение (adedalic)"> ~~~~~ fun main() { repeat(readLine()!!.t...

Full text and comments »

Разбор Educational Codeforces Round 163 [problem:1948A] Идея: [user:BledDest,2024-03-16] <spoiler summary="Разбор"> [tutorial:1948A] </spoiler> <spoiler summary="Решение (Neon)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { int n; cin >> n; if (n % 2 == 1) { cout << "NO" << '\n'; continue; } cout << "YES" << '\n'; for (int i = 0; i < n / 2; ++i) for (int j = 0; j < 2; ++j) cout << "AB"[i & 1]; cout << '\n'; } } ~~~~~ </spoiler> [problem:1948B] Идея: [user:BledDest,2024-03-16] <spoiler summary="Разбор"> [tutorial:1948B] </spoiler> <spoiler summary="Решение (Neon)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { int n; cin >> n; vector<int> a(n); for (auto& x : a) cin >> x; vector<int> b({a[n - 1]}); for (int i = n - 2; i >= 0; --i) { if (a[i] > b.back()) {...

Full text and comments »

Разбор Educational Codeforces Round 130 [problem:1697A] Идея: [user:vovuh,2022-06-13] <spoiler summary="Разбор"> [tutorial:1697A] </spoiler> <spoiler summary="Решение (vovuh)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { #ifdef _DEBUG freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); #endif int tc; cin >> tc; while (tc--) { int n, m; cin >> n >> m; int sum = 0; for (int i = 0; i < n; ++i) { int x; cin >> x; sum += x; } cout << max(0, sum - m) << endl; } return 0; } ~~~~~ </spoiler> [problem:1697B] Идея: [user:BledDest,2022-06-13] <spoiler summary="Разбор"> [tutorial:1697B] </spoiler> <spoiler summary="Решение (Neon)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; vector<long long> p(n), s(n + 1); f...

Full text and comments »

Разбор Educational Codeforces Round 150 [problem:1841A] Идея: [user:BledDest,2023-06-13] <spoiler summary="Разбор"> [tutorial:1841A] </spoiler> <spoiler summary="Решение (BledDest)"> ~~~~~ t = int(input()) for i in range(t): n = int(input()) print('Alice' if n >= 5 else 'Bob') ~~~~~ </spoiler> [problem:1841B] Идея: [user:BledDest,2023-06-13] <spoiler summary="Разбор"> [tutorial:1841B] </spoiler> <spoiler summary="Решение (awoo)"> ~~~~~ for _ in range(int(input())): q = int(input()) a = [] cnt = 0 for x in map(int, input().split()): nw_cnt = cnt + (len(a) > 0 and a[-1] > x) if nw_cnt == 0 or (nw_cnt == 1 and x <= a[0]): a.append(x) cnt = nw_cnt print('1', end="") else: print('0', end="") print() ~~~~~ </spoiler> [problem:1841C] Идея: [user:BledDest,2023-06-13] <spoiler summary="Разбор"> [tutorial:1841C] </spoiler> <spoiler summary="Решение 1 (Neon)"> ~~~~~ #include <bits/stdc++.h> using namespace std; const int val[]...

Full text and comments »

Codeforces Round #861 (Div. 2) <a href="https://ibb.co/hB6SF5F"><img src="https://i.ibb.co/48qHRyR/350-20230320195909.png" alt="350-20230320195909" border="0"></a> Привет, Codeforces! Я очень рад пригласить вас на [Codeforces Round #861 (Div. 2)](https://codeforces.me/contest/1808), который пройдет в [contest_time:1808]. <b>Этот раунд будет рейтинговым для участников, чей рейтинг ниже, чем 2100.</b> Моя искренняя благодарность: - [user:KAN,2023-03-26] и [user:aleks5d,2023-03-26] за выдающуюся координацию раунда! - [user:Wind_Eagle,2023-03-26], [user:BaluconisTima,2023-03-26], [user:kartel,2023-03-26], [user:gepardo,2023-03-26] и [user:244mhq,2023-03-26] за идеи задач для раунда, а также [user:BaluconisTima,2023-03-26], [user:244mhq,2023-03-26], [user:VEGAnn,2023-03-26], [user:Vladik,2023-03-26] и [user:andrew,2023-03-26] за разработку задач. - [user:vilcheuski,2023-03-26] и [user:programmer228,2023-03-26] &mdash; остальную команду авторов, без которых этот раунд бы не состоялся. - [user:Balucon...

Full text and comments »

Разбор Educational Codeforces Round 109 [problem:1525A] Идея: [user:adedalic,2021-05-17] <spoiler summary="Разбор"> [tutorial:1525A] </spoiler> <spoiler summary="Решение (adedalic)"> ~~~~~ #include<bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { int k; cin >> k; cout << 100 / gcd(100, k) << endl; } return 0; } ~~~~~ </spoiler> [problem:1525B] Идея: [user:BledDest,2021-05-17] <spoiler summary="Разбор"> [tutorial:1525B] </spoiler> <spoiler summary="Решение (Neon)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); vector<int> a(n); for (int &x : a) scanf("%d", &x); int ans = 2; if (is_sorted(a.begin(), a.end())) ans = 0; else if (a[0] == 1 || a[n - 1] == n) ans = 1; else if (a[0] == n && a[n - 1] == 1) ans = 3; printf("%d\n", ans); } } ~~~~~ </spoiler> [problem:1525C] Идея: [...

Full text and comments »

Разбор Educational Codeforces Round 85 [problem:1334A] Идея: [user:pikmike,2020-04-11] <spoiler summary="Разбор"> [tutorial:1334A] </spoiler> <spoiler summary="Решение (pikmike)"> ~~~~~ #include <bits/stdc++.h> #define forn(i, n) for (int i = 0; i < int(n); i++) using namespace std; int main() { int tc; scanf("%d", &tc); while (tc--){ int n; scanf("%d", &n); int p = 0, c = 0; bool fl = true; forn(i, n){ int x, y; scanf("%d%d", &x, &y); if (x < p || y < c || y - c > x - p) fl = false; p = x, c = y; } puts(fl ? "YES" : "NO"); } return 0; } ~~~~~ </spoiler> [problem:1334B] Идея: [user:adedalic,2020-04-11] <spoiler summary="Разбор"> [tutorial:1334B] </spoiler> <spoiler summary="Решение (adedalic)"> ~~~~~ fun main() { val T = readLine()!!.toInt() for (tc in 1..T) { val (n, x) = readLine()!!.split(' ').map { it.toInt() } val a = readLine()!!.split(' ').map { it.toInt() }.sortedDescending() ...

Full text and comments »

Разбор Educational Codeforces Round 79 [problem:1279A] Идея: [user:BledDest,2019-12-28] <spoiler summary="Разбор"> [tutorial:1279A] </spoiler> <spoiler summary="Решение (Roms)"> ~~~~~ for t in range(int(input())): a = sorted(list(map(int, input().split()))) print('Yes' if a[2] <= a[0] + a[1] + 1 else 'No') ~~~~~ </spoiler> [problem:1279B] Идея: [user:Roms,2019-12-28] <spoiler summary="Разбор"> [tutorial:1279B] </spoiler> <spoiler summary="Решение (Roms)"> ~~~~~ for t in range(int(input())): n, t = map(int, input().split()) a = list(map(int, input().split())) id = 0 for i in range(n): if a[i] > a[id]: id = i t -= a[i] if t < 0: break if t >= 0: id = -1 print(id + 1) ~~~~~ </spoiler> [problem:1279C] Идея: [user:Roms,2019-12-28] <spoiler summary="Разбор"> [tutorial:1279C] </spoiler> <spoiler summary="Решение (Roms)"> ~~~~~ for t in range(int(input())): n, m = map(in...

Full text and comments »

Разбор Educational Codeforces Round 173 [problem:2043A] Идея: [user:BledDest,2024-12-25] <spoiler summary="Разбор"> [tutorial:2043A] </spoiler> <spoiler summary="Решение (BledDest)"> ~~~~~ t = int(input()) for i in range(t): n = int(input()) ans = 1 while n > 3: n //= 4 ans *= 2 print(ans) ~~~~~ </spoiler> [problem:2043B] Идея: [user:AcidWrongGod,2024-12-25] <spoiler summary="Разбор"> [tutorial:2043B] </spoiler> <spoiler summary="Решение (BledDest)"> ~~~~~ import sys sys.set_int_max_str_digits(6000) def fact(x): if x == 0: return 1 return x * fact(x - 1) t = int(input()) for i in range(t): n, k = map(int, input().split()) n = min(n, 7) s = int(str(k) * fact(n)) for i in range(1, 10, 2): if s % i == 0: print(i, end = ' ') print() ~~~~~ </spoiler> [problem:2043C] Идея: [user:Ferume,2024-12-25] <spoiler summary="Разбор"> [tutorial:2043C] </spoiler> <spoiler ...

Full text and comments »

Разбор Educational Codeforces Round 114 [problem:1574A] Идея: [user:BledDest,2021-09-21] <spoiler summary="Разбор"> [tutorial:1574A] </spoiler> <spoiler summary="Решение (BledDest)"> ~~~~~ t = int(input()) for i in range(t): n = int(input()) for j in range(n): print("()" * j + "(" * (n - j) + ")" * (n - j)) ~~~~~ </spoiler> [problem:1574B] Идея: [user:BledDest,2021-09-21] <spoiler summary="Разбор"> [tutorial:1574B] </spoiler> <spoiler summary="Решение (awoo)"> ~~~~~ for _ in range(int(input())): a, b, c, m = map(int, input().split()) a, b, c = sorted([a, b, c]) print("YES" if c - (a + b + 1) <= m <= a + b + c - 3 else "NO") ~~~~~ </spoiler> [problem:1574C] Идея: [user:BledDest,2021-09-21] <spoiler summary="Разбор"> [tutorial:1574C] </spoiler> <spoiler summary="Решение (Neon)"> ~~~~~ #include <bits/stdc++.h> using namespace std; using li = long long; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; ci...

Full text and comments »

Разбор Educational Codeforces Round 71 [problem:1207A] Идея: [user:BledDest,2019-08-23] <spoiler summary="Разбор"> [tutorial:1207A] </spoiler> <spoiler summary="Решение (Roms)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int t; int b, p, f; int h, c; int main() { cin >> t; for(int tc = 0; tc < t; ++tc){ cin >> b >> p >> f; cin >> h >> c; b /= 2; if(h < c){ swap(h, c); swap(p, f); } int res = 0; int cnt = min(b, p); b -= cnt, p -= cnt; res += h * cnt; cnt = min(b, f); b -= cnt, f -= cnt; res += c * cnt; cout << res << endl; } return 0; } ~~~~~ </spoiler> [problem:1207B] Идея: [user:BledDest,2019-08-23] <spoiler summary="Разбор"> [tutorial:1207B] </spoiler> <spoiler summary="Решение (BledDest)"> ~~~~~ n, m = map(int, input().split()) a = [[] fo...

Full text and comments »