I solve reccurence, then pow to n(which takes log n to quickpow), but it's also TL. How can i improve this not writing my own long arithmetic? It can be solved only with 2 divisions in BigDecimal, but answer length is about 32000 so [maybe] toString gives TLE on conversion binary data to decimal representation. If somebody knows, how to solve this problem - please tell me 2^n = 10^(n*lg(2)) My AC solution: int n0 = (int) (Math.log10(2f) * (n - 1)); int n1 = (int) (Math.log10(2f) * n); int n2 = (int) (Math.log10(2f) * (n + 1)); int len = n1; if (n1 == n2 && n1 == n0 + 1 && n % 2 != 0) { len = n0; } Answer is len. I thought that this problem's solution is : t= (n-(n%10)) /4 +1 if(n>=30) { t=t+1; x=n-n%10; if(n>39&&((x/10)%2)) t=t+(x-30)/20; if(n>49&&((n-n%10)%4==0)) t=t+(x-40)/20; } t= t+ (n%10)/4; cout<<t; but it got WA#8. And i don't understand "if(n==1 && n1==n0+1 && n%2!=0)" statement are for what tests? Would you mind explaining for me! Thanks! bve, your way is brilliant. Thank you! bve, any links to why it works? I have AC in O(1), I use 2 formulas for odd and even n. Good problem, thanks to author! Now I combining both formulas in one. Who has accepted this task, please help with idea. I have not anithing idea! Use log10 to compare 2^n and 10^k 2 svr: I don't understand what you mean ? What I should use formule or ...? This sequence representable in the form of partial sums apparent number, the amount of which is equal to 1 / 6 - to find the desired response should compare the full amount of partial, asked n. only math. -- по-русски: эта последовательность представима в виде частичных сумм очевидного ряда, сумма которого равна 2/3 - чтобы найти искомый ответ необходимо сравнить всю сумму с частичной, задаваемой n. чистая математика. Thanks a lot!!! I've accepted this problem using precalc. Just quick long arithmetics and some trick to make source file of size 4 Kb... I meant the formula a[n]=2/3+(-1)^(n-1)/(3*2^(n-1)) to svr: you are right, this formula is correct (I can prove it). But how to take benefit from this? Of course, using this this formula I can right brute force quick long arithmetics. But this algo will be TL. we should take log10 from abs(2/3-a[n]) ?? use also the formula: 2/3=0.666666+10^(-k)*2/3 I think problem is very interesting. I was trying to solve it in "programming way" for a long time, but all my attempts lead to TL on N > 10000 values. Finally I finished with completely mathematical solution. I think that description from my source can help someone so I'll left it here... /* * Let x[n] be n-th element of given sequence. * Following formula for x[n] can be simply proved: * x[n] = 2/3 + (1/3)/(2^(n-1)) if n - odd * x[n] = 2/3 - (1/3)/(2^(n-1)) if n - even * Let delta = (1/3)/(2^(n-1)) = 0.000XXXX.. (X - any digit) * We can simply find number of leading zeroes after * decimal point (befor XXX..) as: * k = floor[ Log10(3*2^(n-1)) ] or * k = floor[ Log10(3) + (n-1)*Log10(2) ] * Obviously answer always will be k or k-1. * Consider (k-1)-cases: * [1] N - odd (add delta): * A = (1/3)/(10^k) = 0.0003333... (repeat 0 k times) * If A <= delta - then addition will affect k-th digit * and answer will be k-1. * [2] N - even (subtract delta): * A = (2/3)/(10^k) = 0.0006666... (repeat 0 k times) * If A <= delta - then subtraction will affect k-th digit * and answer will be k-1. * Compare logarithms instead of comparing values themself. */ #include <iostream> #include <math.h> using namespace std; int main() { int n,s; cin>>n; if(n%10==7) s=int((n-1)*log((double)2)/log((double)10)); else s=int(n * log((double)2)/log((double)10)); cout<<s<<endl; return 0; } What is lacking in terms? What could I forget? that is what my AC prog gives on some tests: n=7, res=1 n=7777, res=2340 n=77777, res=23412 n=99997, res=30101 n=99998, res=30102 n=52251, res=15728 n=55555, res=16723 n=100000, res=30102 6 1 66 19 666 200 6666 2006 66666 20068 666666 200686 6666666 2006866 66666666 20068666 666666666 200686663 Edited by author 16.02.2010 08:43 I use G++. #include <iostream> #include <math.h> using namespace std; int n; int main() {
cin>>n; cout<<floor(____________); return 0; } Read the FAQ part. ANY function which is included in math.h MUST get DOUBLE: cout<<floor((double)_____); I know the solution that got AC but it fails on my tests If you want this tricky test email my to ravemans at yandex.ru I just dont want them to be published!!! Edited by author 01.03.2008 17:38 This is impossible to create some "tricky" tests for the problem, since set of possible cases is discrete and quite small. I'm sure my program will pass your "tricky" tests =) I've told that i know one guy that got AC but he failed on my tests, ans i'm sure a lot of guys have such incompleteness. There are just a couple of such a test. I've got AC because i testet my program with brute force solution on ALL test cases. You can tell me your solution and i will tell you whether it passes it. Please, send your tests to timus_support@acm.timus.ru , and we will add them to this problem. already did it during the contest Solution's form contest was rejudged ? Can brute-force solution get AC? (quickly multiply of two's degree). Or there is a O(N) math solution? There is O(1) solution I wonder why authors of the problem didn't check all boundary cases... Or what other tricky tests can be found in such narrow set of possibilities??? Please send me your tests at sev[at]hotmail[dot]ru I just want to study you grogram ! thank you! For n=100000 answer is 30000? i can't find my bug. give me test#48, thx. var x, n : integer; t : real; begin readLn(n); if n mod 10 = 7 then t := (ln(3)+(n - 2) * ln(2))/ln(10) else t := (ln(3)+(n-1) * ln(2))/ln(10); x := TRUNC(t); t := t - x; t := exp(t*ln(10)); if t < 1.5 then dec(x); writeLn(x); end. Edited by author 05.03.2008 22:39 Could you explain your program ? How you get this formulas ? Thank you in advance ! if n is very big number then a[n] will be 2/3; lim(a[n]) = 2/3 when n->MAXnumber; you must continued fo'rmula, then you will have a[n] := (...)/2^(n-1); you must write this with 10^x (x-will be answer); like this 10^x = 2^(n-1); x =lg(2^(n-1)) => x = ln(2^(n-1))/ln(10); Hm, n ≤ 100000, but I've always thought that Integer in Free Pascal ≤ 32767... Anyway, I recommend you to switch Integer to Longint and Real to Extended. t := (ln(3)+(n-1) * ln(2))/ln(10) ... <- its really so if n mod 10 = 7 then t := (ln(3)+(n - 2) * ln(2))/ln(10) ... <- but i cant understand this rule if t < 1.5 then dec(x) ... <- is only? you realy must compare: +2/3/(2^n) and 1/3/(10^t) - when odd(n) -2/3/(2^n) and -2/3/(10^t) - when even(n) why its so? because now you must know will the remainder (+/-) 2/3/(2^n) corrupt the (t-1)-th digit of your diabolic number Edited by author 11.03.2008 22:18 thanks a lot! with your help, now i've AC var x, n : integer; begin readLn(n); if n mod 10 = 7 then dec(n); x := 3 * n div 10; writeLn(x); end. with this code WA#48; pls!!! help!!! var x, n : integer; begin readLn(n); if n mod 10 = 7 then x := TRUNC((n - 1) * ln(2)/ln(10)) else x := TRUNC(n * ln(2)/ln(10)); writeLn(x); end. Could you give me some hints? I'm eager to solve this problem, but I have no idea. |
|