Bingo P36031


Statement
 

pdf   zip

html

Un cartón de bingo contiene 15 números del 1 al 99, ordenados en 3 filas de 5 números cada una, sin que el mismo número aparezca más de una vez. Los jugadores van tachando los números de su cartón a medida que estos salen del bombo. Se premia al primer jugador que tacha todos los números de una de las tres líneas de su cartón (“ ‘!Han cantado línea!”) y al primero que tacha el cartón entero (“ ‘!Han cantado bingo!”). Si varios jugadores cantan línea o bingo a la vez el premio se reparte equitativamente.

En este problema se te da el orden en el que saldrán las 99 bolas del bombo, y se te pida que descubras cuáles de los cartones en juego te interesaría haber comprado, asumiendo que el precio del cartón es de 10 euros y que los premios por cantar línea y bingo son 17 y 28 euros respectivamente. En concreto, deberás resolver varias situaciones parecidas: el orden de salida de las bolas será siempre el mismo, pero en cada situación sólo habrá en juego un cierto subconjunto de los k cartones distintos que tiene la compañía que organiza la partida.

Entrada

La entrada consiste en una línea con el número k de cartones, con 1<k<100. A continuación, y separados por líneas en blanco, se dan los k cartones, los 15 números de cada cartón separados por espacios y distribuidos en 3 líneas de 5.

Le sigue en una línea el número q de situaciones distintas, con 1≤ q≤ 10000. Una situación viene definida por el subconjunto de tamaño n de los k cartones que entran en juego, y viene descrita por el número n (1≤ n ≤ k) y los índices i1, …, in, entre 1 y k, de los n cartones distintos que participan en la situación, todos ellos ocupando la misma línea y separados por espacios. Finalmente, separado por una línea en blanco, se dan los 99 números del bombo en el orden en que salen, separados por espacios y cambiando de línea cada 10 números.

Se te pide que resuelvas 5 entradas como las descritas en menos de 1 segundo.

Salida

Escribe q líneas, una por situación. Cada línea contiene la lista ordenada de aquellos cartones que han entrado en juego en la situación y que convendría haber comprado, o sea, aquellos que recibirán un premio superior a 10 euros. Debes escribir estos índices en orden creciente y separados por espacios. Deja una línea en blanco en caso de no haber ningún cartón rentable.

Public test cases

  • Input

    5

1 2 3 4 97
5 6 7 8 98
9 10 11 12 99

1 2 3 4 97
15 6 7 8 98
9 10 11 12 99

1 2 3 4 97
25 6 7 8 98
9 10 11 12 99

1 2 3 4 97
35 6 7 8 98
9 10 11 12 99

1 2 3 4 97
45 6 7 8 98
9 10 11 12 99

5
1 1
2 1 2
5 1 2 3 4 5
3 1 2 3
4 1 2 3 4

1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99

    Output

    1
1 2

1 2 3
1 2 3 4

  • Input

    5

3 18 35 61 68
4 24 41 64 75
12 30 49 66 82

24 35 60 82 93
29 39 65 86 97
34 48 66 87 99

7 31 38 68 83
12 33 46 75 87
23 34 57 79 97

11 19 45 51 74
15 23 49 55 94
16 42 50 66 99

2 17 28 46 66
7 19 37 49 83
16 23 39 64 96

7
1 3
2 5 4
3 3 1 2
2 4 3
4 3 5 4 1
5 1 2 3 4 5
4 1 4 2 3

6 48 97 8 19 66 49 42 95 11
93 51 79 40 7 47 80 26 37 44
86 89 25 72 17 31 15 58 76 57
46 5 61 62 1 4 23 30 55 2
9 90 64 56 12 91 24 45 21 39
99 75 83 32 29 78 59 16 22 13
94 84 77 27 33 85 81 53 69 60
28 68 67 73 87 70 35 10 43 52
63 36 65 38 3 14 50 92 34 96
18 20 71 74 54 41 88 98 82

    Output

    3
5
3
3 4
3 5
3 5
3 4
    • Information
    Author
    Omer Giménez
    Language
    Spanish
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++