Col·leccionista d'ànimes


Enviar solució

Punts: 20 (parcial)
Temps Límit: 1.0s
Límit de memòria: 256M

Autor/a:
tipus del problema
Cerca Binària, Combinatòria, Matemàtiques, Optimització, Ordenació, Timelimit!
Categoria
Categoria Especial
Llenguatges permesos
Bash, C Hashtag, C++, Haskell, Java, Kotlin, PHP, Python

Cictor és un home que col·lecciona ànimes. Originalment, ell té x ànimes. També hi ha \(n\) enemics numerats amb nombres enters de l'\( 1 \) a l'\( n \). L'enemic \( i \) té \( ai \) ànimes.

Cictor va determinar una permutació \(P\). Una permutació és una llista que consta de \(n\) nombres enters diferents d'\(1\) a \(n\) en ordre arbitrari. Per exemple, {2,3,1,5,4} és una permutació, però {1,2,2} no és una permutació (2 apareix dues vegades en la llista) i {1,3,4} tampoc és un permutació (perquè n = 3 però hi ha el número 4 a la llista).

Després d'això, farà \(n\) duels amb els enemics amb les següents regles:

Si Cictor té igual o major nombre d'ànimes que l'enemic \(Pi\), guanya el duel i obté 1 ànima. En cas contrari, perd el duel i no obté res. Les ànimes que obtingui Cictor s'utilitzaran en els pròxims duels. Cictor vol guanyar tots els duels. Quantes permutacions P vàlides ha?

Aquest problema va ser fàcil i no va ser interessant per a \(Sr.M\), qui és amic de Cictor. I Cictor va fer el següent problema a partir de la idea anterior:

Definim \(f (x)\) com el nombre de permutacions vàlides per al sencer x.

Se li dóna \(n\), \(a\) i un nombre primer \(p≤n\). Cridem xicle a un enter positiu \(x\), si el valor \(f (x)\) no és divisible per \(p\). Trobeu tots els enters bons \(x\).

La teva tasca és resoldre el nou problema de Cictor.

Entrada


La primera línia conté dos nombres enters \(n\), \(p\) \((2≤p≤n≤2000)\). Es garanteix que el nombre p és primer (té exactament dos divisors \(1\) i \(p\)).

La segona línia conté n nombres enters \(a1, a2, ..., an (1≤ai≤2000)\), que és la llista d'enemics amb el número d'ànimes que té cadascun.

Sortida


A la primera línia, imprimiu el nombre d'enters xicles \(x\).

En la segona línia, mostri tots els sencers xicles \(x\) en ordre ascendent.

Es garanteix que el nombre de sencers xicles \(x\) no superi els \(10^5\).

Exemple d'entrada

3 2
3 4 5

Exemple de sortida

1
3

Ajuda

En la primera prova, \(p = 2\).

  • Si \(x≤2\), no hi ha permutacions vàlides per Cictor. Llavors \(f (x) = 0\) per a tot \(x≤2\). El nombre \(0\) és divisible per \(2\), de manera que tots els sencers \(x≤2\) no són xicles.
  • Si \(x = 3\), {1,2,3} és l'única permutació vàlida per Cictor. Llavors \(f (3) = 1\), llavors el nombre \(3\) és xicle.
  • Si \(x = 4\), {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1} són totes permutacions vàlides per Cictor. Llavors \(f (4) = 4\), llavors el nombre 4 no és xicle.
  • Si \(x≥5\), les 6 permutacions són vàlides per Cictor. Llavors \(f (x) = 6\) per a tot \(x≥5\), llavors tots els sencers \(x≥5\) no són xicles.

Llavors, l'únic xicle nombre es \(3\).


Comentaris


  • 1
    administrador  comentat a les oct. 30, 2023, 7:34 p.m.

    Aquest és molt divertit un cop aconsegueixes desxifrar la descripció :)