Masala #0182

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.

 

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

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.