3 / 3 / 0
Регистрация: 08.10.2018
Сообщений: 31
Записей в блоге: 2
1

Белоснежка и n гномов

08.11.2018, 15:51. Показов 6031. Ответов 1

Author24 — интернет-сервис помощи студентам
У Белоснежки n гномов, и все они очень разные. Она знает, что для того, чтобы уложить спать
i-го гнома нужно ai минут, и после этого он будет спать ровно bi минут. Помогите Белоснежке
узнать, может ли она получить хотя бы минутку отдыха, когда все гномы будут спать, и если да,
то в каком порядке для этого нужно укладывать гномов спать.
Например, пусть есть всего два гнома, a1 = 1, b1 = 10, a2 = 10, b2 = 20. Если Белоснежка сначала
начнет укладывать первого гнома, то потом ей потребуется целых 10 минут, чтобы уложить второго,
а за это время проснется первый. Если же она начнет со второго гнома, то затем она успеет уложить
первого и получит целых 10 минут отдыха.
Формат ввода:
Первая строка входного файла содержит число n (1 <= n <= 10^5), вторая строка содержит числа
a1, a2, ... an, третья - числа b1, b2, ... bn (1 <= ai, bi <= 10^9).

Формат вывода:
Выведите в выходной файл n чисел - порядок, в котором нужно укладывать гномов спать. Если
Белоснежке отдохнуть не удастся, выведите число -1.

Пример ввода: Пример вывода:
2 2 1
1 10
10 20


Пример ввода: Пример вывода:
2 -1
10 10
10 10


Мое решение:
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
Const
  MaxN=100000;
var
  A,B,C,Num : array [1..MaxN] of longint;
  N,i       : longint;
  procedure QSort_C_Down(L,R:longint);
    var
      i,j : longint;
      x,t : longint;
    begin
      if L>=R then exit;
      x := C[L]; i:=L-1; j:=R+1;
      while i<j do
        begin
          repeat j:=j-1; until C[j]>=x;
          repeat i:=i+1; until C[i]<=x;
          if i<j
            then begin
                   t:=C[i]; C[i]:=C[j]; C[j]:=t;
                   t:=A[i]; A[i]:=A[j]; A[j]:=t;
                   t:=B[i]; B[i]:=B[j]; B[j]:=t;
                 end;
        end;
      QSort_C_Down(L,j);
      QSort_C_Down(j+1,R);
    end;
begin
  readln(N);
  for i:=1 to N do read(a[i]);
  for i:=1 to N do read(b[i]);
  for i:=1 to N do c[i]:=a[i]+b[i];
  for i:=1 to N do Num[i]:=i;
  QSort_C_Down(1,N);
  i:=1;
  while (i<=N-1) and (b[i]>a[i+1]) do inc(i);
  if i>N-1
    then for i:=1 to N do write(Num[i],' ')
    else writeln(-1);
end.
Не понимаю, почему в 1-м тесте выводит наоборот.

Добавлено через 5 часов 51 минуту
Извините, решил:

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
Const
  MaxN=100000;
var
  A,B,C,Num : array [1..MaxN] of longint;
  N,i       : longint;
  procedure QSort_C_Down(L,R:longint);
    var
      i,j : longint;
      x,t : longint;
    begin
      if L>=R then exit;
      x := C[L]; i:=L-1; j:=R+1;
      while i<j do
        begin
          repeat i:=i+1; until C[i]<=x;
          repeat j:=j-1; until C[j]>=x;
          if i<j
            then begin
                   t:=C[i]; C[i]:=C[j]; C[j]:=t;
                   t:=A[i]; A[i]:=A[j]; A[j]:=t;
                   t:=B[i]; B[i]:=B[j]; B[j]:=t;
                   t:=Num[i]; Num[i]:=Num[j]; Num[j]:=t;
                 end;
        end;
      QSort_C_Down(L,j);
      QSort_C_Down(j+1,R);
    end;
begin
  readln(N);
  for i:=1 to N do read(a[i]);
  for i:=1 to N do read(b[i]);
  for i:=1 to N do C[i]:=A[i]+B[i];
  for i:=1 to N do Num[i]:=i;
  QSort_C_Down(1,N);
  i:=1;
  while (i<=N-1) and (B[i]>a[i+1]) do inc(i);
  if i>N-1
    then for i:=1 to N do write(Num[i],' ')
    else writeln(-1);
end.
Добавлено через 1 минуту
Надо было поменять номера гномов .
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.11.2018, 15:51
Ответы с готовыми решениями:

Задача про гномов
Помогите пожалуйста разобраться с задачей-&gt; На скамье длиной L см расположены N гномов. В...

задача про100 гномов
Разработайте программу для решения следующей задачи: «Сто гномов едят одно яблоко весом в 200...

Задачка про Гномов и Злого волшебника Грендальфа
Добрый день. Задали такую головоломку решить на Прологе: ЗАДАЧА №10. Пользуясь методом...

Тема про гномов, эльфов и орков. Ролевики и толкиенисты, кучкуемся!
Девять - струны звонкой лютни, той, что носят менестрели, что воспели в своих песнях девять...

1
Почетный модератор
64303 / 47598 / 32743
Регистрация: 18.05.2008
Сообщений: 115,181
08.11.2018, 15:53 2
Лучший ответ Сообщение было отмечено Alexandr_Ivanov как решение

Решение

Молодец, упорный.
1
08.11.2018, 15:53
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.11.2018, 15:53
Помогаю со студенческими работами здесь

Где скачать фильм "Белоснежка и охотник"
Ребята, где скачать фильм &quot;Белоснежка и охотник&quot;? Уже была премьера, а не видно все равно....(


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru