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

@ITS · Регистрация: 12.01.2016

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

1935. Слёзы утопленников
Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Гадалка Тиа Дальма, давняя подруга капитана Джека Воробья, часто варит зелья. У неё есть выдающаяся коллекция редчайших ингредиентов: крысиные хвосты, пальцы утопленников, слёзы девственниц и многое другое. И всем этим ингредиентам требуется особый уход.
Недавно Тиа Дальма в качестве оплаты получила несколько свежих шкурок летучих мышей и теперь хочет их высушить. Для сушки ингредиентов гадалка обычно использует специально подготовленные книги, так как магические свойства шкурок теряются при длительном контакте с другими объектами. Тиа Дальма знает, сколько листов должно быть с каждой стороны от шкурки, чтобы та не испортилась. Для i-й шкурки это количество равно ai, то есть расстояния от неё до соседних шкурок и обложки книги не могут быть меньше ai листов. Помогите гадалке определить минимальное количество листов, которое должно быть в книге, чтобы редкие ингредиенты не пострадали.
Исходные данные
В первой строке записано целое число n — количество шкурок (1 ≤ n ≤ 100). Во второй строке через пробел перечислены n целых чисел ai (1 ≤ ai ≤ 100).
Результат
Выведите единственное целое число — минимальное достаточное количество листов в книге.
Пример
исходные данные 3 ;5 10 3 ; результат 28;
Мой код:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var
A:array[1..100] of integer;
n,q,w,s:integer;
begin
read(n);
s:=0;
for q:=1 to n do read(A[q]);
for w:=1 to n-1 do begin
if A[w]>A[w+1] then s:=s+A[w]
else s:=s+A[w+1];
end;
s:=s+(A[1])+(A[n]);
write(s);
end.

Что всетаки не так?

ФедосеевПавел · 07.02.2016, 16:04

readln(n) - не?

@ITS · 07.02.2016, 16:23 **[ТС]**

Неет одну n же вводим

ФедосеевПавел · 07.02.2016, 16:26

Но на одной строке, а потом список идёт на другой.

@ITS · 07.02.2016, 16:30 **[ТС]**

Попробовал но все равно не проходит(

ФедосеевПавел · 07.02.2016, 16:40

Плюс прочтите - обсуждение на тимусе для WA#5. Там хорошо объяснили, почему ваш вариант полностью не подходит.

Добавлено через 9 минут
Только что получил WA#5, прочитал пояснения на тимусе, переделал - AC!
Успехов!

@ITS · 07.02.2016, 16:42 **[ТС]**

Интерееесно как так 27 получилось

ФедосеевПавел · 07.02.2016, 16:47

Пояснения - ответом ниже. Даже не зная английского - можно выделить интернациональные.

Добавлено через 3 минуты
Ух! Присмотрелся к никам - а там SpBerkut поясняет! А он уже и здесь - неподалёку!

@ITS · 07.02.2016, 16:53 **[ТС]**

Тоесть сортировка позволяет выявить наименьшее кол-во?Интереесненько

Добавлено через 57 секунд
А можно пояснение почему так получается?

Добавлено через 1 минуту
У вас ник fpa? Я IT если что

@SpBerkut · 07.02.2016, 17:49

Сообщение от ФедосеевПавел

Присмотрелся к никам - а там SpBerkut поясняет!

Хде?!

ФедосеевПавел · 07.02.2016, 18:08

На тимусе в пояснениях к задаче 1935. Не буду приводить ссылку - вроде бы, запрещено правилами давать ссылки на другие ресурсы - но в пояснении "WA #5 why??"

@ITS · 07.02.2016, 18:47 **[ТС]**

Пытаетесь сделать чтобы на 0.001 прошло?)

Добавлено через 4 минуты
SpBerkut, так это вы?

ФедосеевПавел · 07.02.2016, 19:38

Да. Но не пойму почему не получается. Ещё пару попыток и брошу.
Всё бросаю. Надоело.

Добавлено через 27 минут
ITS, а поделитесь секретом - как удалось за столь малое время 0.001?
Я упростил всё что только можно:
1. Не храню и не обрабатываю массив.
2. Сами элементы минимального размера.
Почему у меня время работы 0,015.

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
program t1935;
 
{$ifdef Debug}
  {$ifdef FPC}
uses
  HeapTrc, LineInfo;
  {$endif}
{$endif}
 
var
  n, i: integer;
  a, MaxA: byte;
  Len:  integer;
begin
{$IFNDEF ONLINE_JUDGE}
  Assign(input, 'tin1.txt');
  Reset(input);
  Assign(output, ''{'tout.txt'});
  Rewrite(output);
{$ENDIF}
  readln(n);
  Len  := 0;
  MaxA := 0;
  for i := 0 to n - 1 do
  begin
    Read(a);
    if MaxA < a then
      MaxA := a;
    Len := Len + a;
  end;
  Len := Len + MaxA;
  Writeln(Len);
{$IFNDEF ONLINE_JUDGE}
  Close(input);
  Close(output);
{$ENDIF}
end.

Добавлено через 15 минут
Перебор - всё побеждает!!!

Оказывается, замена типа данных (для переменных a, MaxA) byte на integer не только сокращает время работы программы с 0,015 до 0,001, но и уменьшает расход памяти с 156к до 152к.

@SpBerkut · 08.02.2016, 10:38

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

SpBerkut, так это вы?

Ёлки! Это я. Вот AC, если нужно.

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var
  N, I, M, X: Byte;
  S: Word;
begin
  ReadLn(N);
  M := 0; S := 0;
  for i := 1 to N do
  begin
    Read(X);
    if X > M then M := X;
    S := S + X;
  end;
  WriteLn(S+M);
end.

Добавлено через 2 часа 24 минуты
Этот вариант быстрее.

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
var
  S, N, I, M, X: Integer;
begin
  ReadLn(N);
  M := 0; S := 0;
  for i := 1 to N do
  begin
    Read(X);
    if X > M then M := X;
    Inc(S,X);
  end;
  WriteLn(S+M);
end.

@ITS · 08.02.2016, 17:24 **[ТС]**

А я делал через массив но почему -то на 0.001 прошло)

@SpBerkut · 08.02.2016, 17:44

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

А я делал через массив но почему -то на 0.001 прошло)

Там система проверки иногда дурит. У меня абсолютно идентичный код и 0,015 и 0,001 секунды показывал.

ФедосеевПавел · 08.02.2016, 18:16

А у меня, как и говорил выше, при замене типа двух переменных с byte на integer уменьшились и время и расход памяти. А в остальном - код не менялся. Пришёл к выводу, что потери были на преобразование типов с обнулением старшей части, хотя в листинг не заглянул.

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

ФедосеевПавел Модератор 8647 / 4482 / 1669 Регистрация: 01.02.2015 Сообщений: 13,889 Записей в блоге: 12
	07.02.2016, 16:04
	readln(n) - не? 0

@ITS 0 / 0 / 0 Регистрация: 12.01.2016 Сообщений: 25
	07.02.2016, 16:23 [ТС]
	Неет одну n же вводим 0

ФедосеевПавел Модератор 8647 / 4482 / 1669 Регистрация: 01.02.2015 Сообщений: 13,889 Записей в блоге: 12
	07.02.2016, 16:26
	Но на одной строке, а потом список идёт на другой. 0

@ITS 0 / 0 / 0 Регистрация: 12.01.2016 Сообщений: 25
	07.02.2016, 16:30 [ТС]
	Попробовал но все равно не проходит( 0

ФедосеевПавел Модератор 8647 / 4482 / 1669 Регистрация: 01.02.2015 Сообщений: 13,889 Записей в блоге: 12
	07.02.2016, 16:40
	Сообщение было отмечено ITS как решение Решение Плюс прочтите - обсуждение на тимусе для WA#5. Там хорошо объяснили, почему ваш вариант полностью не подходит. Добавлено через 9 минут Только что получил WA#5, прочитал пояснения на тимусе, переделал - AC! Успехов! 0

@ITS 0 / 0 / 0 Регистрация: 12.01.2016 Сообщений: 25
	07.02.2016, 16:42 [ТС]
	Интерееесно как так 27 получилось 0

ФедосеевПавел Модератор 8647 / 4482 / 1669 Регистрация: 01.02.2015 Сообщений: 13,889 Записей в блоге: 12
	07.02.2016, 16:47
	Пояснения - ответом ниже. Даже не зная английского - можно выделить интернациональные. Добавлено через 3 минуты Ух! Присмотрелся к никам - а там SpBerkut поясняет! А он уже и здесь - неподалёку! 0

@ITS 0 / 0 / 0 Регистрация: 12.01.2016 Сообщений: 25
	07.02.2016, 16:53 [ТС]
	Тоесть сортировка позволяет выявить наименьшее кол-во?Интереесненько Добавлено через 57 секунд А можно пояснение почему так получается? Добавлено через 1 минуту У вас ник fpa? Я IT если что 0

ФедосеевПавел Модератор 8647 / 4482 / 1669 Регистрация: 01.02.2015 Сообщений: 13,889 Записей в блоге: 12
	07.02.2016, 18:08
	На тимусе в пояснениях к задаче 1935. Не буду приводить ссылку - вроде бы, запрещено правилами давать ссылки на другие ресурсы - но в пояснении "WA #5 why??" Миниатюры 0

@ITS 0 / 0 / 0 Регистрация: 12.01.2016 Сообщений: 25
	07.02.2016, 18:47 [ТС]
	Пытаетесь сделать чтобы на 0.001 прошло?) Добавлено через 4 минуты SpBerkut, так это вы? 0

@ITS 0 / 0 / 0 Регистрация: 12.01.2016 Сообщений: 25
	08.02.2016, 17:24 [ТС]
	А я делал через массив но почему -то на 0.001 прошло) 0

ФедосеевПавел Модератор 8647 / 4482 / 1669 Регистрация: 01.02.2015 Сообщений: 13,889 Записей в блоге: 12
	08.02.2016, 18:16
	А у меня, как и говорил выше, при замене типа двух переменных с byte на integer уменьшились и время и расход памяти. А в остальном - код не менялся. Пришёл к выводу, что потери были на преобразование типов с обнулением старшей части, хотя в листинг не заглянул. 0

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

Решение