Super Ugly Number

O'ta xunuk son (Super Ugly Number) deb tub ko'paytuvchilari berilgan primes to'plamidagi sonlardan iborat bo'lgan musbat butun songa aytiladi.

Sizga n va primes massivi berilgan. n-chi o'ta xunuk sonni toping va qaytaring.

Masalan, primes = [2, 7, 13, 19] bo'lsa, O'ta xunuk sonlar: [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, ...].

1 ning tub ko'paytuvchilari yo'q, u kichik holat sifatida kiradi.

func solve(n int, primes []int) int {
    // ...
}

Misollar

Input: n = 12, primes = [2,7,13,19]
Output: 32
Tushuntirish: Ro'yxat: [1,2,4,7,8,13,14,16,19,26,28,32,...]. 12-chi son 32.

Input: n = 1, primes = [2,3,5]
Output: 1

Input: n = 5, primes = [2, 3]
Output: 6

Input: n = 10, primes = [2, 7, 13, 19]
Output: 26

Maslahatlar

1. Har bir yangi "xunuk son" avvalgi xunuk sonlardan birini biror tub songa ko'paytirish orqali hosil bo'ladi — shuning uchun har bir tub son uchun alohida ko'rsatkich (pointer) saqlab boruvchi dinamik dasturlash (DP) haqida o'ylab ko'ring.
2. dp[0]=1 dan boshlang va har bir primes[j] uchun alohida ko'rsatkich (pointers[j]) yuriting; har qadamda barcha j lar bo'yicha dp[pointers[j]] * primes[j] qiymatlarining eng kichigini keyingi dp elementi sifatida oling, so'ng aynan shu eng kichik qiymatni bergan barcha j larning ko'rsatkichini bittaga oshiring (dublikatlarning oldini olish uchun).