Grafos rueda

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 20M

Author:

leocar

Problem type

Allowed languages

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

Para cada natural $N \ge 3$ ~N \ge 3~ se define el grafo rueda de $N$ ~N~ rayos como el grafo $W_n$ ~W_n~ con $N + 1$ ~N + 1~ vértices $v0, v1, v2, ...,$ ~v0, v1, v2, ...,~ vn tal que $v0$ ~v0~ es el centro de una circunferencia y $v1, v2, ..., vn$ ~v1, v2, ..., vn~ son $N$ ~N~ puntos diferentes de la circunferencia, ordenados según el sentido horario. Las aristas del grafo son únicamente las del ciclo $(v1, v2, ..., vn, v1)$ ~(v1, v2, ..., vn, v1)~ y las aristas rayos: es decir los incidentes en $v0$ ~v0~ que lo unen con cada uno de los vértices del ciclo. (Ver dibujos de $W_3$ ~W_3~, $W_4$ ~W_4~ y $W_5$ ~W_5~ en la figura $1$ ~1~.)

Figura: Los grafos rueda con $3$ ~3~, $4$ ~4~ y $5$ ~5~ rayos.

descripción aqui

Tarea

Confeccione un programa para determinar cuántos ciclos de longitud $K$ ~K~ ( $K \ge 3$ ~K \ge 3~) tiene $Wn$ ~Wn~.

Especificación de la Entrada

La entrada estándar contiene en la primera un numero natural T. En las siguientes T líneas aparecerán dos números naturales K y N, separados por un simple espacio, donde K es la cantidad de ciclos a buscar el el grafo W de N + 1 vértices.

Especificación de la Salida

La salida estándar contendrá T líneas. En cada una de ellas deberá aparecer la cantidad de ciclos encontrado.

Restricciones y especificaciones

$1 \le T \le 1 000$ ~1 \le T \le 1 000~
$1 \le K, N \le 1 000 000 000$ ~1 \le K, N \le 1 000 000 000~
El $15$ ~15~ % de los puntos $K \ge N + 1$ ~K \ge N + 1~
El $15$ ~15~ % de los puntos $K = N$ ~K = N~
El $15$ ~15~ % de los puntos $3 \le k \le N$ ~3 \le k \le N~
El $15$ ~15~ % de los puntos $K = N + 1$ ~K = N + 1~
El $40$ ~40~ % de los puntos restantes otros casos
El $50$ ~50~ % de los casos $T$ ~T~, $N$ ~N~ y $K \le 100$ ~K \le 100~

Ejemplo de Entrada

Ejemplo de Salida

4
5
0

Explicación

Explicación de la salida $W(k, n)$ ~W(k, n)~

W(3,3): El ciclo en la circunferencia y los cuatro ciclos $(v0, v1, v2, v0), (v0, v2, v3, v0), (v0, v3, v1, v0),(v1,v2,v3,v1)$ . Luego $W3$ ~W3~ tiene $4$ ~4~ ciclos de longitud $3$ ~3~.

W(4,5): Los cinco ciclos $(v0, v1, v2, v3, v0), (v0, v2, v3, v4, v0), (v0, v3, v4, v5, v0), (v0, v4, v5, v1, v0),(v0, v5, v1, v2, v0)$ . Luego W5 tiene $5$ ~5~ ciclos de longitud $4$ ~4~.

W(6,4): Hágase la figura de $W4$ ~W4~. Todos los ciclos de W4 tienen longitud a lo sumo longitud $5$ ~5~ (es decir no se pueden elegir más de $5$ ~5~ aristas consecutivas de forma que cierren un ciclo). Luego $W4$ ~W4~ tiene $0$ ~0~ ciclo de longitud $6$ ~6~.

Comments

1

leocar commented on Feb. 12, 2020, 4:45 p.m. ← edited →

Arreglado el caso del ejemplo 1 donde dice que son 4 los ciclos de longitud 3.

0

leocar commented on Feb. 12, 2020, 4:28 p.m.

Donde dice K es la cantidad de ciclos, debe ser los ciclos de de longitud K deben de buscar