Отношение

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

Новые блоги и статьи Все статьи Все блоги /
Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .	Запрет удаления строк ТЧ документа при определенном условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .	Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .
Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .

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

	Отношение 02.07.2020, 10:43. Показов 29325. Ответов 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

Отношение

Решение