Ограничение по времени: 1 1 секунда Ограничение по памяти: 256 256 мегабайт Городки — — старинная русская народная спортивная игра. В ней необходимо «выбивать» метанием биты различные деревянные фигуры, находящиеся на некотором расстоянии от игрока. Обычно участники самостоятельно приобретают комплекты для игры в спортивных магазинах, однако есть Очень Богатые Люди, готовые выложить за набор для игры из дорогих сортов древесины круглую сумму. Начинающий предприниматель Тимофей заинтересовался этим перспективным бизнесом. Для организации официальных соревнований требуется изготовить для участников одинаковые биты, а для этого сначала необходимо где‑то раздобыть как можно больше одинаковых деревянных палочек. В распоряжении Тимофея есть палочки‑заготовки из дорогого красного дерева в форме цилиндров одинакового радиуса, но самой разной длины, из которых он и собирается изготовить биты. Если длина палочки является чётным числом d � , Тимофей может распилить её пополам и получить две палочки вдвое меньшей длины d2 � 2 . Если же длина палочки является нечётным числом, Тимофей может распилить её на две части, как можно меньше отличающиеся друг от друга: ⌊d2⌋ ⌊ � 2 ⌋ (d � пополам, округлённое вниз до целой части) и ⌈d2⌉ ⌈ � 2 ⌉ (d � пополам, округлённое вверх до целой части). Распиливать уже распиленные ранее палочки Тимофею лень, и он переходит к следующей заготовке. Задача Тимофея — — получить наибольшее количество бит какого‑нибудь одного размера. Если таких размеров несколько, Тимофей выберет для организации соревнований наименьший. Формат входных данных В первой строке входных данных записано одно натуральное число: n � (1≤n≤105 1 ≤ � ≤ 10 5 ) — — длина самой длинной заготовки. В следующих n � строках записано по одному натуральному числу di � � (0≤di≤109 0 ≤ � � ≤ 10 9 , dn≠0 � � ≠ 0 ) — — количество палочек длины i−1 � − 1 . Так, во второй строке записано количество палочек длины 1 1 , в третьей — — количество палочек длины 2 2 и так далее. В последней строке записано количество палочек длины n � . Обратите внимание, что при заданных ограничениях для хранения входных данных и ответа может понадобиться 64 64 ‑битный тип данных, например, long long в C++, int64 64 в Free Pascal, long в Java. Формат выходных данных Выведите в двух строках два натуральных числа — — наибольшее количество получившихся палочек одного размера и сам этот размер. Система оценки Решения, верно работающие при n≤3 � ≤ 3 , получат не менее 30 30 баллов. Решения, верно работающие при n≤1000 � ≤ 1000 , получат не менее 70 70 баллов. Замечание У Тимофея есть несколько палочек, самая длинная имеет длину 5 5 . Более точно: Нет палочек длины 1 1 ; Одна палочка длины 2 2 ; Нет палочек длины 3 3 ; Одна палочка длины 4 4 ; Две палочки длины 5 5 . Тимофей распилит пополам палочку длины 4 4 и получит две палочки длины 2 2 . Также он распилит обе палочки длины 5 5 и получит две палочки длины 2 2 и две палочки длины 3 3 . Вместе с имеющейся у него одной исходной палочкой длины 2 2 (её Тимофей пилить не будет) в его распоряжении окажется пять одинаковых палочек длины 2 2 . Это наилучший результат, который может получить Тимофей (наибольшее количество палочек длины 1 1 , которое можно получить из исходного набора, равно двум; палочек длины 3 3 — — двум; палочек длины 4 4 — — одному; палочек длины 5 5 — — двум).

Question 1

Задача Задача №2012735

А

Аноним

25 октября 2024 13:53 · публичный вопрос

А

Аноним 25 октября 2024 13:53

Ограничение по времени: 1 1 секунда Ограничение по памяти: 256 256 мегабайт Городки — — старинная русская народная спортивная игра. В ней необходимо «выбивать» метанием биты различные деревянные фигуры, находящиеся на некотором расстоянии от игрока. Обычно участники самостоятельно приобретают комплекты для игры в спортивных магазинах, однако есть Очень Богатые Люди, готовые выложить за набор для игры из дорогих сортов древесины круглую сумму. Начинающий предприниматель Тимофей заинтересовался этим перспективным бизнесом. Для организации официальных соревнований требуется изготовить для участников одинаковые биты, а для этого сначала необходимо где‑то раздобыть как можно больше одинаковых деревянных палочек. В распоряжении Тимофея есть палочки‑заготовки из дорогого красного дерева в форме цилиндров одинакового радиуса, но самой разной длины, из которых он и собирается изготовить биты. Если длина палочки является чётным числом d � , Тимофей может распилить её пополам и получить две палочки вдвое меньшей длины d2 � 2 . Если же длина палочки является нечётным числом, Тимофей может распилить её на две части, как можно меньше отличающиеся друг от друга: ⌊d2⌋ ⌊ � 2 ⌋ (d � пополам, округлённое вниз до целой части) и ⌈d2⌉ ⌈ � 2 ⌉ (d � пополам, округлённое вверх до целой части). Распиливать уже распиленные ранее палочки Тимофею лень, и он переходит к следующей заготовке. Задача Тимофея — — получить наибольшее количество бит какого‑нибудь одного размера. Если таких размеров несколько, Тимофей выберет для организации соревнований наименьший. Формат входных данных В первой строке входных данных записано одно натуральное число: n � (1≤n≤105 1 ≤ � ≤ 10 5 ) — — длина самой длинной заготовки. В следующих n � строках записано по одному натуральному числу di � � (0≤di≤109 0 ≤ � � ≤ 10 9 , dn≠0 � � ≠ 0 ) — — количество палочек длины i−1 � − 1 . Так, во второй строке записано количество палочек длины 1 1 , в третьей — — количество палочек длины 2 2 и так далее. В последней строке записано количество палочек длины n � . Обратите внимание, что при заданных ограничениях для хранения входных данных и ответа может понадобиться 64 64 ‑битный тип данных, например, long long в C++, int64 64 в Free Pascal, long в Java. Формат выходных данных Выведите в двух строках два натуральных числа — — наибольшее количество получившихся палочек одного размера и сам этот размер. Система оценки Решения, верно работающие при n≤3 � ≤ 3 , получат не менее 30 30 баллов. Решения, верно работающие при n≤1000 � ≤ 1000 , получат не менее 70 70 баллов. Замечание У Тимофея есть несколько палочек, самая длинная имеет длину 5 5 . Более точно: Нет палочек длины 1 1 ; Одна палочка длины 2 2 ; Нет палочек длины 3 3 ; Одна палочка длины 4 4 ; Две палочки длины 5 5 . Тимофей распилит пополам палочку длины 4 4 и получит две палочки длины 2 2 . Также он распилит обе палочки длины 5 5 и получит две палочки длины 2 2 и две палочки длины 3 3 . Вместе с имеющейся у него одной исходной палочкой длины 2 2 (её Тимофей пилить не будет) в его распоряжении окажется пять одинаковых палочек длины 2 2 . Это наилучший результат, который может получить Тимофей (наибольшее количество палочек длины 1 1 , которое можно получить из исходного набора, равно двум; палочек длины 3 3 — — двум; палочек длины 4 4 — — одному; палочек длины 5 5 — — двум).

Answer

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

Давайте рассмотрим алгоритм:

Инициализация данных:
- Создать массив для хранения количества палочек каждого размера, где индекс будет представлять размер палочки.
Обработка входных данных:
- Прочитать длины палочек и их количества из входных данных.
- Сохранить данные в структуре, например, в массиве.
Распиловка палочек:
- Перебрать каждую доступную длину палочек и для каждой длины проверить, чётная она или нечётная.
- Если палочка чётная: увеличить количество палочек длиной d/2 на 2.
- Если палочка нечётная: увеличить количество палочек длиной ⌊d/2⌋ и ⌈d/2⌉ на 1.
Подсчёт максимальных палочек одного размера:
- Перебрать массив с количеством палочек и определить максимальное значение.
- Запомнить размер, соответствующий максимальному количеству.
Вывод результата:
- Вывести максимальное количество палочек одного размера и сам размер.

Пример реализации данного алгоритма на Python:

n = int(input())
count = [0] * (n + 1)

for i in range(1, n + 1):
    di = int(input())
    count[i] += di

# Создаем словарь для хранения палочек
sticks = {}

for length in range(1, n + 1):
    if count[length] > 0:  # Если есть палочки этой длины
        if length % 2 == 0:  # Чётная длина
            length_half = length // 2
            if length_half in sticks:
                sticks[length_half] += count[length] * 2
            else:
                sticks[length_half] = count[length] * 2
        else:  # Нечётная длина
            floor_half = length // 2
            ceil_half = (length // 2) + 1
            if floor_half in sticks:
                sticks[floor_half] += count[length]
            else:
                sticks[floor_half] = count[length]

            if ceil_half in sticks:
                sticks[ceil_half] += count[length]
            else:
                sticks[ceil_half] = count[length]

# Поиск максимального количества и размера
max_count = 0
best_length = float('inf')

for length, cnt in sticks.items():
    if cnt > max_count or (cnt == max_count and length < best_length):
        max_count = cnt
        best_length = length

print(max_count)
print(best_length)

Объяснение кода:

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

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

Question 2

Ограничение по времени: 1 1 секунда Ограничение по памяти: 256 256 мегабайт Городки — — старинная русская народная спортивная игра. В ней необходимо «выбивать» метанием биты различные деревянные фигуры, находящиеся на некотором расстоянии от игрока. Обычно участники самостоятельно приобретают комплекты для игры в спортивных магазинах, однако есть Очень Богатые Люди, готовые выложить за набор для игры из дорогих сортов древесины круглую сумму. Начинающий предприниматель Тимофей заинтересовался этим перспективным бизнесом. Для организации официальных соревнований требуется изготовить для участников одинаковые биты, а для этого сначала необходимо где‑то раздобыть как можно больше одинаковых деревянных палочек. В распоряжении Тимофея есть палочки‑заготовки из дорогого красного дерева в форме цилиндров одинакового радиуса, но самой разной длины, из которых он и собирается изготовить биты. Если длина палочки является чётным числом d � , Тимофей может распилить её пополам и получить две палочки вдвое меньшей длины d2 � 2 . Если же длина палочки является нечётным числом, Тимофей может распилить её на две части, как можно меньше отличающиеся друг от друга: ⌊d2⌋ ⌊ � 2 ⌋ (d � пополам, округлённое вниз до целой части) и ⌈d2⌉ ⌈ � 2 ⌉ (d � пополам, округлённое вверх до целой части). Распиливать уже распиленные ранее палочки Тимофею лень, и он переходит к следующей заготовке. Задача Тимофея — — получить наибольшее количество бит какого‑нибудь одного размера. Если таких размеров несколько, Тимофей выберет для организации соревнований наименьший. Формат входных данных В первой строке входных данных записано одно натуральное число: n � (1≤n≤105 1 ≤ � ≤ 10 5 ) — — длина самой длинной заготовки. В следующих n � строках записано по одному натуральному числу di � � (0≤di≤109 0 ≤ � � ≤ 10 9 , dn≠0 � � ≠ 0 ) — — количество палочек длины i−1 � − 1 . Так, во второй строке записано количество палочек длины 1 1 , в третьей — — количество палочек длины 2 2 и так далее. В последней строке записано количество палочек длины n � . Обратите внимание, что при заданных ограничениях для хранения входных данных и ответа может понадобиться 64 64 ‑битный тип данных, например, long long в C++, int64 64 в Free Pascal, long в Java. Формат выходных данных Выведите в двух строках два натуральных числа — — наибольшее количество получившихся палочек одного размера и сам этот размер. Система оценки Решения, верно работающие при n≤3 � ≤ 3 , получат не менее 30 30 баллов. Решения, верно работающие при n≤1000 � ≤ 1000 , получат не менее 70 70 баллов. Замечание У Тимофея есть несколько палочек, самая длинная имеет длину 5 5 . Более точно: Нет палочек длины 1 1 ; Одна палочка длины 2 2 ; Нет палочек длины 3 3 ; Одна палочка длины 4 4 ; Две палочки длины 5 5 . Тимофей распилит пополам палочку длины 4 4 и получит две палочки длины 2 2 . Также он распилит обе палочки длины 5 5 и получит две палочки длины 2 2 и две палочки длины 3 3 . Вместе с имеющейся у него одной исходной палочкой длины 2 2 (её Тимофей пилить не будет) в его распоряжении окажется пять одинаковых палочек длины 2 2 . Это наилучший результат, который может получить Тимофей (наибольшее количество палочек длины 1 1 , которое можно получить из исходного набора, равно двум; палочек длины 3 3 — — двум; палочек длины 4 4 — — одному; палочек длины 5 5 — — двум).

Answer

Для решения задачи, которую поставил Тимофей, необходимо учесть, как распиливаются палочки в зависимости от их длины — чётные делятся пополам, а нечётные распиливаются на две части, максимально близкие по длине. После распиловки нужно подсчитать количество получившихся палочек каждого размера и выбрать размер с наибольшим количеством. Если таких размеров несколько, выбираем наименьший. Давайте рассмотрим алгоритм: 1. **Инициализация данных**: - Создать массив для хранения количества палочек каждого размера, где индекс будет представлять размер палочки. 2. **Обработка входных данных**: - Прочитать длины палочек и их количества из входных данных. - Сохранить данные в структуре, например, в массиве. 3. **Распиловка палочек**: - Перебрать каждую доступную длину палочек и для каждой длины проверить, чётная она или нечётная. - Если палочка чётная: увеличить количество палочек длиной `d/2` на 2. - Если палочка нечётная: увеличить количество палочек длиной `⌊d/2⌋` и `⌈d/2⌉` на 1. 4. **Подсчёт максимальных палочек одного размера**: - Перебрать массив с количеством палочек и определить максимальное значение. - Запомнить размер, соответствующий максимальному количеству. 5. **Вывод результата**: - Вывести максимальное количество палочек одного размера и сам размер. Пример реализации данного алгоритма на Python: ```python n = int(input()) count = [0] * (n + 1) for i in range(1, n + 1): di = int(input()) count[i] += di # Создаем словарь для хранения палочек sticks = {} for length in range(1, n + 1): if count[length] > 0: # Если есть палочки этой длины if length % 2 == 0: # Чётная длина length_half = length // 2 if length_half in sticks: sticks[length_half] += count[length] * 2 else: sticks[length_half] = count[length] * 2 else: # Нечётная длина floor_half = length // 2 ceil_half = (length // 2) + 1 if floor_half in sticks: sticks[floor_half] += count[length] else: sticks[floor_half] = count[length] if ceil_half in sticks: sticks[ceil_half] += count[length] else: sticks[ceil_half] = count[length] # Поиск максимального количества и размера max_count = 0 best_length = float('inf') for length, cnt in sticks.items(): if cnt > max_count or (cnt == max_count and length < best_length): max_count = cnt best_length = length print(max_count) print(best_length) ``` Объяснение кода: - Мы начинаем с чтения количества палочек и заполняем массив с количеством палочек каждого размера. - Затем распиливаем палочки и обновляем их количество в словаре `sticks`. - В конце, анализируем словарь, чтобы найти максимальное количество палочек и запоминаем их размер. Таким образом, Тимофей сможет получить максимальное количество бит одного размера для организации соревнований.