Il mio codice Cabala sembra essere giusto, se non fosse che prende 10/100. Nel secondo esempio, forse fraintendo qualcosa, perchè se il problema chiede di avere in output un resto preso da un numero a 4 cifre, l’esempio prende il resto dal numero 639?
Ciao, ha al più N cifre quindi un numero compreso tra 3-9696 in cui ogni cifra è multipla di 3 e non vi sono due cifre adiacenti uguali. Quindi 639%32 =31 ed è sicuramente il resto maggiore che puoi ottenere.
ti ringrazio
sono riuscito a creare un algoritmo però riesco a prendere solo 10/100, qualcuno ha qualche idea?
Allego il codice:
#include <stdio.h>
#include <assert.h>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
long long occulta(int N, int M) {
//Mettete qui il codice della soluzione
//freopen("output.txt", "w", stdout);
vector<long long> vettore;
long long numero, ultimonumero, in;
long long massimo = 0;
bool si = true;
for(long long i = 3; i <= pow(10, N); i += 1){
si = true;
in = i;
while((in / 10) != 0){
numero = in % 10;
if(ultimonumero == numero){
si = false;
break;
}
if(numero % 3 != 0 || numero == 0){
si = false;
break;
}
ultimonumero = numero;
in /= 10;
}
if((numero = in) % 3 != 0 || (numero = in) == ultimonumero || !si){
//cout << "non va bene" << endl;
continue;
}
/*if(i == 9639){
long long provo;
provo = 9639 % M;
cout << "9639 " << provo << endl;
}*/
vettore.push_back(i);
}
massimo = vettore[0] % M;
for(long long i = 1; i < vettore.size(); i++){
massimo = (vettore[i] % M > massimo) ? vettore[i] % M : massimo;
}
return massimo;
}
int main() {
FILE *fr, *fw;
int T, N, M, i;
fr = fopen("input.txt", "r");
fw = fopen("output.txt", "w");
assert(1 == fscanf(fr, "%d", &T));
for (i=0; i<T; i++) {
assert(2 == fscanf(fr, "%d %d", &N, &M));
fprintf(fw, "%lld ", occulta(N, M));
}
fprintf(fw, "\n");
fclose(fr);
fclose(fw);
return 0;
}
Non ho approfondito il codice perché, nel modo in cui cerca le possibili combinazioni di numeri, finirebbe, comunque, in TLE.
La procedura ottimale sarebbe quella di provare tutte le combinazioni di [3,6,9]x[1, …, N] e verificare quella che ti dà il resto maggiore utilizzando la ricorsione.
oh ok grazie, la implementerò stasera
Qualche idea per rendere più efficiente il mio codice? Riesco a risolvere i primi 2 subtask e i primi 2 testcase del subtask 3.
long long calcolo_modulo(long long num, int m){
return num % m;
}
long long occulta(int N, int M) {
long long max_val = 0, num = 0, i = 0;
while (i < N){
num += (calc_potenza(i)*9);
i++;
}
bool accept;
long long prec_cifra, cifra, val, old_num, potenza, pos = -1, k, red_val;
int last_cifra, last_position;
// int tentativi = 0;
while (num > max_val){
accept = true;
pos = -1;
k = 1;
if (numero_cifre(num)<N)
N = numero_cifre(num);
old_num = num;
// cout << "current number "<<num<<endl;
for (int j=0;j<N; j++){
//potenza = pow(10,N-j-1);
potenza = calc_potenza(N-j-1);
cifra = num/potenza;
if (j==0){
if (cifra == 8 || cifra ==5 || cifra == 2){
accept = false;
k = 2;
pos = N-j;
break;
}
if (cifra == 1 || cifra == 4 || cifra == 7){
accept = false;
pos = N-j;
break;
}
}
else{
if (cifra == prec_cifra){
accept = false;
k = 3;
pos = N-j;
break;
}
if (cifra == 8 || cifra ==5 || cifra == 2){
accept = false;
k = 2;
pos = N-j;
break;
}
if (cifra == 1 || cifra == 4 || cifra == 7){
pos = N-j;
accept = false;
break;
}
if (cifra == 0){
accept = false;
break;
}
}
prec_cifra = cifra;
num -= (potenza*cifra);
}
num = old_num;
if (accept){
val = calcolo_modulo(num,M);
if (val > max_val){
max_val = val;
// cout << "current best number "<<num<<" con resto = "<<max_val<<endl;
}
num = num -3;
}
else{
if (pos == -1)
num--;
else
num = num - k*calc_potenza(pos-1);
}
// tentativi++;
}
// cout << "tentativi "<<tentativi<<endl;
return max_val;
}
La funzione calc_potenza calcola efficientemente potenze di 10 con esponente variabile, mentre la funzione numero cifre calcola il numero di cifre di un numero passato come parametro.
Ciao, anche io ho un problema con questo esercizio.
Dal Task 08 fino al 13 mi da il seguente errore:
Execution killed with signal 6 (could be triggered by violating memory limits)
Ottengo quindi, al massimo, il 30%.
La logica mi sembra corretta. Pare ci sia qualche problema con la memoria…
Ecco il mio codice:
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
long long int numMax=0;
void creaNumRic(string num,short int N,long long int M)
{
long long int numero;
if(num.size()==N||numMax==M-1)
{
return;
}
for(int i=9;i>=3;i=i-3)
{
if(num.size()>0&&num[num.size()-1]==to_string(i)[0]) continue;
num.append(to_string(i));
numero=stoi(num);
if(numero%M>numMax) numMax=numero%M;
creaNumRic(num,N,M);
num=num.substr(0,num.size()-1);
}
}
int main() {
ifstream fin("input.txt");
ofstream fout("output.txt");
short int T, N;
long long int M;
fin>>T;
for(int i=0;i<T;i++)
{
fin>>N>>M;
creaNumRic("",N,M);
fout<<numMax<<" ";
numMax=0;
}
fin.close();
fout.close();
return 0;
}
Qualche suggerimento?
Grazie
Ciao, il problema è generato dalla funzione stoi() per convertire string in un int, poiché N=[1,18] può stare anche in un long long devi quindi usare la funzione stoll() per convertire string in long long.
Grazie!!
Adesso quel problema è risolto.
Mi rimangono gli ultimi 3 Task con il problema: Execution timed out…
Potrebbe migliorare la situazione l’uso di un vector piuttosto delle stringhe? (certo poi dovrei usare una funzione che converte le varie cifre di un vector in un numero).
Grazie
La tua funzione ricorsiva è corretta ma invece di usare una stringa utilizza una variabile long long e per scorrere le posizioni usa le potenze di 10 crescente.
Perfetto. Adesso funziona.
Grazie ancora.