Masala #0182

Xotira 32 MB Vaqt 2000 ms
14

Adizning birlashtirish algoritmi

Laziz Adizga V massivlar to’plamini M massivga birlashtirish uchun berdi. Adiz massivlarni shunchaki ketma-ket birlashtirishni xoxlamay, o’zi massivni birlashtirishning boshqacha usulini o’ylab topdi. Uning birlashtirish usuli quyidagicha:

  • M=[] bo’sh massivni yaratib oladi

  • k=V massivlar to’plamidagi massivlar soni

  • V to’plamda kamida 1 ta bo’sh bo’lmagan massiv mavjud bo’lsa

    • T = [] bo’sh massivni oladi

    • i = 1

    • i <= k shart qanoatlansa

      • agar Vi bo’sh bo’lmasa

        • Vi ning birinchi elementini o’chirib, uni T massivga qo’shadi

      • i = i + 1

    • T bo’sh bo’lib qolmaguniga qadar

      • T dan eng kichik elementni o’chirib M ning davomidan qo’shadi

  • M ni chop etadi

Quyidagi misolda ko’ramiz: V={[3, 5], [1], [2, 4]} bo’lsin

Shunda Adiz quyidagicha amallar ketma-ketligini bajaradi:

Laziz o’zidagi V massivlar to’plamini Adizga berganidan so’ng Adiz o’zining birlashtirish algoritmi orqali massivlarni birlashtirib hosil bo’lgan M massivni Lazizga berdi. Bir necha kundan so’ng Laziz o’zidagi V massivlar to’plamini yo’qotib qo’ydi, unda hozir Adiz birlashtirib bergan M massiv bor xolos. Endi u o’zining V to’plamini qayta tiklamoqchi.

 


Kiruvchi ma'lumotlar:

Birinchi satrda bitta butun son, N(1 <= N <= 1200), keyingi satrda N ta butun son, M(1 <= Mi <= N) massiv elementlari kiritiladi.


Chiquvchi ma'lumotlar:

Laziz o’zining V massivlar to’plamini necha xil ko’rinishda qayta tiklashi mumkinligini aniqlang. Bu son juda katta bo’lishi mumkin, siz shu sonning 109+7 ga bo’lgandagi qiymatini chop eting.


Misollar
# input.txt output.txt
1
3
1 2 3
4
2
3
2 3 1
3
Izoh:

1-test

1-usul

 

2-usul

 

3-usul

 

4-usul

1

2

3

 

1

3

 

 

1

 

 

 

1

 

 

 

 

 

 

2

 

 

 

2

3

 

 

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2-test

1-usul

 

2-usul

 

3-usul

 

 

 

 

2

3

1

 

2

1

 

 

2

 

 

 

 

 

 

 

 

 

 

3

 

 

 

3

1