Задача про разделение апельсинов

05.04.2024, 23:09. Показов 884. Ответов 0

Метки python, алгоритм, олимпиадная задача, олимпиадный python (Все метки)

Студворк — интернет-сервис помощи студентам

Ограничение времени - 1 секунда
Ограничение памяти - 256Mb

Фермер Джон собрал $https://www.cyberforum.ru/cgi-bin/latex.cgi?n$ апельсинов со своей фермы, их массы равны $https://www.cyberforum.ru/cgi-bin/latex.cgi?m_{1},\ldots,m_{n}$ . К нему пришло $https://www.cyberforum.ru/cgi-bin/latex.cgi?k$ гостей, которых он решил угостить собранными апельсинами. Чтобы никто не обиделся, каждому должна достаться одинаковая масса апельсинов. К сожалению, это не всегда возможно, если не резать апельсины. Каждый апельсин можно разрезать на произвольное количество кусков с произвольными массами.

От вас требуется разрезать некоторые апельсины так (каждый апельсин можно разрезать ноль или несколько раз), чтобы их удалось разделить между гостями.

Формат ввода
В первой строке указаны два числа $https://www.cyberforum.ru/cgi-bin/latex.cgi?n$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?k$ ( $https://www.cyberforum.ru/cgi-bin/latex.cgi?n,k \le 20$ ) -- количество апельсинов и количество гостей.

Во второй строке указаны числа $https://www.cyberforum.ru/cgi-bin/latex.cgi?m_1,\ldots,m_n$ ( $https://www.cyberforum.ru/cgi-bin/latex.cgi?1 \le m_i \le 10^7$ ) -- массы апельсинов.

Формат вывода
Выведите единственное число — минимальное число разрезов.

Примеры:

Ввод
Code
1 2
1 3 1
Вывод
Code
1
2
Ввод
Code
1 2
2 3 2 1
Вывод
Code
1
1

IT_Exp

Эксперт

34794 / 4073 / 2104

Регистрация: 17.06.2006

Сообщений: 32,602

Блог

05.04.2024, 23:09

Ответы с готовыми решениями:

Задача про разделение конфет и коммунизм
Ограничение времени - 1 секунда Ограничение памяти - 256Mb Четыре подруги приехали на всероссийскую олимпиаду по истории, и там им...

Что почитать про obb, aab и вообще про разделение проекта на несколько файлов?
В общем проковырявшись кучу времени получил много вопросов, поиск ответов на которые я не знаю как даже искать, может кто-то вкратце...

задача про самолет (аналог задачи про рюкзак)
Мне хотелось бы, чтобы вы посоветовали и помогли мне, как правильно решить задачу. В самолет требуется погрузить n видов предметов,...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

BasicMan

Эксперт

29316 / 5623 / 2384

Регистрация: 17.02.2009

Сообщений: 30,364

Блог

05.04.2024, 23:09

Помогаю со студенческими работами здесь

Задача про взлом кода из книги Эрика Фримена про основы javascript в конце 5 главы.
читаю книгу Эрика Фримена про основы javascript.В конце 5 главы есть задачка про взлом кода.Никак не могу понять как ее решить.НЕ понимаю...

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

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

Деление апельсинов на дольки
Добрый вечер, решаю такую задачку: Катя решила пригласить к себе в гости n друзей. Так как ее друзья очень любят фрукты, то в качестве...

Определить, кто сколько апельсинов съел
Вчера Настина мама купила N апельсинов. Сегодня утром их уже не было. Настя точно помнит, что съела апельсинов на F меньше, чем папа, и на...

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Первый деплой lagorue 16.01.2026 Не спеша развернул своё 1ое приложение в kubernetes. А дальше мне интересно создать 1фронтэнд приложения и 2 бэкэнд приложения развернуть 2 деплоя в кубере получится 2 сервиса и что-бы они. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит: токи, напряжения и их 1 и 2 производные при t = 0;. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .

Наверх