Can someone tell me what is 13.test case? Also, is the only way to solve this problem using long arithmetic? I got time exceeded error. Can somebody tell what is test case? Or tell me how can I optimize my code? I even found to solutions using dp. void lemontale(int n,int k,vector<vector<BigInt>> &mem){ BigInt big_n = BigInt(n); BigInt big_k = BigInt(k); BigInt dva_big = BigInt(2ull); if (mem[n-1][k] == BigInt()){ if (n<0) return ; else if (k==0 && n==1){ mem[n-1][k] = BigInt(1);
} else if (k==0){ lemontale(n-1,k_start,mem); mem[n-1][k] = mem[n-2][k_start];
} else if (n<=k){ BigInt rez = dva_big^big_n;
mem[n-1][k] = rez; } else{
lemontale(n-1,k_start,mem); lemontale(n-1,k-1,mem); mem[n-1][k] = mem[n-2][k-1]+mem[n-2][k_start]; } }
} void lemontale2(int n,int k,BigInt* mem){ BigInt dva_big = BigInt(2ull);
if (mem[n-1]==BigInt()){ if (n<=k) mem[n-1] = dva_big^BigInt(n); else for(int i=0;i<=k;i++){ if (n-i-1 != 0){ lemontale2(n-i-1,k,mem); mem[n-1]+=mem[n-i-2]; } else{ mem[n-1]+=1; } } }
} Edited by author 10.01.2024 16:08 Edited by author 10.01.2024 16:09 Edited by author 10.01.2024 16:09 Edited by author 10.01.2024 16:09 WA #3: 1 1 -> 2 WA #5: 2 1 -> 3 WA #7: 5 3 -> 29 WA #8: 6 5 -> 63 WA #9: 5 1 -> 13 要用高精度。。。long long只对10个点。。。 Use high precision. . . Long long only has 10 points. . . Could anyone give a hint about Test 12? What does it look like? Some possible overflow, etc. My program returns correct answer on 10000 10000 test. @Admins, can you please provide me with JUST an answer for this test? If so, my e-mail: dostoyevsky_at_ukr.net. Thanks a lot. Got AC. Made a mistake in printing long number — need no print leading zeros for non-top parts of number Hello! I have strange WA 22 and really don't understand why. Can anyone help to find the bug in my code. (corrected) Edited by author 04.12.2016 20:25 Your answer to 10000 10000 seems correct, except it misses the very first digit. Thanks! Stupid mistake, as always, just increased size of long number. Give me some test, please!!! 5 3 - 29. 100 0 - 1. 10000 10000 - http://pastebin.com/CMNizjgM . 100 100 - 1267650600228229401496703205376 Edited by author 02.03.2016 13:43 Edited by author 02.03.2016 13:44 Edited by author 23.12.2006 13:14 I also have the same problem. My algorithm runs in O(nk) time it will surely get TLE... how to optimize it? You can do it in O(n) with + and - long arithmetics Still TLE#18. I do it in O(n) with + and - long arithmetics. Help, please! Should I do long arothmetic by 4 numbers? Мне делать длинную арифметику по 4 знака? Мені робити довгу арифметику по 4 знака? :) Edited by author 23.12.2006 14:42 I got accepted, you can do long arithmetic with 8 numbers. By the way I don't think using 4 numbers (10000) as radix will TLE. :) Thanks, I have AC! But a little question: In my first solution (with 1 number) I used array[1..10000][1..3200] of shortint; than, (with 2 numbers) - array[1..10000][1..1600] of integer; Isn't it the same? But in the second case I got MLE! Whats wrong? Is sizeof(integer)=sizeof(longint)? Thanks. That depends on certain compilers. Some compilers will tend to have sizeof(shortint) = sizeof(integer) or sizeof(integer) = sizeof(longint)... that's where the problem lies...:( shortint lies in range -128..127, so sizeof(shortint)=1, while sizeof(integer)=sizeof(longint)=4. So, second array eats double amount of memory in comparison with first one. integer lies in range -32768..32767. It's 2 bytes. Ans longint is in -2147483648..2147483647 It's 4 bytes. integer lies in range -32768..32767. It's 2 bytes. Ans longint is in -2147483648..2147483647 It's 4 bytes. Do you use TP? FreePascal 32-bit compiler Integer - 32 bit Read FAQ for differences I use FP. I write a program var t:integer; begin t:=0; writeln(sizeof(t)); end. It shows 2. var t:longint; begin t:=0; writeln(sizeof(t)); end. Shows 4. sizeof(Integer) depends on version of FPC I use O(n) DP with long arithmetics on 9 digits. Because 2*a-b falls in range -1e+9 ... +2e+9 for every digit. Just use prefix sums to optimise dp. Edited by author 02.03.2016 13:39 I didn't use any long arithmethic but i think it should passes the first test. But judge says WA !!! Help please if you can #include <iostream> using namespace std; long long d[10001][2]; int main () { int n, k;
cin >> n >> k;
d[0][0] = 1; d[0][1] = 0;
int i, j;
for (i = 1; i <= n; ++i) {
d[i][1] = 0; for (j = 1; j <= k; ++j) { if (n - j < 0) continue;
d[i][1] += d[i - j][0]; }
d[i][0] = d[i - 1][0] + d[i - 1][1]; }
cout << d[n][0] + d[n][1];
return 0; } Is it possible to provide the test case? I think the test case is not 30 30 as said in a place in the forum because my code passes that test case I think. Can anyone tell me the actual result of this test? and its input?.. I've been trying like 2 months from now.. so I'm pretty stuck here.. gaston770@gmail.com.. I used O(n) with sum and subtract. But it's too slow to AC Please someone help me. pp: please sorry got AC. i calculated power every time which made it slow later i just multiplied by 2 each time which gave AC I have WA,but I know that my algo is right.Maybe some mistakes with long arithmetics.So,please, give me some tests to help me correct it.Thank!!! Edited by author 03.05.2008 02:44 Edited by author 03.05.2008 02:45 Is my algo correctm or it's defenetely wrong? Firstly, i count all possible changes 2^n. Then i withdraw changes which do not siunt the censor (by fixing k+1 not changed lemons). Later i fix k+2 (one banana and k+1 lemons) and count new unsiutable chages. res = 2^n; res = res - 2^(n-k-1); for (int i = 0; i <= k && i+k+1<n; ++i) { int t = n - k - 2; if (t<0) break; res = res - 2^t; } I've got WA9, so this is cause my algo or my implementation? :) P.S. Nothing to change, then n==k, also must be counted or not? This problem like a 1009 (k=2) Solution - dp try to find f[n] through previous values(f[n-1],f[n-2],..) And you must to use long arithmetics... Thant for clue. Now I got AC. Java's BigInteger and none need for long arithmetic. Mine first algo was wrong, it's need about 2 cicles with minus more to be correct. Can you say some clue about your DP, because mine gets TL on test 13, I use Java, btw. F(n,1/0) i - position 1 - limon 0 - banana F(i,1) = sum(F(z,0)); F(i,0) = F(i-1,1)+F(i-1,0) Give me this test plz It is first test, where result exceeded int: 30 30 - this can be I have probelm with this test too. If n=30, k=30, result 1073741824? Edited by author 29.08.2007 23:15 YES BUT YOU MUST WRITE LONG ARITHMETIC (MINUS AND SUM IN MY SOLVE) What should I do,when n=k.For example n=k=3 Possible ways LBL BLB BBB BBL LBB LLB AND LLL. Should I count LLL too? Problem says: заменить некоторые «лимоны» на гораздо более политкорректные «бананы» таким образом, чтобы задача всё-таки была допущена к контесту. Сколькими способами это можно сделать? I think I shouldn't count LLL too.Am I right? Thank! Edited by author 31.08.2007 18:17 Read the problem statement carefully: "if a word "lemon" occurs more than K times successively, the problem will be immediately disqualified from the contest" Why don't you count case LLL and (what is more strange) case BLL??? They both satisfy problem statement requirement. Right answer for test 3 3 is 8. Thank you very much! Thank you very much!!!It helps me.P.S.I forget BLL. Edited by author 31.08.2007 23:58 give me this test and it's result please. I am stupid :) now I have problems with WA#11 Edited by author 29.08.2007 23:09 |
|