Fişierul intrare/ieşire:nozero.in, nozero.outSursăONI 2019, clasa a 10-a, ziua 2
AutorBogdan IordacheAdăugată deTincaMateiTinca Matei TincaMatei
Timp execuţie pe test0.1 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Nozero

Se dau N şi K.

Cerinţă

Se cere să se determine pentru a K-a permutare în ordine lexicografică, a şirului 1, 2, 3, ..., N, câte poziţii p există astfel încât nici p şi nici valoarea de pe poziţia p nu conţin cifrea zero.

Date de intrare

Pe prima linie din fişierul de intrare nozero.in se află scrise numerele N şi K, separate printr-un spaţiu.

Date de ieşire

În fişierul de ieşire nozero.out se va scrie valoarea căutată.

Restricţii

  • 1 ≤ N, K ≤ 109
  • Pentru teste valorând 16 puncte 1 ≤ K, N ≤ 1.000
  • Pentru alte teste valorând 33 puncte N ≤ 500.000
  • Pentru alte teste valorând 14 puncte K = 1
  • Un şir p1, p2, ..., pN este mai mix lexicografic decât alt şir q1, q2, ..., qN, dacă există o poziţie i, 1 ≤ i ≤ N, astfel încât pi < qi şi pj = qj, pentru orice j, 1 ≤ j < i.

Exemplu

nozero.innozero.out
10 2
8

Explicaţie

A doua permutare în ordine lexicografică de lungime 10, este 1 2 3 4 5 6 7 8 10 9.
Valoarea 9 nu conţine cifra 0, dar se află pe poziţia 10, care conţine cifra 0.
Valoarea 10, de la poziţia 0, conţine cifra 0.
Toate celelalte 8 valori nu conţin cifra 0 şi se află pe poziţii care nu conţin cifra 0.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?