PDA

Visualizza la versione completa : [C] Sottosequenze di una sequenza di interi


andbaz
14-03-2019, 21:57
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:



#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

alka
18-03-2019, 10:37
COSA STO SBAGLIANDO? GRAZIE MILLE

Qual l'errore o il comportamento sbagliato che ottieni?

andbaz
18-03-2019, 22:19
Il problema sembra stare nei 2 cicli for annidati: non riesco a capire come poter fissare come perno un elemento della lista, per poi incrementare progressivamente la dimensione del range per il confronto tra gli elementi.

Loading