Show all threads Hide all threads Show all messages Hide all messages | My stupid solution | andreyDagger | 1407. One-two, One-two | 27 Nov 2021 13:25 | 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) | My Solution is here | vetas | 1407. One-two, One-two | 6 Mar 2019 15:44 | 4 | ## 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 | What about 9 test | Alexander Goncharov | 1407. One-two, One-two | 12 Oct 2012 14:22 | 2 | 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 | Intresting thing | Berbinschi Tudor | 1407. One-two, One-two | 13 Apr 2011 13:45 | 1 | #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 | HINT | hoan | 1407. One-two, One-two | 26 Dec 2010 22:03 | 1 | HINT hoan 26 Dec 2010 22:03 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!!! | Who can get some tests? | Anton_Karpinsky | 1407. One-two, One-two | 7 Nov 2010 12:55 | 2 | 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 ^_^") | To Admins | Ibragim Atadjanov (Tashkent U of IT) | 1407. One-two, One-two | 25 Oct 2010 12:51 | 3 | To Admins Ibragim Atadjanov (Tashkent U of IT) 24 Oct 2010 15:19 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. | where is my mistake? | ooo | 1407. One-two, One-two | 3 Feb 2010 21:00 | 2 | #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=) | To Admins | vetas | 1407. One-two, One-two | 31 Dec 2008 13:29 | 3 | 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. | Is there a recurrence formula? | Grigor Gevorgian | 1407. One-two, One-two | 17 Sep 2008 20:55 | 2 | 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). | Can this problem be solved WITHOUT long arithmetics? (-) | elmariachi1414 (TNU) | 1407. One-two, One-two | 27 Aug 2008 01:36 | 1 | | What's test4 | TUIT_MAD | 1407. One-two, One-two | 1 Apr 2008 12:28 | 1 | | Give me some ideas..please! | realvan1 | 1407. One-two, One-two | 4 Mar 2007 20:09 | 2 | please send me solution of this problem without big numbers on my mail gsaghinadze@yahoo.com | Please, help!!! | [SSAU_#617]snipious_#1 aka Pimenov Sergey Nikolaevich | 1407. One-two, One-two | 6 Feb 2007 18:06 | 10 | Please, help!!! [SSAU_#617]snipious_#1 aka Pimenov Sergey Nikolaevich 9 Jan 2007 00:52 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!!! 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. |
|
|