Show all threads Hide all threads Show all messages Hide all messages | python wrong answer help | akidra_8881 | 1366. Presents | 27 Aug 2020 12:50 | 4 | import itertools surprize =[] x = int(input()) while x > 1: x -= 1 surprize.append(x) print (len(list(itertools.permutations (surprize)))) # n = (n - 1) * ((n - 1) + (n - 2)) surprise = [] def f(): number = int(input()) number = (number - 1) * ((number - 1) + (number - 2)) surprise.append(number) f() print(surprise[0]//3) Edited by author 23.08.2020 08:05 Edited by author 04.09.2020 14:21 Edited by author 04.09.2020 14:21 # wrong answer 11 def F(n): if n<2: return 1 return n*F(n-1) n = int(input()) print (int((F(n)+1)//2.718281828459045)) Try this formula f(n) = (n-1)*(f(n-1)+f(n-2)) ;) Edited by author 27.08.2020 12:50 Edited by author 27.08.2020 12:50 | WA11 | vtalgo16_plitvinov | 1366. Presents | 9 Jan 2020 03:09 | 2 | WA11 vtalgo16_plitvinov 29 Feb 2016 01:22 What is WA11? P.S. subfactorial func is correct P.P.S. Admins, is it possible there are some bugs here? Edited by author 29.02.2016 01:26 Re: WA11 Artem Maksunov 9 Jan 2020 03:09 | Thanks KIT | Sunnat | 1366. Presents | 29 Apr 2013 16:45 | 1 | my code base 100000 accepted 0.015 s 112 kb f[i] = (i-1)*(f[i-1]+f[i-2]) | WA14 | Freezing Sun | 1366. Presents | 17 Sep 2009 19:04 | 1 | WA14 Freezing Sun 17 Sep 2009 19:04 Could someone give me a few tests. I get WA14. I use the formula f(n) = n*f(n-1) + (-1)^n where f(1)=0 and f(2)=1. If someone could take a look at my code, post an email to send it to. | Thanks | freedevc | 1366. Presents | 28 Oct 2008 09:55 | 1 | Thanks freedevc 28 Oct 2008 09:55 Thanks KIT! I used F[n]=(n-1) * (F[n-1] +F[n-2]) to solve and I accepted. (^-^) | Please help!!! MLE#21.Here is code: | CHIDEMYAN SERGEY | 1366. Presents | 28 Feb 2008 22:52 | 8 | [code deleted] Edited by author 26.02.2008 23:57 Your helper about this problem probably may be MSDN because the problem has short simple code No problem.I get AC!!! Edited by author 26.02.2008 23:58 Can you send me your code, please? Li Wang Ji - The Interesting comrade, however.... The not solved tasks and asks to send the code! :) Actually i have solved nearly 200 problems but i submitted them under another nickname...more over i'm solving problems from this site for 3 years. and there are some problems that i can't solve for very long time... among them i have 1040,1066,1090,1107,1183,1189 and so on... therefore i ask for help from those who have solved these problems... in exchange for i can give any problem(if i have solved it)... and don't think about people bad if you don't know the situation... thx in advance... i hope you will help me Because rule of this site doesn't allow me to write solution here,write your e-mail address and I'll send you solution. Edited by author 28.02.2008 19:32 Thank you very much... my e-mail: liwang@mail.ru | What is the answer for N=1000? (-) | Sawe | 1366. Presents | 1 Feb 2007 22:52 | 3 | My AC program outputs 1480300003716690803639166141189660542377872467716834615546918460898888171222360711813189873910548675459590726189130673952565926739378359567722411682225282955956835967209806662206094278319048852420295993918145867464929632177223403177771955752603660100590106551721447382848788617582081310047350358184775693687864320616320161884468076859109403218325729966499814817722523251910400861544265546575384584445357657178710339466137717023503056252650043203882433860978792626830828468703859597819544889563899703925789442886604592950312345074787367168818241367836225845351388059822881452853157092920449246805492179297901159845450144415217557357263061954571997705726917546636177873914180435642912954635442323456238142340910752454816552406177681946008016133704545795503609904692149425055853719332957948207301824597654871393025676689264387133050350749500959081818757218706290284427041888179306280825957697116463097109027133895778139249850841954896876020466195020089609619793369712000118458329727664968204252323090144241603833525494325871758 0459951322429538762079323749213310619485478167533526424544336840634977862657715415393616579517641428024670820968425502109482342196679493125860192623788850206306117990892038912243728009669418031875672954018774352295528769340334462719200819324315004792668311620678980873752032993217592668963103980133320527177306869411988668143940820863453661616212548496824643329908661897203872632014352453015915512281606720947935915897510467617568994297290953898191551861043805896681345455213581061764326832650888474000756305781255775687211982794817701249872000284658432008360288350567522393041571024094338314208769709123757048278135225616280959304899730763636907169037354447533472772222696440183810580410403369885904650807263622112128476725617926138469557580012677787191460879974033313516907808504030187073870072198602651832414459785453439394011054887477145673354881969001489115029988337456903614450407565028424715429112260226257773863450239446806663726060151559041267799765637213898847989262978734485546962599318890221534174397659133578613 4612426484416557074485085137922648888557127618980204107341206517456111787177656668620397156874752365541689736459115633909848251703534756902949331850082296669410306980175719986482188446333446450823956158029544268395051423740042819986368612454904255206373684842598857136228239326853906860111911390847498545181350875035398066868621959973870036473108206470890805125591766035651660263166256071859066523494404932873989243033885387310363168734739688132495065765084286985470381074859852651721482664917019227944750044815550686001 Edited by author 29.12.2006 21:22 | for n=4 answer 6 ? | Lifanov | 1366. Presents | 17 Oct 2006 20:28 | 22 | You are wrong, Lifanov. Result is 9. DCBA CDBA BCDA BDAC BADC DCAB CDAB CADB DABC F(n)=(n-1)! +C(n,2)*F(2)*F(n-2)+C(n,3)*F(3)*F(n-3) ...C(n,n/2)*F(n/2)*F(n-n/2) it is solution , but how i solve this for n=1000 ?? I think the right is we need cals h(n) which is h(n)=f(n,0); f(0,b)=b!; f(1,b)=b*b!; f(a,b)=(a-1)*f(a-2,b+1)+b*f(a-1,b); but I can't prog this for small n, I think h(n) correct I send to judge the stupid prog which not used BIG NUMBERS(num where digits>20) and get wrong in 11 test I think in for 11 test f(a,b) not in longint(2*10^9) 2 hour &30 minute in hole. for n>100 it will be work very slow :( It works so slow... You may use this: f(0) = 1; f(1) = 0; f(n) = (n - 1)*(f(n - 1) + f(n - 2)) It will work much faster. Try to prove this formula. But, why this formula is right ??? We want to find out value of f(n). The child #1 can give his own boxe any of other (n - 1) childrens. Suppose, he give it to the child #2. The child #2 can give his boxe either to the child #1, or to one of the rest of children. In the first case we have f(n - 2), in the second - f(n - 1). f(1) = 0; f(n) = n*f(n-1) + (-1)^n; What you mean placing (+) and (-)? It is much used, but I don't understand it. The formula is very interesting. Re: (+) Victor Barinov (TNU) 25 Apr 2005 21:48 (-) mean, that all that I wanted to say is situated in theme (+) mean, that "will be continue..." :) Yes formula interesting. My friend "create" it, and we get AC on contest, but we can't to prove it "strongly". ------ Sorry for bad English :) end xMagGTU Дмитрий Тишкин GPRS 25 Apr 2005 22:09 >>The formula is very interesting. formula from Victor Barinov (TNU) f(1) = 0; (V1) f(n) = n*f(n-1) + (-1)^n; (V2) same as formula from Kit f(0) = 1; (K0) f(1) = 0; (K1) f(n) = (n - 1)*(f(n - 1) + f(n - 2)) (K2) cose: from v2: (-1)^n = f( n )- n *f(n-1) (-1)^(n+1)= f(n+1)-(n+1)*f( n ) sum they: 0 = f(n+1) +f(n)-(n+1)*f(n)-n*f(n-1) or 0 = f(n+1)- n*f(n)-n*f(n-1) or f(n+1)=n*(f(n)+f(n-1)) or f(n)=(n-1)*(f(n-1)+f(n-2)) That is (K2) ???Victor Barinov (TNU) can you explain how you thot for find V2??? В варианте : h(n)=f(n,0); (Tx) f(0,b)=b!; (T0) f(1,b)=b*b!; (T1) f(a,b)=(a-1)*f(a-2,b+1)+b*f(a-1,b);T(2) Можно расуждать так пуст (a) детей ещё могут нарватся(вытащить из оставшихся кучи свой хлам) и (b) детей не нарвутся уже точно (их презент уже нашёл нового хозяина). Расмотрим все возможные варианты ребёнка из группы а: 0) выташил свой, 1 случай -> Дальше лудше и не представлять:) 1) выташил презент кого то другого из a, (a-1 случай )-> тем самым сделав того б :) то есть (a-1)*f(a-2,b+1), 2) вытащил презент кого то из b (b случаев) -> a уменшилось на 1,число b осталось преждним: b*f(a-1,b) и граничные случаи: 0)когда все подарки чужие (то есть их бывшие владельцы уже взяли чьёто добро и ушли с воспитателем на прогулку): f(0,b)=b! 1) когда остался 1 хозяин , остальное чужое (хозяин может выбрать один из чужих(b вариантов), и случай сведется к предыдущему f(1,b)=b*b! >>if use this formula and BIG NUMBERS we have TLE. Послано >>Lifanov 24 апреля 2005 18:19 >>for n>100 it will be work very slow :( при использовании таблицы предвычислений!!!(то есть считать одно и тоже конкретное f(a,b) только раз )и арифметики BIGNUM tle не будет, не должно быть, э ну ... А вы Lifanov использовали таблицу или всё в рекурсии? >>>F(n)=(n-1)! +C(n,2)*F(2)*F(n-2)+C(n,3)*F(3)*F(n-3) ...C(n,n/2)*F(n/2)*F(n-n/2) (L1) it is solution , but how i solve this for n=1000 ?? ???Lifanov can you explain how you thot for find L1??? Кто силён в рекурентностях, как свести Tx-T2 к K0-K2? PS. Sorry, My Eng bad , so some Thot i write in rus, I understend that this site is for all piple , so if someWhy translate(If need) , that shud be great Мой друг ее угадал, как я уже, кажется, говорил. Sorry. We can to continue discussion by e-mail. Mine is victorbarinov@ua.fm L1 - Эта формула не верна. Она учитывает некоторые варинаты повторно. >>if use this formula and BIG NUMBERS we have TLE. Послано >>Lifanov 24 апреля 2005 18:19 >>for n>100 it will be work very slow :( при использовании таблицы предвычислений!!!(то есть считать одно и тоже конкретное f(a,b) только раз )и арифметики BIGNUM tle не будет, не должно быть, э ну ... А вы Lifanov использовали таблицу или всё в рекурсии? Думаю тут предвычисления не помогут.Причин две очень большой размер операндов (порядка 2600 десятичных знаков -> долго обрабытвать так как много операций) и во вторых нужно слишком много памяти даже для хранения одних только факториалов от 1 до 1000. А если попытаться хранить f(a,b) где 1<=a,b<=1000 то нужно 1 млн BIGNUM :) Sorry, Thot i write in rus Edited by author 27.04.2005 20:38 Edited by author 27.04.2005 20:38 Edited by author 27.04.2005 20:40 Нарыто: online база числовых последовательностей основаная на известном справочнике Слоана: http://www.research.att.com/~njas/sequences/index.html Оказывается для последовательности f= 0,1,2,9,44,265 из задачи 1366 есть имя(одно из имён) Субфакториал. Варианты решения(1366): 1)Классическое образование(классные преподы -классные студенты) -> знание что за весчь Субфакториал 2)Отличный ум и хорошая интуиция из ?,0,1,2,9,44 -> продолжить f(n)=n*f(n-1)+(-1)^n либо f(n)=(n-1)(f(n-1)+f(n-2)) (т.е. повторить Эйлера :) ) 3)чит во время интернет-контеста последовательности через интернет http://www.research.att.com/~njas/sequences/index.html PS f(a,b) ещё проще можно делать f(0,b)=b! f(a,b)=f(a-1,b)-f(a-1,b-1) Очень рекамендую поигратся http://www.research.att.com/~njas/sequences/index.html One of the rights of this forum is using only English language. Please, do it. The answer is exactly equal to round(n!/e) >You may use this: >f(0) = 1; >f(1) = 0; >f(n) = (n - 1)*(f(n - 1) + f(n - 2)) >It will work much faster. >Try to prove this formula. This formula is great, just like mine :D. But there is one small mistake: f(0)=0 and f(1)=1 Good luck ... Andrew, you're wrong - F(0)=1 and F(1)=0 :) For n=1, there is no way that the child gives his present to anybody else, so the answer has to be 0. P.S. I seem to have the best time for this problem... :D You are wrong, Lifanov. Result is 9. DCBA CDBA BCDA BDAC BADC DCAB CDAB CADB DABC What the difference between 1st and 5th variant??? A >> D >> C >> B >> A Edited by author 06.11.2005 18:05 |
|
|