Spoj 370 - Ones e zeri (ONEZERO)

Question

sto cercando di risolvere SPOJ problem "Ones and zeros":

Alcuni numeri interi positivi hanno la loro rappresentazione decimale costituito solo da uno e zero, e con almeno una cifra uno, ad esempio, 101. Se un numero intero positivo non ha una tale proprietà, si può provare a moltiplicarlo per un numero intero positivo per scoprire se il prodotto ha questa proprietà.

Il mio approccio a questo problema stava semplicemente facendo BFS. Prendendo una stringa contenente solo '1' e poi facendo BFS con esso e ad ogni passaggio aggiungendo '1' e '0'. Tenere traccia del numero in forma di stringa e resto fino ad ora. Quando il resto è zero, il numero è stato trovato.

Il mio problema è: il mio codice impiega troppo tempo per i casi di test, ad es. 9999 o 99999. Come posso migliorare il runtime dell'algoritmo?

// Shashank Jain 
/* 
    BFS 
*/ 
#include <iostream> 
#include <cstdio> 
#include <cstring> 
#include <climits> 
#include <string> 
#include <algorithm> 
#include <vector> 
#include <cmath> 
#include <queue> 
#include <stack> 
#define LL long long int 
using namespace std; 
LL n; 
string ans; 

void bfs() 
{ 
    string str,first,second; 
    str+='1'; // number will start with '1' always 
    if(n==1) 
    { 
    ans=str; 
    return; 
    } 
    queue<pair<string,LL> >q; // pair of STRING(number) and long long int 
          // (to hold remainder till now) 
    pair<string,LL>p; 
    p=make_pair(str,1); 
    q.push(p); 
    LL rem,val,temp; 
    while(q.empty()==0) 
    { 
    p=q.front(); 
    q.pop(); 
    str=p.first; 
    val=p.second; 
    if(val==0) // remainder is zero means this is number 
    { 
     ans=str; 
     return ; 
    } 
    // adding 1 to present number  
    temp=val*10+1; 
    rem=(temp)%n; 
    firstone=str+'1'; 
    p=make_pair(firstone,rem); 
    q.push(p); 
    // adding 0 to present number  
    temp=val*10+0; 
    rem=(temp)%n; 
    secondone=str+'0'; 
    p=make_pair(secondone,rem); 
    q.push(p); 
    } 
} 

int main() 
{ 
    int t,i; 
    scanf("%d",&t); 
    while(t--) 
    { 
    scanf("%lld",&n);  
    bfs(); 
    for(i=0;i<ans.size();i++) 
    { 
     printf("%c",ans[i]);   
    } 
    printf("\n"); 
    } 
    return 0; 
} 

Answer 1

Ho appena risolto il problema. Non vorrei inviare il mio frammento, ma darò i punti per cui il codice è più lento

1. Come sukunrt detto è necessario mantenere un allineamento visitato di dimensione n, dove è possibile contrassegnare il modulo attualmente ottenuto come visitato così che non lo visiti di nuovo, perché se sei a un modulo già visitato non hai bisogno di considerare la parte di stringa ottenuta fino ad ora in quanto rende solo il numero più grande (abbiamo bisogno di un minimo), cioè significa che una volta visita un modulo che dici x quindi trovi il numero minimo composto da 0 e 1 che dà x come resto quando dividi per n.

2. Si passa sempre la stringa così ottenuta al bambino, che non solo aumenta la memoria ma anche il tempo. Per evitare questo, basta prendere altri due array dire value[] e parent[] entrambi di dimensione n.

   parent[i] memorizza il modulo genitore del modulo i.

   value[i] negozi che è il bit corrente corrispondente al modulo i (0 < = i < n).

   Alla fine è possibile tornare indietro per formare l'intero numero solo per modulo = 0.

   Anche dopo aver apportato delle modifiche, il tuo codice darà WA perché devi prima spingere il bambino ottenuto aggiungendo '0' alla fine e poi il bambino ottenuto aggiungendo '1' alla fine. (Puoi dimostrarlo tu stesso).

Answer 2

Ecco un suggerimento. pensare in questo modo:

Supponiamo che il numero che si desidera è X. X mod N = 0.

quindi è necessario memorizzare solo N afferma cioè 0-n-1. Inizia con 1. e fai il bfs. Devi scartare i rami che hanno lo stesso resto di prima. Lascerò la prova a te.