Ciao,
Testo del problema:
Si riceve in input una sequenza S di N numeri interi x_0,...,x_{N-1}.
Contare quante sono le sottosequenze non vuote di S strettamente crescenti.
Una sottosequenza di S si ottiene quando si selezionino alcuni degli elementi di S come elementi da tenere, e si nascondano gli altri elementi. La sottosequenza è essa stessa una sequenza in quanto viene mantenuto l'ordine tra gli elementi conservati. La sottosequenza è non vuota se almeno un elemento è stato selezionato e mantenuto. La sottosequenza è identificata dagli indici degli elementi selezionati, non dal loro valore. (Vedi esempi.) Pertanto, due diverse sottosequenze possono risultare uguali quando viste come sequenze, ma noi le dobbiamo conteggiare entrambe.
Dati di input
La prima riga del file \verb'input.txt' contiene il numero N: la lunghezza della sequenza.
Le successive N righe contengono, ciascuna, un numero della sequenza.
L'i-esimo elemento della sequenza è quello nella riga i+1.
Dati di output
Nel file 'output.txt' si scriva un unica riga contenente il numero delle sottosequenze non vuote e crescenti, modulo 1024.
Esempio
4
5
1
1
3
Contiene 6 sequenze
La mia soluzione:
codice:
#include <cstdio>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <string.h>
#define INPUT "input.txt"
#define MAXN 1000
#define BREAK_LINE "\n"
using namespace std;
int main() {
ifstream infile;
infile.open(INPUT);
int n;
infile >> n;
printf("%d\n", n);
printf(BREAK_LINE);
int x[MAXN], max = 0, y;
for (int i = 0; i < n; i++) {
infile >> x[i];
y = x[i];
printf("%d\n", y);
if (y > max)
max = y;
if (i > MAXN)
break;
}
printf(BREAK_LINE);
int seq[MAXN], count = 0, cursor = 0, temp = 0;
for (int i = 0; i < n; i++) {
cursor = x[i];
if (max == cursor) {
printf("%d ", cursor);
printf(BREAK_LINE);
count++;
continue;
}
count++;
int temp, times = 0, dim = 1;
for (int j = i; j < n;) {
temp = x[j];
if (times < dim) {
times++;
if (cursor <= temp) {
printf("%d ", temp);
j++;
} else {
printf(BREAK_LINE);
}
} else {
dim++;
}
}
printf(BREAK_LINE);
}
printf("Number of sequences: %d\n", count);
printf(BREAK_LINE);
infile.close();
return 0;
}
COSA STO SBAGLIANDO? GRAZIE MILLE