Олимпиадная задача Приключение

@Magaragorn · Регистрация: 01.03.2012

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

Условие
Теплым весенним днем группа из N школьников-программистов гуляла в окрестностях города Кисловодска. К несчастью, они набрели на большую и довольно глубокую яму. Как это случилось — непонятно, но вся компания оказалась в этой яме.
Глубина ямы равна H. Каждый школьник знает свой рост по плечи hi и длину своих рук li. Таким образом, если он, стоя на дне ямы, поднимет руки, то его ладони окажутся на высоте hi + li от уровня дна ямы. Школьники могут, вставая друг другу на плечи, образовывать вертикальную колонну. При этом любой школьник может встать на плечи любого другого школьника. Если под школьником i стоят школьники j1, j2, …, jk, то он может дотянуться до уровня hj1 + hj2 + … + hjk + hi + li.
Если школьник может дотянуться до края ямы (то есть hj1 + hj2 + … + hjk + hi + li ≥ H), то он может выбраться из нее. Выбравшиеся из ямы школьники не могут помочь оставшимся.
Найдите наибольшее количество школьников, которые смогут выбраться из ямы до прибытия помощи, и перечислите их номера.
Формат входных данных
В первой строке входных данных задается натуральное число N (1 ≤ N ≤ 2000) — количество школьников, попавших в яму.
Далее в N строках содержится по два целых числа: рост i-го школьника по плечи hi (1 ≤ hi ≤ 105) и длина его рук li (1 ≤ li ≤ 105).
В последней строке указано целое число — глубина ямы H (1 ≤ H ≤ 105).
Формат выходных данных
В первой строке выведите K — максимальное количество школьников, которые смогут выбраться из ямы. Если K > 0, то во второй строке в произвольном порядке выведите их номера, разделяя их пробелами. Школьники нумеруются с единицы в том порядке, в котором они заданы во входных данных. Если существует несколько решений, выведите любое.
Примеры
Входные данные Выходные данные
2
10 4 0
5 2
20
______________________________
6
6 7
3 1
8 5 4
8 5 1 4 2 5
4 2
10 5
30

Заготовка программы

Pascal
1
2
3
4
5
6
7
8
9
10
11
var N,H,i,b,max,u,min,min1:longint;
m:array[1..100000] of longint;
k:array[1..100000] of longint;
begin
u:=0;
readln(n);
for i:=1 to n do
begin
read(m[i]); read(k[i]);  end;
readln(H);
end.

Прошу алгоритма программы.
Заранее благодарю.

@H@ker · 19.06.2012, 15:48

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

число N (1 ≤ N ≤ 2000) — количество школьников, попавших в яму.

О_о "Две тысячи школьников"...
А ничего, если без использования файлов, т.е. чтобы все руками вводить?
По идее, надо упорядочить всех школьников по возростанию их роста и длины рук (эти величины, скорее всего, пропорциональны), а затем складывать эти величины, начиная с самого высокого школьника (и с самыми длинными руками) по убыванию до того момента, когда один из школьников сможет достать края ямы. Тогда по нему смогут взобраться все те, кто ниже его (если так можно), а потом и он сам. Если же нельзя, то тогда выберется он и все те, чьи рост и длина рук позволят выбраться. То есть во втором варианте останутся самые высокие и самые низкие, а в первом - только самые высокие.

@DaskOFF · 19.06.2012, 16:49

Сообщение от H@ker

О_о "Две тысячи школьников"...
А ничего, если без использования файлов, т.е. чтобы все руками вводить?

задача проверяется машиной
на разных сайтах по разному есть где решения принимаются со считыванием данных из файла и с вводом через пробел, решение от этого не меняется

@H@ker · 19.06.2012, 17:02

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

задача проверяется машиной

т.е. лучше все ж таки с фалами?

@DaskOFF · 19.06.2012, 17:12

Сообщение от H@ker

т.е. лучше все ж таки с фалами?

разницы нету, зависит от сервиса где он решает эту задачу, там могут не приниматься решения без использования файлов

@H@ker · 19.06.2012, 17:37

Magaragorn, тогда жду вашего ответа.

@Magaragorn · 20.06.2012, 10:17 **[ТС]**

Благодарю. На сайте файл проверяется тестировщиком.Что не дает фантазировать в программе.

Добавлено через 4 минуты
Но вводить можно и руками)

Добавлено через 26 минут

Сообщение от H@ker

Magaragorn, тогда жду вашего ответа.

У вас отличный алгоритм.Только как вывести номера детей,которые выбрались из ямы.?
Ведь после сортировки номера теряются.

Добавлено через 13 часов 12 минут

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
38
39
40
41
42
43
44
45
46
47
var N,H,i,s,x,j,q,t,op,schet,max,max1:longint;
m:array[1..100000] of longint;
k:array[1..100000] of longint;
l:array[1..100000] of longint;
begin
readln(n);
max:=n;
for i:=1 to n do
begin
read(m[i]); read(k[i]); l[i]:=i;  end;
readln(H);
   for i:=2 to n do begin
  j:=i;
  while m[j]>m[j-1] do begin
   s:=m[j];
   m[j]:=m[j-1];
   m[j-1]:=s;
   t:=k[j];
    k[j]:=k[j-1];
   k[j-1]:=t;
   op:=l[j];
   l[j]:=l[j-1];
   l[j-1]:=op;
   dec(j);
 
   if j=1 then break; end;  end;
   max1:=k[1];
   for i:=2 to max do
   if k[i]>max1 then
   max1:=k[i];
   //for i:=1 to n do begin write(m[i],' '); write(k[i],' '); writeln(l[i]);  end;
   while n>0 do begin
   for i:=1 to n do
   x:=x+m[i];
   x:=x+k[n];
   if x<h then
   break else
  if x>=h then
  begin
  x:=0;  q:=q+1;  end; x:=0;   n:=n-1;
 end;
 
   
 writeln(q);
 for i:=max downto max-q+1 do
 write(l[i],' ');
end.

Вот программа.Тестрировщик всего 4 теста принял(
Прошу,поправьте.(

@H@ker · 20.06.2012, 12:19

Я так понял, что у вас каждый массив - это или номера детей, как они есть, или номера детей по росту, или номера детей по длине рук. Просто я подумал, что если все-таки рост и длина рук школьников пропорциональны, то можно использовать двумерный массив, где первый индекс - настоящий номер ученика, а второй - при упорядочении по росту.

@Magaragorn · 20.06.2012, 14:39 **[ТС]**

Ну,я уже релизовал.Почему-то только 4 теста верные,из 25!(

@Dani · 20.06.2012, 16:55

Magaragorn, просто сделать запись, где будет храниться рост и номер, или просто сортировать одновременно 2 массива - в одном - рост, в другом - номера.

@Magaragorn · 21.06.2012, 13:16 **[ТС]**

Я так и сделал.

@igor_kz · 23.06.2012, 22:47

Ссылку на систему можно ?)

Добавлено через 3 минуты
Нашел, ВсеРос 2006.
http://informatics.ru/viewprob... und_id=104 --- здесь есть решение как бы

@Magaragorn · 24.06.2012, 17:01 **[ТС]**

Там С++,С и делфи.
А мне паскаль нужен)

@igor_kz · 24.06.2012, 17:11

Ну дельфи тот же паскаль )

Добавлено через 3 минуты
тот алгоритм что вам описали является жадным, и здесь он не подходит)
ДП в помощь )
P.S. advent_bv.dpr прекрасно компилируется fpc )

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. 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? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

@H@ker 19 / 19 / 17 Регистрация: 25.04.2012 Сообщений: 138
	19.06.2012, 17:37
	Magaragorn, тогда жду вашего ответа. 0

@H@ker 19 / 19 / 17 Регистрация: 25.04.2012 Сообщений: 138
	20.06.2012, 12:19
	Я так понял, что у вас каждый массив - это или номера детей, как они есть, или номера детей по росту, или номера детей по длине рук. Просто я подумал, что если все-таки рост и длина рук школьников пропорциональны, то можно использовать двумерный массив, где первый индекс - настоящий номер ученика, а второй - при упорядочении по росту. 0

@Magaragorn 2 / 2 / 3 Регистрация: 01.03.2012 Сообщений: 40
	20.06.2012, 14:39 [ТС]
	Ну,я уже релизовал.Почему-то только 4 теста верные,из 25!( 0

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	20.06.2012, 16:55
	Magaragorn, просто сделать запись, где будет храниться рост и номер, или просто сортировать одновременно 2 массива - в одном - рост, в другом - номера. 0

@Magaragorn 2 / 2 / 3 Регистрация: 01.03.2012 Сообщений: 40
	21.06.2012, 13:16 [ТС]
	Я так и сделал. 0

@igor_kz 154 / 154 / 81 Регистрация: 16.06.2012 Сообщений: 314
	23.06.2012, 22:47
	Ссылку на систему можно ?) Добавлено через 3 минуты Нашел, ВсеРос 2006. http://informatics.ru/viewprob... und_id=104 --- здесь есть решение как бы 0

@Magaragorn 2 / 2 / 3 Регистрация: 01.03.2012 Сообщений: 40
	24.06.2012, 17:01 [ТС]
	Там С++,С и делфи. А мне паскаль нужен) 0

@igor_kz 154 / 154 / 81 Регистрация: 16.06.2012 Сообщений: 314
	24.06.2012, 17:11
	Ну дельфи тот же паскаль ) Добавлено через 3 минуты тот алгоритм что вам описали является жадным, и здесь он не подходит) ДП в помощь ) P.S. advent_bv.dpr прекрасно компилируется fpc ) 0