Tutte le sfide
Media 0 risolte 0% di accettazione

Vincitori della lotteria

Conta quanti biglietti della lotteria hanno indovinato 0, 1, 2, ... numeri vincenti.

Cosa imparerai

  • Usare un insieme per verificare rapidamente l'appartenenza
  • Contare i numeri indovinati da ogni biglietto
  • Costruire un istogramma dei punteggi

Problema

Per una raccolta fondi, la scuola organizza una lotteria a numeri. L'estrazione sceglie alcuni numeri vincenti distinti, e ogni biglietto contiene la stessa quantità di numeri distinti. L'ordine dei numeri sul biglietto non conta: il punteggio di un biglietto è quanti dei suoi numeri sono vincenti. Per stabilire i premi, gli organizzatori devono sapere quanti biglietti hanno ottenuto ciascun punteggio.

Implementa ticket_lottery(winning, tickets).

Input

winning: i numeri vincenti, tutti distinti.

tickets: i biglietti; ogni riga contiene i numeri distinti di un biglietto ed è lunga quanto winning.

Output

Restituisci una lista di lunghezza len(winning) + 1 in cui la posizione k contiene il numero di biglietti che hanno indovinato esattamente k numeri vincenti.

Vincoli

1 ≤ len(winning) ≤ 10

0 ≤ numero di biglietti ≤ 5 000

1 ≤ ogni numero ≤ 99

Esempi

Esempio 1
Input:
winning = [3, 11, 20]
tickets = [
    [3, 11, 20],
    [20, 5, 7],
    [1, 2, 4],
    [11, 3, 9]
]

Output atteso:
expected = [1, 1, 1, 1]
Input:
std::vector<long long> winning = {3, 11, 20};
std::vector<std::vector<long long>> tickets = {
    {3, 11, 20},
    {20, 5, 7},
    {1, 2, 4},
    {11, 3, 9}
};

Output atteso:
std::vector<long long> expected = {1, 1, 1, 1};
Input:
long[] winning = new long[] {3, 11, 20};
long[][] tickets = new long[][] {
    new long[] {3, 11, 20},
    new long[] {20, 5, 7},
    new long[] {1, 2, 4},
    new long[] {11, 3, 9}
};

Output atteso:
long[] expected = new long[] {1, 1, 1, 1};

Spiegazione

I biglietti indovinano 3, 1, 0 e 2 numeri, quindi ogni punteggio da 0 a 3 compare una volta: [1, 1, 1, 1].

Esempio 2
Input:
winning = [7, 8]
tickets = [
    [8, 7],
    [7, 1],
    [1, 7]
]

Output atteso:
expected = [0, 2, 1]
Input:
std::vector<long long> winning = {7, 8};
std::vector<std::vector<long long>> tickets = {
    {8, 7},
    {7, 1},
    {1, 7}
};

Output atteso:
std::vector<long long> expected = {0, 2, 1};
Input:
long[] winning = new long[] {7, 8};
long[][] tickets = new long[][] {
    new long[] {8, 7},
    new long[] {7, 1},
    new long[] {1, 7}
};

Output atteso:
long[] expected = new long[] {0, 2, 1};

Spiegazione

Un biglietto ha entrambi i numeri (l'ordine non conta) e due ne hanno uno: [0, 2, 1].

Come affrontarlo

Prova prima da solo, poi apri un suggerimento alla volta.

Suggerimento 1

Metti i numeri vincenti in un insieme oppure in un array di booleani indicizzato per numero.

Suggerimento 2

Conta i numeri indovinati da un biglietto, poi aggiungi 1 al contenitore di quel punteggio.

Suggerimento 3

Il risultato ha un contenitore in più rispetto ai numeri vincenti.

Complessità attesa

tempo O(t × k), spazio aggiuntivo O(k)

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.