Задание. Отношение
Дан массив a1, a2, ... an. Необходимо выбрать в нем два элемента ai и aj, такие что i < j, и отношение aj / ai - максимально и больше 1.
Входные данные
В первой строке задано целое число 2 <= n <= 100000 - количество элементов в массиве. Во второй строке записаны n целых положительных чисел ai(1 <= i <= n, 1 <= ai <= 5000).
Выходные данные
Выведите два числа - индексы элементов i и j. Если ответов несколько, то выведите любой из них.
Если ответа нет, то выведите два нуля, разделенных пробелом.
Примеры
Ввод:
6
10 3 5 3 11 9
Вывод:
2 5
Ввод:
4
5 5 5 5
Вывод:
0 0
1. Сначала мы получаем входные данные - количество элементов массива и сами элементы массива.
2. Создадим переменные `max_ratio = 0`, `index_i = 0` и `index_j = 0` для хранения максимального отношения и индексов элементов.
3. Начнем перебирать элементы массива с помощью цикла `for`, начиная с первого элемента и до предпоследнего. Для каждого элемента `ai` будем перебирать следующие элементы, начиная со следующего за `ai`.
4. Для каждой пары элементов `ai` и `aj`, где `aj` идет после `ai`, найдем их отношение `ratio = aj / ai`.
5. Если `ratio` больше `max_ratio`, то обновим `max_ratio` и запишем индексы `index_i` и `index_j` равными `i` и `j`.
6. По окончании перебора, проверим значение `max_ratio`. Если оно равно 0, значит подходящих пар элементов не найдено и мы выводим "0 0". В противном случае, выводим значения `index_i` и `index_j`.
Пример решения на языке Python:
```python
n = int(input()) # Вводим количество элементов массива
arr = list(map(int, input().split())) # Вводим элементы массива
max_ratio = 0
index_i, index_j = 0, 0
for i in range(n-1):
for j in range(i+1, n):
ratio = arr[j] / arr[i]
if ratio > max_ratio:
max_ratio = ratio
index_i, index_j = i+1, j+1
if max_ratio == 0:
print("0 0")
else:
print(index_i, index_j)
```
Теперь школьник должен понять каждый шаг решения и сможет использовать его для решения поставленной задачи.