Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Максимальное произведение

(Время: 1 сек. Память: 64 Мб Сложность: 23%)

Задан массив натуральных чисел [a1, a2, ... , an]. Весом массива назовём сумму его элементов. Необходимо разрезать заданный массив на два непустых массива [a1, a2, ... , ai] и [ai+1, ai+2, ... , an] так, чтобы произведение их весов было как можно больше.

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

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

В первой строке входного файла INPUT.TXT находится целое число n — количество элементов в массиве (2 ≤ n ≤ 2×105). В следующей строке находятся n целых чисел a1, a2, ... , an — элементы массива (1 ≤ ai ≤ 109).

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

В выходной файл OUTPUT.TXT выведите одно число — номер элемента, после которого необходимо разрезать заданный массив. Если оптимальных вариантов ответа несколько, можно вывести любой из них.

Пример

INPUT.TXTOUTPUT.TXT
13
1 2 3
2

Пояснение к примеру

Если сделать разрез после первого элемента, произведение весов равно 1×(2+3) = 5, а если после второго, то (1+2)×3 = 9.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 A. Разность квадратов
 B. Превышение скорости
 C. Борьба с рутиной
 D. Олимпиада для роботов
 E. Максимальное произведение
 F. Планировка участка
 G. Банкомат
 H. Плакаты

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru