| ENG RUS | Timus Online Judge |
Обсуждение задачи 1605. Дьявольская последовательностьFaeton (Kyiv - Mohyla Academy) is java's BigDecimal acceptable? [6] // Задача 1605. Дьявольская последовательность 6 мар 2008 16:17 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? elmariachi1414 (TNU) Re: is java's BigDecimal acceptable? [5] // Задача 1605. Дьявольская последовательность 29 мар 2008 01:21 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 bve Re: is java's BigDecimal acceptable? [4] // Задача 1605. Дьявольская последовательность 29 окт 2008 00:05 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. freedevc Re: is java's BigDecimal acceptable? // Задача 1605. Дьявольская последовательность 4 ноя 2008 17:57 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! Artem Khizha [DNU] Re: is java's BigDecimal acceptable? [1] // Задача 1605. Дьявольская последовательность 31 окт 2010 23:24 bve, your way is brilliant. Thank you! balatskayaolha Re: is java's BigDecimal acceptable? // Задача 1605. Дьявольская последовательность 20 фев 2020 21:30 Thanks you! exwRabbits_AlMag(VNTU) Re: is java's BigDecimal acceptable? // Задача 1605. Дьявольская последовательность 18 фев 2020 04:27 bve, any links to why it works? Gleb Formula of x[n], n>=1 // Задача 1605. Дьявольская последовательность 25 май 2018 22:59 x[n] = J[n]/2^(n-1), J[n] - Jacobsthal number and J[n] = (2^n - (-1)^n)/3. https://en.wikipedia.org/wiki/Jacobsthal_number [RISE] Levon Oganesyan [RAU] I can't believe, but it was right idea! [1] // Задача 1605. Дьявольская последовательность 30 май 2014 02:44 I have AC in O(1), I use 2 formulas for odd and even n. Good problem, thanks to author! [RISE] Levon Oganesyan [RAU] Re: I can't believe, but it was right idea! // Задача 1605. Дьявольская последовательность 1 авг 2014 12:33 Now I combining both formulas in one. Nurbek_[KTMU MANAS] HELP WITH IDEA!!! [10] // Задача 1605. Дьявольская последовательность 3 мар 2008 13:33 Who has accepted this task, please help with idea. I have not anithing idea! svr Re: HELP WITH IDEA!!! [8] // Задача 1605. Дьявольская последовательность 3 мар 2008 13:43 Use log10 to compare 2^n and 10^k Nurbek_[KTMU MANAS] Re: HELP WITH IDEA!!! [7] // Задача 1605. Дьявольская последовательность 3 мар 2008 13:53 2 svr: I don't understand what you mean ? What I should use formule or ...? alex zaharov Re: HELP WITH IDEA!!! [2] // Задача 1605. Дьявольская последовательность 3 мар 2008 14:14 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. чистая математика. Nurbek_[KTMU MANAS] Re: HELP WITH IDEA!!! [1] // Задача 1605. Дьявольская последовательность 3 мар 2008 16:06 Thanks a lot!!! Vedernikoff Sergey Re: HELP WITH IDEA!!! // Задача 1605. Дьявольская последовательность 3 мар 2008 16:31 I've accepted this problem using precalc. Just quick long arithmetics and some trick to make source file of size 4 Kb... svr Re: HELP WITH IDEA!!! [3] // Задача 1605. Дьявольская последовательность 3 мар 2008 20:45 I meant the formula a[n]=2/3+(-1)^(n-1)/(3*2^(n-1)) vgu Re: HELP WITH IDEA!!! [2] // Задача 1605. Дьявольская последовательность 5 мар 2008 02:27 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. KIRILL(ArcSTUpid coder:) Re: HELP WITH IDEA!!! // Задача 1605. Дьявольская последовательность 5 мар 2008 03:07 we should take log10 from abs(2/3-a[n]) ?? svr Re: HELP WITH IDEA!!! // Задача 1605. Дьявольская последовательность 5 мар 2008 10:16 use also the formula: 2/3=0.666666+10^(-k)*2/3 SkorKNURE Re: HELP WITH IDEA!!! // Задача 1605. Дьявольская последовательность 29 окт 2010 05:38 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. */ 8P What is lacking in terms? What could I forget? // Задача 1605. Дьявольская последовательность 15 фев 2010 21:23 #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? Oracle[Lviv NU] Some tests [1] // Задача 1605. Дьявольская последовательность 3 ноя 2008 22:25 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 8P Re: Some tests // Задача 1605. Дьявольская последовательность 21 янв 2010 08:57 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 And IV What c++ compile is used on Timus? CE [1] // Задача 1605. Дьявольская последовательность 7 мар 2008 01:54 I use G++. #include <iostream> #include <math.h> using namespace std; int n; int main() { cin>>n; cout<<floor(____________); return 0; } Seyyed Mehran Kholdi Re: What c++ compile is used on Timus? CE // Задача 1605. Дьявольская последовательность 5 июн 2008 22:21 Read the FAQ part. ANY function which is included in math.h MUST get DOUBLE: cout<<floor((double)_____); RAVEman More test cases!!! [11] // Задача 1605. Дьявольская последовательность 1 мар 2008 17:29 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 Vedernikoff Sergey Re: More test cases!!! [5] // Задача 1605. Дьявольская последовательность 1 мар 2008 22:47 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 =) RAVEman Re: More test cases!!! [4] // Задача 1605. Дьявольская последовательность 2 мар 2008 00:04 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. Sandro (USU) Re: More test cases!!! [3] // Задача 1605. Дьявольская последовательность 2 мар 2008 00:20 Please, send your tests to timus_support@acm.timus.ru , and we will add them to this problem. RAVEman Re: More test cases!!! [2] // Задача 1605. Дьявольская последовательность 2 мар 2008 00:24 already did it during the contest Vladimir Yakovlev (USU) Your tests have been added [1] // Задача 1605. Дьявольская последовательность 2 мар 2008 01:24 Chmel_Tolstiy Re: Your tests have been added // Задача 1605. Дьявольская последовательность 2 мар 2008 03:24 Solution's form contest was rejudged ? vgu Brute force [3] // Задача 1605. Дьявольская последовательность 2 мар 2008 12:16 Can brute-force solution get AC? (quickly multiply of two's degree). Or there is a O(N) math solution? RAVEman Re: Brute force [1] // Задача 1605. Дьявольская последовательность 2 мар 2008 21:59 There is O(1) solution Vedernikoff Sergey Re: Brute force // Задача 1605. Дьявольская последовательность 3 мар 2008 00:43 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 DK [Samara SAU 1: X2008] Re: Brute force // Задача 1605. Дьявольская последовательность 14 май 2008 00:48 Yes, brute force can get AC e.g., my 1st solution http://acm.timus.ru/status.aspx?space=1&num=1605&author=46516 Momchil Tomov Re: More test cases!!! // Задача 1605. Дьявольская последовательность 28 мар 2008 14:51 is 386 one of them? freedomyunfei who can give the program for 1002 // Задача 1605. Дьявольская последовательность 7 май 2008 18:30 I just want to study you grogram ! thank you! Aydar Bykeev !!! [2] // Задача 1605. Дьявольская последовательность 1 мар 2008 15:46 For n=100000 answer is 30000? SuperLight Re: !!! // Задача 1605. Дьявольская последовательность 1 мар 2008 22:41 NO))))) Aneto Re: !!! // Задача 1605. Дьявольская последовательность 15 мар 2008 22:03 30102 Bobur WA#48, pls help!!! [6] // Задача 1605. Дьявольская последовательность 5 мар 2008 15:43 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 Denis Re: WA#48, pls help!!! [1] // Задача 1605. Дьявольская последовательность 10 мар 2008 01:40 Could you explain your program ? How you get this formulas ? Thank you in advance ! Bobur Re: WA#48, pls help!!! // Задача 1605. Дьявольская последовательность 10 мар 2008 21:16 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); denton Re: WA#48, pls help!!! [1] // Задача 1605. Дьявольская последовательность 10 мар 2008 23:39 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. Bobur Re: WA#48, pls help!!! // Задача 1605. Дьявольская последовательность 11 мар 2008 20:22 it doesn't work... Fox Re: WA#48, pls help!!! [1] // Задача 1605. Дьявольская последовательность 11 мар 2008 21:24 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 Bobur thank you veryyy much!!! // Задача 1605. Дьявольская последовательность 11 мар 2008 23:15 thanks a lot! with your help, now i've AC Bobur WA#8!!! pls give me more tests [1] // Задача 1605. Дьявольская последовательность 4 мар 2008 17:58 var x, n : integer; begin readLn(n); if n mod 10 = 7 then dec(n); x := 3 * n div 10; writeLn(x); end. Bobur Re: WA#8!!! pls give me more tests // Задача 1605. Дьявольская последовательность 4 мар 2008 22:49 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. Lee, Taeyoon @ ICU Could you give me some hints? // Задача 1605. Дьявольская последовательность 2 мар 2008 10:09 Could you give me some hints? I'm eager to solve this problem, but I have no idea.
|