Определить минимальное время за которое гости закончат есть свои блины после перекладывания части блинов

@CyberNinjaProg · Регистрация: 10.03.2019

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

Здравствуйте. Встретилась непонятная задачка на informatics. Условие так себе понятно,а вот как решить совсем не получается. Пожалуйста помогите.

Условие:
Мы все знаем, что начавшаяся зима скоро закончится, и на праздновании Масленицы все будут есть блины. Об этом и будет наша задача.

N гостей сидят за столом, и перед каждым стоит тарелка с блинами. На тарелке i-го гостя лежит ai блинов. Каждый гость съедает один блин за одну минуту, таким образом, время, когда закончит есть блины последний человек, равно наибольшему значению из ai.

Неожиданно к ним присоединился ещё один человек, и теперь все присутствующие могут переложить часть своих блинов (в том числе могут переложить все свои блины, а могут не перекладывать ни одного блина) вновь пришедшему человеку. Перекладывание блинов происходит одновременно и моментально.

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

Программа получает на вход натуральное число N, не превосходящее 100.000, – первоначальное количество гостей. Следующие N строк содержат натуральные числа ai – количество блинов на тарелке i-го человека. Значения ai даны в порядке не убывания, то есть ai ai+1. Сумма значений всех ai не превосходит 2109.

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

Пояснение к примеру
За столом сидят 4 человека, у них на тарелках 1, 3, 5, 6 блинов. Новому гостю последний гость отдаст 2 блина, а предпоследний – 1 блин, и тогда у всех, включая нового гостя, будет не более 4 блинов.

Примеры
входные данные
4
1
3
5
6
выходные данные
4

@valen10 · 20.03.2019, 12:41

IGPIGP, моделирование?

Способ хорош тем, что он понятен и наиболее близок к тому, как бы поступили реальные люди в такой ситуации. Нереальным его делают безжалостные цифры: на самом деле в оригинальном тексте задания упоминается не 2109, а $https://www.cyberforum.ru/cgi-bin/latex.cgi?2 \cdot 10^9$ блиноединиц.

Не по теме:

Только представьте, какой будет стопка блинов единственного гостя в худшем случае. Если принять толщину блиноединицы в 1мм, полученные 2000км моментально сорвут крышу дома. Несчастный гость соберет все лестницы в округе, чтобы забраться на самый верх и скидывать оттуда по одному блину для опоздавшего. А потом их ждет сытный ужин и неизбежный throw StomachOverflowException xD

Что-то я отвлекся. При таких количествах блиноединиц перекладывать по одной получится долго. IGPIGP, спасибо Вам за подробное описание, теперь стало понятно, как ваша программа решает задачу, и стала понятна причина TLE (превышение времени выполения). А ТС - жирный минус за неточную формулировку задания.

Добавлено через 26 минут
SivaMore, вы немного опоздали: готовые решения у меня закончились несколько дней назад, а новая партия задерживается на неопределённый срок (поставщик оказался ненадёжным). Теперь остаётся ждать, когда CyberNinjaProg поделится с нами своим кодом, или может быть, кто-нибудь другой пожелает решить эту хитрую задачу.

IGPIGP · 20.03.2019, 14:21

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

Несчастный гость соберет все лестницы в округе, чтобы забраться на самый верх и скидывать оттуда по одному блину для опоздавшего.

В задаче крышу блин срывает. Буквально.

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

При таких количествах блиноединиц перекладывать по одной получится долго.

Я не вчитался в момент, каюсь:

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

все присутствующие могут переложить часть своих блинов (в том числе могут переложить все свои блины, а могут не перекладывать ни одного блина) вновь пришедшему человеку. Перекладывание блинов происходит одновременно и моментально.

Зато достаточно наглядно, но теперь ясно что нужно разность пополам делить.

В общем объедятся они. Как пить дать.

@zayats80888 · 20.03.2019, 15:41

CyberNinjaProg, особо не тестил, но можете попробовать:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
using namespace std;
int main()
{
    size_t N;
    cin >> N;
    size_t* arr = new size_t[N];
    for (size_t i(0); i < N; ++i) cin >> arr[i];
    size_t count(N - 1);
    size_t result = 0;
    for (; count > 0 && result < arr[count]; --count) result += arr[count] - arr[count - 1];
    size_t sum = 0;
    for (size_t i(count + 1); i < N; ++i) sum += arr[i];
    result = sum / (N - count);
    if (sum > result*(N - count)) result += 1 + (sum - result * (N - count)) / (N - count);// "(sum - result * (N - count)) / (N - count)" возможно лишнее
    cout << result;
}

@CyberNinjaProg · 20.03.2019, 19:34 **[ТС]**

Спасибо, но не все прошло есть неправильные ответы....

@zayats80888 · 20.03.2019, 20:19

подправил

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
int main()
{
    int N;
    cin >> N;
    int* arr = new int[N];
    for (int i(0); i < N; ++i) cin >> arr[i];
    int count(N - 1);
    int result = 0;
    for (; count >= 0 && result < arr[count]; --count) {
        if (count > 0) result += arr[count] - arr[count - 1];
    }
    int sum = 0;
    for (int i(count + 1); i < N; ++i) sum += arr[i];
    result = sum / (N - count);
    if (sum > result*(N - count)) ++result;
    cout << result;
}

@CyberNinjaProg · 20.03.2019, 20:43 **[ТС]**

ВСЕ прошло. ОГРОМНОЕ ВАМ СПАСИБО!

IGPIGP · 20.03.2019, 23:45

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

ВСЕ прошло. ОГРОМНОЕ ВАМ СПАСИБО!

CyberNinjaProg, а где вы нашли задание и где можно его решение протестировать?

@valen10 · 21.03.2019, 00:01

IGPIGP, тут. Гуглится по слову informatics и началу задания.

IGPIGP · 21.03.2019, 00:41

valen10, спасибо)

@var_gotovets · 13.04.2021, 19:58

А можете эту же задачу на Пейтоне решить, пожалуйста?

Новые блоги и статьи Все статьи Все блоги /
Doom для терминала без стрельбы и монстров. 3D Raycasting на ascii. dcc0 05.07.2026 Попросил нейронную сеть deepai. org написать рейкастинг 3D с библиотекой ncurses для Linux. Чтобы можно было ходить на стрелочки. Чтобы стены были отрисованы символами. Справилась. Первый вариант. . .	Установка статуса документа по условию Maks 05.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "НарядПутевка" разработанного в КА2. Задача: в табличной части "Материалы" документа при записи автоматически устанавливать статус. . .	Сезонность и суточность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .	В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .
интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .	Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .	Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .	rest api anylogic - выполнение модели на своём русском сайте anaschu 02.07.2026 Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .

@CyberNinjaProg -3 / 3 / 0 Регистрация: 10.03.2019 Сообщений: 108

	Определить минимальное время за которое гости закончат есть свои блины после перекладывания части блинов 18.03.2019, 23:08. Показов 11913. Ответов 29 Метки java, python 3.6 (Все метки) Здравствуйте. Встретилась непонятная задачка на informatics. Условие так себе понятно,а вот как решить совсем не получается. Пожалуйста помогите. Условие: Мы все знаем, что начавшаяся зима скоро закончится, и на праздновании Масленицы все будут есть блины. Об этом и будет наша задача. N гостей сидят за столом, и перед каждым стоит тарелка с блинами. На тарелке i-го гостя лежит ai блинов. Каждый гость съедает один блин за одну минуту, таким образом, время, когда закончит есть блины последний человек, равно наибольшему значению из ai. Неожиданно к ним присоединился ещё один человек, и теперь все присутствующие могут переложить часть своих блинов (в том числе могут переложить все свои блины, а могут не перекладывать ни одного блина) вновь пришедшему человеку. Перекладывание блинов происходит одновременно и моментально. Гости хотят переложить блины таким образом, чтобы после перекладывания они съели все блины за минимальное время (которое равно наибольшему числу блинов на тарелках у гостей, включая нового гостя). Определите, за какое наименьшее время гости смогут съесть свои блины после перекладывания. Программа получает на вход натуральное число N, не превосходящее 100.000, – первоначальное количество гостей. Следующие N строк содержат натуральные числа ai – количество блинов на тарелке i-го человека. Значения ai даны в порядке не убывания, то есть ai ai+1. Сумма значений всех ai не превосходит 2109. Программа должна вывести одно целое число – минимальное время, за которое все гости закончат есть свои блины после перекладывания части блинов на тарелку нового гостя. Пояснение к примеру За столом сидят 4 человека, у них на тарелках 1, 3, 5, 6 блинов. Новому гостю последний гость отдаст 2 блина, а предпоследний – 1 блин, и тогда у всех, включая нового гостя, будет не более 4 блинов. Примеры входные данные 4 1 3 5 6 выходные данные 4 0

@valen10 Параллельный Кот 1905 / 827 / 350 Регистрация: 25.03.2016 Сообщений: 2,045
	20.03.2019, 12:41
	IGPIGP, моделирование? Способ хорош тем, что он понятен и наиболее близок к тому, как бы поступили реальные люди в такой ситуации. Нереальным его делают безжалостные цифры: на самом деле в оригинальном тексте задания упоминается не 2109, а $https://www.cyberforum.ru/cgi-bin/latex.cgi?2 \cdot 10^9$ блиноединиц. Не по теме: Только представьте, какой будет стопка блинов единственного гостя в худшем случае. Если принять толщину блиноединицы в 1мм, полученные 2000км моментально сорвут крышу дома. Несчастный гость соберет все лестницы в округе, чтобы забраться на самый верх и скидывать оттуда по одному блину для опоздавшего. А потом их ждет сытный ужин и неизбежный throw StomachOverflowException xD Что-то я отвлекся. При таких количествах блиноединиц перекладывать по одной получится долго. IGPIGP, спасибо Вам за подробное описание, теперь стало понятно, как ваша программа решает задачу, и стала понятна причина TLE (превышение времени выполения). А ТС - жирный минус за неточную формулировку задания. Добавлено через 26 минут SivaMore, вы немного опоздали: готовые решения у меня закончились несколько дней назад, а новая партия задерживается на неопределённый срок (поставщик оказался ненадёжным). Теперь остаётся ждать, когда CyberNinjaProg поделится с нами своим кодом, или может быть, кто-нибудь другой пожелает решить эту хитрую задачу. 1

@CyberNinjaProg -3 / 3 / 0 Регистрация: 10.03.2019 Сообщений: 108
	20.03.2019, 19:34 [ТС]
	Спасибо, но не все прошло есть неправильные ответы.... Миниатюры 0

@CyberNinjaProg -3 / 3 / 0 Регистрация: 10.03.2019 Сообщений: 108
	20.03.2019, 20:43 [ТС]
	ВСЕ прошло. ОГРОМНОЕ ВАМ СПАСИБО! 0

@valen10 Параллельный Кот 1905 / 827 / 350 Регистрация: 25.03.2016 Сообщений: 2,045
	21.03.2019, 00:01
	IGPIGP, тут. Гуглится по слову informatics и началу задания. 1

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 9007 / 4708 / 630 Регистрация: 04.12.2011 Сообщений: 14,003 Записей в блоге: 16
	21.03.2019, 00:41
	valen10, спасибо) 0

@var_gotovets 0 / 0 / 0 Регистрация: 13.04.2021 Сообщений: 1
	13.04.2021, 19:58
	А можете эту же задачу на Пейтоне решить, пожалуйста? 0

Определить минимальное время за которое гости закончат есть свои блины после перекладывания части блинов

Решение