Parole saturnine

Aiuto
1

Ciao a tutti,
Qualcuno mi da un aiuto su come risolvere parole saturnine?

Il mio problema è che non riesco di conteggiare una sola volta quelle parole che contengono più di una volta la sequenza S: ad esempio con S=“01” io conterei 0101 due volte. 

Come posso risolvere?

Grazie  :D
2

Io l’avevo risolto differentemente, anzichè cercare di contare ed eliminare quelle che non andavano bene, ho contato quante stringhe che vanno bene posso costruire utilizzando la programmazione dinamica.

3
Io l'avevo risolto differentemente, anzichè cercare di contare ed eliminare quelle che non andavano bene, ho contato quante stringhe che vanno bene posso costruire utilizzando la programmazione dinamica.

Mazzetto

Puoi spiegare un po' più approfonditamente come fai?
1 Mi Piace
4

Ho usato una ricorrenza ric(int p, int k) che ha p come la lunghezza della stringa costruita fino ad ora e k il numero di caratteri della stringa S che ho matchato fino ad ora.

5

Grazie mille, ho risolto :slight_smile:

Comunque come hai fatto a trovare questa soluzione? Avevi già risolto altri problemi simili?

6

Posso intromettermi pure io?
E’ tutto il giorno che cerco di implementare l’idea in DP ma senza successo.

L’algoritmo è strutturato in questo modo: F(n,s) dove n è la lunghezza della stringa che sto costruendo ed s è la lunghezza del matching con la stringa S.

1) Controllo:
-Se s=M return 0 (ho trovato S prima di completare la parola)
-Se n=N return 1 (ho completato la parola senza trovare S)
-Se DP[n][s]=/=-1 return DP[n][s] (restituisco la soluzione se l’ho già calcolata).

2) Ad ogni passo ricorsivo ho due scelte:
-Estendo il matching della stringa S (quindi risolvo F(n+1,s+1)).
-Annullo il matching corrente (cioè inserisco la lettera opposta di S[s+1]) e calcolo il nuovo matching.

3) Sommo i risultati (modulo 2011) e li salvo nella tabella DP

Per il punto 2.2 faccio un esempio:
-S=100011
-Pcorrente=10001 (la parola P che sto costruendo)
Se voglio annullare il matching corrente allora dovrò inserire “0” ottenendo “100010” e rilanciando F(6,2) dato che le ultime due lettere “10” stanno “costruendo” un matching per S.

Se invece avessi:
-S=110011
-Pcorrente=11001
Per annullare il matching dovrei inserire sempre “0” ottenendo “110010” ma in questo caso rilancerei F(6,0).

Questo è quello che ho scritto, sperando sia un po’ più chiaro da capire rispetto alla spiegazione >_<

#include <cstdio>
const int MAXM=1005;

int N, M, S[MAXM], mem[MAXM][MAXM];

int solve(int,int);

int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	
	for(int i=0; i<MAXM; i++)
			for(int j=0; j<MAXM; j++)
					mem[i][j]=-1;
	
	scanf("%d %d", &M, &N);
	
	for(int i=1; i<=M; i++) scanf("%d", S+i);
	
	printf("%d\n", solve(0,0));
	
	return 0;
}

int solve(int n, int s)
{
	if(mem[n][s]!=-1) return mem[n][s];
	if(s==M) return mem[n][s]=0;
	if(n==N) return mem[n][s]=1;
	
	//Estendo il matching
	int a=solve(n+1,s+1);
	
	//Annullo il matching corrente calcolando quello nuovo
	int nuovaLettera=(S[s+1]==1)? 0:1, i, nuovaS;
	bool found=false;
	
	for(nuovaS=s; nuovaS>0 && !found; nuovaS--){
		if(S[nuovaS]==nuovaLettera)
		    for(i=1, found=true; i<nuovaS && found; i++)
	 			 if(S[s+1-i]!=S[nuovaS-i]) found=false;
	}
	
	int b=solve(n+1,nuovaS);
	
	return mem[n][s]=(a+b)%2011;
}

( http://pastebin.com/L2mdee9y )

7

Non è necessario calcolare ogni volta il numero di lettere matchate. Ti basta farlo una volta e salvarti il risultato

8

Non ho problemi di TLE ma di WA :0


EDIT: comunque grazie lo stesso per il consiglio, ha abbassato il tempo da 0.65 a 0.04! 
9

Ah… allora non so. Forse il modo in cui trovi il nuovo valore per il matching non è corretto, il resto sembra giusto. Domani me lo guardo meglio

10

No ok mi sento un idiota…

Leggevo la stringa S con un for per interi senza considerare che la sequenza “1100101…” fosse tutta attaccata…
In pratica in S[0] avevo già tutta la sequenza salvata come un int <__<

Risolto e grazie lo stesso!
11
Leggevo la stringa S con un for per interi senza considerare che la sequenza "1100101..." fosse tutta attaccata..

VashTheStampede

Un modo per accorgersi facilmente di questi errori è abituarsi a “wrappare” le chiamate a scanf con assert(scanf() == numero di variabili lette), cambiando quindi:

scanf(“%d”, &x);
in:
assert(1 == scanf(“%d”, &x));