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

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

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

Здравствуйте. Встретилась непонятная задачка на 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

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

Новые блоги и статьи Все статьи Все блоги /
Работа с объемным DOM в javascript Htext 04.04.2025 Сегодня прочитал статью тут о расходах памяти в JS, ее утечках и т. п. И вот что вспомнил из своей недавней практики. Может, кому пригодится. Хотя, в той статье об этом тоже есть. Дело в том, что я. . .	Оптимизация производительности Node.js с помощью кластеризации run.dev 04.04.2025 Масштабирование приложений для обработки тысяч и миллионов запросов — обыденная задача для многих команд. Node. js, благодаря своей асинхронной событийно-ориентированной архитектуре, стал популярной. . .	Управление зависимостями в Python с Poetry py-thonny 04.04.2025 Стандартный инструмент для установки пакетов в Python - pip - прекрасно справляется с базовыми сценариями: установил пакет командой pip install и используешь его. Но что произойдёт, когда разные. . .	Мониторинг с Prometheus в PHP Jason-Webb 04.04.2025 Prometheus выделяется среди других систем мониторинга своим подходом к сбору и хранению метрик. В отличие от New Relic, который использует агентный подход и отправляет данные во внешнее хранилище,. . .	Пакет Context в Golang: Управление потоками и ресурсами golander 04.04.2025 Работа с горутинами в Go часто напоминает управление непослушными детьми - они разбегаются кто куда, делают что хотят и не всегда завершаются вовремя. К счастью, в Go 1. 7 появился пакет context,. . .
Контейнеризация React приложений с Docker Reangularity 03.04.2025 Контейнеризация позволяет упаковать приложение со всеми его зависимостями в автономный контейнер, который можно запустить на любой платформе с установленным Docker. Это существенно упрощает процессы. . .	Свой попап в SwiftUI mobDevWorks 03.04.2025 SwiftUI, как декларативный фреймворк от Apple, предоставляет множество инструментов для создания пользовательских интерфейсов. В нашем распоряжении есть такие API как alerts, popovers, action sheets. . .	Антипаттерны микросервисной архитектуры ArchitectMsa 03.04.2025 Хорошо спроектированная микросервисная система может выдержать испытание временем, оставаясь гибкой, масштабируемой и устойчивой к большинству проблем. Такая архитектура обладает высоким уровнем. . .	std::mutex в C++: Советы и примеры использования bytestream 03.04.2025 std::mutex - это механизм взаимного исключения, который гарантирует, что критический участок кода выполняется только одним потоком в каждый момент времени. Это простое, но могущественное средство. . .	Не удержался от оценки концепции двигателя Стирлинга. Hrethgir 03.04.2025 Сколько не пытался - она выдавала правильные схемы, причём случайно рисовала горячие области в середине, холодные по краям, трубки с краёв в низ и магнит в соединяющей, но при этой выдавала описание. . .

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

	Определить минимальное время за которое гости закончат есть свои блины после перекладывания части блинов 18.03.2019, 23:08. Показов 11234. Ответов 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

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 9005 / 4704 / 630 Регистрация: 04.12.2011 Сообщений: 14,003 Записей в блоге: 16
	20.03.2019, 14:21
	Сообщение от valen10 Несчастный гость соберет все лестницы в округе, чтобы забраться на самый верх и скидывать оттуда по одному блину для опоздавшего. В задаче крышу блин срывает. Буквально. Сообщение от valen10 При таких количествах блиноединиц перекладывать по одной получится долго. Я не вчитался в момент, каюсь: Сообщение от CyberNinjaProg все присутствующие могут переложить часть своих блинов (в том числе могут переложить все свои блины, а могут не перекладывать ни одного блина) вновь пришедшему человеку. Перекладывание блинов происходит одновременно и моментально. Зато достаточно наглядно, но теперь ясно что нужно разность пополам делить. В общем объедятся они. Как пить дать. 0

@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

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 9005 / 4704 / 630 Регистрация: 04.12.2011 Сообщений: 14,003 Записей в блоге: 16
	20.03.2019, 23:45
	Сообщение от CyberNinjaProg ВСЕ прошло. ОГРОМНОЕ ВАМ СПАСИБО! CyberNinjaProg, а где вы нашли задание и где можно его решение протестировать? 0

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

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 9005 / 4704 / 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

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

Решение