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

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

Что-то я немного торможу, забыл что уже лето в разгаре. Насколько я знаю, у 9-11 классов последние экзамены закончились в мае, сейчас только пересдача, у студентов понятия не имею, но если ещё остались экзы, то удачи вам!!!

Как проходит лето? У меня отлично, школа наконец оставила меня в покое, за год вышел отличником (по химии чуть 4 не получил XD). Переезд в Россию уже совсем скоро, завтра забираем документы и выезжаем! За это время я буду инактив, в пути посетим несколько городов и только в первом (Астана, Нур-Султан) у меня будет кратковременный доступ к сети, 1-2 дня. После вайфай у меня появится только на конечной остановке — в Санкт-Петербурге. Мобильного интернета тоже не будет, ибо SIM-карта будет в нерабочем состоянии на территории РФ. И да, переезд будет осуществляться на автомобильном транспортном средстве, из чего понятно, что зайти на сайт и вообще куда либо я смогу очень и ооочень не скоро. (Может в каком то хостеле по пути ненадолго подключусь к их сети, но не факт). Чем заняться в дороге я ещё не знаю, по ходу дела будет видно (но я то знаю, что буду просто спать всё время :D).

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

А чем вы будете заниматься в этот жаркий сезон? Будет интересно почитать, пишите внизу.

P.S. Вот теперь интересный вопрос, каким образом я буду писать контест завтра :/

Невероятно, вклад +17, спасибо вам огромное!

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

Как вы поняли я абсолютно не программировал почти последний месяц на cf-е, увидев свою статистику я застыл с открытым ртом. 3 ЗАДАЧИ ЗА ПОСЛЕДНИЙ МЕСЯЦ! Это стыдно, очень стыдно. И были бы они тяжёлыми, так нет, Ашки и Бшки из Див.3 контестов :/. Актив уже как минимум нужно повышать, иначе попросту ничего толкового не выйдет. Во-вторых, не пишу контесты. И будем честны, найти 2-3 часа раз в почти месяц можно было для этого. Не писал под страхом потерять рейтинг или ещё хуже — потерять цвет никнейма. Но я вижу что у друзей спокойно получается подняться до 1300+, а у некоторых и вовсе до специалиста. Почему бы не попробовать? Не знаю когда ближайший контест, но нужно постараться сделать все дела и оставить время на его написание.

На асмр я кстати до сих пор потихоньку решаю, но приоритет всё же на codeforces-е выше.

Ну и куда же без изучения теории. Тут уже затруднительней, поскольку те темы на которые я натыкаюсь, либо не используют почти на практике, либо слишком тяжёлые. Поэтому я хочу спросить у вас, что мне изучать дальше? Пишите вниз, я обязательно прочитаю.

Пока что всё...а нет, забыл сказать важную вещь. Не путайте дфс с бфсом. Я как то раз перепутал и сказал что задачу надо решать бфсом, на меня косо стали смотреть, потом дошло что не так. Вот теперь всё!

Всем снова хай! Столько всего было, происходили и радостные вещи и крахи, всё что только можно, обо всём по порядку.

Самым давним важным событием, не упомянутым у меня на страничке, стала забавная вещь, которая меня не огорчила, но и не порадовала — я не участвовал на финале Технокубка. Вы спросите: "Чего?! Ты гонишь?". Нет, были на то свои причины. Время? Неа, было навалом. Другое обстоятельство, а именно мне не удалось и вовсе зарегаться. В регистрации нужно было указать паспорт, файл с согласием на обработку персональных данных и со школы ещё какой-то документ. Этот самый документ получить не удалось, онлайн обучение, на выходные школа закрыта. Подумал, ладно, не важно, потом разберусь (не разобрался :/), начал спрашивать у учителя информатики, что за обработка персональных данных и как дать на неё согласие. В ответ услышал "Не знаю, наверное там не файл а галочку надо поставить, внимательно посмотри". Посмотрел, нету, файл какой-то. Ну и не поучаствовал. Спустя какое-то время захожу в группы, в которых я состою и угадайте что вижу? +1 группа с названием "Технокубок 2020/2021". Честно говоря, до сих пор без понятия, мог ли участвовать я не зарегистрировавшись или доступ бы не дали, короче напишите в комменты что к чему.

Далее, ничего такого выделяющегося на фоне повседневности. Скука, скука, скука... Бац! Знакомый пишет. Спрашивает, могу написать прогу, чтобы она меньше чем за 10 минут перебрала все шестизначные числа с ведущими нулями. Зачем? Бесила одноклассница, хотел взломать её акк в инсте и сделать там публикацию, из-за которой её бы забанили. Услышав это, сначала заинтересовался, а потом такой в голове у себя: "Зачем, потрачу своё время, ещё и такие вещи делать запрещено, нет, спасибо". Вроде сейчас не вспоминает за это, буду надеяться. Да и желания никакого нету, интереса тоже...

Опять суровые будни школьника. Собираемся переехать в Питер, ищем новую школу (вернёмся во времени назад, в середину февраля). Наткнулся на 239. В мозгу промелькнула, мысль, что если в Казахстане учусь в РФМШ, то и там смогу поступить. Готовился усердно. 3 дня до экзаменов, сердце начало не переставая сильно стучать, очень неприятное явление. Написал экзамен, резы должны были быть через 3 дня (уже возвращаемся как раз за эти 3 дня до резов). Мало того, что это не утихло, так сердцебиение ещё и удвоилось в силе (знал бы, что всё это будет зря...). С чего бы такое могло произойти? Были ли предпосылки такому? Были, и не одна. Знаю, будет кому то скучно опять возвращаться назад, в конец 3 учебной четверти, поэтому кому не интересно, игнорируйте следующий абзац.

И так, вот мы как раз в этом самом конце 3 четверти. Контрольные, всё равно страшно, а в этот раз было по особенному боязно за оценку. Все мы волнуемся перед экзаменами, что тут такого. А ВОТ И НЕТ! Не просто не нужно это делать, я бы даже сказал ни в коем случае нельзя!!! Каждое волнение отражается на организме, копится как снежный ком. И вот, закончились контрольные, жду оценок, снова боюсь. Вижу на телефоне уведомление — сообщение от учителя физики. Знал, что оно про четвертную контрольную. И тут... сердце застучало, голова закружилась, стало тошнить немного. Пол минуты так было, вроде поутихло. Хотя написал всё равно не фонтан, можно было изначально забить. Нет же, днём снова такое повторилось, только уже беспричинно, и даже дважды. С чего бы это? Начал следить внимательно, поспешных выводов не делал, волнение пока не подозревал. Но жду ответов на другие профильные предметы — вновь и вновь это повторялось. Уже не оставалось сомнений, что доигрался со своим здоровьем. "Всё делается хорошо на холодную голову". Тут то я и понял, почему. Не только потому, что голова свежее и лучше работает. Гробя себя, я сам того не заметив довёл себя до этого. Лютое задротство перед учебниками, что мне это дало? Да ничего, те же оценки только ухудшились. Думаете всё? Конечно же нет. Началась 4 четверть, проблема вернулась, но приняла уже намного более устрашающий облик. Безусловно, такой сильной аритмии (не хотел писать это слово, не знаю аритмия ли это, поправьте если что внизу :) ), но за то она не прекращалась. Да, да, с 1 апреля и до сих пор она не проходит. Так ещё и местами хуже становится. Школа не даёт мне расслабиться, так тут ещё и вот это произошло...

И вот, сегодня выходят резы на поступление в 239 лицей. Все поддерживали меня, желали удачи. Благодарю вас всех очень сильно и столь же сильно прошу у вас прощения. Я вас подвёл, экзамен был провален. И этот день можно назвать началом следующей главы моей жизни. Весь следующий год, я буду учиться в простой школе. Всё это время будет считаться эпизодом провала и восхождения. Да, теперь я уже не уверен, что в 9 классе всё изменится к лучшему, но надежда умирает последней. Но я уже присмотрел одну школу при университете и к счастью она даже совпадает с моими интересами. И по статусу она вроде не уступает, просто не такая популярная. В неё и попытаюсь попасть. Ну а весь этот год будет для меня очень тяжёлым. Кто знает, что произойдёт в будущем. Но буду надеяться на лучшее! И да, кстати, увеличение актива будет зависеть от мотивации писать что-то. Она уже зависит от оценки постов. Ну а так пока что всё!

P.S. НЕ ЗАДРОТЬТЕ НАД УЧЁБОЙ, ВСЕГО В МЕРУ!

Очень извиняюсь, по личным причинам задержался на пол недели, обо всём в следующем посте

Результаты голосования удивили, вам действительно интересен мой блог и поэтому с радостью сообщаю, что не закрываю его! Новая публикация в течении часа ;)

Я заметил что мой вклад сильно поднялся с -33 (примерная цифра) до -24

Но сами статьи пользуются переменным успехом

И настал момент спросить у вас, читателей, продолжить ли мне писать сюда? Если да, то активность сильно увеличится, иначе здесь не будет ничего в будущем, может даже навсегда. Если эта публикация будет иметь положительную оценку (+1 и выше), то я буду считать это как ответ ДА, в противном случае — при неположительной оценке (0 и меньше) блог больше не будет вестись. Через неделю всё узнаем...

Конечно запоздал я с этой новостью, но лучше поздно чем никогда. По результатам 3 раунда я занял 185 место и прошёл в финал Технокубка!!! Когда будет сам финал я не знаю, но попытаюсь к нему хорошо подготовится.

Долго не писал в блог, соревнований не было, да и ничего особенного не происходило. Но эта неделя будет напряжённой. Через пол часа начнётся очередной див.3 контест, а в воскресенье будет 2 отборочный раунд Технокубка. Единственное, что я могу сказать на данный момент, это пожелать всем удачи! :)

P.S. Постараюсь делать заметки чаще

Что же делать, когда на Cf нет подходящих для меня контестов? Кто-то смотрит видеоматериалы по изучению с++, кто-то и вовсе не посещает никаких сайтов, а я решаю задачи на acmp.ru. Это не реклама))), а лишь небольшая заметка по моей подготовке к различным соревнования на Codeforces (многим интересна эта тема). Всем советую)

P.S. Уже заскучал без соревнований :(

Учёба близится к концу, контрольные идут одна за одной. Возможности посещать Cf не представляется практически вообще. Однако для такого события я решил поискать.

Что же по результатам? Для начал скажу, что отборочный раунд имел сложность где то див.2, смог решить лишь 1 задачу из 6. Я ожидал что окажусь где то в самом низу турнирной таблицы, но мне удалось даже попасть в 1/3 лучших участников! Повезло конечно сильно и не только здесь. Самым неожиданным стало неестественно большое повышение рейтинга. Однако такого результата для прохода в финал скорее всего будет недостаточно, известно будет позже!

Новый рейтинг: 911 (+241)!

пока писал статью интернет вылетал один раз(((

Всем снова HI. Большинство из Вас слышали о соревновании под названием Технокубок и лично я буду на нём участвовать впервые. Основное его отличие от других турниров в том, что он проводится для школьников 8-11 классов (а значит он по зубам и мне). А что же на счёт подготовки?

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

Так что об этом соревновании одно могу сказать точно — попасть в финал будет крайне сложно, поэтому хорошая подготовка здесь не помешает никому. А ещё и удача, которую я вам желаю)

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

1) Разбор различных задач

2) Обучение по С++

3) О моих личных тренировках и подготовках к соревнованиям

4) Что-нибудь другое (написать подробно)

Свои ответы пишите в комментариях под этой статьёй (позже оглашу результаты голосования)

Задача A

Условие:

Есть дом, в котором расположены 10 000 квартир, пронумерованных от 1 до 10 000. Назовем номер квартиры скучным, если ее номер состоит из одинаковых цифр. Примерами скучных квартир являются 11,2,777,9999 и так далее. Наш герой очень наглый и он любит звонить в домофоны всех скучных квартир до тех пор, пока кто-то не ответит, в следующем порядке: сначала он обзванивает квартиры, состоящие из цифр 1, в возрастающем порядке (1,11,111,1111); затем он обзванивает квартиры, состоящие из цифр 2, в возрастающем порядке (2,22,222,2222); и так далее. Житель скучной квартиры xx ответил на звонок. После этого наш герой перестал обзванивать кого-либо еще. Наш герой хочет знать, как много цифр он суммарно нажал. Ваша задача — помочь посчитать ему суммарное количество нажатых клавиш. Например, если житель квартиры 22 ответил, то наш герой звонил в квартиры с номерами 1,11,111,1111,2,22. Таким образом, суммарное количество нажатий равно 1+2+3+4+1+2=13. Вам нужно ответить на tt независимых наборов тестовых данных.

Решение:

Исходя из условия, нетрудно понять, что из одной цифры можно сделать 4 номера и суммарно в них будет 10 цифр. Значит, для начала нужно посчитать, сколько можно сделать номеров, состоящих из цифр, меньших чем те, которые используются в числе x. Далее, нужно посчитать количество номеров квартир состоящих из цифр числа x и не больших, чем оно само.

Задача B

Условие:

Есть книжная полка, на которой может уместиться n книг. i-я позиция на книжной полке ai=1, если на этой позиции находится книга, и ai=0 иначе. Гарантируется, что есть как минимум одна книга на книжной полке. За один ход вы можете выбрать какой-то непрерывный отрезок [l;r], состоящий из книг (то есть для каждого i от l до r должно выполняться условие ai=1), и: Сдвинуть его вправо на 1: переместить книгу с индекса i в i+1 для всех l≤i≤r. Этот ход можно свершить только тогда, когда r+1≤n и на позиции r+1 нет книги. Сдвинуть его влево на 1: переместить книгу с индекса i в i−1 для всех l≤i≤r. Этот ход можно свершить только тогда, когда l−1≥1 и на позиции l−1 нет книги. Ваша задача — найти минимальное количество ходов, необходимое, чтобы собрать все книги на полке в непрерывный (последовательный) отрезок (т.е. отрезок без промежутков). Например, в a=[0,0,1,0,1] есть промежуток между книгами (a4=0 при a3=1 и a5=1), в a=[1,1,0] нет промежутков между книгами и в a=[0,0,0] тоже нет промежутков между книгами. Вам нужно ответить на t независимых наборов тестовых данных.

Решение:

Решение этой задачи немногим сложнее, чем в задаче A. Нам нужно лишь сдвинуть книги самым оптимальным способом, то есть друг к другу. Из этого вытекает логический вывод, что нужно лишь посчитать количество пустых расстояний между книгами (количество нулей между крайними единицами, которое надо найти при помощи цикла). Так как за один ход мы можем сдвинуть книги лишь на одно такое расстояние, то найденного нами значения кол-ва нулей будет достаточно, чтобы ответить на вопрос, поставленный в этой задаче.

Задача C

Условие:

В аквариуме есть n пираний с размерами a1,a2,…,an. Пираньи пронумерованы слева направо в том порядке, в котором они живут в аквариуме. Ученые из Берляндского государственного университета хотят узнать, есть ли в аквариуме доминирующая пиранья. Пиранья называется доминирующей, если она может съесть всех пираний в аквариуме (за исключением самой себя, конечно же). Другие пираньи не будут делать ничего, пока доминирующая пиранья будет есть их. Поскольку аквариум довольно узкий и длинный, пиранья может есть только одну из соседних пираний за один ход. Пиранья может делать сколько угодно ходов (конечно же, до тех пор, пока она может). Более детально: Пиранья i может съесть пиранью i−1, если пиранья i−1 существует и ai−1<ai. Пиранья i может съесть пиранью i+1, если пиранья i+1 существует и ai+1<ai. Когда пиранья ii съедает какую-либо пиранью, ее размер увеличивается на единицу (ai становится равным ai+1). Ваша задача — найти любую доминирующую пиранью в аквариуме или определить, что таких пираний нет. Обратите внимание, что вам нужно найти любую (ровно одну) доминирующую пиранью, вам не нужно находить всех подходящих пираний. Например, если a=[5,3,4,4,5], то третья пиранья может быть доминирующей. Рассмотрим последовательность ее передвижений: Пиранья съедает вторую пиранью, и a становится равным [5,5,4,5] (подчеркнутая пиранья — наш кандидат). Пиранья съедает третью пиранью, и a становится равным [5,6,5]. Пиранья съедает первую пиранью, и a становится равным [7,5]. Пиранья съедает вторую пиранью, и a становится равным [8]. Вам нужно ответить на t независимых наборов тестовых данных.

Решение:

Разумеется, самым главным и наиболее подходящим претендентом на доминирующую пиранью, является рыба с самым наибольшим показателем ai. Однако таких пираний может быть несколько. Для начала нужно найти их количество. Если оно равно кол-ву рыб в аквариуме, значит каждый сосед каждой рыбы не может быть съеден. В противном случае, ответ найдётся всегда, им будет являться любая рыба с максимальным показателем, имеющая хотя бы одного более мелкого соседа, так как после его съедения эта пиранья станет фаворитом среди остальных и ей будет «по зубам» любой конкурент, нужно лишь пробежавшись по массиву найти первую попавшуюся рыбку, удовлетворяющую всем вышеперечисленным условиям.

Я перевожу блог на этот аккаунт, так как вести его на старом было очень неудобно. Эту идею мне дал Dart-Xeyter, за что ему огромное спасибо!

Сюда я перекидываю лишь последнюю статью, так как остальные уже потеряли свою актуальность.

Честно говоря, такого результата я не ожидал вообще! Слов не хватает, чтобы описать произошедшее, но я попытаюсь).

Соревнование прошло не только успешно, но и с невероятным прогрессом! Мне удалось решить половину контеста (3.5 из 7 задач, задача D была решена при тестах с отсортированным массивом и сам алгоритм был уже верно продуман), место занял тоже неплохое — 6179. Звучит довольно слабо, но на деле даже туда добраться было целым испытанием.

По решённым задачам (A,B,C) я решил сделать разбор, выложу позже.

Новый рейтинг: 670 (+309)!!!