| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| Statement clarification | Fajnyi | 1677. Обезьяна за клавиатурой | 18 апр 2024 20:53 | 1 |
So clearly realising (if monkey will follow others then monkey never will create that word because of re-using letters)? |
| What does it mean?(Что это означает) | daminus | 1677. Обезьяна за клавиатурой | 22 янв 2018 15:37 | 2 |
I don't understand!!! How given (2, aa) answer is 6. I think that must be 4!!! Please help, who know that!!!!! (Я не понел Как 2 и аа могут дать ответ 6 Я думаю что должно быть 4 Помогите------------) expected time is inifinite sum of time * p(time), where p(time) is the probability to get resulting string exactly in 'time' steps.
for aa:
probability to get 'aa' in exactly 1 step is 0. (simple)
probability to get 'aa' in exactly 2 steps is 1/4 (simple)
probability to get 'aa' in exactly n steps is probability to get a string of length == n - 1 that ends with 'a', and doesn't contain 'aa' as substring multiplyed by 1/2 (when you have such string there is a 1/2 chance that the next character will be 'a').
for n == 3: 1/8, for n == 4: 1/8 etc.
If you simulate such steps and get a sum for n = [2.. 10000] you will get answer equal to 6
PS.
this is simulation of 10 steps:
0.000000 * 1
0.250000 * 2
0.125000 * 3
0.125000 * 4
0.093750 * 5
0.078125 * 6
0.062500 * 7
0.050781 * 8
0.041016 * 9
0.033203 * 10
|
| Fail(checker) | White2302(Vologda ML) | 1677. Обезьяна за клавиатурой | 30 июл 2015 16:15 | 1 |
when i submit i have fail(checker). What can I do with that? |
| Does this problem need FFT? | Sevenk | 1677. Обезьяна за клавиатурой | 27 ноя 2013 00:06 | 2 |
After AC, I find that the answer is NO.
Edited by author 20.08.2010 09:25 You can speed up your solution by using FFT though. |
| can you please tell me answer for this test..(+) | Alias aka Alexander Prudaev | 1677. Обезьяна за клавиатурой | 6 фев 2013 17:36 | 3 |
26
aaaaaaaaaaaaaaaaaaaaaaaaaaaa....
(30000 times char 'a') I can't tell it to you because it contains more then 40000 digits))
I think this fact could be used as a hint. 164995638358040283998558247271204747554937412400241772943263871150905944349595615420081206975554820850921624856054038153859196529033815101903464382846692933053008808266967597945511250588747177427538894981681583079428776338455646935210864233795821563020358516088934115001021851907911483642912292826913089776493236970804939871339375091002303082116223043331364594585979091746578257809320051137569263537783308444200808535237613293477380526910155345869780882916873693851524881515887855876464002995834434158195569663050992960397989683511448895106705315045331118186333702824424485281416335270263881221177902127150866297795088677334244804727372613504364778767285203002121931664243096812815473099417899083781537002813577269572235032661940635923834388626857680880921172212006050352406906806881942580528128796940321297510619511595568037446623709367064442940206976165321186007068121732632151689817959463145559149030804764906277063600946187428630986394779798699707606708497131579593605452031297452580572128253295691878569265293487442776742057687119126789583591013032430962609384093279129083714076174815249775267334986482295792272824023752317578271201890821798753473491128324270802728478351157578289866778922804301313128438233196906277679850250656248399945522646675413579275432734963496821710803418553083181986490798163802206155915412722579961069257323856859979895542471949935784925986852932926174376038473739932834041573692750676452645426442009926964769367151014148870225933674033884229905491844531436067884832391451948846438338609497257840459258259779132759347096854704260929638577327617785370539875183166506177135522770142090076514248697595661195575711890385510179696486418116150821714108145642661315317632683312054460598535343098569213319968969563454493485474903400399900045282088008250409745700489433096682190819067118709820443599009075951759220206159008379183421001756174192278283209374666306732203299044725642506005932378967534778249681379403925236249614794074146603437299391985749154167969860521496725848483677570317179641547418002623323820924483356655583751072227716900410538147444695924946601769926213495145263517860298058293624021565848279895901698248692292196109755427544568154849663183091771663218520762773872554200731296319405085005765572872387865866558398814061823815739537349546468772750411999964555060515024933502272672415699744861209975497251761855231751143849219304424954910835506930691882329693510272480481519990747128674034813643067245327015254691582773568615332922960431707490429828748139516688111278955093870096251294507100245316864507978900277279541499261656766853499758779186003084748784890318404455700180831248179300513219071437806429206131581963265561442447318793173355588408741528003849942881295457830392606700329315404658349617193595077962495797990150344461761854778548727916973475404718057373401975941282882439357467226947116438266100582617355765894779304708252821363516888523920668198721770698031259170441792664948798591427408955347674247270754824394654047692230955306688514506028717781023638749167985873321958975335582847256149238605109067186669548485055626073230113984031014833644251935385431385012031913941836442839086567413175099755848287678627313317001610262061253930512465058482516886542337626325880451029233374844562622360094010209808210376963305344214661852643173531624399870167724802903501431421588613616154883265888176427070422013434450831161439622548832700860674193438203417611324674030942479338031924524219374309671226267358134300585916117731276031003984604101670544481747595728106625008819290297876154320232923485228458168168318033498049538823659365208227139467263497921174519832762628691639114266559089965162150555192876117653982866366098958848995485065280069945352219362477861434675301845548499042466889527643265259436017987438760985887181155402248216252712333912314946498196987549055801740694461812381080486123756106018994323747034577585651590282982006039002140094278952707326836751764286509749448410869425025788615085055114966087465915015830794236350439311750336249399623723693716645941685772861954543525065807658055517345776490425065468782235577638883053762243103190845106064598128377159322737235176142022459602354968250625811943120465302029450481765702283294447135452301323750431553843006166413797261944719550397672372901526823992460577703747527102468158870967230536706553373140680334040597484490316305257404236831827760064763136538868727320299380669336005707587060793481204964673834204863341552784328934449847089059302600468156618581057797459052052272406710541111120357861086716848188554828230299697563221114087527770468398073362998921943810136246614206447416141706484415511366817420578151222485016519871845712775082892627613785895866168923719656103204222840156156698917807201707460728893004276465412389091888780202037172652477497403511415567454963778710514542296660856619523418952343657642552442120544924813709596750720590827576035936543823174025712661799621608223171428984346862330265076915051892248328773465037531653880313895305984736086864210482898367451527520021064107300294066843612736359370546216498944336322836552973676199182674814408539665842140905655207689865330799721818723430527821604917082838404695959417556749476152095117622013555634880431620568796772256626592470876991786185533978486922406375446685592390798073396051265248463089822413050629020269839897845159896512596999167282179986890153338692315590782642347960543110721120634589320848353366577127952445341215601815381919999105402950515650392153832853994653679111253698951878407191555401127146161806617582359683524577762958702727884909225142156676566234143632169319948646142215689023531235621022702496846285021545152919730493768193948492115554493231167872369110746165617056311655338993696903904996939789322315739086740358032428757618334602855753400475109636014615606290047509046000518177958102454020526629249881301779065342025492672541369043241484684617145179344217761499131354462712590799456576119171715340220980906868080531762242832097112261183325421825393305638247616318272484026980343648132899269567600916613580122364692578191379678173699235349094917764199815488511014636737627677562898319220394250465271988649438925320349305426057194041943966587174750995588922774760138300366409549705312792917958495231850600857212885393536779764249485254706582857185869852463879269104656159366329515196207855901880551130303340723997220721554236639756984506284602149525439131975987602269432839923725989127306419076393492474415268298398397282099477581778863202595406254101227463400974746289081202385994513038526313080071688891391159042535512778781954665836033781421456368111067855225692055187980473418387275589603152571790631457253718896775691281395107158558835334987814196475716269237827028427284219682665760678357920434895217174874259077261379464857983751986652163736255079680881886040394274154680990187023642195761640849705370561527375715079186421389301360060060966391005509182384602003073005191009357957159932435576629076038516894798512301401269836663703735169195771315228566445228734349556929132133999030341896518325096930306929409608083068655251134353387072322300343875663584372941648857132593979654634198583178644109320299427028339676655088364523759107902524120152002924742787251402281285947030476235584720183272801721451788574747281944124203352469939049133105134360115596379944529106053296717064910044312378292709345903573002986704808812566682945192447914455238675069248665586452040481004566843630595129638779485087986586016665320398769168302156814845110255127136982247993644200688650906866711405142362891893365006896908581022851742218627169481940264966684750214426754937056545391321347037246338716963115097192759470526088979047952485699768774168906596464967873008465512418406684800072460442894075583692213955236489202312043551404347144064810331652297017727685243953280463695984393396577503194222307467613422503523645989498506318318379930330551584797285693059145722521077552022404463461411631895860764248476460501466394931507653494799028942749964304609479818673425249407796832729563822525717311177189293555069748693239626670854925019181305680817601502958612861624319745915513770787244382563809957935762152895215949281522508350976991875128977688146537564030092177835315018678787797860795179321428138036429764987821741450718531993459983580191944354497610971604177222429238883051900286061171114324452113141491869678373833228601732624284133110643341631441503723792362822847660169991001647489414612448347589568485826742102840149910449908335447122037823349067073323897759671547914285335712935371412658181950197446035117655544511213373725716748940067761345377678843379133908607298108525785826185616141985553597232937280182425592944772881848257980769654732470161723511184026582485440542961486195608394915126546581546776793849240201589400175298751866492053823298983462516746432361788864454222868279169263560714887684332532031295130662932202038789034821557032039450100872698831445921869583951761743602412091347940594250361310480903106794384122209919203468867383658691136204811986115669086935987625011230833360508468216458343445964226775641552305362596714087801154826286210520661925351606313439578476357196341819231121253183446480137923294560719367137380083108566759893131659129048112914824385529352890616861150783534900896615097405749134684962799895914431883270043428833480803651850780617371265246451866063668341559716859359734355756170267751885844558726067586661848873172529762435373918419015400441627190942463576850427563829918590169702066572278798595990126822052464086649035096056930376638694012943028143365643469579024844106328108974940894100772106794559824032931983463928077750301463121750147423666180251154109628541349922218316799757371484765101242518086399208354042946457167195313425891393913037329275362060391454353509689958315866281263783121788843196345499059972294780844217190978942227248696672661158596626740105495895972988155539309309741645063587237023999819259751946770787071029922169326846874433035849503537098113852018512965499103220511088101159459192708650595240468282328252177982050630683363134307900484796424195941502416964450053183076969220080728582136306659171602927072696692422536048804292669828523161698801658498649498051937583978639114641777398407046788656210376461361727274829079316837525805113206484671013161505408367475872180553555081773589540581876144613334871156976180046423272844269759409033400059037843678530518466665911339900883028588453661267518447019762740424423206426268218760404172754578057233250919414129610770274131766802137225680256331675997816189252971982839371065780980205147717603495314697963631047479630845968980598534408424892479438163353338885345658749672050633213116497429750987786146029900123824696214778688428450982586574818380200343463568586785840205160160304566506129327432972516343194053193515412902387665635828096929645546901079275990430086711547732587037159973712003538352544311714721273038956825576631036024496512408378639237314427155440919766195333798634646830767730165795285984223156585282668970884864465169968196195849254688373430870498872565237797228522148065028399913002251579472860816530756987357206562297964823612367166381344979917717665061745384451917118407085585340352609176619896641058643410300775869112177949699892528690194640594672015524883855625610818256461696644281727933614695156032260698475918087643297560457940104088408966314630542307521990162546596684840600698607943313274422025752177883523987801732884349739982897579586707921373596348628959358982883495879998134643918652043678346997887325202967065224682948867113161283566794179498275668006939785148646461805299748467945744678112624066149434647520498820726076880086700687518488386926471022195842839555853303702669820530458457755254616404755207018794330499709161874304261385537017587839791605154156149648501367363280401060797389859199813731930058399806656061660331762102904409539934025617965008147986357210062246398783166063426022234213859408820635323683779330678752232811163582021443013539618120230908310756257699111454381251493146205800287374688565408446629431121405175637186302334375658970579081501862461530429511674738128636820492545035853260896076484032341369767365034574321743608225217798874285889974445388135563614553116114066125859472946547363414139709952313375651730774057584437503942321536872933346059312854582514350142070937013844965439847743283581482156536897958197709124104821663713535789683555421722035838274696435129255304231495716145025131334634561286070978741706520329288899488314072754853244648187334656158412194684923518771814344568522128233608880765218526396742951881467339805629104111855234929126579077623431371613384171439321332992009316835667975803843527449205006932918981731478823523365492250712507226076932892927714929580105250488472569939987740449806863573499110503208202785339417977423771250010630116199260241017875852266152524240893104685988954092681697009132034060623699011943565424523146720024556763888995337904620040043150630398049822742418586373298570751568252572790434011607763288196854707546375976915646560254785802493109143133815327189672040663395256148073091996309562005651106808701998372592620729244888877339207545087168621447780406955518073167549023918453483196022703486849103083590222967006332529575841707237723893951783192721658425493205638718438442146147253396297356366910677572108021140871635299348830318019457609497544778085166554253971803140506993985130131707547450274197184849497252952469946183688038409942951041385145241081201726718306070361036060519659613629336320328068682548213776921110418194774600288188483263265290649647618794436754988949476879833766739852224239581768159167521937320696775123291360867615622905026873329628457753332067097817800634652306844039825299843537265590421341510834724467541217826922184447472880713697880911356626439212634153759739233588726118335932454974345859074732015744749906322798067555799135278327725991887733309881559174044036073164827209918700595041399239952211606145855890478018912228835049249994047751057888538258264962065685920912127061923169010158117485564703984455053544399745299058898527918590830553043938397687440455326649289152633404620465147895530756712756317936906641288233846860370113406975950524015655974552323064505925424109705682535615992668092760932081979569644422067470102120402590292273860072236620756357205225343100521400954955035020233621200079500842087523580655204676221664301300601637054086282000212368514705328059609561345493947441274879344105860264631231081215828572073922888645529800482752576032294535782883943260112022144206952447761757848984374182664714055016827720240509649389972173009959354270199737515177947444742789422270292061338009205811912772083020359035783634146259949944954307646746645257717768866668245270827563181309961355057149509915277352596490384397255734018226536694738657433260608455725511297496900711558326914378760340895853092518470293148785305683162842658792322327374453541800378170399461868318441501670467950290631927682062853526068532502531389122662359090153370390769869298411928578123401188703991739646696917879877797124147711951185132861640333086320927924871774487597595741536588444339473998588759248363262323927392313593817647705227729752158118012340654154340307221229424272881010837917608840595352065635262404308226590553302307403380853605782718558291017090627849671127773850077592650959533512722177974162054723068745578794532719249341203111041138907737540919865346262725097908067129792457464186062551034712919216437609544453367610369777968855841498918510384370318413642785454007844053018457662450745155525678750693934902217940890657122828486293116446730161198485362021710409688095526259089912437330198777138220834886512453165070338073940618088559861266847536927133869305842234009933370694427704256935765130647648519158569274916761106640488423233445822089980311659929814911122494629794129085518574303084016915991120381733751764304903408526130627520861114450882975669456944699658256805946639734306762316005195425285221176856367596261912019709870876283191251712797183677359824957577132981547238346854136447807499939861396520865445470236350624429853256353413016778888658965955752891655873340860986017361074238875202266596955300762179751957490217580816502928867798687548904090151947308061743941478577630525269529322305804479275043834069736390232612699753282048196606973116994091709345406067449115063622227144896829936129914664404019062007606485126078727368992900714083382315692303463299197594062192959972832667969014832905869864579442412342041492197456253073540419298328954267446444263198800280758592239057790749757458014270566727641845826361328459318642681590056327229536228108286742554975273669370513746737802664395145085553669532334623272871868944150430377727608400222702254275410814938740034643524008075858247922288559095368348580687216852296524744767653558349326057942338343517037407389108773582975148204182098022294163696950152277523747102135530340304925441084874397160255542827148321475716479592064954120788567914875955247079947748338863543065338391070029048573168412102782148335681561094265437050251080766346529642344208381191234051483629379518018460886177676131231042500500702837717643953577593710476708201800679974516884742904502466017420522338429179434006652715078810577040341031791889562079831240466698424622673062154703442783571259789799772179480552613965076911820372282324433315080386735941136512870183688070982626121227438021666502330742711215871018775742122134802145903912923923586667023831802849996825159668537594764601416293854874713650803089181048152830367313444499747820450551852200602041248164014513459488382913369626851219647270981524011846292664121737629488862612471892429372756301201664491946348911059653831780487585063978241081500943967838762446274832848538843632818531286571073167638186569643495674658868410437994026197636912089689013362252985384931310356510794435336110285028277218491250153515034742187862893362261704588042534594018116386230396658500354004164545633669002681278902956817299507751331665872665164223410691179687882597557495510692079858443009509872813448480489046785338962760185127281286200595286325681897076292066762157694926273191265327549949600314420202081159332517647310826222793504988483618989831676526724909364813788794522287362316529918916587676133562338981144573424975521206050706657804617999715062321566215088815120974957184618934620215540487471462988631960851360479351979211979262506269739490876016909435495626326097096594087172138602755411338205992204781885515731638418293805959019141969092891800872954677258254751465750688657132306611566025475513570314328183271953444333790372825357616489515579213705121163184787306104280657091618253197297792813214666205470400668941836446670983373919354070625211436053670277137932964322410169627431660025347795400116414947747662776959637834930267833960421011945725753186187505323759451260564929673195926074022505834517056263747487651825838510913834373774142588739816546115576673253293536411856203147484940721532598369916027660298743496989929522404125002704299277496415476851248201429506377639682274174802329983615058637420223800970985292612321198022794455516115309312708419066238487152617257186094964995652038726025132918909280605082281925972334273891007485551464104167433015511795344847012190378540549247041717880100454930775533873810238179565688946854979891277798142183588911590017943188480264110812144287459841627799130546454762832177342157219925538529369798818317201809028985813969934425341024656410282279564747911044077770279629016871700623329418791701909200072229118567505565861477234503476619213061202257532714382723556975518452209456967332265390833634169101706634913705597143225508475352743921123355552754093624643171128721685605218338490930498682561441177154546417418729819879201947587283845501559010196869128232494899961072813903494079122691115044041942657301676369141906569501595081853294703272323451942966782744393260033559212623519909565629640579343233616880085819770691000723754125719693408545402248864475226580994180172138576641224350619714914509018249279689225658683337376437465583384874567604746547897301926783266147881052006112210144126490557064436788610016026461546785297397297797806962829796680827194305436748781360288442572947772759744512385233362848604367616901787823282417567562308956440951832419769547192180812334519383533392328429789368761955041329392210864345723174510486665348955222974221310396852977971187536607703496511794756276468738704350837592941363933844017663951461096786592236255134922099653388289481985239164597697995521410471018679229243138491537651274956546850528527665395791618491988508420993281233918454483807240302704532712411060842194970971101647145694480417230228597645983445693766561911893502211068366733771855598251819722920665412485984329538510852230283066248540932132316156704768769669936234791188913220462665647039953259372694930370659155865649289956505672953199601487009512737831137113661689867812938650983840176291223822365618200621497876034034188255686763380855458345077141190810366631337810369611005095569397900544436899723060494300873340846012645799121228485111408030967426798650029145316454246053807855736722967308675655008499307204330732282947267982994316588572872415601816507063232046469209441658873853907297934364239852994655169069983134056746189877631399879318008405543604617555167082586658283113593655420002152623681748200508001438875403676994939779125681522981354048066461694542114988540474091248542506353222843067382177521769489231509309390734294125810714022410063127794255397327757927388288416453495624344865905968956231783011584973526018512712184304084391526457221207344292778216051078709203198528629874357293423993589882725354500832995090314916428983858936864645270346478835682931997599594040487433472398022528167993746627833315204646788025807755555015004529544758017826170853155159981457910782161963161980406042936456702524578361636119631637408397384047777150903897080995739477972597752704327083595503686006551067651451420866435601325652268208344750446468599340130860781972132020749497906775318930862383637854438562652390725317143429425753052585421028597944995802403740903199709261647603695865441891087608704571782360041878969229321744915720639698592747972579449418234201345829607608443054375886389821482378721946716793946753686007726062437739098863542782130191603360080064453334158206278700077656184625030603189057462870502736840662027158855126147480116054161137818964142060524983593091644383466496012861907868684932135453874809448100230666252344034450642727705397395252960189133173985670533990571701151426283331523518792221113902447876791622191630755334821714347458520426375458975891037208930862958825422117839525156541675297691719651585763794393902852271123391074536219987702037520026064797510661789528914141689781028608976138218723873255069514288227823886747366536255230634994379719899773876090151707728340058940479767323072902266486619492409024700438650492422142711787589727826870882141190958991786974961173618213564398966724649905257805435941371195721549698253706864269450603549260617058856139432510443797752314170513383638527317464787017233660138828286109793804079970109451192394916394075786919716164521473985176038734906393424758898251140098805917869922807611478462055967382227676370041622998629567336379042367936669734646456884992907104452656058343006914518831160203970986142267286331674501053526879527394978556467998109917895700382964369064799500277765339069990613295120902029452333166092209086465273596593529606515784003468667498508701089442594802458163205595292863100353013529082044342505454814751273125725402997050043417986879975414956260740832359621667344030748766317212190280721546086456861949238211420291898003151477700855316712934468422364919319838957996141547112193007469426407960660102549104663841383947790899230733511501775562649132825404771216432341619884164910809382155939104233016576979318567430154776604470031439171080043893553193848598226496647606356703951514058196886108982823225526259436986489420560706836210873446684027290047826189990028995507199873298257728434828563254938649763913420711228969806485533827175660074601531770337765006748414333003476916559640047140642738065426420392121590960720605641850262716723327256238936492179633873826349493756145158549255045457310947588957230036697573328234069389045653740135029048430763993029970416725413063943499250603332346252216954900920524530320761141809425987163151748235837367360895610338425938962311130654136668244402645789643026888157340938787251918047271296090191714407155951599897370049183486841640377117904343666419921886304405639706946562796547115451598200673979747629031119656937330167318502792972124017264234651663239356554949674085028708497953889341882849344156521134098721646613042932423326969080131458485041212592855419428526847461279508860216206616498144411066903776235962278326354913670620774677900150896250507936005036413283039113816621178641800278146875507267880260040221753033139797847046076987377203462995167582147263541127203315014707511945274035579463785963112449562581695349730557472420858875354449161886049653427419161289037366827334151152968126135150875619275404395984776684618821607055647747825873677781236110703124351975403084253549420476043291255241393881143973567776723636938952877963538584568186653328021237371683891386033759809499866465955843621207879302434563683726195527724688188096306914846476480004913644993914548992167589597930765701638742830069966483621711623439052425416937598492330600703498803595859774050142096354484889310214630495709316931414822119103700977252146459571919088430009063391127984674209027402136015272010544810538139422751074969255568555354863620846981774442800586127911458532635224030931544747896337314533562025070619649440180269948496570921683655951514974711570294077431907177457468891157369499178977584437814411255179874207206296455962451147009378461175907536529207059887005946355308253147084143444623020750020254659134671274857376345329548113755968859199745428637605865626915204827633744569212270020622833292474780376397780888350007206998637025684175289717761131691181512520302204633055210640740636811606147704166800093338012382835634887086088401079670860166830735772418363553491381932830798349670671274142953126749990284728519873388869821384846818217955689199224573386308257795786468929932917416671352929174811923866145251362075429095245320252914635876441452301436885038446142928044331564233286177923673164796738414804315968015741438522971069689763951479197792932440406870279422958465288585240949607900733536684261863060288314304471022398748074609766996318190129932216952056014660485363393928461551250821223770464080052387878763931409512838790460634904122337559878947216548101897275524748595582190935789307651103822854333199170992157304073295689418488689899822417715208328358005620753152429392179254357464558942860645304810049735997097479199579097686287655050916221974360480288791874822595015528008504809916770657590066640075348563969203469719658541174610349655957605724279862389931036487181765499034937075328463054746769518833387599948060334045949164259523746860297111774439005888096117896206399072111057509320169728424185196483707301675858610984278966222528591864705173679599712048961998908064040017612390493856318290461665738589763931570327469522866884541137375898855535244823287756809171542506905798330304704939124154740557934358410150043310311472276688607437335405000515808129227051267663929512393058275771378482827350553121556618087065597027182198054230137149540449217458745361989386647301396269842171700253777545441911845686283026558465549500422189575526356833180876802270546011921762408653103681179827465263863775756421632900476735815515471218182629096779687381741514885560589817260017609966882365708735031867742525080345941225878128334153245441953514410092779225828218462717068789757073794966215595226717276342047847848614080988554677153646556987038132919008834020717238734670908252386700284093483625052367324118365492075242054275600494187209120255982160638460074161146361824314924130625315446203429788509064960839655974667506601443972726021232796765030803686030939615298070770231013402009165896857545779293103260028328637791867865911042123529847050385621942080635357531473888635452978597802190363831572555189319498309351540546585209108036320424198361293641596431510982527420284356351623209237393448811995257792552484203420839018864502443812450582376700277795606846537318027111303453877365179875586215515260098680766330380255699426830257623097742401939384393669414598820525042743696699143953636541348461542513043574962698951608473241962736282425018764201905335699937939373006539937703296055324440547763418387944370691699400669126196795971677342101301443971822497245666943482172611024888940996015050500104716730478070714635610605688183245798975745756887628461260843186736820744689133071153895958349032961570520338120146065393514750722942262195940987911604156359891431066951302201743120049844565424805708535560597844837018282683301852611460454381242798913407464274132256208498201388994421878178387077066447970785547537506111880609445545265955829398206884198704214323286665014297034193704770908395321146077348236995657444487304475840774010665786541198670183710650115037282039515718300948179542849091896848721363047617811259765285854362199973200864694893193528764095892444968798697143361413549816110354783572196656305216746986394953986139824166875621406592906333326970558968470519734149063184705645176051602809029536603793719256287325397981213532490240243791174865698967583353787674527673325862029202070537997343690637719297667368048613893172064475237345854385410893747051096120563074932456185973048975644168590252281113659168444469035645462010882386846615861579424689713779270501038266689979981390049297133746776700736091812233579149666614996681100236246073157290588776070623247248535363659845914473244967569891124953867978666926730047557624749910190508752784458836189954575387661476055171012203409910362522384844387375041553333689405133646439182324679957875583904604743309079892824762177535470486903110970659735502684508493708654026234822434186813828800616097106084328296751433476612609817259781939909144078390901565044714543154786824723368303456296674128749701881042458436875734632089821040643227824095044984884094863978018444057018515401798648160301738517170153082750976525481442909701895265961308925879460739954449464102357477397944486274688111799608010055207560641884928187849639604521617702850878877494919297217913236661589013951166847439070257490488056825093800114775321267494417002392667742888533501532417588752548320690888620854587901450786398821483370409260580783363470258890990926998507125496854354251834633345404972994282705529438549531997097757103443673513442759445238672365848103283764213192878691234917630663323290339336236885234728407091721089068203864642591389631600367624682166280996017539934563913436042029033917706027067970502042335204346076710774954445375601942753146595776118099130077985106591426279596397884624884927829682921951029462139444988051841790733394710041237348019184934123072739325164649622907834587275609104896335665516975335379767121518531683113898184092022114955271997092319711331620161307153545136185772336201110359971226482388154764878039735567782711661903666823954414437352610193547314801780589315027442890591826418540669461889911589841167617816560544615510932328429369225517671165620843670693450887837571127513263602515331062043471536745447922405945055712952010353926276659908314719256200743578311212247141746451431346457067369631625879332517821052538818275527612460937922524595265619740141322874656259275971973171079172437938277149092097066853530958860387305062722697859518708438428039220411444478661069346477947093895947794658017923970574149927986976315725949527834551371838872107481972446615469476377734281825468662132551488194927026036987313054353140803939272560790660782360989894948000763173523997390266809001835124248999546841922569096151987294276482362018290266498587654097537209435989564053416192286498382509745861782980764747466459484695422542694767084934149119572162196370483325155242256129127453893348163519136043679338531707413760365713667857294319297523616236621154697985017149979116977125358708057386664544131092352405265539595244451740831156839138453566682028944966675024259901063307448464771067687064153150041208478145925888220355668439494243287674599079266083304254184857432294966179592142990979441307439465115551631392218741117990347082680173934717822402489335514895545034459791821973225633541335204196872951708499676853439709619865746633366207588825613698515762093337645883442097636892779234309411559271277128108515997825982020939430871499056566124511836239253938133842656013019612266282225907888677391539779387776009132486112238912676476811415918283177222083252622521371125089375437882099750436384843908584437669811860057335860294412318338853705557213514876429500298436292432307859584500297031155660947538947143682516191075388507792451113595584985327108860898148731134986680493321264251437239998469763604356896154723549811979772066861988851546075435361619047752029428558214103037299483161113009986748548638487811110667280462356336371191745534818207314043991820259786112433689525157575650111326833833981297335369961924901289561427706988575034424916465985894018768355682308855409047889102047654675625609912628255708642144250290115415490524266992771607160091082594248705986763484822859187035554464725921830040400681240956590003412928528975000302648599252676126768195832838224326718082170125638278784553448439451684325463940177242012641775692773677970994661413813390572893332054855611911151050434685839251127425159425001368191354634505993416468879354641946585760404215756946662446664168798864289418673898983891161556861018252193720788788257439067728460161973841043679117366258674964933384231557009881925504419450228826904567142605915295011829120920434560436237046637396987377972755945507934351313429520181727490172290981248689578321456066579388232485845564427402854794592529505640885171192987129463158048076271613358820818532566655862609844048138209706442144145031451232138429791551577535097663612471622873690994342156504513212197475857325592175999116632995218336603004151907615299170683168688753904670718705945001521270776850698923355792681976257458477802595830748409038256623730782655602142669882781195587390941511381189080488636584261263220755571293724509692906988964595050335061903121644001211575407166274321714624515049548603850215087260032650025715443218753060552863840824745740929961998346562158725489278596531457232645837573736972234138039910532420995033440745241577859461010650908565018981489726234165169084750392808883265780462596437684098656085526566750121519666603752764319952464444827455076338549643996789868381422962638541236605891332845181054261738063193362646935572158071302468424016014595725553952319437799309798701387814676360312686462505972561138887661630430877226966335094116491598779499779499369924875751803009706877335662754381824490443912910304512155482123402151692998335651103943028207175345036391212854581048641972311678219638220934892550733010500582243178846121076212812194937484280605479063514788131155062610298925265911485182107688950796334347814013967878039605677957017757517280921152390452520098834630466588173171737941785752958776454375144402671489009665513860574751779329668902520804573493846775142771095646129769281626404124868312002038650855874505442463874192646246231072538731076836801240856910371276580090016365090963613798725501666874914422676186971668206585404802914609133648388636718441475770687146330115410617714214796285553998487612529851749227188115374929234670706437593077964006317719321674212127589118088944550714741300468053186440515613857893846462116168372154574996780274773979392333228851335711047304118947510937036375965194769860080178322298143118509571138544299987284081096565682457387383530524067196871278071399268780253213860133810545969103796374229396134615144338665916455979858394040666326485163755695344369519463282601599349206155952600386935040460780957612843656851911246525799042005114607302380040384461461729835212145979537811212379581764384254319211148124198499341567076267575874385066788035324511480504222615344595277471685425891574336988644255041479426851314105062751505992029845216463855674856989559757689839699461239009619106850563014098672844780744882021808479633396099768578711089281768865803990708731102502870123446685954524354914845385749761086300119389475999636551398579482437224005176252780387188239373477016552086966535436365282031301250713614039431070070335913099249300974681772237381137315568375771411196184874504277160686245487931133392739379768635137619661286355268720951923564340560762063364580849463985300231023496139969851276947924496793101259564705737268220470683619063230361363493290562130412222026580942511695611912194946048545819982892924609272977051018419804758173947440488128589636976519756449491043264053293955193007249963607926692898924883339317651903551826560600781107417434911139217575002598039521049320065538460211779453789589206599999779189046850987181604245367259014401777522675933497415901717009863536913369319817002031452832530347908871865839745771886964880450483199213493947064903866515269805709615691703138103036720216416357874026985088503329497752305459171579111570222893883061812762453688603273447669620195622072077857638161315538016101682551993949835274225770940990863204977981899017343384011913007152526363999176337154553874091292701852254265151067802181023639982508911657226881808640856559217846263882552622676797172108636150743071776746125199586595283257100461362414760929267447333346497043303630746139923236318010733847514155517178669444153851936048233429441822613739517249216305664073184038758841323451415729306240169560930552987846158578705361866050852395464970176049789989751516468019253208375444431914129517975566752961090489673771432308147785964426211876847471050910730359860838301020919711525394657468503902590902634200617165745011816691569605281216145891757708362003058342141686778178561504110189412966732261568490695183582965935298486959740204758441736835958695889266970076440596079315942276029259705240856282575628171933051910906751498353692989886587197715324945198380945703649032357672529158563315175736672303856725054904600315945374855127405348407146316305678148961718900411301541157801116328201688340332644771036079986452288147704868514009412671089867224806563131562638515314905345822424917586138712005114237117211745546591862435504667678547573648517727324694667465559038740925760513023170380123946758786446049699568871634051254873715878875635531962731798178056780197441195525903230611916856558827876948154161702675644052217578624656823673848329950177039177738935414141465840056861464272245586700860529470973180511854478605647662849650482366488351772134977960117525702477088452233187761652076047284306592925404871017015290506434258603702148116466953435134206396639444055833890280960470472460891347449300232019906522200752833678266489199600178875071384877587450560764224188019229355481216525888866239554697425832047365067692494089524539472416540579900768960188499417084973362777968755995199232879081207991942848416559809259430538279627647299586091557120063152796995359102135959915913168417187477542873977655040898784793392219951287900086257282026133763787018391057158956758242154084396628704200966511741997333711249839274053261186258370491719467156176175816763634334665007773713414760010656873358097852952554623541381519988361849416679482034129066320767302010558450600303517950018551597995787749404611898102345227990569474025950943222386246119896096946514818199391476642461225101054582237769542907031598375880592621338184267523098358222275985229990822626318230178519658083349073940424864481661092295854294938915938688922497754005839343937713586103497692196015423924522452108534079684782193537388060952924861263950591426293206241013107779073955128290615084388397346827930289360351091304198931378098614459096424514932206382431166410375513114387102598624361409892310374190116326424147677118247178004471390597687155243850207275237990035800438749594456812469692043690796366874391827658459855551478710586185558728462860288610559539712362831490255789966279558976099091118002075554347962458209024150955732096179273378486635665829004705672486870527618357269115976388385891952486106057815014687527284836432702270549094033372300814245873638409692280845419609873640999131965014340485935657677271361584211072786029678240315401591646911858365938439512765607225657802896672082095126987876564057176954818011316236483849698751977459729682715777429467956763919996895069412395630234690042977983114025078970940288742040829492383155318795847181247614005594946849060576406769638513779424328357933328017518051286474649512070401301104631932070636085418886684157363566874463745905688879237394211300558385185738566525179233364384152330413853928970616778360237376738901217096850010370674208283010499713558788617147534525957810593498411911665736756126351208777559484925324000702281371766208620383100649500730034078371450966821625570195005542818774779598973909970440059134150883952260603117899012228249338705331104673339324217078370148571189179716222033404266126706596390722480521376684749438427700156472706654790509082879016834510416569007717400259654956896544522914726611413420084199233427471465533585839011806940021886531969664862869881095834183810325051440149533791230734011955732796609041314403271174596055499834944167388926154463466682382908496401647520295925785086341772340067766314251208481189892698377365250807340956042616976209105901280722837711118718267919097038616211428279916113562719925306582032575404858278605190561068510586343072768434860927756721546402992497568909581930063900226343693580854687525725401515021506583634830833540815995260447315346084744877826584503790589618898278773003290568139662652564785254120873750313830892995550840963671316945770824904284891742289358841480731787437728737047738547499879504229339974239636617956340572029520616135871601993159646346954088923992187718931200994085746353174523136508113419980605429314438329939266124855997499096595116402186768788650874374959678559084455760786336356824916835085464173964620483933222871783599197025539189700325568407241611232374080020719263066767251475702015944715509087081138005720131401766798542234036893976175151066237752187184718873722341643516253652847392892781977539910651538865263619833978824266610431537248335629795020757492311480838574428138299360456662914557991086482310767873875080559160830490323065221586898741579642591732314444127589974626158264916820566639185112530807784480515845745617656822956916580450354924230946684835375012599327650606618429938168136391130063143912781974616523787555873750
Was it so hard? =) |
| Please explain task | AterLux | 1677. Обезьяна за клавиатурой | 13 сен 2010 18:07 | 2 |
What is "Expected" time?
Google give no answer
Edited by author 13.09.2010 02:05 |
| pls, help dummy! | Макс | 1677. Обезьяна за клавиатурой | 9 авг 2010 12:56 | 4 |
don't have idea how to solve (( pls anybody write to debowir4eg@gmail.com how to solve this hard problem. Or it will break my brains. sloane dictonary for generating functions I solved this problem, but I don't know what are talking about. Can you send me the idea of your approach? Maybe I'll share my idea too))
Edited by author 02.04.2010 19:06 I use Markov chain to solve this problem, but apparently it will tle or wa, could you send me the idea of your approach? thanks~ |
| task is improper | allaksus | 1677. Обезьяна за клавиатурой | 14 мар 2009 12:18 | 9 |
I cannot understand how much probability.
If probability equal 1, answer in infinity.
Edited by author 09.03.2009 09:02 You don't have the right to call the problem improper only because you don't understand it!!!
Maybe read the statement more carefully and find out what is the expected time in mathematics. I think I understend task well and how decide it if we don't think about probability. If we have {2,"ba"} I find the solve is 4.6(6). But monkey can push "bbbbbb" with probability>0. You can answer me to allaksus@rambler.ru . Actually the probability of typing "bbbbbb..." (infinity times) is 0 although this can happen!
And the answer to {2,"ba"} is exactly 4. Sorry, I agree with you =4 (I found one error), but the probability this event is 0.6875 . Why it isn't 0.999 or 0.99999.
If I will be audietorium I will be intrest how many maximum time I must wait with probability 0.99 You mustn't find the maximum time but the EXPECTED time, which is equal to 1*P(1) + 2*P(2) + 3*P(3) + 4*P(4) + ...
P(i) is the probability of the situation, where the first appearance of the required word ends at position i.
I don't know how to explain it more clearly.
Edited by author 14.03.2009 01:42 The task doesn't say about condition (EXPECTED time, maximum time, ...) . |
| Infinity? | bve | 1677. Обезьяна за клавиатурой | 17 янв 2009 08:30 | 1 |
Test:
2
aa
Answer: 6
Why not just Inf? |
| round(2.5) = ? | =HPF= | 1677. Обезьяна за клавиатурой | 10 янв 2009 13:54 | 2 |
|
