So, if you have a number, that divides 2^n, than you can add some numbers in the begining (not more than 10) to get number, that divides 2^(n+1). That means, you can bruteforce all possible numbers, that you can add in the begining. Works in O(n*2^10)

## Russian ##

## 1 Идея ##

1) Представим число A в виде 10x+m1, где x - число десятков
m1=2 (m1 не может быть равно 1, так как в этом случае искомое число A нечетное и на 2^N не разделится). Разделим число на 2, получим A=5x+1.
2) Пусть x=10y+m2, где y - число сотен. После подстановки получим A=5(10y+m2)+1=50y+5m2+1. Чтобы число A разделилось на 2, надо, чтобы m2 было нечетным. Следовательно выбираем m2=1. После деления на 2 получим: A=(50y+5*1+1)/2=25y+3.
3) Пусть y=10z+m3, где z - число тысяч. После подстановки получим A=25(10z+m3)+3=250z+25m3+3. Чтобы число A разделилось на 2, надо, чтобы m3 было нечетным. Следовательно выбираем m3=1. После деления на 2 получим: A=(250z+25*1+3)/2=125z+14.
4) Пусть z=10t+m4, где t - число десятков тысяч. После подстановки получим A=125(10t+m4)+14=1250t+125m4+14. Чтобы число A разделилось на 2, надо, чтобы m4 было четным. Следовательно выбираем m4=2. После деления на 2 получим: A=(1250t+125*2+14)/2=625t+132.

Далее процесс повторяется N раз. Последовательность mN...m4m3m2m1 образует ответ. Алгоритм требует применения длинной арифметики. Общее решение достигается за N шагов.

## 2 Алгоритм ##
Пусть m[1]=2; a_[1]=5; b_[1]=1;
Цикл i = от 2 до n
нц
  m_[i]=(если b_[i-1] нечетное, то 1, иначе 2)
  b_[i]=(если b_[i-1] нечетное, то (a_[i-1]+b_[i-1])/2, иначе (2*a_[i-1]+b_[i-1])/2)
  (так как a_[i-1] нечетное всегда по определению)
  a_[i]=a_[i-1]*5;
кц

## English (in short) ##

## 1 The Idea ##

1) Let me A = 10x+m1, where x - number of Tens
m1=2 (m1<>1, as A - odd). Division A in 2, let's receive A=5x+1.
2) Let me x=10y+m2, where y - number of Hundreds. Then A=5(10y+m2)+1=50y+5m2+1. if A%2==0, m2 is odd. Then m2=1 and A=(50y+5*1+1)/2=25y+3.
3) Let me y=10z+m3, where z - number of Thousand. Then A=25(10z+m3)+3=250z+25m3+3. if A%2==0, m3 is odd. Then m3=1 and A=(250z+25*1+3)/2=125z+14.
4) Let me z=10t+m4, где t - number of Tens thousand. Then A=125(10t+m4)+14=1250t+125m4+14. if A%2==0, m3 is even. Then m3=1 and A=(1250t+125*2+14)/2=625t+132.

Further process repeats N time. Sequence mN... m4m3m2m1 forms the answer. The algorithm demands application of long arithmetics.

## 2 The Algo ##
Let me m[1]=2; a_[1]=5; b_[1]=1;
for i = 2 to n
begin
  m_[i]=(if b_[i-1] is odd, then 1, else 2)
  b_[i]=(if b_[i-1] is odd, then (a_[i-1]+b_[i-1])/2, else (2*a_[i-1]+b_[i-1])/2)
  a_[i]=a_[i-1]*5;
end

Give 9 test please.

Edited by author 12.10.2012 14:16

Edited by author 12.10.2012 14:16

#include <iostream>
#include <cmath>
using namespace std;
int i,x[1000],k;
int n,nr;
int main()
{
    cin >>n;
    for (i=1;i<=n;i++)
    {
        if (i%3==2)
            nr=nr*10+1;
        if (i%3==0)
            nr=nr*10+1;
        if (i%3==1)
            nr=nr*10+2;
    }
    i=n;
    while (i>=0)
    {
        x[i]=nr%10;
        nr=nr/10;
        i--;
    }
    nr=0;
    for (i=n;i>0;i--)
        nr=nr*10+x[i];
    k=1;
    for (i=1;i<=n;i++)
        k=k*2;
    if (nr%k==0)
        cout <<nr;
    else
        cout <<"No solution";
    return 0;
}
With this source code I get WA on test 4.
Pretty strange.HuH?

Edited by author 13.04.2011 13:45

Edited by author 13.04.2011 13:45

prove that for any n, exist number only whit 1 and 2 digit and have n digit that divided by 2^n.
like this:
n=1 -> 2
n=2 -> 12
n=3 -> 112
n=4 -> 2112
.
.
.

sorry for my poor english.
GOOD LUCK!!!

Whith n>4

Edited by author 27.06.2009 12:40

something wrong with the 1st test or tests
Following prog give me ans for all n (1..100)
but at first test it gave me TL

import java.math.BigInteger;
import java.util.Scanner;

public class Timus1407 {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        String s = "2";
        BigInteger two = new BigInteger("2");
        for (int i = 2; i <= n; i++) {
            BigInteger bigInteger = two.pow(i);
            String tmp = "1" + s;
            if(new BigInteger(tmp).mod(bigInteger) == BigInteger.ZERO){
                s = tmp;
            }
            else{
                s = "2" + s;
                if(new BigInteger(s).mod(bigInteger) != BigInteger.ZERO){
                    for(;;){}
                }
            }
        }
        System.out.print(s);
    }
}

#include  <iostream.h>
bool z(int);
void main()
{int n,i,q=1;
cin>>n;
for(i=1;i<=n;i++) q*=2;
for(i=0;i<10000;i++) if((z(i)) && (i%q==0)) {cout<<i; break;}
if(i==10000) cout<<"No solution";}
bool z(int x)
{int j=0;
while(x!=0) {if((x%10!=1) && (x%10!=2)) j++; x=x/10;}
if(j==0) return true;
else return false;}

I read N next follow (C#):
    int n=int.Parse(Console.ReadLine().Trim())
and have crash in test 5.

When I read N next follow
    string s=""; string s1="";
    while ((s1=Console.ReadLine())!=null) s+=s1;
    s=s.Trim();
    int n = int.Parse(s);
have Accepted

This is bug (test 5) or no?

Sorry for my bad english

I know that f(n) can be formed by adding 1 or 2 in front of f(n-1),but I dont see any order in addings.If you know,please tell me.

The biggest integer, that I find is 11111212122112, but I do not find any sequense or algo, what can I do???

Edited by author 09.01.2007 00:55