Enigmath Machine 0/100

Scusate sono nuovo qui, volevo chiedere se il codice che ho scritto gli viene conferito 0/100 perché il codice è troppo lento oppure perché ci sono degli errori nel codice. Grazie.

#include
#include
#include
using namespace std;

bool isTrue;
int eMax, eMin, diff, sum, x;
vector output;

void findN(string n, int _sum, int e){
int _n = 0;
for (int i = 0; i < n.length(); i++)
{
_n += n[i] - 48;
}
_sum += _n;
if (_sum == e){
if (_n < 10)
isTrue = true;
}else
if (_n >= 10)
findN(to_string(_n), _sum, e);
}
int main(){
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
cin >> eMin >> eMax;
diff = eMax - eMin;
#define MAXN 100000
vector<vector > outputs (diff + 1, vector(MAXN, 0));
if (diff == 0)
{
if (eMax < 10)
output.push_back(eMax);
else
for (int i = 11; i < eMax; i++)
{
sum = i;
findN(to_string(i), sum, eMax);
if (isTrue)
{
isTrue = false;
output.push_back(i);
if (output.size() > 1)
break;
}
}
if (output.size() == 0)
cout << “IMPOSSIBLE”;
else if(output.size() == 1)
cout << output[0];
else
cout << “AMBIGUOUS”;
}
else{
x = 0;
for (int i = eMin; i <= eMax; i++)
{
int k = 0;
if (i < 10)
outputs[x][k] = i;
else
for (int j = 11; j < i; j++)
{
sum = j;
findN(to_string(j), sum, i);
if (isTrue)
{
isTrue = false;
outputs[x][k] = j;
if(k == 1)
break;
k++;
}
}
x++;
}
for(int i = 0; i <= diff; i++){
if (outputs[i][0] == 0)
cout << “IMPOSSIBLE” << endl;
else
if (outputs[i][1] == 0)
cout << outputs[i][0] << endl;
else
cout << “AMBIGUOUS” << endl;
}
}
}

Se clicchi sul codice della sottoposizione puoi leggere se l’output non è corretto, se hai usato troppo tempo o troppa memoria, e quali test hai sbagliato.

1 Mi Piace

Ciao, nel tuo codice hai un vector di vector con diff * MAXN interi. Se un’intero occupa 4 Byte e tu hai fino a 10^{11} interi, ti servirebbero 400 GB di memoria, decisamente troppi.

Queste sono alcune idee per la soluzione:

  • Quanti step N \to s(N) puoi fare al massimo?

  • E - N = (N + s(N) + s(s(N)) + ...) - N può essere arbitrariamente grande?

  • Sia D un intero sicuramente maggiore di E-N. I valori nell’intervallo [E_{min}, E_{max}] si possono ottenere solo partendo da interi nell’intervallo [E_{min} - D, E_{max}].
1 Mi Piace

Grazie mille delle vostre risposte, mi hanno aiutato, ma ho anche capito che il mio codice conteneva anche dei buchi che prima o poi cercherò di risolvere. Grazie mille ancora per l’aiuto.