Olimpiadi informatica 2/12/2011

[milizia96]

Oggi ho partecipato alla fase d'istituto delle olimpiadi di informatica, e ho scelto come linguaggio il Pascal.
Ho delle perplessità sull'esercizio numero 9, che recita:

Si consideri il seguente frammento programma:

Program E9 (input,output);
var T: array [1..25] of Integer;
var S: array [1..10] of Integer;
var W: array [1..5] of Integer;
var i: Integer;
begin
    i:=0;
    while (i<=24) do begin
        S[T[i]-1]:=S[T[i]-1]+1;
        i:=i+1;
        end;
    i:=0;
    while (i<=9) do begin
        W[S[i]-1]:=W[S[i]-1]+1;
        i:=i+1;
        end
end.

Si supponga che i vettori T,S, e W inizialmente contengano i seguenti valori:
T = [1,1,2,2,2,3,3,3,4,4,4,5,6,6,7,7,8,8,8,8,8,9,10,10,10];
S = [0,0,0,0,0,0,0,0,0,0];
W = [0,0,0,0,0];

Scrivere il contenuto del vettore W dopo l'esecuzione del programma.

Secondo me l'esecuzione del programma causerebbe un errore, in quanto alla prima esecuzione del ciclo while i è uguale a 0, mentre gli indici dei vettori partono da 1.
Errore nel testo? Oppure mi è sfuggito qualcosa?

[vict85]

Immagino sia un errore del testo dovuto al fatto che in C gli array partano da $0$. Trovo che comunque pascal sia ormai un linguaggio datato e soprattutto non viene più usato da nessuno. Meglio Ada tra i linguaggi pascal-like ma conoscere C, C++ o python risulta molto più utile. L'unico linguaggio diverso dal C, che non sia usato nel web o sia legato a programmi come matlab, di una certa rilevanza pratica è fortran. Ma il suo uso è molto settoriale.

[garnak.olegovitc1]

Salve milizia,
il problema qual'è?
Cordiali saluti

[milizia96]

"garnak.olegovitc":Salve milizia,
il problema qual'è?
Cordiali saluti

Siccome mi sembrava strano che un testo delle olimpiadi avesse degli errori, volevo avere la conferma che non si trattasse di un errore mio (non si sa mai, magari mi era sfuggito qualcosa), ma del testo.
A questo punto credo (e spero) che annulleranno l'esercizio (anche a quelli che hanno scelto il C/C++), altrimenti chi ha scelto il Pascal risulterebbe svantaggiato.

"vict85":Trovo che comunque pascal sia ormai un linguaggio datato e soprattutto non viene più usato da nessuno.

Vero: io ero l'unico della mia scuola ad averlo scelto...

[garnak.olegovitc1]

Salve milizia,
a prescindere se hai sbagliato tu o il testo, cosa dovevi fare con questo algoritmo?Dovevi inserire da tastiera i valori nei vettori, lasciando W per ultimo?
Cordiali saluti

[apatriarca]

@garnak.olegovitc: il testo mi sembra chiaro. C'era quel codice e si chiedeva quale dovesse essere il valore di W dopo l'esecuzione del codice presentato (assumendo quei valori per gli altri array).

Da quel poco che so di Pascal mi sembra proprio che tu abbia ragione. Non dare però per scontato che l'errore verrà trovato da chi corregge queste prove. Normalmente hanno semplicemente un elenco di risposte e si basano su quelle. Prova a contattare il professore che si occupa di queste olimpiadi nel tuo istituto.

[milizia96]

Ora c'è un altro esercizio che mi lascia perplesso:

Esercizio N° 5 – La risposta esatta vale 3 punti.
Le Ferrovie dello Stato hanno deciso di dotare ogni treno di un team di 5 persone per il rapporto a bordo con
i viaggiatori. Il team deve essere composto da due persone che controllano i biglietti (Servizio Biglietti) una
persona per interagire con i viaggiatori nel caso di reclami a bordo (Servizio Clienti) e due persone per il
servizio d’ordine. Nell’organizzare un team siamo a conoscenza delle seguenti preferenze:
i. A,B e C sono disponibili per il Servizio Biglietti
ii. C,D ed E sono disponibili per il Servizio Clienti
iii. F,G,H sono disponibili per far parte del Servizio d’Ordine
iv. A e H possono lavorare solo se sono insieme nello stesso team
v. E preferisce lavorare solo se F lavora
Quanti diversi team è possibile organizzare rispettando le preferenze di cui ai precedenti punti da i. a v. ?
a) 5
b) 8
c) 10
d) 13

Io mi ero fatto tutte le combinazioni ed ero arrivato alla conclusione che si possono formare 10 diversi team.
Ma, trovata la tabella di correzione su internet, leggo la risposta: B.
Ho riprovato a casa e mi viene sempre 10. Questo è un esercizio molto importante per me, perché mi farebbe perdere ben 4 punti per una risposta che penso di aver dato correttamente. A voi quanto viene?

[apatriarca]

Vediamo un po'.. Proviamo prima di tutto a far lavorare quindi A e H. Ognuno dei due è disponibile per un solo lavoro per cui:
A servizio biglietti e H è nel servizio d'ordine. Dobbiamo ancora scegliere uno nel servizio biglietti, uno nel servizio clienti e uno nel servizio d'ordine. Se scegliamo B per il servizio biglietti, abbiamo 3 possibilità per il servizio clienti. Se scegliamo C o D, abbiamo altre 2 possibilità per il servizio d'ordine, se scegliamo invece E, ne abbiamo solo una. In questo caso abbiamo quindi 2*2 + 1 = 5 possibilità. Nel caso scegliessimo invece C nel servizio biglietti, ci sono solo due possibilità per il servizio clienti e 3 possibilità in tutto. Supponiamo quindi di non dare lavoro ad A e H. In questo caso abbiamo quindi che il servizio biglietti è determinato e anche quello d'ordine mentre abbiamo due possibilità per il servizio clienti. Per cui in tutto sembrerebbe essere 10.

D'altra parte anche cercando di pensare ad una diversa interpretazione del punto v, In cui la preferenza valga per entrambi (sia E che F), non si otterrebbe 8. In questo caso avremmo infatti solo 3 possibilità nel caso in cui A e B siano al servizio biglietti, 2 possibilità nel caso in cui ci siano A e C e 1 sola possibilità nel caso in cui al servizio biglietti ci siano B e C. Ma in tutto ci sarebbero 5 possibilità e questa interpretazione è decisamente una forzatura.

Sembrerebbe proprio che tu abbia di nuovo ragione. A meno che qualcuno non intervenga a trovare un errore nel nostro ragionamento.

[vict85]

Devo ammettere che anche a me viene 10.

[hamming_burst]

anche a me torna un 10.
Se consideriamo:
- C non può comparire in Bigletti e Clienti nello stesso momento, perciò la scelta non cambia il totale.
- scremiamo i risultati con IV perchè è un vincolo globale
- il vincolo V è già inglobato nelle scelte totali

Le possibili soluzioni con vincolo A&H sono una combinazione di:
- Bigl={AB,AC} = 2 scelte
- Cli={D,E} = 2
- Ord={FH,GH} = 2

scelte totali= 2*2*2 = 8

Soluzione complementare A&H:
- Bigl={BC} = 1
- Cli={D,E} = 2
- Ord={FG} = 1

1*2*1= 2

considerando che le soluzioni di V sono già comprese nelle combinazioni sopra, perchè se F lavora o non lavora comporterà la non scelta di E e della combinazione che lo contiene.

A me sembra, comunque, manchi qualcosa...

EDIT:
corretto svarione.

[Rggb1]

Confermo la risposta "10 team". Eventualmente, una spiegazione per la risposta "8 team" è data dal fatto che fra questi dieci ci sono due gruppi in cui non compaiono A e H (ovvero: sono 8 quelli con dentro A e H); ma in questo caso è evidente che chi ha compilato le risposte abbia sbagliato a non contarli .

[vict85]

"Rggb":Confermo la risposta "10 team". Eventualmente, una spiegazione per la risposta "8 team" è data dal fatto che fra questi dieci ci sono due gruppi in cui non compaiono A e H (ovvero: sono 8 quelli con dentro A e H); ma in questo caso è evidente che chi ha compilato le risposte abbia sbagliato a non contarli .

È evidente che le risposte derivano da una cattiva interpretazione delle condizioni iv e v

10 è quella corretta
8 si fa imponendo che A e H fossero nel team
5 si fa imponendo che che F implichi E
13 si produrrà penso in modo simile.

Tutto fa pensare che l'errore sia stato quando hanno riportato le risposte corrette.