E’ da un po’ di tempo che sto provando a risolvere questo problema e sono arrivato quasi alla soluzione definitiva. Dico quasi dato che provando a dare in input gli input di esempio li riesce a risolvere, ma quando provo a dare gli input dell’allegato cabala.input2.txt riesce a dare giusti tutti i casi tranne quelli che come output hanno 0, e il mio codice in quei casi come output dà 1. Quindi non capisco per quale motivo dovrebbe dare 0 al posto di 1.
Ecco il mio codice:
#include <cmath>
#include <stdio.h>
#include <assert.h>
#include <iostream>
using namespace std;
long long fast_exp(int base, int n) {
if (n == 0) {
return 1;
}
else if (n == 1) {
return base;
}
else if (n % 2 == 0) {
long long half = fast_exp(base, (n / 2));
return (half * half);
}
else {
return base * (fast_exp(base, (n - 1)));
}
}
long long respect(long long C, int lenn) {
int cifra = 0;
long long ci = C;
long long expon = fast_exp(10, lenn);
int n1, n2;
for (int i = lenn; i > 0; i--) {
cifra = C / expon;
n1 = cifra;
if (cifra == 0 || (cifra % 3 != 0 && cifra != 1)) {
return 0;
}
C -= cifra * expon;
expon = expon / 10;
cifra = C / expon;
n2 = cifra;
if (n1 == n2) {
return 0;
}
}
if (C == 0 || (C % 3 != 0 && C != 1)) {
return 0;
}
return ci;
}
long long occulta(int N, int M) {
long long C, ans = 0;
long long anss = 0;
long long maxx = fast_exp(10, N);
int lenn = 1;
for (C = 1; C < maxx; C++) {
lenn = log10(C);
ans = respect(C, lenn);
anss = max(anss, (ans % M));
}
return anss;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
FILE *fr, *fw;
int T, N, M, i;
//fr = fopen("input.txt", "r");
//fw = fopen("output.txt", "w");
//assert(1 == fscanf(fr, "%d", &T));
cin >> T;
for (i=0; i<T; i++) {
cin >> N >> M;
cout << occulta(N, M) << " ";
//assert(2 == fscanf(fr, "%d %d", &N, &M));
//fprintf(fw, "%lld ", occulta(N, M));
}
//fprintf(fw, "\n");
//fclose(fr);
//fclose(fw);
return 0;
}
Se qualcuno riesce a rispondere a questa domanda mi farebbe un grandissimo piacere, Grazie!