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

@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 уменьшились и время и расход памяти. А в остальном - код не менялся. Пришёл к выводу, что потери были на преобразование типов с обнулением старшей части, хотя в листинг не заглянул.

Новые блоги и статьи Все статьи Все блоги /
изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 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 считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .

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

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

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

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

ФедосеевПавел Модератор 8648 / 4483 / 1669 Регистрация: 01.02.2015 Сообщений: 13,890 Записей в блоге: 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

ФедосеевПавел Модератор 8648 / 4483 / 1669 Регистрация: 01.02.2015 Сообщений: 13,890 Записей в блоге: 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

ФедосеевПавел Модератор 8648 / 4483 / 1669 Регистрация: 01.02.2015 Сообщений: 13,890 Записей в блоге: 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

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

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

Решение