Эксперт за 100 дней — День 5 („• ֊ •„)

Что я сделал

Попытался разобраться с E Дива 2, мало что понял. Стоит ли мне решать задачи на 2000+ по разборам? Мне нужны мнения опытных людей по этому поводу, напишите в комментариях пж. После E я не начал дорешивать контест от тренера, а вместо этого сел создавать задачу в Полигоне (у меня там есть дело одно, короче мне нужно периодически выделять время на разработку задач). Разработка задачи в итоге затянулась, я устал, и так и не начал дорешивать контест от тренера, хотя хотел. Такое себе, конечно. Буду выделять отдельные дни для разработки задач, чтобы не было такого, что я хочу сделать одно, а делаю другое.

Планы

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

До завтра ( •◡-)-♡

Эксперт за 100 дней — День 4 (งツ)ว

Что я сделал

Сегодня у меня было очень много свободного времени, однако большая его часть куда-то пропала, вообще не понял куда. Буду следить за собой и писать планы на день, чтобы такого больше не было. Ну короче, неплохо щас дорешал тот Див 2, на котором недавно участвовал (решил D1 и D2, с E разберусь завтра). Мне очень понравилось, что я щас смог побороть лень и желание спать, и всё-таки сел дорешивать Див 2. Если бы не ведение блога, я бы просто не смог себя заставить..) Круто, ваша поддержка реал помогает.

Планы

Завтра у меня будет свободный день. Уже писал, но повторюсь, что завтра посмотрю E Дива 2, в котором я сегодня решил D1 и D2, и начну уже наконец-то дорешивать ИОИП от тренера. Чтобы завтра не оплошаться и не потратить свободное время впустую, распишу план на день.

Всем пока, увидимся завтра ~(^-^)~

Эксперт за 100 дней — День 3

Что я сделал

Сегодня был ДР друга, из-за чего на прогу времени не осталось.

Планы

Так, завтра дома надо будет хорошенько поработать. У меня в планах дорешать Див и начать дорешивать ИОИП прошлых годов, которые мне дал тренер.

Завтра ультану, до встречи :>

Эксперт за 100 дней — День 2

Что я сделал

Написал сегодня мун. тур на 307 баллов. Придя домой сел дорешивать вчерашний Див 2, но почемут появилось очень жёсткое отвращение. Я просто не смог себя заставить доделать раунд, надеюсь, это я просто выдохся после муна и такое больше не повторится. Щас доделаю уроки и лягу спать.

Планы

Есть небольшая вероятность, что я не выйду в рег. Если такое произойдёт, то меня заставят делать какой-то IT-проект, а если я его не буду делать, то меня выгонят из IT-класса, чтобы я не портил рейтинг школы. Есть проблема: я не хочу делать этот проект, я хочу продолжать заниматься ол. прогой даже если не выйду в рег. Похоже, мне остаётся только молиться, что я выйду в рег и дела обойдутся без всяких проектов.

На этом пока всё, увидимся завтра ;)

Эксперт за 100 дней — День 1

Что я сделал

Завтра у меня мун тур... Сегодня я прорешал мун. тур прошлого года, чтобы понять, какие у меня шансы выйти в рег. В итоге набрал 400 баллов, так что с высоким шансом и завтра смогу затащить. Так же я поучаствовал в Диве 2, хотя, конечно, лучше не нагружать голову перед олимпиадой.

Планы

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

Увидимся завтра ( ˘ ³˘)♥

Привет, Codeforces! (ﾉ◕ヮ◕)ﾉ*:･ﾟ✧

Меня зовут Коля, сейчас я учусь в 9-ом классе. Хотелось бы рассказать вам о том что со мной приключилось...

Произошедшее

Цель

Ну начнём с того, что я поставил себе цель, для выполнения которой мне придётся постараться. Я очень хочу добиться хороших высот в олимпиадном / спортивном программировании, и мне очень повезло, ведь у меня есть всё для этого — личный тренер с небольшой группой, с которым можно обсудить любые вопросы, я учусь в неплохой школе, да и время у меня есть (но с каждым днём его становится всё меньше и меньше). Казалось бы, сиди и ботай, всё у тебя хорошо, вот только есть проблема...

Моя проблема

Я привык к тому, что раньше я везде был лучшим, при этом особо ничего не делая. Многие мои знакомые, в отличие от меня, привыкли к тому, что лучших вещей нужно добиваться упорным трудом, и я считаю это правильно, именно так и надо двигаться по жизни. Мне же не очень повезло, ведь по особому стечению обстоятельств я долгое время во многом был среди лучших, при этом даже не трудясь. Кроме того, ещё и родственники со знакомыми хвалили меня, говоря: "Какой же ты умный и одарённый! Молодец!", хотя я вообще не трудился и не заслуживал этой похвалы (я не виню родственников, во всём происходящем виноват я, однако эти слова тоже сыграли свою роль). Из-за всех этих обстоятельств у меня сложились ошибочные взгляды на жизнь. Я начал думать, что я один такой самый "умный", "лучший", "одарённый", я начал считать себя победителем по жизни. Самое страшное, что я начал думать, что для достижения успеха нужно не трудиться, а просто родиться "одарённым" — таким, как я. В итоге я продолжил двигаться в этом неправильном направлении.

Перелом

После поступления в класс с профилем IT в 7-ом классе я столкнулся с людьми, которые добились огромных знаний и высот путём своего труда. Для меня стало неожиданностью то, что есть кто-то лучше меня. Это сломало меня. Я практически сразу начал завидовать, комплексовать, депрессировать, сравнивать себя с другими. Я столкнулся с тем, что теперь для того, чтобы стать лучшим, мне нужно трудиться, но я не был готов к этому, у меня не было ни дисциплины, ни моральных принципов. Я уже был запущен...

Программирование

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

И наконец...

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

Блог

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

Первый вызов

Итак, ребята, я бросаю себе первый вызов: $$$\color{blue}{\textbf{Эксперт}}$$$ за 100 дней.

Придётся поработать. Ждите, завтра в моём блоге начинают публиковаться ежедневные отчёты.

Всем привет!

Наверняка вы, как и я, готовитесь к ВсОШ по информатике. И вам всем было бы очень удобно, чтобы все задачи с предыдущих годов и соревнования для подготовке были в одной большой группе, чтобы можно было легко и быстро выбрать подходящее для себя соревнование.

Специально для этого я создал группу, в которую я буду добавлять все задачи с предыдущих туров ВсОШ которые смогу найти на сайте. Кроме того, я и сам занимаюсь переноской задач на сайт и поэтому буду добавлять все свои перенесённые задачи в том числе.

Ссылка на группу тут: https://codeforces.me/group/AXmHCZYOtq

У меня день рождения в один день с tourist! Похоже, это знак! Кстати оно сегодня — 25 сентября, поэтому я хочу поздравить tourist и себя с днём рождения! Очень буду рад принять поздравления и от вас

Примечания к задаче

Загадка последовательной суммы — простая, но интересная задачка на математическую логику, которая является первой задачей из соревнования Codeforces Round 747 (Div. 2).

Условия к задаче

Данные

Имя входного файла: Стандартный ввод / input.txt

Имя выходного файла: Стандартный вывод / output.txt

Ограничение по времени: 2 секунды

Ограничение по памяти: 256 мегабайт

Условие

У Теофаниса есть для вас загадка, и, если вы сможете ее решить, он угостит вас халлуми — кипрским сыром.

Вам задано целое число $$$n$$$. Вам нужно найти два целых числа $$$l$$$ и $$$r$$$ таких, что $$$−10^{18}$$$ ≤ $$$l$$$ < $$$r$$$ ≤ $$$10^{18}$$$ и $$$l$$$ + ($$$l$$$+$$$1$$$) + … + ($$$r$$$−$$$1$$$) + $$$r$$$ = $$$n$$$. ..

Формат входных данных

В первой строке задано одно целое число $$$t$$$ ($$$1$$$ ≤ $$$t$$$ ≤ $$$10^{4}$$$) — количество наборов входных данных.

В первой и единственной строке каждого набора входных данных задано одно целое число $$$n$$$ ($$$1$$$ ≤ $$$n$$$ ≤ $$$10^{18}$$$).

Формат выходных данных

Для каждого набора входных данных выведите два целых числа $$$l$$$ и $$$r$$$ таких, что $$$−10^{18}$$$ ≤ $$$l$$$ < $$$r$$$ ≤ $$$10^{18}$$$ и $$$l$$$ + ($$$l$$$+$$$1$$$) + … + ($$$r$$$−$$$1$$$) + $$$r$$$ = $$$n$$$.

Можно показать, что ответ всегда существует. Если существует несколько ответов, выведите любой.

Пример

Стандартный ввод:

7

1

2

3

6

100

25

3000000000000

Стандартный вывод:

0 1

-1 2

1 2

1 3

18 22

-2 7

999999999999 1000000000001

Объяснение задачи

Ввод

Первым делом, мы должны прописать правильный ввод данных.

Ввод данных здесь очень простой, мы должны просто ввести число t, после чего t раз ввести число n при помощи цикла for:

t = int(input())
for i in range(t):
    n = int(input())
    pass

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

Алгоритм решения

Итак, что же делать дальше? Как решить задачу? Фактически, нам нужно найти два целых числа $$$l$$$ и $$$r$$$ таких, что сумма арифметической прогрессии от $$$l$$$ до $$$r$$$ включительно должна равняться данному числу $$$n$$$. Но как это сделать?

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

Итак, в условии нам сказано, что числа $$$l$$$ и $$$r$$$ могут быть с любым знаком, это важно. Логика здесь очень простая: никто не поспорит с тем, что если взять произвольное целое неотрицательное число $$$x$$$, то сумма арифметической прогрессии от $$$-x$$$ до $$$x$$$ равна нулю (например, от $$$-2$$$ до $$$2$$$, тогда $$$-2$$$ + $$$-1$$$ + $$$0$$$ + $$$1$$$ + $$$2$$$ = 0). Отсюда в сумме арифметической прогрессии от $$$-x$$$ до $$$x$$$ + $$$1$$$ ($$$-x$$$...$$$x$$$ + $$$x$$$ + $$$1$$$) $$$-x$$$...$$$x$$$ можно заменить на $$$0$$$, тогда получим $$$0$$$ + $$$x$$$ + $$$1$$$, что равно $$$x$$$ + $$$1$$$ (например, от $$$-2$$$ до $$$3$$$, тогда $$$-2$$$ + $$$-1$$$ + $$$0$$$ + $$$1$$$ + $$$2$$$ + $$$3$$$ = 3). Теперь, вместо $$$x$$$ + $$$1$$$ нам достаточно подставить данное нам число $$$n$$$, это будет ответ $$$r$$$. Тогда, ответом $$$l$$$, соответственно, будет число $$$-(n - 1)$$$.

Теперь нам достаточно просто вывести наши полученные значения, это и будет решением задачи:

t = int(input())
for i in range(t):
    n = int(input())
    print(-(n - 1), n)

Мой комментарий

Вот таким вот получился разбор, это был мой первый опыт объяснения задачи на логику в блоге, очень надеюсь, что вам понравилось. Если так и есть, то обязательно голосуйте плюсиком за этот разбор, мне будет очень приятно :)

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

Всем удачи! :D

Примечания к задаче

Крош и битовые операции — очень интересная задача, основанная на свойствах операции побитового исключающего ИЛИ, которую можно встретить в Зимнем личном турнире памяти С. А. Григорьева в 2023 году.

Условия к задаче

Данные

Имя входного файла: Стандартный ввод / input.txt

Имя выходного файла: Стандартный вывод / output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

Условие

Крош недавно ознакомился с битовыми операциями, и ему в голову пришла следующая задача: Пусть дан массив A из 2ⁿ неотрицательных элементов $$$a_{0}$$$,$$$a_{1}$$$,...,$$$a_{2ⁿ−1}$$$. Ему нравится операция побитового исключающего ИЛИ – xor, поэтому он рассматривает все пары индексов (i,j), такие, что i⊕j=k, где k – заданное число, ⊕ – операция побитового исключающего ИЛИ. По всем таким парам он хочет найти наибольшее суммарное значение величины $$$a_{i}$$$+$$$a_{j}$$$.

Формат входных данных

В первой строке вам дано число n (1 ≤ n ≤ 18) и число k (1 ≤ k < 2ⁿ). В следующей строке вам даны 2ⁿ целых неотрицательных чисел – $$$a_{0}$$$,$$$a_{1}$$$,...,$$$a_{2ⁿ−1}$$$ (0 ≤ $$$a_{i}$$$ ≤ 10⁹).

Формат выходных данных

Выведите ответ на задачу.

Система оценки

• Подзадача 1 (40 баллов) n ≤ 9.
• Подзадача 2 (60 баллов) без дополнительных ограничений.

Пример

Стандартный ввод:

3 3

1 4 2 7 3 1 5 2

Стандартный вывод:

8

Объяснение задачи

Ввод

Первым делом, мы должны прописать правильный ввод данных.

Реализовать ввод нескольких значений в одну строку можно при помощи встроенной функции map:

n, k = map(int, input().split())

Таким образом, мы присвоили переменным n, k значения, введя их в одну строку. Тоже самое мы делаем с набором чисел a. При этом, мы преобразуем его в список при помощи функции list:

a = list(map(int, input().split()))

Теперь, в переменной a хранится список, состоящий из введённых во второй строке чисел через пробел. Получаем код:

n, k = map(int, input().split())
a = list(map(int, input().split()))

Алгоритм решения

Что же делать дальше? Как решить задачу?

40 баллов ✓

Первое, что может прийти в голову — это тупой перебор, реализуется он довольно просто.

Давайте попробуем его написать, для начала создаём вложенный цикл, в котором мы будем перебирать индексы i и j:

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(2 ** n):
    for j in range(2 ** n):
        pass

Мы перебираем индексы именно до 2ⁿ, так как длина списка по условию задачи равна 2ⁿ. Ничего не делающий оператор-заглушка pass оставлен для удобства, он показывает место, где мы ещё не успели дописать код.

Теперь нам нужно сделать поиск максимума, это тоже не так трудно. Перед началом цикла создадим переменную, в которую будем записывать максимум, а в самом цикле сделаем проверку выполнения равенства i⊕j=k и обновление максимума, которое ориентируется на сумму i-того и j-того элементов. Не забудем и про вывод ответа, в результате получив следующий код:

n, k = map(int, input().split())
a = list(map(int, input().split()))
mx = -1
for i in range(2 ** n):
    for j in range(2 ** n):
        if i ^ j == k and a[i] + a[j] > mx:
            mx = a[i] + a[j]
print(mx)

Обратите внимание, что за выполнение операции побитового исключающего ИЛИ в языке Python отвечает оператор ^.

Из-за вложенного цикла данный код будет работать довольно медленно, из-за чего он превысит ограничение по времени выполнения на второй подзадаче. В результате, за этот код мы получим 40 баллов.

100 баллов ✓✓

Как же оптимизировать алгоритм и не напороться на ограничение по времени выполнения? Для этого нам нужно избавиться от вложенного цикла из решения на 40 баллов, так как он сильно замедляет время работы нашей программы.

Сделать это можно, опираясь на интересное свойство операции xor. Это свойство гласит о том, что если выполняется равенство i⊕j=k, то тогда j=i⊕k (в этом можно убедиться и самостоятельно, подобрав разные числа и сравнив значения чисел i, j, k). Таким образом, зная индекс i, мы можем найти подходящий к нему индекс j при помощи числа k (т. к. j=i⊕k). Это означает, что мы можем перебирать только индексы i и уже по ним находить индексы j и проводить поиск максимальной суммы.

Вот так мы и должны заменить вложенный цикл на линейный, что позволит нам обойти ограничение по времени выполнения нашей программы. Теперь осталось лишь написать наш "победный" код. Сделать это очень просто, для начала создадим линейный цикл, перебирающий индексы i:

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(2 ** n):
    pass

Мы перебираем индексы именно до 2ⁿ, так как длина списка по условию задачи равна 2ⁿ. Ничего не делающий оператор-заглушка pass оставлен для удобства, он показывает место, где мы ещё не успели дописать код.

Далее нам нужно сделать поиск максимума, это тоже не так трудно. Перед началом цикла создадим переменную, в которую будем записывать максимум, а в самом цикле будем находить индекс j по формуле j=i⊕k и обновлять максимум, ориентируясь на сумму i-того и j-того элементов. Не забудем и про вывод ответа, в результате получив следующий конечный код:

n, k = map(int, input().split())
a = list(map(int, input().split()))
mx = -1
for i in range(2 ** n):
    j = i ^ k
    if a[i] + a[j] > mx:
        mx = a[i] + a[j]

Обратите внимание, что за выполнение операции побитового исключающего ИЛИ в языке Python отвечает оператор ^.

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

Мой комментарий

Вот таким вот получился разбор, очень надеюсь, что вам он понравился. Если так и есть, то обязательно голосуйте плюсиком за этот разбор, мне будет очень приятно :)

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

Всем удачи! :D

Примечания к задаче

Розы — несложная задача, которая встречалась на Муниципальном этапе олимпиады по программированию в 2021 году в городе Казань

Условия к задаче

Данные

Имя входного файла: Стандартный ввод / input.txt

Имя выходного файла: Стандартный вывод / output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

Условие

Известный садовод Гладиолус Ромашкин выращивает розы у себя в теплице, а потом продаёт их в городе на цветочном рынке. Перед походом на рынок Ромашкин пересчитал лепестки у каждой розы и решил, что розы с k лепестками он будет продавать за r рублей. Если лепестков у розы меньше k, то отсутствие каждого из лепестков уменьшит цену на 1 рубль. Если же лепестков больше k, то такую розу Ромашкин будет продавать в 2 раза дороже, то есть за 2r рублей. К концу дня Гладиолус Ромашкин продал все n роз и хочет подсчитать свою выручку. Ваша задача — помочь ему в этом.

Формат входных данных

Первая строка содержит три целых числа k, r и n (1 ≤ k ≤ 100; k ≤ r ≤ 10⁵; 1 ≤ n ≤ 10⁵).

Во второй строке записано n целых чисел aᵢ — количество лепестков каждой из роз (1 ≤ aᵢ ≤ 1000).

Формат выходных данных

Запишите одно число — выручку Гладиолуса Ромашкина.

Пример

Стандартный ввод:

10 20 3

10 5 15

Стандартный вывод:

75

Замечание

В примере Ромашкин сможет продать первую розу за 20 рублей, вторую — за 15 рублей, а третью — за 2 · 20 = 40 рублей. Общая выручка составит 20 + 15 + 40 = 75 рублей.

Объяснение задачи

Ввод

Первым делом, мы должны прописать правильный ввод данных.

Реализовать ввод нескольких значений в одну строку можно при помощи встроенной функции map:

k, r, n = map(int, input().split())

Таким образом, мы присвоили переменным k, r, n значения, введя их в одну строку Тоже самое мы делаем с набором количеств лепестков роз. При этом, мы преобразуем его в список при помощи функции list:

roses = list(map(int, input().split()))

Теперь, в переменной roses хранится список, состоящий из количеств лепестков на каждой розе. Получаем код:

k, r, n = map(int, input().split())
roses = list(map(int, input().split()))

Алгоритм решения

Как же поступать дальше? На самом деле, всё очень просто.

Мы просто пробегаемся по списку roses, сравнивая каждое его значение со значением переменной k.

Итак, для начала давайте заведём переменную ans, к которой мы будем прибавлять цену каждой розы, пока они не закончатся и мы не получим конечный ответ. Изначально она равна нулю:

ans = 0

Теперь с помощью цикла for пробегаемся по списку roses, сравнивая его значения со значением переменной k, и в зависимости от результата прибавляем к переменной ans цену, указанную в условии для этого результата.

for i in roses:
    if i < k:
        ans += r - (k - i) #Вычитаем из r кол-во недостающих до k лепестков и прибавляем это к ans
    elif i == k:
        ans += r #Прибавляем r к ans
    else:
        ans += 2 * r #Прибавляем 2r к ans

После этого просто выводим полученный ответ:

print(ans)

Получаем конечный код:

k, r, n = map(int, input().split())
roses = list(map(int, input().split()))
ans = 0
for i in roses:
    if i < k:
        ans += r - (k - i)
    elif i == k:
        ans += r
    else:
        ans += 2 * r
print(ans)

Вот и всё, алгоритм придуман, код готов, именно таким и является решение данной задачи

Мой комментарий

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

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

Всем удачи! :D

Приветствую всех, меня зовут Александров Николай и сейчас вы читаете мой блог.

В своём блоге я буду публиковать разборы различных задач по программированию на языке Python ;)

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

Учтите, что я сам только учусь и могу не знать решения некоторых сложных задач, иногда ошибаться в оптимизации их кода, давать не самый лучший вариант их решения и т. п., поэтому я буду очень рад услышать вашу критику в комментариях, дабы самому развиваться дальше! Не стесняйтесь указывать на ошибки и предлагать свои решения задач! Будем развиваться вместе!