Решение задачи Красивые числа с Codeforces
Без пояснения   Просмотров: 64
Вам дана перестановка p=[p1,p2,…,pn] целых чисел от 1 до n. Назовем число m (1≤m≤n) красивым, если существует два индекса l,r (1≤l≤r≤n), таких что [pl,pl+1,…,pr] это перестановка чисел 1,2,…,m.
Например, пусть p=[4,5,1,3,2,6]. В этом случае числа 1,3,5,6 красивые, а 2,4 нет. Это так, потому что:
если l=3 и r=3 мы получим перестановку [1] для m=1;
если l=3 и r=5 мы получим перестановку [1,3,2] для m=3;
если l=1 и r=5 мы получим перестановку [4,5,1,3,2] для m=5;
если l=1 и r=6 мы получим перестановку [4,5,1,3,2,6] для m=6;
невозможно взять некоторые l и r, так что [pl,pl+1,…,pr] будет перестановкой чисел 1,2,…,m для m=2 и для m=4.
Вам дана перестановка p=[p1,p2,…,pn]. Для всех m (1≤m≤n) определите, является ли это число красивым или нет.
Например, пусть p=[4,5,1,3,2,6]. В этом случае числа 1,3,5,6 красивые, а 2,4 нет. Это так, потому что:
если l=3 и r=3 мы получим перестановку [1] для m=1;
если l=3 и r=5 мы получим перестановку [1,3,2] для m=3;
если l=1 и r=5 мы получим перестановку [4,5,1,3,2] для m=5;
если l=1 и r=6 мы получим перестановку [4,5,1,3,2,6] для m=6;
невозможно взять некоторые l и r, так что [pl,pl+1,…,pr] будет перестановкой чисел 1,2,…,m для m=2 и для m=4.
Вам дана перестановка p=[p1,p2,…,pn]. Для всех m (1≤m≤n) определите, является ли это число красивым или нет.