Отношение

@Алле · Регистрация: 26.06.2020

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

Дан массив a1,a2,…an. Необходимо выбрать в нём два элемента ai и aj, такие что i<j, и отношение aj/ai — максимально и больше 1.

Входные данные

В первой строке задано целое число 2 ≤n≤ 100 000 — количество элементов в массиве.

Во второй строке заданы n целых положительных чисел ai(1 ≤i≤n, 1 ≤ai≤ 5000).

Выходные данные

Выведите два числа — индексы элементов i и j. Если ответов несколько, то выведите любой из них.

Если ответа нет, то выведите два нуля, разделённых пробелом.

@Fudthhh · 02.07.2020, 12:00

На коленке, должно работать:

Python
1
2
3
4
5
6
7
8
9
n, elements  = int(input()), map(int, input().split())
 
maximum, indexes = 1, (0, 0)
for i, current in enumerate(elements):
    for j, element in enumerate(elements[i:]):
        if element / current > maximum:
            maximum, indexes = element / current, (i, i + j)
 
print(*indexes)

@Алле · 04.07.2020, 12:18 **[ТС]**

В 5 строчке ошибка: "builtins.TypeError: 'map' object is not subscriptable"

@palva · 05.07.2020, 00:25

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
n = 5
a = [2, 5, 1, 6, 7]
#a = [2, 3, 4, 5, 6]
p = [0] * n
p[n-1] = n-1
for i in range(n-2, -1, -1):
    if a[i] < a[p[i+1]]:
        p[i] = i
    else:
        p[i] = p[i+1]
mx = 0.0
i1 = 0
i2 = 0
for i in range(0, n-1):
    if a[i] < a[p[i+1]]:
        continue
    if a[i]/a[p[i+1]] > mx:
        mx = a[i]/a[p[i+1]]
        i1 = i
        i2 = p[i1]
print(i1, i2)

Добавлено через 2 часа 17 минут
Индексы в задаче отсчитываются от единицы. А я вывел в предположении, что индексы считаются от нуля. Так что конец программы надо поправить.

Python
1
2
3
4
5
6
7
8
9
10
i1 = -1
i2 = -1
for i in range(0, n-1):
    if a[i] < a[p[i+1]]:
        continue
    if a[i]/a[p[i+1]] > mx:
        mx = a[i]/a[p[i+1]]
        i1 = i
        i2 = p[i1+1]
print(i1+1, i2+1)

Добавлено через 11 минут
И еще ошибка обнаружилась. Не то отношение максимизировал. Вмести aj/ai делал для ai/aj.
Но тут уж сами переделывайте. Идея ясна.

@JIvan · 05.07.2020, 00:30

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n = int(input())
a = list(map(int, input().split()))
i = 0
j = 1
m = 0
for k in range(1,n):
    if a[k] > a[j]:
        j = k
        
    if a[k] < a[m]:
        m = k
        
    if m < j:
        i = m
        
if a[j] <= a[i]:
    print(0,0)
else:    
    print (i+1 ,j+1)

почему-то сириус не принимает...

@Вия · 05.07.2020, 00:31

palva, программа выдаёт неверный ответ

@eaa · 05.07.2020, 06:57

Сортировка подсчётом (counting sort) читайте.

@palva · 05.07.2020, 07:50

Сообщение от Вия

palva, программа выдаёт неверный ответ

Вия, Естественно. Я же написал о том, что решал задачу для перевернутого отношения -- не сразу разглядел в условии.
Переделайте и выложите. Обсудим. Если вы не поняли идею, то я готов в двух словах объяснить. Нам нужно проверить все кандидаты (i,j) и выбрать из них наилучший. Самый тупой алгоритм дает нам сложность, которая растет как квадрат n. Нам же нужен алгоритм с линейной сложностью. Вы написали об этом в заголовке своего сообщения (которое уже удалили из-за дублирования задачи). То есть ваш тупой алгоритм пройдет несколько простых тестов и завалится по времени на более сложных. Этот алгоритм построен так: проверяем по очереди все аi и для каждого ищем оптимальное аj справа от ai. Оптимальное, значит максимальное (я искал минимальное, поскольку неправильно понял задачу). Таких поисков будет много, около n. Но все их можно сделать за линейное время, если вычислять последовательно -- сначала для двух последних, потом трех последних, потом четырех и т. д. При этом поиск осуществляется не просмотром всех aj а использованием результата поиска на предыдущем шаге: когда у нас добавился элемент, то результат поиска будет равен предыдущему результату, если этот элемент его меньше и равен этому элементу в противном случае. Все эти поиски вы осуществите за линейное время. Результат поисков у меня записывается в список b, посмотрите в программе каким образом. После этого можно перебирать ai и находить глобальный максимум.

Вы получите линейный алгоритм, который пройдет уже больше тестов, чем тупой. Но не исключаю, что кое-какие тесты он не пройдет, поскольку тупость в нем все же осталась. Мы храним претендента на максимум в виде плавающего значения mx, при этом мы можем потерять точность. По-хорошему претендента надо хранить в виде mxn / mxd то есть в виде двух целых чисел. Такие "обыкновенные дроби" нам надо будет уметь сравнивать, что добавит еще несколько строк кода. Один из тестов может быть составлен так, что завалит вашу программу, если вы будете здесь терять точность переходом к плавающему значению.

Добавлено через 10 минут
Вот составьте три программы: идеальную, с одной тупостью и совсем тупую. Запустите их и сравните, сколько тестов они пройдут.
Естественно, они должны быть правильными, то есть давать правильный результат на 6-элементных тестах, предложенных в условии. (В этой ветке Алле сэкономил свои усилия и эти тесты не привел. Я имею в виду те тесты, которые были в вашем посте.)

@JIvan · 05.07.2020, 10:30

palva, подскажите пожалуйста - в чем может быть ошибка в моем решении?
Задача вроде бы как элементарная: найти мин и макс с учетом что индекс макс больше индекса мин

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n = int(input())
a = list(map(int, input().split()))
i = 0
j = 1
m = 0
for k in range(1,n):
    if a[k] > a[j]:
        j = k
        
    if a[k] < a[m]:
        m = k
        
    if m < j:
        i = m
        
if a[j] <= a[i]:
    print(0,0)
else:    
    print (i+1 ,j+1)

P.S.
Все приложеные тесты програма проходит естественно

@Roket_Flame · 05.07.2020, 12:12

Вот решение, все тесты проходит и по времени тоже

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
n, elements = int(input()), list(map(int, input().split()))
 
ibest = 0
jbest = 0
imin = 0
for i in range(2, n):
    if elements[i - 1] < elements[imin]:
        imin = i - 1
    if 1 < elements[i] / elements[imin] > elements[jbest] / elements[ibest]:
        ibest = imin
        jbest = i
ibest = 0 if ibest == 0 else ibest + 1
jbest = 0 if jbest == 0 else jbest + 1
print(ibest, jbest)

@JIvan · 05.07.2020, 12:38

Roket_Flame, чем оно отличается от моего ??? Ведь дробь максимальна когда числитель максимален и знаменатель минимален...

@palva · 05.07.2020, 15:03

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

palva, подскажите пожалуйста - в чем может быть ошибка в моем решении?

Даём на вход
4
3 6 2 5
Получаем
1 2
Хотя надо
3 4

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

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

все тесты проходит

Ну, положим, не все
4
2 5 3 6
Но это какая-то мелкая ошибка. А так, по-моему, алгоритм правильный.

@TukTukL · 05.07.2020, 20:28

Вообщем ,постараюсь объяснить, в чем, я думаю, ошибка. Во-первых нужно искать минимум до какого-то элемента, не включая этот элемент.

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

if a[k] > a[j]:
j = k

Во-вторых, когда ты проверяешь

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

if a[k] > a[j]:
j = k

то на том же самом примере от palva 5<6(во время самого максимального k), поэтому j даже не меняется, хотя должно было бы. Нужно проверять максимальное значение не чисел, а отношений.

Новые блоги и статьи Все статьи Все блоги /
Как я обхитрил таблицу Word Alexander-7 21.03.2026 Когда мигает курсор у внешнего края таблицы, и нам надо перейти на новую строку, а при нажатии Enter создается новый ряд таблицы с ячейками, то мы вместо нервных нажатий Энтеров мы пишем любые буквы. . .	Krabik - рыболовный бот для WoW 3.3.5a AmbA 21.03.2026 без регистрации и смс. Это не торговля, приложение не содержит рекламы. Выполняет свою непосредственную задачу - автоматизацию рыбалки в WoW - и ничего более. Однако если админы будут против -. . .	Программный отбор значений справочника Maks 21.03.2026 Установка программного отбора значений справочника "Сотрудники" из модуля формы документа. В качестве фильтра для отбора служит предопределенное значение перечислений. Процедура. . .	Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .
Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .

@Алле 1 / 1 / 0 Регистрация: 26.06.2020 Сообщений: 30

	Отношение 02.07.2020, 10:43. Показов 29196. Ответов 12 Метки нет (Все метки) Дан массив a1,a2,…an. Необходимо выбрать в нём два элемента ai и aj, такие что i<j, и отношение aj/ai — максимально и больше 1. Входные данные В первой строке задано целое число 2 ≤n≤ 100 000 — количество элементов в массиве. Во второй строке заданы n целых положительных чисел ai(1 ≤i≤n, 1 ≤ai≤ 5000). Выходные данные Выведите два числа — индексы элементов i и j. Если ответов несколько, то выведите любой из них. Если ответа нет, то выведите два нуля, разделённых пробелом. 0

@Алле 1 / 1 / 0 Регистрация: 26.06.2020 Сообщений: 30
	04.07.2020, 12:18 [ТС]
	В 5 строчке ошибка: "builtins.TypeError: 'map' object is not subscriptable" 0

@Вия 2 / 2 / 0 Регистрация: 28.05.2020 Сообщений: 40
	05.07.2020, 00:31
	palva, программа выдаёт неверный ответ 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	05.07.2020, 06:57
	Сортировка подсчётом (counting sort) читайте. 0

@JIvan 0 / 0 / 0 Регистрация: 05.07.2020 Сообщений: 10
	05.07.2020, 12:38
	Roket_Flame, чем оно отличается от моего ??? Ведь дробь максимальна когда числитель максимален и знаменатель минимален... 0

Отношение

Решение