Tag Archives: algorithm

Per un pugno di baht

L’incredibile Hulk si trova in Tailandia e purtroppo ha un carattere irascibile: ha rotto diverse macchine automatiche per distribuire le merendine perché non erano in grado di fornirgli il resto.
Per prevenire l’ira di Hulk in tali situazioni, la ditta costruttrice ha deciso di predisporre un sistema centrale che sia in grado di calcolare, per ciascuna di tali macchine, il minimo resto che la macchina stessa non è in grado di fornire.
Le monete tailandesi (i baht) che sono presenti nelle macchine possono essere di qualsiasi taglia (1 baht, 2 baht, 3 baht, ecc.) e quantità.

Possono essere combinate in qualsiasi modo: ad esempio, il resto di 5 baht non può essere dato se la macchina contiene una moneta da 1 baht e 2 monete da 3 baht (in questo caso il più piccolo resto che non può essere dato è 2).

Con 6 monete da 1 baht e 2 monete da 2 baht, è invece possibile fornire il resto di 5 baht in vari modi (in questo caso il resto più piccolo resto che non può essere dato è 11).

Il tuo compito è di aiutare la ditta a calcolare, per un certo numero di macchine, qual è il minimo resto che ciascuna macchina non è in grado di fornire.

Dati di input

Il file input.txt è composto da 2P+1 righe, dove P è il numero di macchine su cui valutare il resto.
Per ogni macchina, la ditta presenta la corrispondente sequenza di monete e chiede il minimo resto che la macchina non è in grado di fornire.
Sulla prima riga si trova P, il numero di macchine.
Le rimanenti righe sono così composte.
Per 1 ≤ i ≤ P, le righe 2i e 2i+1 contengono le informazioni per la i-esima macchina distributrice: la riga 2i contiene Ni, il numero di monete presenti nella macchina; la riga successiva (2i+1), contiene la sequenza di valori M1, M2, …, MNi delle monete presenti nella macchina, separati l’un l’altro da uno spazio.
I valori delle monete sono interi positivi.

Per esempio, se la seconda riga del file contiene il numero 7 e la terza riga i numeri 10 2 14 1 13 2 3, questo significa che nella prima macchina sono presenti 7 monete.
Siccome le monete vanno inserite una alla volta, risulta una moneta da 10 bath, poi una da 2 bath, poi una da 14 baht, una da 1 bath, una da 13 bath, ancora una da 2 bath e, infine, una da 3 bath.
In tal caso, il minimo resto che la macchina non riesce a restituire è di 9 baht.

Dati di output

Il file output.txt è composto da P righe.
Sulla i-esima riga (con 1 ≤ i ≤ P) si deve trovare il minimo resto che la i-esima macchina non può fornire.

Assunzioni

  • 1  P  1000
  • 1  Ni ≤ 10000 per ogni i
  • 1  Mj < 220 per ogni j
  • Per ciascuna macchina, la somma delle monete nella rispettiva sequenza è sempre inferiore a 231

Esempi di input/output

input.txt output.txt
2
7
10 2 14 1 13 2 3
9
1 16 2 1 23 18 1 4 3
9
13

Teste di serie

Un torneo è composto da K gironi, con N squadre partecipanti in ciascun girone (per un totale di KxN squadre nel torneo).
Dopo le eliminatorie, passa soltanto la prima classificata di ogni girone.
A ogni squadra è associato un coefficiente di bravura, ovvero un intero positivo che è tanto maggiore quanto più la squadra è forte.
Per rendere più vivace il torneo, gli organizzatori vogliono far gareggiare le squadre più forti tra loro soltanto dopo le eliminatorie: in altre parole, le K squadre con i coefficienti di bravura più alti devono giocare in gironi distinti.

Aiutate gli organizzatori a verificare che la composizione del torneo rispetti il loro volere: prese le K squadre con il più alto coefficiente di bravura, ciascun girone deve contenere esattamente una di esse (da notare che due o più squadre possono avere lo stesso coefficiente).

Dati di input

Il file input.txt è composto da K+1 righe.

  • La prima riga contiene due interi positivi separati da uno spazio: il numero K di gironi e il numero N di squadre per girone.
  • Le successive K righe contengono i coefficienti di bravura delle squadre: la j-esima di tale righe contiene N interi positivi separati da uno spazio che sono i coefficienti di bravura delle N squadre nel j-esimo girone, per 1 ≤ j ≤ K.

Dati di output

Il file output.txt è composto di una riga contenente un solo intero:

  • 1 se il torneo rispetta i vincoli imposti dagli organizzatori,
  • 0 altrimenti.

Assunzioni

  • 1 < N ≤ 100
  • 1 < K ≤ 100

Esempi di input/output

input.txt output.txt
3 4
3 5 7 9
3 6 78 90
43 78 71 32
0
3 4
2 2 2 1
2 1 3 1
2 4 2 1
1

Ordinamento

Ordinare una sequenza di interi oppure di un certo TIPO