Col·leccionista d'ànimes


Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types
Cerca Binària, Combinatòria, Matemàtiques, Optimització, Ordenació, Timelimit!
Category
Categoria Especial
Allowed languages
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\).


Comments


  • 1
    administrador  commented on Oct. 30, 2023, 7:34 p.m.

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