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 dp[i][1] = dp[i - 1][1] is wrong, should be: dp[i][1] = dp[i - 1][0] 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) I don't want to live in this world anymore. wow!!!! you probably made an easy thing too complicated. Looks like you're using golden ratio to calculate Fibonacci Way too complicated. I solved entirely using bitwise operations and an array with the first 64 Fibonacci numbers. I get, Runtime error (non-zero exit code), even if I send a program such: fn main() { println!("{}",-1); } 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)" 1 10 it could be useful if the poor guy is not dead already i solved, but my algo so slow, how can i solve this problem faster, sorry for my english. thx! 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. thanks a lot, i think i can find it!! wow i feel good ¬¬_.'[smoke] ty for the idea Tnk u. Ur hint is very helpful. I got AC! 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 Please give me test 6? 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 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 AC at 0.015 145 KB :) AC @ .015 and 112KB :) The same, AC 0.015 and 112 KB 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. 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! 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?~:) 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?~:) 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?~:) 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~~~ do you have any idea about this test? 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 > :) 74 authors lost AC after rejudge. 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 I've added these tests, but you seem to be the only author who doesn't pass them. :) 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 I think you forget this:"Write −1 if the number K is larger than the number of valid sequences" 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 Ops, he already found decision=) Edited by author 24.06.2009 23:32 #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 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 you forgot about -1. When k is bigger than all possible sequences then the answer is -1 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 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 Finally found out the problem. When you solve this problem take a look to overflows! 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). |
|