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

@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++

#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++

#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

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

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

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

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

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

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

@CyberNinjaProg -3 / 3 / 0 Регистрация: 10.03.2019 Сообщений: 108
		1
	Определить минимальное время за которое гости закончат есть свои блины после перекладывания части блинов 18.03.2019, 23:08. Показов 11050. Ответов 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	21
	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 [ТС]	24
	Спасибо, но не все прошло есть неправильные ответы.... Миниатюры 0

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

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

Решение