Петр Васильевич, директор ОАО "Рога и рога", собирается раздать премию всем менеджерам компании, он добрый и честный человек, поэтому хочет соблюсти следующие условия:

[Андрей К@]

На 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);

[BDA]

А где же ваши наработки? Что не получается? Если говорить об алгоритме решения, то ничего лучше бинарного поиска размера премии в голову на первый взгляд не приходит. Найти сумму на всех счетах и разделить нацело на количество менеджеров - это будет максимально возможная премия Pmax (без учета одной транзакции на премию). Если она 0 ye, то сразу ответ 0. Иначе, минимально возможная премия Pmin - 1 ye. Проверить Pmax на транзакции (посчитать, сколько раз можно заплатить такую премию с каждого счета и сравнить количество раз с количеством менеджеров). Если Pmax невозможна, то начинать бинарный поиск, выбрав размер премии посередине.

[stalkerybr]

Сообщение от BDA

А где же ваши наработки? Что не получается? Если говорить об алгоритме решения, то ничего лучше бинарного поиска размера премии в голову на первый взгляд не приходит. Найти сумму на всех счетах и разделить нацело на количество менеджеров - это будет максимально возможная премия Pmax (без учета одной транзакции на премию). Если она 0 ye, то сразу ответ 0. Иначе, минимально возможная премия Pmin - 1 ye. Проверить Pmax на транзакции (посчитать, сколько раз можно заплатить такую премию с каждого счета и сравнить количество раз с количеством менеджеров). Если Pmax невозможна, то начинать бинарный поиск, выбрав размер премии посередине.

У меня есть пример решения, однако при проверке все-равно указывает, что имеется ошибка. Пока ее не нашел

package package1;

import java.util.Scanner;

public class Solution_012_task1 {

    public static void main(String[] args) {

        Scanner console = new Scanner(System.in);
        int N = console.nextInt();
        int M = console.nextInt();

        int[] arrayN = new int[N];
        int sum = 0;

        for(int i = 0; i < arrayN.length; i++)
        {
            arrayN[i] = console.nextInt();
            sum += arrayN[i];
        }

        int up, down = 0, prem_res = 0, prem = sum / M;
        up = prem;

        if(prem == 0)
        {
            System.out.println(prem);
        }
        else
        {
            int count1 = 0;
            for(int i1 = 0; i1 < 65; i1++)
            {
                if(i1 == 64)
                {
                    System.out.println(prem_res);
                }
                count1 = 0;
                for(int i = 0; i < arrayN.length; i++)
                {
                    count1 += (arrayN[i] / prem);
                }
                if(count1 == M)
                {
                    System.out.println(prem);
                    break;
                }
                if(count1 < M)
                {
                    up = prem;
                    prem -= (up - down) / 2;
                    continue;
                }
                if(count1 > M)
                {
                    down = prem;
                    prem += (up - down) / 2;
                    prem_res = down;
                    continue;
                }
            }
        }
    }
}

[BDA]

Так, вроде, работает (не нашел пример, на котором бы не совпало с "наивным" алгоритмом).

        int up, down = 1, prem = sum / M;
        up = prem + 1;

        if (prem == 0)
        {
            System.out.println(prem);
        }
        else
        {
            while (down + 1 < up)
            {
                int count1 = 0;
                for (int i = 0; i < arrayN.length; i++)
                {
                    count1 += (arrayN[i] / prem);
                }
                if (count1 < M)
                {
                    up = prem;
                    prem -= (up - down) / 2;
                }
                else
                {
                    down = prem;
                    prem += (up - down) / 2;
                }
            }
            System.out.println(down);
        }

[stalkerybr]

BDA, У вас весьма оригинальный выход из цикла, очень понравился. А не скажете, зачем вы присвоили down = 1, а не down = 0?
В плане решения задачи, правда, один хрен выдает ошибку, неправильный, якобы, ответ. И я не знаю при каких вводных данных, чтобы хотя-бы понять в каком месте косяк
На другом форуме еще предположили, что, мол, высокая сложность, делать цикл в цикле, но по другому я не умею. Тем более, мне кажется, что при высокой сложности бы выдало не "Неправильный ответ", а "Превышение лимита времени выполнения", как мне выдавало, когда я снижал переменную prem просто декрементом в цикле, после сравнения с count1

[stalkerybr]

Вот скриншот с пояснениями ошибок

[BDA]

Сообщение от stalkerybr

весьма оригинальный выход из цикла

Да, вроде, стандартный для бинарного поиска (идти до сужения границ).

Сообщение от stalkerybr

А не скажете, зачем вы присвоили down = 1, а не down = 0?

Да решил хранить в down минимально возможную премию (а нулевая премия отброшена раньше), а в up "невозможную" премию.

Сообщение от stalkerybr

когда я снижал переменную prem просто декрементом в цикле, после сравнения с count1

Вот этот способ и назвал "наивным" алгоритмом.

Сообщение от stalkerybr

Тем более, мне кажется, что при высокой сложности бы выдало не "Неправильный ответ", а "Превышение лимита времени выполнения"

Согласен, что дело не сложности, а в чем-то другом. Попробуйте заменить int на long (только сейчас заметил, что сумма всех счетов не влезает в int).

[stalkerybr]

BDA,
В общем, действительно, необходимо было использовать тип пошире int. Даже попробовал в блокноте накопировать 100000 строк по 100000000 как указано в условии, и загнать эти цифры в ввод программы. С типом int ответ был 13161, тогда как с типом long преобразился до 100000000, как и должно быть.
Ответ на сайте приняли благополучно. Огромная Вам благодарность!
Выставили новую задачу, посложнее

[rustamych]

Всем привет!
Вот мой вариант кода:

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int moneyCashCn, countsN, managersM,
                award = 0,
                counter = 0;
        String scString = reader.readLine();
        String[] scStrings = scString.split(" ");
        countsN = Integer.parseInt(scStrings[0]);
        managersM = Integer.parseInt(scStrings[1]);
        // 1. making array for counts with available cash
        int[] cash = new int[countsN];
        for (int i = 0; i < countsN; i++) {
            moneyCashCn = Integer.parseInt(reader.readLine());
            award += moneyCashCn;
            cash[i] = moneyCashCn;
        }
//        // 2. finding average of all cash to start reduce with in part 3
        award = award / managersM;
//        // 3. let's find the max award for our managers
        while (counter < managersM && award != 0) {
            for (int i = 0; i < cash.length; i++) {
				counter = counter + (cash[i] / award);
			}
		if (counter >= managersM)
		break;
		    else {
		    counter = 0;
		    --award;
		    }
        }
        System.out.println(award);

Но он не проходит, по причине: "Превышение лимита времени выполнения".
Насколько я понимаю сложность поиска тут O(n^2), и видимо надо эту сложность как-то снизить...
Подскажите пожалуйста в каком направлении думать?

[BDA]

rustamych, бинарный поиск + long переменные.