# Parole saturnine

**URL:** <https://forum.olinfo.it/t/parole-saturnine/3852>\
**Category:** Aiuto\
**Created:** [5 Settembre 2014, 12:03pm UTC](https://forum.olinfo.it/t/parole-saturnine/3852 "2014-09-05T12:03:30Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![mark03](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/439d5e/32.png) [@mark03](https://forum.olinfo.it/u/mark03)\
**Post date:** [5 Settembre 2014, 12:03pm UTC](https://forum.olinfo.it/t/parole-saturnine/3852/1 "2014-09-05T12:03:30Z")

</div>

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.&nbsp;

Come posso risolvere?

  

Grazie &nbsp;:D

---

<div class="post-metadata">

**Author:** ![Mazzetto](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/87869e/32.png) [@Mazzetto](https://forum.olinfo.it/u/Mazzetto)\
**Post date:** [5 Settembre 2014, 1:50pm UTC](https://forum.olinfo.it/t/parole-saturnine/3852/2 "2014-09-05T13:50:33Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![mark03](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/439d5e/32.png) [@mark03](https://forum.olinfo.it/u/mark03)\
**Post date:** [5 Settembre 2014, 2:36pm UTC](https://forum.olinfo.it/t/parole-saturnine/3852/3 "2014-09-05T14:36:45Z")

</div>

> 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?

---

<div class="post-metadata">

**Author:** ![Mazzetto](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/87869e/32.png) [@Mazzetto](https://forum.olinfo.it/u/Mazzetto)\
**Post date:** [5 Settembre 2014, 3:28pm UTC](https://forum.olinfo.it/t/parole-saturnine/3852/4 "2014-09-05T15:28:29Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![mark03](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/439d5e/32.png) [@mark03](https://forum.olinfo.it/u/mark03)\
**Post date:** [5 Settembre 2014, 7:15pm UTC](https://forum.olinfo.it/t/parole-saturnine/3852/5 "2014-09-05T19:15:11Z")

</div>

Grazie mille, ho risolto 🙂  
  
Comunque come hai fatto a trovare questa soluzione? Avevi già risolto altri problemi simili?

---

<div class="post-metadata">

**Author:** ![VashTheStampede](https://forum.olinfo.it/user_avatar/forum.olinfo.it/vashthestampede/32/10_2.png) [@VashTheStampede](https://forum.olinfo.it/u/VashTheStampede)\
**Post date:** [8 Settembre 2014, 8:55pm UTC](https://forum.olinfo.it/t/parole-saturnine/3852/6 "2014-09-08T20:55:16Z")

</div>

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 \>\_\<

```auto
#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](http://pastebin.com/L2mdee9y) )

---

<div class="post-metadata">

**Author:** ![Degiac](https://forum.olinfo.it/user_avatar/forum.olinfo.it/degiac/32/9_2.png) [@Degiac](https://forum.olinfo.it/u/Degiac)\
**Post date:** [8 Settembre 2014, 10:29pm UTC](https://forum.olinfo.it/t/parole-saturnine/3852/7 "2014-09-08T22:29:06Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![VashTheStampede](https://forum.olinfo.it/user_avatar/forum.olinfo.it/vashthestampede/32/10_2.png) [@VashTheStampede](https://forum.olinfo.it/u/VashTheStampede)\
**Post date:** [8 Settembre 2014, 10:35pm UTC](https://forum.olinfo.it/t/parole-saturnine/3852/8 "2014-09-08T22:35:48Z")

</div>

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!&nbsp;

---

<div class="post-metadata">

**Author:** ![Degiac](https://forum.olinfo.it/user_avatar/forum.olinfo.it/degiac/32/9_2.png) [@Degiac](https://forum.olinfo.it/u/Degiac)\
**Post date:** [8 Settembre 2014, 11:06pm UTC](https://forum.olinfo.it/t/parole-saturnine/3852/9 "2014-09-08T23:06:11Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![VashTheStampede](https://forum.olinfo.it/user_avatar/forum.olinfo.it/vashthestampede/32/10_2.png) [@VashTheStampede](https://forum.olinfo.it/u/VashTheStampede)\
**Post date:** [10 Settembre 2014, 12:24pm UTC](https://forum.olinfo.it/t/parole-saturnine/3852/10 "2014-09-10T12:24:05Z")

</div>

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!

---

<div class="post-metadata">

**Author:** ![wil93](https://forum.olinfo.it/user_avatar/forum.olinfo.it/wil93/32/2862_2.png) [@wil93](https://forum.olinfo.it/u/wil93)\
**Post date:** [10 Settembre 2014, 2:31pm UTC](https://forum.olinfo.it/t/parole-saturnine/3852/11 "2014-09-10T14:31:23Z")

</div>

> 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));
```