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

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

Новые блоги и статьи Все статьи Все блоги /
Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .
Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .	Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при создании или изменении элементов справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .

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

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

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

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

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

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

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

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

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

Решение