Страница 1 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) Give 9 test please. Edited by author 12.10.2012 14:16 Edited by author 12.10.2012 14:16 My program print this result: 9 212122112 #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!!! 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); } } Strange... On my computer it gives nothing except infinite running. You shouldn't compare BigInteger with "==". Use "compareTo" method. Strange but it is not tl in my computer. Its working still. Whith n>4 Edited by author 27.06.2009 12:40 5 -- 22112 6 -- 122112 7 -- 2122112 8 -- 12122112 9 -- 212122112 10 -- 1212122112 (Maybe it will be useful for someone ^_^") 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 There were empty lines before the number in the Test 5. We have fixed all tests in this problem. Now they don't contain leading or trailing spaces and empty lines. I think, "int.Parse(Console.ReadLine())" should be OK now. ## 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 thank you! excellent idea! Можно проще. Индукция: для любого n существует число x(n) из 1 и 2 длиной n, делящееся на 2^n. База: n=1=>x(1)=2. Переход n->n+1: если x(n) делится на 2^(n+1), то в качестве x(n+1) можно взять x(n+1)=2x(n) (т.е. слева приписать 2), иначе x(n+1)=1x(n). Edited by author 10.03.2019 13:22 #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;} Imagine that n is 100. q (2 ^ 100) will be overflowed. You must have 10000 digits but not number under 10000=) 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. AFAIK, I solved it looking at base-2 representation of 122221212121...(base-10). With each step you multiply it by 10 and add 1 or 2 (next decimal digit from left to right). You want the result to become 10000000000000...000 (base-2). 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 86 digits left for solution Use long arithmetics why 86? my solution has 98 digits. BTW, does anyone know what is the shortest answer? My helpprogram work very long... %((( Edited by author 09.01.2007 08:43 It's very easy to constract answer with length N... (induction) It's very easy to constract answer with length N... (induction) You mean that it can be solved without long numbers? I can not find nothing better than divide number on 2^N on every step Let H[N]- number under considaration. Let we define integer K[N]=H[N]/(2^N); Then K[N+1]=(m*(5^(N-1))+K[N-1])/2; where m=1 or 2; and K[1]=1; We solve this reccurence in long arithmetics. In my module was bad long dividing, thank to this problem that bug removed now. I find 2^100 and than add 2^100 until all digits will be 1 and 2... My programm worked 2 hours, but didn't give me the answer!!! Am I right??? Some number is divisible on 2^n if number which has been written down in his last n digits is divisible on 2^n. Means we can consistently select digits in the answer. please send me solution of this problem without big numbers on my mail gsaghinadze@yahoo.com Страницы: 1 |
|