| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | python wrong answer help | akidra_8881 | 1366. Подарки | 27 авг 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. Подарки | 9 янв 2020 03:09 | 2 | WA11 vtalgo16_plitvinov 29 фев 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 янв 2020 03:09 | | Thanks KIT | Sunnat | 1366. Подарки | 29 апр 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. Подарки | 17 сен 2009 19:04 | 1 | WA14 Freezing Sun 17 сен 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. Подарки | 28 окт 2008 09:55 | 1 | Thanks freedevc 28 окт 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. Подарки | 28 фев 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. Подарки | 1 фев 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. Подарки | 17 окт 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 апр 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 апр 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 |
|
|
