Permutaciones casi idénticas

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 64M

Authors:

sanchezIII, FrankHG

Problem type

Allowed languages

Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

Una permutación $p$ ~p~ de tamaño $n$ ~n~ es un arreglo donde cada entero desde $1$ ~1~ hasta $n$ ~n~ aparecen exactamente una sola vez. Se le llama a una permutación casi identica si existe un mínimo de $n-k$ ~n-k~ índices $i (1 \leq i \leq n)$ ~i (1 \leq i \leq n) ~ tal que $p[i] = i$ ~p[i] = i~. Tu tarea es contar el número de permutaciones casi identicas para los números $n$ ~n~ y $k$ ~k~.

Entrada

La primera linea contiene dos enteros $n$ ~n~ y $k$ ~k~ $(4 \leq n \leq 1000, 1 \leq k \leq 4)$ .

Salida

Imprima el número de permutaciones casi identicas para los números $n$ ~n~ y $k$ ~k~.

Ejemplo 1 de Entrada

4 1

Ejemplo 1 de Salida

Ejemplo 2 de Entrada

4 2

Ejemplo 2 de Salida

Ejemplo 3 de Entrada

5 3

Ejemplo 3 de Salida

Ejemplo 4 de Entrada

5 4

Ejemplo 4 de Salida

Comments

0

Pimienta commented on Aug. 3, 2021, 8:40 p.m.

Asere me sale q ningún juez está disponible para este problema y no pueo enviar mi solución Esperemos q esto never pase en un concurso en vivo

0

aniervs commented on April 17, 2020, 12:52 p.m.

Los Admin deberían revisar el caso de prueba 17, creo que está mal.

0

josed commented on April 17, 2020, 10:37 p.m.

En efecto, la entrada contenía caracteres extraños por lo que fallaba la lectura. Lo curioso es que los que declararon $n$ ~n~ y $k$ ~k~ como variables globales no tuvieron problema ya que $n$ ~n~ y $k$ ~k~ se quedaban con valor $0$ ~0~ y la respuesta con esos valores coincidía con la respuesta para ese caso. Gracias por avisar.

0

Sekai02 commented on April 14, 2020, 11:01 p.m.

Alguien me podria dar alguna idea de como puedo resolver este ejercicio?

3

aniervs commented on April 15, 2020, 8:30 p.m.

Hay varias formas de hacerlo. Te voy a explicar una: Primero, digamos que $f(i)$ ~f(i)~ es la cantidad de permutaciones de $i$ ~i~ elementos distintos tal que ninguno caiga en su posición, esto se llama desarreglo, después veremos cómo hallarlo. Ahora iteramos por $i\in[n-k,n]$ ~i\in[n-k,n]~ y queremos contar cuántas permutaciones hay con exactamente $i$ ~i~ elementos en su posición correspondiente, podemos elegir estos $i$ ~i~ elementos de $C_i^n$ ~C_i^n~ formas diferentes, donde $C_i^n$ ~C_i^n~ es la cantidad de formas de elegir $i$ ~i~ elementos de $n$ ~n~ disponibles (esto se da en el aula, por lo que no lo voy a explicar, de todas formas si es necesario me preguntas y lo explico); ahora por cada una de esas formas los restantes $n-i$ ~n-i~ elementos deben ser permutados sin que caigan en su posición, hay $f(n-i)$ ~f(n-i)~ formas de hacerlo, por tanto la solución es:

$\displaystyle \sum_{i=n-k}^n C_i^n\cdot f(n-i)$

Ahora para hallar $f()$ ~f()~, como $k\le 4$ ~k\le 4~ podemos generar todas estas permutaciones.