ЦІКАВИЙ ПОЛІТ "Летіти в подорож на одну планету – це досить нудно”, – подумала Элен і прийняла рішення завітати й до інших цікавих планет. Всі інопланетяни знають, що будь-яка планета має таку характеристику як привабливість. Звісно, коли планувала мандрівку Элен обирала най-найпривабливішу планету. А Эдик, як завжди, склав список з N планет, повз які вони будуть пролітати, та розташував їх у порядку огляду. Але виявилось, що не все так просто. Справа у тому, що задля найкращих вражень від подорожі потрібно відвідати максимальну кількість планет, ще й відвідувати їх слід лише по неспадаючій їх привабливості. До того ж, слід обирати для відвідування такі планети, привабливість яких строго більше ніж X (за проханням Эльберта). Оскільки, жоден з інопланетян неспроможний обрати таку послідовність планет, щоб їх подорож була ідеальною, то вони попросили вас зробити це. Вхідні дані: В першому рядку дано два числа N та X – кількість планет у списку Эдика та поріг привабливості планет за думкою Эльберта, відповідно. В другому рядку задано N цілих чисел ai, де ai – привабливість i-ої планети. 1 <= N <= 1e5, -1e9 <= X <= 1e9, -1e9 <= ai <= 1e9. Вихідні дані: В першому рядку виведіть максимальну кількість планет, яку зможуть відвідати інопланетяни. В другому рядку виведіть індекси цих планет (зі списку Эдика). Якщо таких послідовностей декілька – виведіть будь-яку. Якщо інопланетяни не зможуть відвідати жодної планети, то виведіть -1.
Приклад:
Вхідні дані Вихідні дані
4 1 2
1 3 2 5 3 4
//Pascal ABC.NET 3.1 сборка 1219
Type
ty=record
valu:integer;
count:integer;
end;
Const
n=3;
Var
ma:array[1..n,1..n] of integer;
tyar:array of ty;
se:set of integer;
i,j,z,k,MaxCount:integer;
begin
randomize;
se:=[];
k:=0;
MaxCount:=integer.MinValue;
writeln('Matrix:');
for i:=1 to n do
begin
for j:=1 to n do
begin
ma[i,j]:=random(-10,10);
write(ma[i,j]:4);
if not(ma[i,j] in se) then
begin
inc(k);
setlength(tyar,k+1);
tyar[k].valu:=ma[i,j];
tyar[k].count:=1;
se:=se+[ma[i,j]];
end
else
for z:=1 to k do {O(n^3) в худшем случае - нормальные люди ненавидят это}
if tyar[z].valu=ma[i,j] then
begin
inc(tyar[z].count);
break;
end;
end;
writeln;
end;
for i:=1 to k do
if MaxCount<tyar[i].count then MaxCount:=tyar[i].count;
writeln('Res:');
for i:=1 to k do if tyar[i].count=MaxCount then writeln(tyar[i].valu);
end.
Пример работы программы:
Matrix:
-7 -2 10
8 0 -2
6 10 1
Res:
-2
10