La morra binaria è un gioco a due giocatori.
I due partecipanti scelgono ciascuno un numero intero (compreso fra 0 e 32000).
A questo punto, i due numeri vengono scritti in binario, a partire dalla cifra meno significativa (ed eventualmente aggiungendo zeri alla fine del più corto in modo che alla fine risultino della stessa lunghezza).
Fatto questo, viene calcolato il punteggio dei due giocatori confrontando i due numeri binari cifra per cifra, con la seguente regola:
- se le due cifre sono due zeri, viene aumentato di uno il punteggio del primo giocatore;
- se le due cifre sono due uni, viene aumentato di uno il punteggio del secondo giocatore;
- se le due cifre sono diverse, viene aumentato di uno il punteggio del giocatore che ha la cifra 1.
Vince il giocatore che ha il punteggio più alto; se i due giocatori risultano avere lo stesso punteggio, la partita termina in parità.
Dovete scrivere un programma che determini l’esito di una sequenza di partite.
Esempio 1
Supponete che il primo giocatore scelga 1 e il secondo scelga 8. Scrivendo i due numeri in binario a partire dalla cifra meno significativa si ha:
Giocatore 2 0001
Le cifre che aumentano il punteggio del giocatore 1 sono la prima (1/0), la seconda (0/0) e la terza (0/0); quindi il punteggio del primo giocatore è 3.
L’unica cifra che aumenta il punteggio del giocatore 2 è la quarta (0/1); quindi il punteggio del secondo giocatore è 1.
In questa partita vince dunque il giocatore 1.
Esempio 2
Supponete che il primo giocatore scelga 101 e il secondo 466.
Scrivendo i due numeri in binario a partire dalla cifra meno significativa si ha:
Giocatore 2 010010111
Le cifre che aumentano il punteggio del giocatore 1 sono la prima (1/0), la terza (1/0), la quarta (0/0) e la sesta (1/0): quindi il punteggio del primo giocatore è 4.
Le cifre che aumentano il punteggio del giocatore 2 sono la seconda (0/1), la quinta (0/1), la settima (1/1), l’ottava (0/1) e la nona (0/1); quindi il punteggio del secondo giocatore è 5.
In questa partita vince dunque il giocatore 2.
File di input
Il file di input, di nome input.txt, ha il seguente formato:
- la prima riga contiene un numero intero, N, che rappresenta il numero di partite giocate;
- le successive N righe contengono ciascuna due interi, separati fra loro da uno spazio; in particolare, la riga i-esima contiene i due numeri Ai e Bi giocati rispettivamente dal primo e dal secondo giocatore nella partita i-esima.
File di output
Il file di output, di nome output.txt, è costituito da una singola riga, terminata da un a-capo.
Tale singola riga è costituita da esattamente N caratteri, ognuno dei quali può essere 1, 2 o X.
In particolare, l’i-esimo carattere sarà 1 se l’i-esima partita è vinta dal giocatore 1, sarà 2 se l’i-esima partita è vinta dal giocatore 2, e sarà X se l’i-esima partita finisce in parità.
Assunzioni
Si fanno le seguenti assunzioni:
- 0 <= N <= 32000
- 0 <= Ai, Bi <= 32000
- il file di input non contiene altri caratteri oltre a quelli indicati nel testo;
- il file di output non deve contenere altri caratteri oltre a quelli indicati nel testo; inoltre, il programma non deve produrre alcun altro input/output oltre a quelli indicati: deve limitarsi a leggere il file di input e a scrivere i risultati sul file di output;
- i file di input/output vanno specificati senza alcuna indicazione di path, e quindi verranno aperti in C con un’istruzione tipo
fr = fopen( “input.txt”, “r” );
fw = fopen( “output.txt”, “w” );e in Pascal con un’istruzione tipo
assign( fr, ‘input.txt’ );
reset( fr );
assign( fw, ‘output.txt’ );
rewrite( fw );
Esempio
| input.txt | output.txt |
| 20 12196 24515 21377 25893 11093 25785 29964 4542 22268 27235 26506 19690 21576 25074 10155 8602 23477 5001 23830 12795 11701 7778 18088 10816 255 10558 31214 8628 27191 20243 4581 5631 30911 5105 10481 27832 1244 28214 14875 10028 |
2122222112X12122222X |
- Il numero massimo di bit significativi per la partita è 15 quindi il primo bit potrebbe essere eliminato prima del ciclo while().
- L’operatore & con la maschera 0x8000 estrae il bit più significativo di un intero.
/*
www.valcon.it
OII 2002 - Fase territoriale - MORRA BINARIA
*/
#include
char gioca(int A, int B)
{
int i,
bit=15;
while((bit >= 0) && !(A & 0x8000) && !(B & 0x8000))
{
A <<= 1; // elimina le coppie di zeri iniziali
B <<= 1;
bit--;
}
int puntiA=0, // calcola i punti di A e B
puntiB=0;
int bitA,
bitB;
for(i=bit; i >=0; i--) // per ogni coppia di bit
{
bitA = (A & 0x8000);
bitB = (B & 0x8000);
if(bitA == 0 && bitB == 0) puntiA++;
else if(bitA == 0 && bitB != 0) puntiB++;
else if(bitA != 0 && bitB == 0) puntiA++;
else if(bitA != 0 && bitB != 0) puntiB++;
A <<= 1; // prossima coppia
B <<= 1;
}
if(puntiA > puntiB) return '1'; // il risultato è...
else if(puntiA == puntiB) return 'X';
else return '2';
}
int main()
{
int i,
N, // numero di partite
primo, // i due numeri giocati
secondo; // ...
FILE *fileIN = fopen( "input.txt", "r");
FILE *fileOUT = fopen("output.txt", "w");
fscanf(fileIN, "%d", &N);
for(i=0; i < N; i++)
{
fscanf(fileIN, "%d %d", &primo, &secondo);
fprintf(fileOUT, "%c", gioca(primo, secondo));
}
fclose(fileIN);
fclose(fileOUT);
return 0;
}