#include <stdio.h>

#define maxn 1000001
        long n;
       short result[31],b[maxn];
       int tr[maxn];
      long count,i,j;

main()
{
       scanf("%ld",&n);
      for (i=0;i<n;i++) b[i]=0;
      b[1%n]=1;
      tr[1%n]=0;
      if (n!=1) b[2%n]=2;
      tr[2%n]=0;
      count=1;
       while (b[0]==0 && count <30)
      {
          count++;
          for (i=1;i<n;i++)
         if  (b[i]!=0)
         {
             if (b[(i*10+1)%n]==0)
            {
                b[(i*10+1)%n]=1;
               tr[(i*10+1)%n]=i;
            };
             if (b[(i*10+2)%n]==0)
            {
                b[(i*10+2)%n]=2;
               tr[(i*10+2)%n]=i;
            };
         }
      }
      if (b[0]==0)
      {
          printf("Impossible");
      }
      else
      {
          i=0;
         j=1;
         result[j]=b[i];
         while (tr[i]!=0)
         {
             i=tr[i];
            j++;
            result[j]=b[i];
         }
         for (i=j;i>0;i--) printf("%d",result[i]);
      }
    getchar();
}

dp[i][j] - можно ли получить остаток j если длина равна i.
я получал всякие превышение памяти и времени, только потому что я сохранял предка. Но если не сохранять предка, а вычислять самому, то решение будет < 100 миллисекунд. Восстанавливал и находил минимальный ответ через рекурсию  почти как дфс.

1.Use a DP with the O(30N) time
2.Use ternary (long long in C++ is needed) to indicate each solution
3.Use a rolling array in case it MLEs

Good luck! ~_~

Edited by author 05.07.2011 19:05

n = 2

Just give me some hint pls: intueor19@gmail.com
I really don't understand what is wrong... It passes all tests on that forum but still has WA15

#include <iostream>
#include <vector>

using namespace std;

vector < int > pm (30, 0);
vector < vector < char > > d (31, vector < char > (1000000, 0));
int n;

void printAnswer (int, int);

int main () {
    cin >> n;

    pm[0] = 1 % n;
    for (int i = 1; i < 30; ++i)
        pm[i] = (pm[i - 1] * (10 % n)) % n;

    d[0][0] = 1;
    char found = 0;

    for (int i = 1; i <= 30; ++i) {
        int m1 = pm[i - 1];
        int m2 = ((2 % n) * pm[i - 1]) % n;

        if (d[i - 1][(n - m1) % n] != 0) {
            printAnswer (1, i);
            found = 1;
            break;
        }

        if (d[i - 1][(n - m2) % n] != 0) {
            printAnswer (2, i);
            found = 1;
            break;
        }

        for (int j = 0; j < n; ++j) {
            if (d[i - 1][j] == 0)
                continue;

            d[i][(j + m2) % n] = 2;
            d[i][(j + m1) % n] = 1;
        }
    }

    if (!found)
        cout << "Impossible";

    return 0;
}


void printAnswer (int digit, int lvl) {
    int k = 0;
    int x, j;

    while (lvl != 0) {
        cout << (int)digit;
        j = ((digit % n) * pm[lvl - 1]) % n;
        x = (k >= j) ? (k - j) : (n - j + k);
        digit = d[lvl - 1][x];
        k = x;
        --lvl;
    }

    return;
}

I got AC with other code but I still don't understand what's wrong with this one. Help me PLS!!!

Edited by author 09.02.2014 19:37

Just use DP, which is fast enough (AC 0.187s),
and works without using long arithmetics in O(30*n).
Only remember simple math theorems about mod, i. e.
(a+b) mod c = ((a mod c) + (b mod c)) mod c
(a-b) mod c = ((a mod c) - (b mod c)) mod c
(a*b) mod c = ((a mod c) * (b mod c)) mod c

give me plz some test!

Can anyone explain me what is yhe problem with my program.

#include<cstdio>
using namespace std;
int k,nr,n,p,u,i,j,obt[1000001],fol[1000001],ap[1000001],x[1000001],x1[1000001],cif[100];
char bst[1000002][32],cr[32];
int cmp(char a[32],int n,char b[32],int m)
{
    int i;
    if(n<m) return -1;
    if(n>m) return 1;
    for(i=1;i<=n;i++)
        if(a[i]!=b[i]) break;
    if(a[i]>=b[i]) return 1;
    else return -1;
}
int main()
{
//freopen("input","r",stdin);
//freopen("output","w",stdout);
scanf("%d",&n);
u=2;
x[1]=1%n;
x[2]=2%n;
ap[1%n]=1;
ap[2%n]=1;
obt[1%n]=1;
obt[2%n]=2;
fol[1%n]=1;
fol[2%n]=1;
bst[1%n][1]='1';
bst[2%n][1]='2';
for(i=2;i<=30;i++)
{
    p=0;
    for(j=1;j<=u;j++)
    {
        for(k=1;k<=fol[x[j]];k++)
            cr[k]=bst[x[j]][k];
        cr[k]='1';
        if(ap[(x[j]*10+1)%n]==0||cmp(bst[(x[j]*10+1)%n],fol[(x[j]*10+1)%n],cr,fol[x[j]]+1)>0)
        {
            ap[(x[j]*10+1)%n]=1;
            obt[(x[j]*10+1)%n]=1;
            fol[(x[j]*10+1)%n]=fol[x[j]]+1;
            for(k=1;k<=fol[x[j]]+1;k++)
                bst[(x[j]*10+1)%n][k]=cr[k];
            p++;
            x1[p]=(x[j]*10+1)%n;
        }
        cr[fol[x[j]]+1]='2';
        if(ap[(x[j]*10+2)%n]==0||cmp(bst[(x[j]*10+2)%n],fol[(x[j]*10+2)%n],cr,fol[x[j]]+1)>0)
        {
            ap[(x[j]*10+2)%n]=1;
            obt[(x[j]*10+2)%n]=2;
            fol[(x[j]*10+2)%n]=fol[x[j]]+1;
            for(k=1;k<=fol[x[j]]+1;k++)
                bst[(x[j]*10+2)%n][k]=cr[k];
            p++;
            x1[p]=(x[j]*10+2)%n;
        }

    }
    if(ap[0]==1) break;
    u=p;
    for(j=1;j<=u;j++)
        x[j]=x1[j];
}
nr=0;
if(ap[0]==0) printf("Impossible\n");
else
{
    for(i=1;i<=fol[0];i++)
        printf("%d",bst[0][i]-48);
    printf("\n");
}
return 0;
}

Can anyone give me test 1.MY solution is in O(n+30)

I write program and get WA3:
the number must be minimal.

Any Help?

give solition

What is this test?

I do not understand!
Show me super-tests!

Thanks

This is my code:
{$I-,Q-,R-,S-}
VAR n,i,p,r   :longint;
    a         :array[0..30]of byte;

Procedure INIT;
  begin readln(n); end;
Procedure OUT;
  begin writeln('Impossible'); end;

Function OK:boolean;
var i,j,ost    :longint;
begin
  i:=1; ost:=0;
  while i<=a[0] do begin
    j:=i;
    while(ost<n)and(j<=a[0]) do begin ost:=ost*10+a[j]; inc(j); end;
    i:=j;
    ost:=ost mod n;
  end;
  OK:=FALSE;
  if ost=0 then OK:=TRUE;
end;
Procedure REC(r,p,pp:byte);
var i   :byte;
begin
  a[p]:=r; a[0]:=p;
  if p>pp then exit;
  if OK then begin for i:=1 to a[0]-1 do write(a[i]); writeln(a[a[0]]); halt; end;
  REC(1,p+1,pp); REC(2,p+1,pp);
end;

BEGIN
  INIT;
  if n mod 5<>0 then begin
    r:=n; p:=0;
    while r<>0 do begin inc(p); r:=r div 10; end;
    for i:=p to 30 do begin
      REC(1,1,i); REC(2,1,i);
    end;
  end else OUT;
END.

Edited by author 27.01.2007 00:49

Thanks.

Somebody has WA#15, but I have TLE# 12. Please help me.


Edited by author 21.10.2006 22:06