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

@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

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

Новые блоги и статьи Все статьи Все блоги /
Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .	Часы с будильником на основе класса QLCDNumber Uhbif79 12.08.2026 Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .	Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия	Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо anaschu 10.08.2026 Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .
Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .	Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .

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

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

Опции темы

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

Решение