|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
Hello 2016Ended |
C - Campinatorics
Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)
Alice esta a cargo de uno de los campamentos del parque. El campamento puede ser descrito como una matriz de N * N, donde cada celda tienes espacio para a lo sumo una tienda.
Con el objetivo de acomodar las familias en el campamento hay varias regulaciones que cumpir:
1. Solo familias con 1, 2 o 3 miembros estan permitidas en el campamento. Además cada tienda debe contener miembros de solo una familia,
y una familia no puede acomodarse en varias tiendas.
2. Por razones de seguridad ninguna fila o columna puede tener mas de 3 miembros.
3. Además no debe haber mas de 2 tiendas en ninguna fila o columna.
Adicionalmente Alice conoce que al menos X familias de 3 miembros visitarán el campamento, y habrán suficientes familias de 1 o 2 miembros
para rellenar el campamento.
Por ejemplo estos son campamentos válidos para N=3 y X = 0:
1 2 0 | 3 0 0
0 1 2 | 0 1 2
2 0 1 | 0 2 1
Estos no son campamentos validos para N = 3 y X = 1:
1 2 0 | 0 3 0 | 1 2 0 | 1 1 1
0 1 2 | 3 0 0 | 0 2 0 | 1 1 1
2 0 1 | 0 0 0 | 2 0 1 | 1 1 1
*El primero no es válido porque deberia haber al menos una familia de 3 miembros.
*El segundo no es válido porque el número de personas en la tercera columna(y fila) no es 3.
*El tercero no es válido porque el número de personas en la segunda columna es mayor que 3.
*El último no es válido porque contiene más de dos tiendas por fila o columna.
Alice quiere saber cuántos campamentos válidos hay para un N y X dados.
Input
La primera linea de la entrada contiene un entero T, la cantidad de casos de pruebas.
Cada caso consiste de exactamente dos enteros N y X, el tamaño del campamento y la minima cantidad de familias de 3 miembros respectivamente.
Output
Para cada caso imprima una linea que contenga "Case #X: Y", donde X es el numero del caso empezando por 1 y Y es el numero de posibles campamentos.
*La respuesta puede ser bien grande entonces imprima la solución modulo 1000000007
Limites:
1 <= T <= 200
1 <= N <= 1000000
0 <= X <= N
Sample test(s)
Input
3
2 2
3 1
15 0
Output
Case #1: 2
Case #2: 24
Case #3: 738721209
Hints
En el caso #1 usted tiene dos arreglos distintos del campamento
0 3 | 3 0
3 0 | 0 3