Олимпиадный тренинг

Задача . Минимальное максимальное


Задача

Темы:
Алексей Юрьевич и Михаил Леонидович отправились на поезде в Троицк. По дороге к ним подсели вахтовик и дембель. После знакомства и небольших историй о себе вахтовик и дембель решили устроить Алексею Юрьевичу и Михаилу Леонидовичу тест «на мужика»: нужно решить непростую задачку по программированию.
Помогите Алексею Юрьевичу и Михаилу Леонидовичу пройти тест «на мужика».
Задан массив целых чисел a1,a2,...,an.
Стоимостью подотрезка массива 1 <= l <= r <= n назовем величину f(l,r) = sum(l,r) − xor(l,r), где sum(l,r) = al +al+1+...+ar, а xor(l,r) = al ⊕al+1 ⊕...⊕ar (⊕ здесь обозначает операцию XOR, побитовое исключающее «ИЛИ» чисел, подробнее в разделе «Замечание»).
Требуется найти подотрезок заданного массива с максимальным значением f(l,r). Если ответов несколько, то среди них нужно найти подотрезок с минимальной длиной, то есть минимальным значением r − l +1.
Входные данные
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число t (1 <= t <= 104) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит единственное целое число n (1 <= n <= 105) — длину массива.
Вторая строка каждого набора входных данных содержит n целых чисел a1,a2,...,an (0 <= ai <= 109) — элементы массива.
Гарантируется, что сумма n по всем наборам входных данных не превосходит 2 · 105.
Выходные данные
Для каждого набора входных данных выведите два числа 1 <= l <= r <= n таких, что значение f(l,r) максимально по всем подотрезкам массива a, а длина r −l +1 минимальна. Если существует несколько правильных ответов, выведите любой из них.
 
Примеры
Входные данные Выходные данные
1 6
1
0
2
5 10
3
0 2 4
4
0 12 8 3
5
21 32 32 32 10
7
0 1 0 1 0 1 0
1 1
2 2
3 3
2 3
3 4
4 6

Замечание
Операция XOR двух чисел a и b — это битовая операция, которая применяется независимо к каждой паре соответствующих битов a и b. Эта операция представляет собой сложение по модулю 2. Вот её таблица истинности для пары битов:
a b a⊕b
0 0 0
0 1 1
1 0 1
1 1 0

В первом наборе входных данных f(1,1) = 1 − 1 = 0.
Во    втором    наборе    входных    данных    f(2,2)    =    10 − 10    =    0.    Заметим,    что f(1,2) = (10 + 5) − (10 ⊕ 5) = 0, но нам среди максимальных значений f(l,r) нужно найти подотрезок с минимальной длиной.
В четвертом наборе входных данных f(2,3) = (12+8) − (12 ⊕ 8) = 16.
В пятом наборе входных данных есть два правильных ответа, так как f(2,3) = f(3,4) и их длины равны.

 


time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w641
Python1
Комментарий учителя