1-kurslar uchun musobaqa #12

Problem Tasks

# Date State
Not Contest

# Date State

F. Pufakchali saralash

Time limit : 1000 ms
Memory limit : 64 mb

1-kurs talabalari endi C++ fanidan saralash algoritmlarini o’rganishni boshlashdi. Birinchi bo’lib pufakchali saralash algoritmini o’rganishdi. Pufakchali saralash usuli O(n2) amal talab qiluvchi algoritmlardan biri. Unda jami n-1 ta iteratsiya bo’lib, har bir iteratsiyada qo’shni elementlar taqqoslanadi va ular noto’g’ri tartibda joylashgan bo’lsa ularning o’rni almashtiriladi. Har bir iteratsiyada navbatdagi eng katta son o’z joyini topib boradi:

     long long k = 0;

     for (int i = n; i >= 2; i--) {

         for (int j = 1; j < i; j++) {

              if (a[j] > a[j+1]) {

                 int t = a[j];

                 a[j] = a[j+1];

                 a[j+1] = t;

                 k++;

              }

         }

     }

  cout<<k;

a massiv birdan boshlab indekslangan. Bu masalada sizning vazifangiz berilgan pufakchali saralash dasturi uchun almashtirishlar soni k ni topishdan iborat.

Kiruvchi ma’lumotlar

Birinchi qatorda n – massiv elementlari soni berilgan(1≤n≤105). Ikkinchi qatorda n ta butun son – a massiv elementlari bitta probel bilan ajratib berilgan. Massiv elementlari modul  jihatdan 109 dan oshmaydi.

Chiquvchi ma’lumotlar

Bitta sonni – masalaning javobini chiqaring.

Misollar

Kiruvchi ma’lumotlar

Chiquvchi ma’lumotlar

1

3

3 1 2

2

 

Tayyorladi: Azat Yusupov