| ENG RUS | Timus Online Judge |
Обсуждение задачи 1081. Двоичная последовательность>>> i solved dp[i] - the number of sequences of length i [2] // Задача 1081. Двоичная последовательность 21 окт 2021 00:48 Ivan Re: i solved dp[i] - the number of sequences of length i [1] // Задача 1081. Двоичная последовательность 23 янв 2022 01:33 dp[i][j] - amount of i-digit numbers ending with j. therefore we form 2d table dp[n][2] then dp[i][0] = dp[i - 1][0] + dp[i - 1][1] dp[i][1] = dp[i - 1][1] It's not hard to see that dp[i][0] + dp[i][1] (i.e. number of all valid sequences) forms a fibonacci sequence. dp[i][0] + dp[i][1] = 2*dp[i - 1][0] + dp[i - 1][1] you can treat as f_n = 2*f_(n - 2) + f_(n - 3) But still, I don't know how to solve this problem :) Edited by author 23.01.2022 01:36 Edited by author 23.01.2022 01:37 So Sui Ming Re: i solved dp[i] - the number of sequences of length i // Задача 1081. Двоичная последовательность 6 апр 2024 22:41 dp[i][1] = dp[i - 1][1] is wrong, should be: dp[i][1] = dp[i - 1][0] Sergey AC with this formula [5] // Задача 1081. Двоичная последовательность 9 окт 2011 01:01 I've used this formula to solve this problem: a(n) = 2^(b(n)-1) + a(n - c(1+b(n))) b(n) = -1+floor(log(((n+0.2)*sqrt(5)))/log((1+sqrt(5))/2)); c(0) = 0, c(1) = 1, c(n) = c(n-1) + c(n-2) daftcoder [Yaroslavl SU] Re: AC with this formula // Задача 1081. Двоичная последовательность 16 окт 2011 17:46 INSANE! htzfun Re: AC with this formula // Задача 1081. Двоичная последовательность 1 май 2012 17:44 I don't want to live in this world anymore. Md. Taufique Hussain Re: AC with this formula // Задача 1081. Двоичная последовательность 3 июн 2013 13:32 wow!!!! you probably made an easy thing too complicated. Shubh Srivastava Re: AC with this formula // Задача 1081. Двоичная последовательность 24 май 2018 00:24 Looks like you're using golden ratio to calculate Fibonacci Hristo Nikolaev (B&W) Re: AC with this formula // Задача 1081. Двоичная последовательность 18 апр 2023 17:54 Way too complicated. I solved entirely using bitwise operations and an array with the first 64 Fibonacci numbers. motoras Admins, cannot submit any kind of rust solution for this problem [1] // Задача 1081. Двоичная последовательность 21 фев 2019 15:24 I get, Runtime error (non-zero exit code), even if I send a program such: fn main() { println!("{}",-1); } motoras Re: Admins, cannot submit any kind of rust solution for this problem // Задача 1081. Двоичная последовательность 21 фев 2019 16:16 If I paste the solution, in the submission text box, I am able to get an answer from the judge. If I uploaded I always get "Runtime error (non-zero exit code)" 4llower How to solve this tusk? // Задача 1081. Двоичная последовательность 9 апр 2018 15:50 CaCO3 nice problem // Задача 1081. Двоичная последовательность 22 дек 2017 08:10 it's cooooooool Husan please help! I have WA10! Give me some tests [2] // Задача 1081. Двоичная последовательность 6 мар 2008 19:36 Posazhennikov Maksim Re: please help! I have WA10! Give me some tests [1] // Задача 1081. Двоичная последовательность 16 июл 2013 01:35 1 10 S.Ged Re: please help! I have WA10! Give me some tests // Задача 1081. Двоичная последовательность 25 сен 2016 17:31 it could be useful if the poor guy is not dead already Bobur TLE#5, how can i solv this with fibonachchi, [6] // Задача 1081. Двоичная последовательность 23 мар 2008 16:22 i solved, but my algo so slow, how can i solve this problem faster, sorry for my english. thx! PersonalJesus Re: TLE#5, how can i solv this with fibonachchi, [5] // Задача 1081. Двоичная последовательность 17 апр 2008 17:16 Lets consider the sequence for n=4: 0000 0001 0010 0100 0101 1000 1001 1010 Try to find a connection between the number of all sequences with length 4, those which begin with 0 and those which begin with 1. After that look "deeper" and "deeper" into each sequence and try to find a way to generate the k-th sequence. Sorry that I'm not telling you the algorithm directly, but the feeling when you discover it yourself is great :) (it's even greater when you get Acc from 1-st submition :P). I hope that you find this helpful. Bobur Re: TLE#5, how can i solv this with fibonachchi, // Задача 1081. Двоичная последовательность 7 май 2008 18:53 thanks a lot, i think i can find it!! Bobur now, i've AC too!! [1] // Задача 1081. Двоичная последовательность 8 май 2008 18:49 cookie Re: now, i've AC too!! // Задача 1081. Двоичная последовательность 11 сен 2009 07:48 wow i feel good ¬¬_.'[smoke] ty for the idea † SiriuS † [TWYT Union] Re: TLE#5, how can i solv this with fibonachchi, // Задача 1081. Двоичная последовательность 18 май 2014 16:12 Tnk u. Ur hint is very helpful. I got AC! Mewtwo Re: TLE#5, how can i solv this with fibonachchi, // Задача 1081. Двоичная последовательность 25 июл 2016 13:18 PersonalJesus писал(a) 17 апреля 2008 17:16 Lets consider the sequence for n=4: 0000 0001 0010 0100 0101 1000 1001 1010 Try to find a connection between the number of all sequences with length 4, those which begin with 0 and those which begin with 1. After that look "deeper" and "deeper" into each sequence and try to find a way to generate the k-th sequence. Sorry that I'm not telling you the algorithm directly, but the feeling when you discover it yourself is great :) (it's even greater when you get Acc from 1-st submition :P). I hope that you find this helpful. Thank u so much.... :) It really feels wow... :D Sherxon WIUT What is Test 6? [1] // Задача 1081. Двоичная последовательность 11 фев 2015 11:33 Please give me test 6? Mewtwo Re: What is Test 6? // Задача 1081. Двоичная последовательность 25 июл 2016 13:09 Sherxon WIUT писал(a) 11 февраля 2015 11:33 Please give me test 6? Try these Tests: Test 1: 43 999999999 Ans=>1010000100100001010101000001000101000100101 Test 2: 42 999999999 Ans=> -1 Test 3: 40 100000000 Ans=>0010101001010100001010000010101010000010 aslan7470 WA 8 // Задача 1081. Двоичная последовательность 16 мар 2015 15:21 Please, send me test 8 Haile What's up with test #6 ? // Задача 1081. Двоичная последовательность 18 ноя 2013 14:46 My damned solution keep giving WA on test 6 with C11. I tested on big numbers and every corner case (yes, it works with 1 1 -> '0', yes, it gives '-1' on 3 6, etc..) Suggestions? What's in test 6? The exact same algorithm in python gives AC.. (and it's not a bignum issue, I tested the C version with 43 and 10**9) Edited by author 24.11.2013 01:26 Freezing Sun Accepted [3] // Задача 1081. Двоичная последовательность 22 авг 2009 07:57 AC at 0.015 145 KB :) Al-Xorazmiy Re: Accepted // Задача 1081. Двоичная последовательность 8 окт 2010 16:05 arif1122 Re: Accepted [1] // Задача 1081. Двоичная последовательность 3 апр 2012 13:13 AC @ .015 and 112KB :) PrankMaN Re: Accepted // Задача 1081. Двоичная последовательность 24 мар 2013 15:05 The same, AC 0.015 and 112 KB rrpai Crash why ? [6] // Задача 1081. Двоичная последовательность 29 дек 2006 11:18 My java program crashes for this. I do not understand why. I tested for even big inputs and it is working fine for me in my machine. How do I know where it crashed ? No information is given by judge. Peter Huggy Re: Crash why ? // Задача 1081. Двоичная последовательность 20 мар 2007 13:13 Test 6 contains numbers on different lines (I suppose so). I have Crash in my C# program on this test. And now it is AC! WangKaixiang Re: Crash why ? // Задача 1081. Двоичная последовательность 8 авг 2008 09:37 I have the same trouble, also with java! Scanner in = new Scanner(System.in); int n = in.nextInt(); int k = in.nextInt(); Above is like the A+B problem, I think it's right. Any one can help me plz?~:) WangKaixiang Re: Crash why ? // Задача 1081. Двоичная последовательность 8 авг 2008 09:40 I have the same trouble, also with java! Scanner in = new Scanner(System.in); int n = in.nextInt(); int k = in.nextInt(); Above is like the A+B problem, I think it's right. Any one can help me plz?~:) WangKaixiang Re: Crash why ? // Задача 1081. Двоичная последовательность 8 авг 2008 09:40 I have the same trouble, also with java! Scanner in = new Scanner(System.in); int n = in.nextInt(); int k = in.nextInt(); Above is like the A+B problem, I think it's right. Any one can help me plz?~:) WangKaixiang Re: Crash why ? // Задача 1081. Двоичная последовательность 8 авг 2008 09:51 I know why crash!~ for the input:40 1000000000 no problem what about this one: 1 1 I carsh because can't pass 1 1 But now AC~~~ barry Re: Crash why ? // Задача 1081. Двоичная последовательность 22 июл 2012 08:12 maybe....-1 imereli WA7 // Задача 1081. Двоичная последовательность 6 июл 2012 00:23 do you have any idea about this test? vongang Help ! What's the meaning of this problem ??? [1] // Задача 1081. Двоичная последовательность 9 окт 2011 08:43 Silent_coder Re: Help ! What's the meaning of this problem ??? // Задача 1081. Двоичная последовательность 27 янв 2012 23:56 You should print lexicographically kth sequence for length n like for n=3 we have, 000 -- 1st 001 -- 2nd 010 -- 3rd 100 -- 4th 101 -- 5th and for n=4 0000 - 1 0001 - 2 0010 - 3 0100 - 4 and so on.. you find kth sequence for length n :) Hope it helps > :) Sandro (USU) Problem 1081 "Binary Lexicographic Sequence". New tests were added. (+) [2] // Задача 1081. Двоичная последовательность 14 мар 2007 14:22 74 authors lost AC after rejudge. mariami [Freeuni] Re: Problem 1081 "Binary Lexicographic Sequence". New tests were added. (+) [1] // Задача 1081. Двоичная последовательность 15 сен 2011 03:00 I believe the tests are still weak. My solution which answers with "110...0" to "4 4", "5 6", "7 14", "8 22" got Accepted. Edited by author 15.09.2011 03:00 Edited by author 15.09.2011 03:00 Sandro (USU) Re: Problem 1081 "Binary Lexicographic Sequence". New tests were added. (+) // Задача 1081. Двоичная последовательность 15 сен 2011 13:43 I've added these tests, but you seem to be the only author who doesn't pass them. :) ENick(TNU) test#1 [2] // Задача 1081. Двоичная последовательность 28 сен 2008 19:08 Please,take me a test#1.My program's output on example test are "000",but got WA#1 many times....((( Edited by author 28.09.2008 19:09 Steven Re: test#1 [1] // Задача 1081. Двоичная последовательность 19 апр 2010 06:51 I think you forget this:"Write −1 if the number K is larger than the number of valid sequences" remdy21 Re: test#1 // Задача 1081. Двоичная последовательность 26 июл 2010 17:01 thanks a lot bobchennan Give advices to the person who has WA#1 [1] // Задача 1081. Двоичная последовательность 7 май 2009 17:57 It's very easy. TEST#1 is a data which result is -1(It means "no answer"). I submit my program ,and accept! Edited by author 07.05.2009 17:59 FaLLeN Re: Give advices to the person who has WA#1 // Задача 1081. Двоичная последовательность 24 июн 2009 23:30 Ops, he already found decision=) Edited by author 24.06.2009 23:32 hhh help me // Задача 1081. Двоичная последовательность 12 мар 2009 16:10 #include <iostream> using namespace std; long long n,k,a[45],i=0,b[50],j,t=0,r=0,z,c[50]; int main() { cin>>n>>k; a[0]=1; a[1]=2; t=n; for(i=2; i<=n; i++) a[i]=a[i-1]+a[i-2]; if(k>a[n]) { z=-1; cout<<z; return 0; } else{ b[1]=b[2]=0; b[3]=1; b[4]=2; for(i=5; i<=n; i++) b[i]=2*b[i-1]+1; while(a[i]<=k) { i++; j=i; } for(i=1; i<=j; i++) z+=b[i]; r=k+z-1; while(r!=0) { c[t]=r%2; r/=2; t--; } for(i=1; i<=n-t; i++) c[i]=0; for(i=1; i<=n; i++) cout<<c[i]; return 0; }} wa#2 Alias (Alexander Prudaev) what's wrong? [1] // Задача 1081. Двоичная последовательность 15 мар 2007 18:34 WA#9 But, Why? It' is right program! int p = n; for (int i = 0; i < n; i++) { if (f[p]>=k) s[i] = '0'; else { s[i] = '1'; k -= f[p]; } p--; } s[n] = 0; printf("%s\n",s); f[1] = 1, f[2] = 2, f[i] = f[i-1]+f[i-2]; Edited by author 15.03.2007 18:38 Yashar Abbasov Re: what's wrong? // Задача 1081. Двоичная последовательность 17 янв 2008 09:59 you forgot about -1. When k is bigger than all possible sequences then the answer is -1 Juri Krainjukov I don't understand what's wrong . [4] // Задача 1081. Двоичная последовательность 1 дек 2002 03:16 I checked this program for all sequences n<= and it worked properly. I don't see any reasons why it shouldn't work with another n. [code deleted] Edited by moderator 13.02.2007 20:54 Juri Krainjukov I found my mistake!!! [3] // Задача 1081. Двоичная последовательность 1 дек 2002 03:40 Georgiy Savchenko Re: I found my mistake!!! [2] // Задача 1081. Двоичная последовательность 5 фев 2007 03:03 I have approximately the same solution And I'm having WA6 What can be wrong? [code deleted] Edited by author 05.02.2007 03:03 Edited by moderator 13.02.2007 20:54 Georgiy Savchenko Re: I found my mistake!!! [1] // Задача 1081. Двоичная последовательность 6 фев 2007 04:27 Finally found out the problem. When you solve this problem take a look to overflows! Peter Huggy Re: I found my mistake!!! // Задача 1081. Двоичная последовательность 13 мар 2007 12:53 Georgiy Savchenko писал(a) 6 февраля 2007 04:27 Finally found out the problem. When you solve this problem take a look to overflows! I don't understand what overflow we can have. For N=43 the number of different sequences is equal to 1,134,903,170 (fits to int32).
|