<PREV Problem:
NEXT>
Solved by 46 users: vi002, JohnJones_001, KZ, fetetriste, tourist, Alexander_Afanasiev, WsemirZ, zloy_mipt, DAV, mage, soseux, dan, Chmeli_BSU, Jacob, Mishunin_Alexander, mazahaka, Agarb, UdH-WiNGeR, RAVEman, defrager, knightry, topspin, sasha_s, LiuChenheng, Philip_PV, chumbalov, Kuznetsov_S, abortmozga.ru, mikhail4021, Dest, ignat, ilnurKh, Losik, JustFun, ripatti, kornakovBSU, stupid_coder, Darii, vitar, NIGHTFIT, mikelan, mathematic, Nevermore, Robert_Gerbicz, murphy, LOD.
UserDateAttemptTimeCMSC
vitar22 may 2011C++1300.43223 
vitar22 may 2011C++1200.42225 
LOD31 may 2017C++100.87249 
Philip_PV31 jul 2009C++900.40251 
ignat25 apr 2010C++300.45255 
Philip_PV31 jul 2009C++800.40265 
Philip_PV31 jul 2009C++600.40276 
soseux09 oct 2008C++300.77276 
Darii19 dec 2010C++1400.37283 
Dest23 apr 2010C++400.34293 
mage01 oct 2008C++200.76302 
vi00223 sep 2008C++300.72308 
stupid_coder02 dec 2010C++400.72308 
Languages
C++
40
Java
4
Kylix
2
C
2
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

Прогноз погоды

Time limit = 2 second(s)

Memory limit = 64 Mb

Физкультурник, в принципе, добрый малый. Но у него свои корыстные цели. Спортивный корпус закупил свою собственную метеостанцию, и физкультурник хочет, чтобы Вы помогли ему наладить прогноз температуры на завтра и выводить онлайновую информацию на сайте спортивного корпуса МФТИ.

Для предсказания температуры метеостанция ежесекундно снимает значение температуры. Температура на датчике измеряется в некоторых условных единицах, так что значение температуры является всегда целым числом и лежит в диапазоне [-20000000, 20000000].

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

Для этого нужно написать программу, которая считывет числа и периодически, через каждые M чисел, для последних N чисел, выдавала бы значение минимального и максимального числа, а также значение медианы, то есть числа, которое стояло бы в ячейке с индексом ⌊(N-1)/2 ⌋ (индексы начинаются с нуля), если N чисел упорядочить в массиве по возрастанию.

Input Первая строка входа содержит числа N и M. 1 ≤ N, M ≤ 200000.

Затем идут целые числа a0, a1, a2, … из диапазона [-20000000, 20000000], разделённые произвольным количеством пробельных символов. Их число заранее неизвестно, но оно не превосходит 200000. Их необходимо считывать до конца входа.

Output Выход должен содержать несколько строчек, в каждой из которых указано три целых числа : минимальное, медиана и максимальное из некоторого диапазона входных чисел. Строке с номером K (K = 0, 1, 2, …) соответствует диапазон из N чисел: aK⋅ M, aK⋅ M+1, …, aK⋅ M+N-1.

Последовательность {ai} не обязательно обрывается на элементе с индексом вида aK⋅ M+N-1 для некоторого K. В этом случае для последних чисел статистики не выводятся. Могут быть разные случаи: N < M, N > M, N = M.

Input#1
5 3
1 2 3 4 5 6 7
8 9 10 11 
Output#1
1 3 5
4 6 8
7 9 11
Input#2
4 1
10 1 9 2 8 3 7 4 6 5 
Output#2
1 2 10
1 2 9
2 3 9
2 3 8
3 4 8
3 4 7
4 5 7

Author:
Ворожцов Артем, индивидуальное первенство МФТИ по программированию, 21 сентября 2008 года
20 сентября 2008

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 18.210.24.208