City Flooding (manhole) 40/100

Aiuto
1

Salve a tutti, sto provando a risolvere questo problema ma ottengo 40/100 per output errati nei seguenti casi: 20, 24, 25, 26, 27.
per risolverlo ho utilizzato una ricorsiva tenendo conto della memoization, non capisco dove sbaglio, il modulo l’ho messo correttamente? oppure è un altro l’errore?
grazie in anticipo.
codice:

#include <bits/stdc++.h>
#define MOD 10007

using namespace std;

ifstream fin("input.txt");
ofstream fout("output.txt");

int l, n, k, v[10000];
int memo[101][101][1001];

int fattoriale(int N){
    if (N==0) return 1;
    int ris=1;
    for(int i=1; i<=N; i++){
        ris*=i;
        ris=ris%MOD;
    }
    return ris%MOD;
}

int dp(int num, int pos, int sum){
	if(pos>=n) return 0;
	if(num==k){
		if(sum>=l){
			return (fattoriale(k)*fattoriale(n-1-k))%MOD;
		}
	}
	if(memo[num][pos][sum]!=-1) return memo[num][pos][sum];
	int a=dp(num+1, pos+1, sum+v[pos])%MOD;
	int b=dp(num, pos+1, sum)%MOD;
	memo[num][pos][sum]=(a+b)%MOD;
	return memo[num][pos][sum];
}

int main(){
	fin >> l >> n >> k;
	for(int x=0; x<n-1; x++) fin >> v[x];
	memset(memo, -1, sizeof memo);
	fout << dp(0, 0, 0);
}
2

Quando fai il modulo di un prodotto di int ti conviene passare per i long long o rischi overflow. Ad esempio:

#include <bits/stdc++.h>

int main()
{
    int a = 2000000000, b = 2000000000;
    printf("%d\n%d\n", (a * b) % 1000000007, (a * 1LL * b) % 1000000007);
}

Stampa

-651507193
196

dove solo il secondo è il risultato giusto. Quindi quando fai

ris*=i;
ris=ris%MOD;

quello che in realtà dovresti fare è

ris = (ris * 1LL * i) % MOD;
3 Mi Piace
4

ris=(ris * 1LL * i)%MOD;
return (fattoriale(k) * 1LL * fattoriale(n-1-k))%MOD;
grazie per l’aiuto ma nonostante il cambiamento di queste due righe il risultato non cambia

5

Ciao, devi fare attenzione al fatto che la somma potrebbe superare il valore massimo di litri d’acqua con la conseguenza che non sai con certezza dove vengono salvati i dati all’interno della matrice. Suggerisco di sostituire sum+v[pos] con min(l,sum+v[pos]).

In questo task il modulo è stato messo appositamente a 10^4+7 invece del solito 10^9+7 proprio per prevenire questa cosa.

2 Mi Piace
6

Pensavo al caso generico :sweat_smile:

2 Mi Piace
7

Risolto, grazie mille ad entrambi

8

ma in questo caso cercando di accedere ad una posizione inesistente non dovrebbe andare in signal 11?

9

E’ un undefined behaviour, cioè nel migliore dei casi crasha e dà signal 11. Se invece accede fuori dall’array ma comunque in memoria che il sistema operativo ha riservato al programma legge dati “sporchi” e continua l’esecuzione

2 Mi Piace
10

ok grazie mille per l’aiuto

11

In realtà signal 11 si ottiene quando si tenta di accedere ad un area di memoria non autorizzata ma in questo caso la matrice mantiene gli elementi contigui e perciò accedi ad un area di memoria autorizzata ma non quella corretta, ecco un esempio:

int M[2][2]{1,2,3,4};
cout<<M[0][3]; //4
3 Mi Piace