Here's another problem... any ideas?

[Nineshadow]

sorry, i meant S(5)

Do prime even numbers work?

[Ciccioo]

Do prime numbers work?

...yes?

[Nineshadow]

...yes?

I meant even numbers.

 

Sorry, it's late.Mixing up English and Romanian right now.In Romanian an even number is "par". Dunno how I made that into prime.

[Nineshadow]

@Ciccioo

Actually, S(5) does equal 42.

S(5) = S(2 * 2 + 1) = 3^(2-1) * 14 = 3 * 14 = 42

[MrSuperb]

 

Ok guys, found a mathematical solution, I think :

 

S(1)=5

S(2)=8

S(3)=14

 

S(2k) = 3^(k-1) * S(2)  , k > 1

 S(2k+1) = 3^(k-1) * S(3) , k > 1

 

Not too sure though.It was kind of random...

Can you guys compare these results with yours?

 

 

yep, works as well.

actually not much different from what I was hinting to.

[Ciccioo]

@Ciccioo

Actually, S(5) does equal 42.

S(5) = S(2 * 2 + 1) = 3^(2-1) * 14 = 3 * 14 = 42

oh, awesome! toucheè

[Nineshadow]

oh, awesome! toucheè

S(5000) is still ridiculously huge...but hey, it works <3.

[Ciccioo]

S(5000) is still ridiculously huge...but hey, it works <3.

well no number is big if you have a method to compute it in constant time, you're good

 

i will hide the disappointment of not having thought of that solution by posting S(100000)

3081092347974906376385589411201884836653271734965494051774792345157558936974289575361300105899303791590136337854628826207539730824876809965790367171445937008739776449933103564618332752468749725581480793388789909544528973425209985691491333960060989093188636365911274615727023813295968245237532452558539252201465587533348168149233913569428448369561557750645599283079801876817752739063714616304777470782080455892832886413681537016465617464696869587591673539823342032518244907676545262016661589445814638491200815307573098612821328307723140085305109874656994690680752445496499565993895065481160418497682053317273994351129652151180304211265364250369389685608874094671760500380145063998488751965671385547895114772831112513965810815847105435538311105492014551004416226521043159804868017097500648883290580750263971079496849231544044979917025851443657592469101545438527080934260942963347350933183575190144899562030423909878439700446059295331176338237101299953626494705685508764034308776881648402989142431676344043447652972779854725680216710115102591066301134369425598864935621194416187477267808865449946637508778182154718598064280061159331038884975101185617357803008934215123938034202046498023311190596253465091580918894068375806096095837122482067154739805222732584474426024341820426562383067551825784608398237661587372697559217068219619948200408730829351981832798891416544096566464717971027276078653649101650239316656699656405692989159626372686193392308114522009034474330832446142425507610734086490668987805369794691326476804237937689175527122025573417915143395760828489298500998885356366130589282066795237083325812361837150256206413593810954663522926463962292364476935092596472788019009893587500186661862930796753895023793276770680426604615705332482738535885041657038593508636245791615721756919299774049893390799728969945965130420768923805021226967964188466809282050159516327262755015858092865747648312217419883720681533957898516821028164981197382599563067700057827811930602604480143632480850547739313189990123972786753613394917169803689748460166044895292045976623191760288391243067897246836208446327305059920091492525793548890651702339182639644240566080154910455297524017236499804130214195867238446812768918725535856195847890794694547316826880523051683926620575537562297215426357019432372118693581310054667409413587218352206805059708768569984274690265726990219578153362542976338662109659394257215068503890371490153068851579563539216082176007465199218588930436194259619074093107491126712316358840317192993819633879102761951810539643029508578209984459721412991877713737315461556303375026614407306391491746355147387411474084915467390634473022423254819697403037859777808594084162145449896620980876305576884555187633243436329723171702111794015962017334674475686441196884271579412772126531699162604307568481078286668165710260742903729164772638697440275682737438551193150454960013078465705784670620057896644653563751273800978807662623156602961248578002775134818938642048692127396968739130097028605376250705572403925022994386371478377310385858661271965603461704162132019697382579535127295347434952958206947019317554457383277107271482270252104950759230821578928231887106324284354481721093009779416872473915694830601728472937551028126809356627455123205508149428863734682336353149816716775981494169951854802723136317758893160922080316726208145227263769740522360806152339793727693605475708401288675856370510976780895628253280720844048985134492016777515281268920798250094507392658496355076875887782254111430505525308691737723210021174796284566599896792197047813321779162792651172276461893258882861245343099712951106452680863546430350655528550215831976258912709898072613364956998199738101498452808251784928803598677507848105267467634435044223750456184219797416005582998193583735934364602359620881460254150866591694816860884793546026847702062929110337882066912345163019781418907240918530125561301587369322140013509000264212672933009094470799115974412037445878732715467194224805586782594324355220968424541678216340911994556219087394861858891773106555816007370109345679502710837498153585221513723261118310003610731592324600474742567132211665623998205708174490970275478843848438852672754946185426686309104450062359688823150107089016841527687449949821636838105699809272557738054126631165892325095688856594930030816799003108345402016115395312997317124683621478973857700765115470040879417143067994920224711481539898083501758077683882591968290475636507822988725434336557980059428388265868388874471266293626982512137992031215739759041065531122321601576041658744423721923650651165896001645600597854572350652421603831867916876849833183193275627887290934667768822057218547364345966775070241204580504368422297311253387020886071524870045816381068974738212238448576373423769215596863682398023483029573915454755339210389324286954991232219332308782360106717204189488924446951127427652811246322803310877945343185495425031377796156602428162441204151652930003627540771631269939970589798144115705414381174565545296715438317218461053552383191264688554610534268389379420581464432458997057266693616038951398000145330038205819302823333254342860213325344738092703773154529706650282504067479525022725317997267177458239255808335692724111060212438134293188423091555845544854573750792542056006756839089747452999498268949473756955157516489846562812094780818344169018172475021610402067717530506967691714140331683786546276455603513279105601807852670653572688515122725437255641287551587614413805383537905437389095406392375515743869108123661414256891383352209654169700524127957756541920331134452000987476267101370801289691980091341349663295685405193029069104641650539499413408443617525245152901250151645142721485470689554919078670840320798204740394677079962970021515831818087362367012461802194564117476838598350670685467360368561851584142488515403692519696921119248835631129635219439718839556325948926719851877918338825881406509644931451449243389997993134447192871814826201153502435575268871047027947043185368080218138047635085910114564898982380842367527348955697559741229591028523044507655753175987344841407716804117782513596408565151983825365576248689832168925022185736550305520502306469039780749941760139438798932103449227283904925874090649110736132915344364755591561685438915979402112407002137798669930457599345763303878792511341330892493372664473832447311944872528481967722769001552291852955419346327531012099477779349780954562784723458735513438588854972695937451470137968143147681395067471024985648836361997810723475445498481927120744536463926801027224807681458133296602900112546297029400184148468715486965030494018816906184435018261216034606086681366459123941805285761759125191208833802178898583498591373093544184592925442741589750773516963094932551965616360675024651666480636165112337942319608058941987800140002047446395340224047291733910727008972761240952263517741882275107247894733937607100415137443202525506143955524687234126801229147280872996968553236309973558230712755502194460808408021557370085599038898620988908381320682570941137706628091735351923016660592305433982491624550596707585644424074734132188224104505644837882010944948507662494011241084353038509515653663047730833340946865143626967238741709735040209996517353137256811588184956865290673850027989619320289418455630318020101153053020944681271326654989007685192961760149279020617057386066993319397782309834523574577047238741927013302036016822985041271564301410695658680365098715404539324143280569040849655002803601551837239568671088040062311509149266300761173363389171479756906312922199965123048874785622321412476828587891586908015700252965700664966930684674431570513212413809343659395832222028040266463077112327324136349424045675447511266293331984469036393238885533965026559115648165111468632350553069366360290699579756817000592938779097074010147274889919879992959550218877783122365168921612183607582388446272485340025954538187542506879519285439749222270725423336601542089721059576633813259053968945887601987538245343934097798164045607013408163263946343342173249558962748343598915219012338058244780874599073108110567552796593424062445349617136753726002484529330462594917119749087047702641728391401655725210421934226219851212537488259170117377372217627741320109184610061812885668267033677843669328114832580627579403111146754510179689340205152155165958124059744230082243555159516075740053301652106751660840625689309804106513952258352754466474597860807478615864453444615545279898993212018925522634564522831526437038423686702883904516880728385683181819637626717670517541443877242486177616566094407205139337650262119385117000958074285448904575985542589050797988954501082982606540786658425591131844259137167225534027794682931701571888626803659076369158678286634507237946472529287123845248748080802222829067275184836093868293994704395803778901987500920171064814159222268167931991562179586939605959040268665848879779441407649945592333688047764790071185576825212962171169203281354818100175196673898366926792242163383832358519337205398359907935893163129757450943315888843987777489439306408330611085404950339575809182202698000335065417757679389485253771585491644442141770771933624250542211273636235539006882900894156500536017641814072065553785213358560591964438109011571784652191010813331795100918247779087608384577577843817278122792451258486110290447967046503698993655663694303627300534361679707668642646615625594655675524402622685551105369680557560824129851704898431610334417556087687337522283245568985171919808949253733929469559842056657661269266327028285846270365378264867455375840862910090454044403530404684305730665542642750436837827856248041903535583133167598501260472316184894462094604418560770388057162050308803591586075066013087847298744839687019241595269372060290629686577757613975998253129299104400127078008397697704327259686933894324771153239252479705815010113457033779857997631234594781665086244617658882987080393005870120920659106103530612748579597626082202730108487942749390507350664278245324098859338236775151802762567359126971949736345177837233038455068775436975196960533072376420276957954721370338022700876197609458346556954808654460884507529607787630903257520814045794506264218301306890928711630407507759194018950676794911057161866922779315957206381628672344511495102846977221123246751567138662107644721551319710286188632508827885453304204661651998671216769037099201107680939808704017884221796896016112593939354005507574140298940404536914374165773838442200165341871858188283583924742151415760746539215279739681357868351585350788761312231905917519717926557761802830025286680429856892700134208895212478354608284587135376318909394754051724368504879891165364163034958847491684933262614918740240425106036013576502584525582270666650988426649314281227427206329604802981578972825677142728883528819242139600906345432500934036143543768529133290469190445492455398180216558594744345070760517656708097170845133869580918488949534270587005900086629283575939687352075544367323528662148088064144021172516942302565346466445679244466923966664479981799978864415788285180610928155296144963658638772552100694012489053465087458326054227397933480734919137056261315058115300738512462210318788868979555833222355264771898029249074178935706562312366020042144481876217489056065146156418766983540646123613308445889598073668553132722819201734885724060136991906750672110739932465543154306307939617926970487969170888569667664019835137792083316089127355205284033552996942368982691170290573852127924431813134447653184192134979712865405148976096380404421693246847393855135294058506453462095920842206314766870390577076227959292339280224218559419411203748108024751785257037897279847362514641378008484337242816382381606583815673306143806728925044313118276954279367933370484751748097522180164120667994618521379135722349398213164607769865210080259887402102414633562010300045996549920386569264317451046456386183527393519243299194202353447811943095183957380289550060809406738262902566892485088637970347435762405341908926840576940510964662571773703942143224704019773115280334397114406465953326436416903690967837212890878354191403184296078063912736025724415622702124948158732350376706816485369899401575297425609418711377443097220841331610090660540426669685430954324867716188596607221909031449978424962940330858904630689245993221777230130260303666737754786356292626595109159964108497733174119183997699514025845440346973848958325271783272968747045026193169188234522408972947008567395093971393047433901033862355110510184349913047745757839392568331116767095222059516779271978573350403185418104349007228458970783603025386573744024228610445496634167110315735149089441979501597614182904808159727453670342966233697654134944661604753776274300643054294081812261992105767541802023989704330208410356700845060171355910683124619460720777234954172057816040403853369848464709809900117938033887045494416238286193014764156845381680672302475932444600878275610775082758306467850729619392358270480527237674145664812270416658593060608273414762441667248395974133086978585759520818027260230612152112570723221113759519306345633641364989267156428826915601158437425689433910371595119956125211472690514193580224525643545337369526065079108809383225516179565594895952666829168781937864477146347228793437841231855247526369960455567884309432059263172872957502787564149210249182987877099882131384066834325130759105377250669294088829565157177091987386246551639283902771778429392382571225398460408368019335268280871828152375452943826306612054466145950202611234686367441125959869625185952283929128933413013489455128113307806022193832923795361416516602977866216825960007080325471315500072441037824109219176631586057621091974194000458344270677312278961480936002199364284359969189690435629711932720098877947654708243279771334109411255319717994062103737944440547190274532663002462924895687071360749584970453499431387983643119936852021582475666546611415139092857844966961801331897271499963231274842493079003258988800714730530193609500263603366519655174921611862648678127352311724929583472963169997981660270879645586146572874531835861425145890099083914655840279588604348866800990859379881075677828222096688084360735131164680067112815259355551324972552431801080344896092588950256769497727310648152630818647960759933296967452146787968915506942500350121354017396749151935602285721186297817308408920294827105821963565016581645087057657033004363047819339090923813407708030586577175779993832818340650703003836011803621005722106937463290335370507882857664994871314898563721974801119927774691560340107964203981647626838923260267156640321807214051292178452468511894493322589148523863371805416431923878627610428916979327090845172042703945218446234177340769558766074807349175385281712929610331017734828547669635953622177338433472290042223640618043131316275761609436862795629216300500313956474324484558070807417638636211110354620625934412164535330839264116561260308637628895565657214654511634315096956584838102707062467450966302846910824807498500023639920032396011411070233251604270312386983326002387271675985813050241266267044971474540979428125404287802157495864704813135556267291162080763301156110881581121006473154368628007359622243533139379810415872571425403964890225234358710166514569329856060430559678170036764754742088573919338701779201722652319201497517362567180847767827618258163721419670982744333472713392462714165764115695541106369820898072711399709137422760816930467793287627576631509162333027050012189963952261038852640972026979566189843067039505860785239017155508917060009530862348046324695010255519278154054737458668002834769774331100442677292333001502735149347898255010284305167771818012093054106065378798314318874364930454891605483321466700144692178087011813385992854005532892601103056919212853842160991421526767905290589324606530375852092291404125061390308579823791805637628396189465431263090692290759512863368253652495545546928427862379684253437177823337853342484114468660706181173857036369392186315509509218176439031049747616555563534020872343498209348545290234955646054521469750431586173664886372410281408395462138818823685180523535982839072986277200389004891901698179492685661008637885418279946443465109361976513241568570786933124287211269936608851381916202729917745181959686456146489641057183752088302369692923712629038459671479947373192750866086914278035258195978364334130729486085237847282152579753451101813553503782883655106423977383629577804434707919580601712202180701075619102814846874770032394684295757322642419018549163793454324232869281313940726348684156382587125033499926016856280037581530369414344683620535871934081629647884822221727210163683082603620280951736060700419088045610832182264132885112072654381537310379942225190455811188293472868560281200092059410113800309152862662342688033694471233923289567858315527612213342352158042011005479682649259670399633982151057694757567534693854444544294029027429700037856666625405327991464582145846018210081004981520422386284917279830081751062657330879564721104361019784506077867035941986125402516108708491202372943014877395248890756203836575220742134352453975197752341560120707093007649613432564703566424940509910948570517490478346601131716292099578257851217641980022845607859592806635645466138030862025828768705844002676440552999599802624838510419623443869022417709238334636651401153109748570391865185779201797308378261193214504388455657243053268459244147496992176053819259243272329465062249089131984154117204353819036850847148135778158953558588751421596631127466037989765197144931729540144144259278063708469803129173956657183933801328945717356002305814194500669595356240404233707948851858102092415142756075934606692489627328687066583124349532834313933630425003405209964845155772875188472888578184816510021491069759824896585091001242769682567348170471243636223838620752303981730070089720879273175623223373765742772737828021820399120604979038181132512330396756416378144444605686819385711720329067902940416575397779824853983410929491875153211825069645895834689489257321210083868736770377074438536986784564635398010187469905859155665879928940585212967087811721513533432524328593023475297551099130301671704367906516979017330666513437463110667407072891675537250423671723500487305532093894302808045689532694909706238494879673167602479753325163618734875039517833527408980422323731762486160528078516013696923984203906571804856430260762776721394516417544393070706751774765226501066122124296529671882096729903225996009509795141865270783421630006740775632351976219430033682815165736791590283151755219462628380221174774683333307518140167396050232701292523990656004317831763977835600431223873572573041566621709072041834684631436864820771841738698937817768771193578956346826130298969631663596467015304494174636653016184213259281780470949770029240378543671226541165797434852078523220411507374082787886109738229507080772733905227998567910926789661586100266880883226043735537007438116528449407257784346192851616733039882743508578671734393253055660669652042291325305323210758613738742875764154622721421352730541426066965000272742360196791128840002445965786174854391626895391222450777049159445442994849750988241750932954769162708602006015318440585342436693430526416029068667798952715447692859347373250777911286236989703441322770939759613647064151772056711995155603308537940408955075138485579546416064209926821564082242458373717042512937475074727512489166253040178939746052839454382092804034505935967906955158898910149517540980670679950336242916187853591489510661384892237750616940726305375350335875324759695877131538063304220397852243427267452838054700326904962416245223590035427045629285934538486437092156950163026563096797498537073594762318737492966228562522727688770906894862718612702690025227028100160268397362890383893742267811954239869282915260991891740172504982695605417853809106363676725474402220704977074964699532515156879505696218094315313850227951367340959820844710866861156696582388147307830538143600552228414446519738136108281296478929750448207255802921899978775640138467926655170477836667221166159799843003772412549108117283313524478979397113436878642788223986859643473992778203770606933468809503802042127878583896976995267795963414859782158721981415354835124627808908477929016733103714416670338398832865919638164187896385939176409189231162316965284654621905271866355853398137201558642602695926030823404459828436468714722734641855643109098639206988874056814897805515386936790441642710149364708286350218120188717604061934627333018545211786495851750342684441009250340194762663427317588581875228181757813476513644912009506760276687720460358076724640258836944115972543215867877409259974023405673336934632606535507044313899611499892928984383248196481149693033886962345218855456838254136878032001295407147248399341167861062770632897238915846159766835450234497960066957429349989281655626418559149482483782241986168708018733381378933749509296726516775758365654091275216651496832372504204136279987976868261572037701812641503569015838129254981532697262698025653739219828703394472567602507875805842359945500891476650798003421394634533669294865185402183476065829035352280703064862642263374785760453334786404889315799314494997128991484463606463972798390156222464074107456639203261960209327529476347987209978564769725635039758174840966154039453131175155676918032390817476211582692661601555386914549111952590981545008315707167027510766039423596713574490578165897734036625296111679961156190139382867652308440413200862301519419592342734701353161909845669545320639451439944911762667349730650691359070292381030003622243976148808531019301390003320471651274738208582674556658822112960985447021578371795282304247860623558633519078644326031882590190050285618798336012925332251097532755822216091774042483131943554153384480360770541154607539923590477701702509654132319710905625887957656188828244151707104778821348259497230684801654503722899025639382787838168845396514211041732392073346092951653590271932038949212624095230814938011330635841111859759738214573490031031006698693353666108849348787637673902618718003555102006428937209937482301011203415471959953569876247841528537004995878718786876524396351459430568912625179415340525562692709536904663923069610735064478404865311261753904910053771098485913925649893117663259437877003190378371358577616542663951252131288330843376586015443981453075312132555952502660208166556417417280072044029268724230751520242187098963574766371265076579023591711463037719760449442113780207726945549467593773856473325289937121037209197262583122093407628141444944420385444393555574211333153788469552712037341180423171713246865221572187496316712095160634172274867212796784169747622349988236191737153241433194200067300438083945358672075616563887346165496255285653980067045431531253892914731557771592046056494766933001342326865464299884892596448799820617492681965183259338263001269015614874895744668977260972940787496810756740899490603122228653656524448184405523720257912946872535689350698879282953401370807596586127090876318212499144233597798274474184970826570002288733630879738298945242871833148658632907236563726750918589128380715429957940629690918552951998668288117878697101573629399867897231337130073971903399227466660035869991777857258092793229392840337387585660629590675700124302240994411665342792185038361413578590846582458565203053251632315738612693705990497438847969006299196733459276835804663618284705433020983977252863506496243604460830589332968852079418175583247653823490135632774924688947671399605981320076169839302187526065437907368914221518938302621324292062550123651479336113398058088776415075327828508491095003248191406589706690097889330252569045912639939676522097572008008701447686670634658747931177476981614759218007432446893424239675416945740541210722940530275256148342182365833411984990551213887484294576813974178540969178713751808328323406348909495539427117797629326874465518117750983299409173910797021710008247344369816881666301246927481085956312072975725507539991211603592947403728448227722326815077066035615624694983018890065154029333336

posting big numbers makes me feel pro, bear with me

 

edit: either the last digits remain unchanged, or the number is wrong. i think it's right though

[MrSuperb]

well no number is big if you have a method to compute it in constant time, you're good 

edit: either the last digits remain unchanged, or the number is wrong. i think it's right though

you mind posting your solution?

[Ciccioo]

you mind posting your solution?

sure, here it is

the idea is that, for the i_th board, i keep track of how many combinations lead to having a blue board there, or a white one... and so on

knowing those combinations, i can compute the combinations of the i+1_th board

 

 

var next = {	w: ['b'],	b: ['w', 'r'],	r: ['b', 'g'],	g: ['r', 'y'],	y: ['g']};function makeStatus(n){	var status = {};	for(var color in next)	{		status[color] = new BigNumber(n);	}	return status;}function combinations(N){	if(N == 0) return new BigNumber(1);	var status = makeStatus(1);	for(var i = 1; i < N; i++)	{		var newStatus = makeStatus(0);		for(var color in next)		{			var nextColors = next[color];			var weight = status[color];			for(var j = 0; j < nextColors.length; j++)			{				var nextColor = nextColors[j];				newStatus[nextColor].add(weight);			}		}		status = newStatus;	}	var total = new BigNumber(0);	for(var color in next)	{		total.add(status[color]);	}	return total;}

function BigNumber(n){	var V = [];	var digits = 15;	var limit = Math.pow(10, digits);	this.add = function(n)	{		if(!(n instanceof Object)) n = new BigNumber(n);		var l = n.getSize();		var remainder = 0;		for(var i = 0; i < l || remainder != 0; i++)		{			this.stretch(i);			n.stretch(i);			var a = this.getAt(i);			var b = n.getAt(i);			var total = a + b + remainder;			remainder = Math.floor(total / limit);			V[i] = total % limit;		}	}	function leadingZeroes(len, n)	{		var result = '' + n;		while(result.length < len)		{			result = '0' + result;		}		return result;	}	this.toString = function()	{		var last = V.length - 1;		var result = "";		for(var i = last; i >= 0; i--)		{			result += leadingZeroes(digits, V[i]);		}		return result;	}	this.getAt = function(i)	{		return V[i];	}	this.stretch = function(n)	{		while(n >= V.length)			V.push(0);	}	this.getSize = function()	{		return V.length;	}	function init()	{		while(n > 0)		{			V.push(n % limit);			n = Math.floor(n / limit);		}	}	init();}window.onload = function(){	var n = combinations(100000);	document.body.innerHTML = n.toString();}

[Nineshadow]

well no number is big if you have a method to compute it in constant time, you're good

posting big numbers makes me feel pro, bear with me

 

edit: either the last digits remain unchanged, or the number is wrong. i think it's right though

I once tried to post the biggest test for a problem like this on LTT...big mistake. BSOD.Really, the txt file was 922MB big.

What the heck man. Some people are really crazy.

 

A 1GB notepad file.

Ahahaha.

[Ciccioo]

A 1GB notepad file.

that's a lot of notes

[Midnight]

Computer Science contest.

 

I'm almost positive you use a prime modulus to make the answer smaller because a lot of languages can't handle large numbers.

[Midnight]

C++ solution, with answer modded by 1bil+7.

 

#include <iostream>#include <cstring>#include <algorithm>#define LL long long#define MOD 1000000007#define LIM 2500using namespace std;LL arr[LIM+1];int init[2];void pre_compute(){	init[0] = 8;	init[1] = 14;	arr[0] = 1;	for(int i=1; i<=LIM; i++){		arr[i] = (3*arr[i-1]) % MOD;	}}int main(){	int n;	cin >> n;	pre_compute();	if(n==1){		cout << 5 << endl;	}	else{		cout << (arr[(n >> 1)-1]*init[n & 1]) % MOD << endl;	}	return 0;}