|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
24.08.2021, 07:52 | #1 |
Новичок
Джуниор
Регистрация: 24.08.2021
Сообщений: 1
|
Петр Васильевич, директор ОАО "Рога и рога", собирается раздать премию всем менеджерам компании, он добрый и честный человек, поэтому хочет соблюсти следующие условия:
На java пожалуйста.
Петр Васильевич, директор ОАО "Рога и рога", собирается раздать премию всем менеджерам компании, он добрый и честный человек, поэтому хочет соблюсти следующие условия: премия должна быть равной для всех менеджеров должна быть максимально возможной и целой должна быть выдана одной транзакцией с одного счета для каждого менеджера, без использования нескольких счетов для отправки одной премии У Петра Васильевича открыто N корпоративных счетов, на которых лежат разные суммы денег Cn, а в компании работает M менеджеров. Необходимо выяснить максимальный размер премии, которую можно отправить с учетом условий. Если денег на счетах компании не хватит на то, чтобы выдать премию хотя бы по 1 у.е. - значит премии не будет, и нужно вывести 0. Входные данные (поступают в стандартный поток ввода) Первая строка - целые числа N и M через пробел (1≤N≤100 000, 1≤M≤100 000) Далее N строк, на каждой из которых одно целое число Cn (0≤Cn≤100 000 000) Проверка входных данных и обработка неправильных данных на входе не нужна, тестовые данные для проверки гарантированно подходят под описание выше Выходные данные (ожидаются в стандартном потоке вывода) Одно целое число, максимально возможная премия Пример 1 Ввод: 3 6 453 220 601 Вывод: 200 Пример 2 Ввод: 2 100 99 1 Вывод: 1 Пример 3 Ввод: 2 100 98 1 Вывод: 0 Примечания по оформлению решения Возможно использование только стандартных библиотек языков, установки и использование дополнительных библиотек невозможны. При отправке решений на Java необходимо назвать исполняемый класс Main. В решении не нужно указывать пакет. Работа со стандартными потока ввода и вывода Для JS можно использовать readline и console.log: const readline = require('readline'); const rl = readline.createInterface(process.st din, process.stdout); rl.on('line', (line) => { // Введенная строка в переменной line, тут можно написать решение и вывести его с помощью console.log console.log(String(result)); rl.close(); return; }).on('close', () => process.exit(0)); в Python можно использовать встроенные функции input() и print(): line = input() ... print(result) в Java можно использовать java.util.Scanner и System.out.println: Scanner in = new Scanner(System.in); String line = in.nextLine(); ... System.out.println(result); |
24.08.2021, 09:14 | #2 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,291
|
А где же ваши наработки? Что не получается? Если говорить об алгоритме решения, то ничего лучше бинарного поиска размера премии в голову на первый взгляд не приходит. Найти сумму на всех счетах и разделить нацело на количество менеджеров - это будет максимально возможная премия Pmax (без учета одной транзакции на премию). Если она 0 ye, то сразу ответ 0. Иначе, минимально возможная премия Pmin - 1 ye. Проверить Pmax на транзакции (посчитать, сколько раз можно заплатить такую премию с каждого счета и сравнить количество раз с количеством менеджеров). Если Pmax невозможна, то начинать бинарный поиск, выбрав размер премии посередине.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
|
29.08.2021, 19:13 | #3 | |
Регистрация: 17.01.2018
Сообщений: 5
|
Цитата:
Код:
|
|
29.08.2021, 20:42 | #4 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,291
|
Так, вроде, работает (не нашел пример, на котором бы не совпало с "наивным" алгоритмом).
Код:
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
Последний раз редактировалось BDA; 29.08.2021 в 20:44. |
01.09.2021, 20:08 | #5 |
Регистрация: 17.01.2018
Сообщений: 5
|
BDA, У вас весьма оригинальный выход из цикла, очень понравился. А не скажете, зачем вы присвоили down = 1, а не down = 0?
В плане решения задачи, правда, один хрен выдает ошибку, неправильный, якобы, ответ. И я не знаю при каких вводных данных, чтобы хотя-бы понять в каком месте косяк На другом форуме еще предположили, что, мол, высокая сложность, делать цикл в цикле, но по другому я не умею. Тем более, мне кажется, что при высокой сложности бы выдало не "Неправильный ответ", а "Превышение лимита времени выполнения", как мне выдавало, когда я снижал переменную prem просто декрементом в цикле, после сравнения с count1 Последний раз редактировалось stalkerybr; 01.09.2021 в 20:12. |
01.09.2021, 20:17 | #6 |
Регистрация: 17.01.2018
Сообщений: 5
|
Вот скриншот с пояснениями ошибок
|
01.09.2021, 20:53 | #7 | |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,291
|
Да, вроде, стандартный для бинарного поиска (идти до сужения границ).
Да решил хранить в down минимально возможную премию (а нулевая премия отброшена раньше), а в up "невозможную" премию. Цитата:
Согласен, что дело не сложности, а в чем-то другом. Попробуйте заменить int на long (только сейчас заметил, что сумма всех счетов не влезает в int).
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
|
|
01.09.2021, 23:07 | #8 |
Регистрация: 17.01.2018
Сообщений: 5
|
BDA,
В общем, действительно, необходимо было использовать тип пошире int. Даже попробовал в блокноте накопировать 100000 строк по 100000000 как указано в условии, и загнать эти цифры в ввод программы. С типом int ответ был 13161, тогда как с типом long преобразился до 100000000, как и должно быть. Ответ на сайте приняли благополучно. Огромная Вам благодарность! Выставили новую задачу, посложнее Последний раз редактировалось stalkerybr; 01.09.2021 в 23:18. |
03.09.2021, 09:21 | #9 |
Новичок
Джуниор
Регистрация: 03.09.2021
Сообщений: 1
|
Всем привет!
Вот мой вариант кода: Код:
Насколько я понимаю сложность поиска тут O(n^2), и видимо надо эту сложность как-то снизить... Подскажите пожалуйста в каком направлении думать? |
03.09.2021, 12:37 | #10 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,291
|
rustamych, бинарный поиск + long переменные.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
всем добрый !!день помогите пожайлуста решить задачку | лЮСИК007 | Паскаль, Turbo Pascal, PascalABC.NET | 2 | 07.10.2016 17:34 |
соблюсти условия | eikhner | Microsoft Office Excel | 12 | 24.09.2012 00:08 |
Ищу работу: руководитель проектов, директор департамента, технический директор. | GAG123123 | Фриланс | 1 | 03.12.2008 01:08 |
Всем добрый день, прошу помощи :) | Brian Lee Jones | Фриланс | 4 | 19.06.2008 19:18 |