Salve a tutti, stavo cercando di risolvere il problema “regali gemelli” delle OIS2016.
il codice da 30 punti. Non capisco dove sbaglio. Qualche soluzione? Grazie
#include <stdio.h>
#include <assert.h>
#include <iostream>
#define MAXN 10000
#define MAXQ 1000
using namespace std;
int compra(int N, int Q, int* G[]) {
int soluzione = 0;
int blocco = 0;
int blocco2 = 0;
bool trovato = true;
for(int j = 0; j<Q; j++){
if(trovato==true){
trovato=false;
}
else {
break;
}
for(int i = 0; i<N-1; i++){
trovato=false;
if(G[blocco][blocco2] == G[i+1][blocco2]){
soluzione++;
trovato=true;
break;
}
}
blocco2++;
}
return soluzione;
}
int* G[MAXN];
int main() {
FILE *fr, *fw;
int N, Q, i, j;
fr = fopen("input.txt", "r");
fw = fopen("output.txt", "w");
assert(2 == fscanf(fr, "%d %d", &N, &Q));
for(i=0; i<N; i++) {
G[i] = (int*)malloc(Q*sizeof(int));
for (j=0; j<Q; j++) {
assert(1 == fscanf(fr, "%d", &G[i][j]));
}
}
fprintf(fw, "%d\n", compra(N, Q, G));
fclose(fr);
fclose(fw);
return 0;
}
Prova a spiegare cosa cerca di fare il tuo algoritmo così è più facile aiutarti. 
2 Mi Piace
Sostanzialmente verifica, partendo dalla prima riga se il relativo numero della matrica è uguale al suo successivo in colonna… se è uguale incremento un contatore che mi conta le cifre uguali e mi assegna un vero in una variabile booleana se effettivamente lo ha trovato uscendo cosi in modo forzato dal ciclo con break… altrimenti se tutto questo non si dovesse verificare semplicemente vado avanti con il ciclo fin quando non trova valori uguali… nel momento in cui mi trovo fuori dal ciclo incremento la colonna e vado avanti cosi via… quando il tutto finisce nel ciclo delle colonne vedo se ci sono effettivamente valori uguali, altrimenti esco direttamente rilasciandomi la soluzione…
non è molto chiaro ma spero di aver reso l’idea,.
Partendo dal presupposto che non ho capito bene cosa fai 
.
Questo esercizio malgrado le assunzioni 2 ≤ N ≤ 10 000
e 1 ≤ Q ≤ 100. la soluzione più lenta quindi O(NNQ) con le giuste accortezze rimane nel TL.
Quindi provando a confrontare ogni giocattolo con tutti gli altri (possibilmente i suoi successivi, il confronto con i precedenti è stato fatto dai precedenti stessi) e calcolando effettivamente quanto vale il prefisso massimo si ottiene 100/100.
Se ho capito cosa intendi fare con la tua soluzione questo tc dovrebbe risultarti errato:
4 4
1 2 3 4
1 3 4 5
2 3 4 5
2 3 4 6
1 Mi Piace
Come sospettavo Il tuo codice sbaglia quel tc, se non ho capito male è come se dessi maggior priorità al primo elemento.
2 Mi Piace
La soluzione O(NNQ) ha come caso peggiore 0.336s, sta benissimo nei tempi.
Ne approffito per chiedere come scrivere le complessita in modo figo, come si fa ?
Aggiungi un ‘$’ prima ed uno dopo al testo interessato.
3 Mi Piace