Задача J. Бирено парти



Дата22.10.2018
Размер24 Kb.
#92929
ТипЗадача
НОВ  БЪЛГАРСКИ  УНИВЕРСИТЕТ

Департамент Информатика

XVIIІ РЕПУБЛИКАНСКА СТУДЕНТСКА ОЛИМПИАДА ПО ПРОГРАМИРАНЕ

13 - 14 май 2006 г.



Задача J. БИРЕНО ПАРТИ

Смарти е програмист, който предпочита да си лежи, отколкото да пие бира, което е второто най-важно нещо в живота му (и чак тогава идва ред на програмирането). Един ден той бил поставен пред следния проблем. На бирено парти домакините били подредили в много дълга редица N бутилки бира от K различни вида. Тъй като бил колекционер на празни бирени бутилки и нямал в колекцията си нито една бутилка от тези K вида, той трябвало да направи нещо, за да си ги занесе в къщи. Но единственият начин да си вземе някакво количество бирени бутилки бил, да избере една непрекъсната подредица от тях и да ги изпие. Тъй като е много мързелив и му е много трудно да отваря бутилките, решил да избере най-късата непрекъсната подредица от бутилки, която съдържа поне по една от всичките K различни вида. Смарти е вече достатъчно пиян (нали е на бирено парти) и не може да си спомни алгоритъма, който решава тази задача. Затова ще трябва да му помогнете, като напишете програма J, която определя позициите в редицата на първата и последната бутилки от най-късата непрекъсната подредица, изпълняваща условието. Ако има няколко такива подредици, програмата трябва да намери тази, която се среща най-рано в редицата.


Вход


Програмата трябва да прочете от първия ред на стандартния вход броят T на ситуациите, които трябва да обработи. Данните за всяка ситуация са в два реда на стандартния вход. На първия са записани числата N и K (1 £ N £10000000, 1 £ K £13000, N.K £ 170000000) разделени с интервал, а на втория – N числа (от 1 до K), разделени с по един интервал.

Изход


За всяка ситуация програмата трябва да изведе на стандартния изход две числа – номерата на началната и крайната бутилки в подредицата, която трябва да изпие Смарти.

ПРИМЕР

Вход:

2

5 3



1 3 3 2 1

5 3


1 1 2 2 3
Изход:

3 5


2 5
Каталог: 2006
2006 -> Бележки по последните изменения и допълнения на зут асен Запрянов, адвокат от Пловдив
2006 -> Трети клас 15 април 2006г., Силистра
2006 -> Министерство на правосъдието агенция по вписванията
2006 -> Център за култура и дебат „червената къща” годишен отчет 2006
2006 -> Отчет за дейността на Висшия адвокатски съвет за периода 25 2005 24 2006 г
2006 -> I. Дъщерни предприятия на “Софарма” ад, включени в предварителния консолидирания отчет към 31. 12. 2006 г : “
2006 -> Указания за писане: Основни принципи и задължителни правила Професор Дейвид Пост Юли 2006 Превод: Катина Панчева, ІV курс Европеистика
2006 -> Едно от основанията за прекратяване на наказателното производство е посоченото в чл. 24, ал. 1, т
2006 -> Осъществяването на индивидуалното трудово правоотношение
2006 -> 1. Обхват на признаването


Сподели с приятели:




©obuch.info 2022
отнасят до администрацията

    Начална страница