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

Question 1

Задача Задача №2011798

А

Аноним

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

А

Аноним 25 октября 2024 11:10

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

Answer

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

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

Считать данные: Первое, что нужно сделать, это считать входные данные — длины палочек и их объем. Используйте массив для хранения количества палочек каждой длины.
Распил палочек:
- Если длина палочки четная, просто разделите её пополам и увеличьте счетчик для полученной длины.
- Если длина палочки нечетная, округлите деление на два вниз и вверх, и добавьте полученные длины в соответствующие счетчики.
Подсчет палочек: На любом этапе, так как мы распиливаем палочки, важно сохранять текущий счетчик всех возможных размеров палочек, чтобы в конце определить, сколько палочек каждого размера у нас есть.
Определение результата: В конце нужно найти максимальное количество палочек одного размера. Если таких размеров несколько, выбираем наименьший.

Пример реализации:

Вот пример на Python, который описывает решение:

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

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

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

# Обработка палочек
for i in range(1, n + 1):
    if sticks[i] > 0:
        # количество палочек длины i
        for _ in range(sticks[i]):
            length = i
            while length > 0:
                if length % 2 == 0:
                    count[length // 2] = count.get(length // 2, 0) + 2
                    break
                else:
                    count[length // 2] = count.get(length // 2, 0) + 1
                    count[length // 2 + 1] = count.get(length // 2 + 1, 0) + 1
                    break
                length //= 2

# Нахождение максимального количества палочек одного размера
max_count = 0
max_length = float('inf')

for length, total in count.items():
    if total > max_count or (total == max_count and length < max_length):
        max_count = total
        max_length = length

print(max_count)
print(max_length)

Пояснение к коду:

Программа начинает с ввода n — самой длинной палочки.
Затем она инициализирует массив sticks, который хранит количество палочек каждой длины.
При помощи вложенного цикла программа распиливает палочки, при этом увеличивая соответствующие значения в словаре count.
В конце она определяет, какой размер палочек встречается в наибольшем количестве и наименьший среди размеров, имеющих максимальное количество.

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

Question 2

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

Answer

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