Yo`nalishlar
Hozirda online

Statistika

Masalalar soni: 909

Foydalanuvchilar soni: 8824

Jo'natishlar soni: 714622

Muhokama yozuvlari: 4541

Yangiliklar soni: 98

Yangiliklar izohlari: 1177


So'ngi izohlar

689. Saralash
Vaqt limiti: 1 sekund
Xotira limiti: 64 MB

  Bilamizki saralash algoritmlarining turlari juda ham ko’p. Lekin bu algoritmlar faqat sonlarni hech qanday qonuniyatga bo’ysunmasdan saralay oladi. Lekin savol tug’iladi, agarda sonlarni almashtirishlarda cheklovlar bo’lsa, bunday sonlarni qanday saralash mumkin?

            Sizga N soni va 1 dan N gacha bo’lgan sonlardan tashkil topgan perestanovka berilgan. – son o’zidan a[i] masofada turgan element bilan almasha oladi holos, ya’ni i – o’rinda turgan son j – o’rindagi son bilan almashtirilishi mumkin, qachonki |i - j| = a[i]. Siz ushbu cheklovlar orqali perestanovkaning 1-leksikografik ko’rinishiga olib kelish mumkin yoki yo’qligini tekshirishinggiz kerak bo’ladi.

 

Kiruvchi ma’lumotlar: Birinchi satrda N soni (1 ≤ N ≤ 1000000) beriladi. Ikkinchi satrda 1 dan N gacha bo’lgan sonlar bitta probel bilan ajratilgan holda beriladi. Uchinchi satrda esa N ta elementdan tashkil topgan a[] massivi elementlari bitta probel bilan ajratib beriladi.

Chiquvchi ma’lumotlar: Agarda perestanovkani so’ralgan holatga olib kelib bo’lsa “YES” so’zini, aks holda “NO” so’zini chiqaring.

 

¹

Kiruvchi ma’lumotlar

Chiquvchi ma’lumotlar

1

4

4 3 2 1

1 1 1 1

YES

2

7

4 3 5 1 2 7 6

4 6 6 1 6 6 1

NO

 

 

Tayyorladi: Yo'ldoshboy Sultonov
Online Contest#11
Mening urinishlarim(0) Muhokama (2) Jo'natish Eng yaxshi yechimlar Barcha muvaffaqiyatli urinishlar(15) Barcha urinishlar(80)