France-IOI
Contexte
Dans beaucoup d'applications internet, on veut qu'un programme situé sur un serveur distant s'exécute sur les données que lui envoie un utilisateur depuis son navigateur web, et, une fois l'exécution terminée, qu'il renvoie le résultat au navigateur. Entre le navigateur web du client et le serveur web sur lequel l'application est basée, la communication est relativement restreinte : comme elle se base sur divers protocoles, elle ne doit en particulier pas utiliser les caractères spéciaux réservés par ces protocoles. Ainsi, on ne peut par exemple pas envoyer directement des entiers en représentation binaire : à la place, on envoie généralement leur représentation sous forme de chaîne de caractères.
D'autre part, dans les domaines dans lesquels on doit manipuler de manière exacte de très grands entiers (par exemple en cryptographie), il n'est pas non-plus possible d'utiliser la représentation de base des entiers, qui est limitée aux entiers jusqu'à 2^32-1 ou 2^64-1 en général. Typiquement, la multiplication de deux très grands entiers doit être décomposée en opérations sur des entiers plus petits.
Énoncé
Dans cet exercice, on va manipuler des entiers trop grands pour qu'on utilise le type entier de base. Plus précisemment, on va calculer l'image par un polynôme P d'un grand entier n. Les coefficients du polynôme ne pourront valoir que 0 ou 1, ainsi on pourra le décrire par la liste des indices de ses coefficients valant 1 (le polynôme "1+x+x^3" sera donc représenté par la liste "0 1 3", par ordre croissant d'indices). Les indices descriptifs des polynômes seront toujours suffisamment petits pour pouvoir être représenté en mémoire par un entier de base (type int/integer). L'entier x sera donné, comme d'habitude, par la chaîne de caractères de sa représentation (en base 10), mais cette fois, on ne pourra pas directement la convertir en un entier du langage. Pour le polynôme "1+x+x^3", si on donne x=5, il faudra donc rendre 1+5+5^3 = 1+5+125 = 131.
Étant donnés P et x, calculer P(x).
Limites de temps et de mémoire (Python)
- Temps : 1 s sur une machine à 1 GHz.
- Mémoire : 8 000 ko.
Entrée
L'entrée se décompose en deux lignes :
- la liste des indices (entiers de base) des coefficients de P valant 1, séparés par des espaces,
- le grand entier x (suivi d'un retour à la ligne).
Sortie
La sortie est l'image de x par P (la chaîne de caractère de sa représentation en base 10) suivie d'un retour à la ligne.
Chaque test prendra maximum 10 secondes. BIEN TROP GROS, FAIRE ATTENTION
Exemples
Exemple 1
entrée :
0 1 3 5
sortie :
131
Exemple 2
entrée :
2048 1234
sortie :
10314473393184679736869298135856868318837274800666285917699525506489711515683426144545388948855924836610603373058799281849682651065988858782417538649301179102873828149409699413583084797951635780398778447732215611870761221393264523486002711233415134476171948872576575778768058011869312394591433671496879353256738653311677337099147038801178802825724209634362823173593923386084549067434085830227178209239457137723321770731042777558081406940147139667990254228174094508419077175917973307871411709893603768521725352746054623497685665327201622303372424658312521419745237362576122972550411123177530637072736945420602737409247085086197444880905363205329115498242538864156716516004470724097605836056043034133474693083990402162129452692576896540277875176000967208481663008305270779098122334262775595417270282185179548580515206247779118774906786183050811702471674146166149803311182972416699829540706588938052114725525166333700534024163518525835705844865095812434193830300810584567348339063060254784935172886897905368793945036837060678840784377623212307066293478248259199295086890845629779939516438001812731583068743144024869568176657542850823599628676354743022896101288541512338254692855856491413860404584618384121873303041378456656136366688754986770014955682983791917100352816811205498775881167027933860193337903855936566654695289705441485007450284401317541731400163085203202464038923977133729728444995448705501059566776050331467672460234435651696388567462253236613657556602492244386233370516692785049936212947187784092471105265363251362482079054595394088226079396643428440406046715199288972892667246824803025777050765153050158207185599316188815127235269005260845180224938784405752344000196617139022210902941870017230276852467661686273842434092129772043778649314239341843067737377741465354324338647802050252602973668592651879269931432960377904833702477294624579415798930596149523156395532402286585254141623180332293099332498635969118752013374800761843730343195851520798792002080860894194327163823932070017035680389655943108043707866824600318114763717790263778165435145708022450049443792979191757650574366528343895054081735118627208952467449626867677088042416506202076189774198997817001248570852909547095338289285053111855941099875518334686280494716391040289318425253683527142114431604340907441422236144080530900382772341689844103805677753237058580274967498853385372790838312705823615800044575538898621019951035085917874388422204024549141803950182994201831369099198598374090124626190118774284700729042114162959165413089474734086716292643850700400406340750242321507070619133318635396559323917849164333871996535653848937867702658108518399835143962001793078739201468119223976682639904731309585203997453784169831700998500778160634548765947944279233550582146181695398959909547691025726626714869810471970739115983438642038653385682415429105002688522228682162612436744486672814171552673109044377400019892612275501152777559320067108877299876750768168850326730019461670989804870020003038373990122722474508992394073677540034473391984833231719453945877501937042759481310393639709816188872244716857492268872833102982078465185312761755684203508245448381208254842095952815314087257537969774766056295247186230697371093839657730397637544168916216667810424012567555201394649859106251176301599020289407279821492798749147519888069572684645064480836781516428385507845669975519975928489762754862433196224664092561466669521053210690184290115694686304047801672007360745755877798083249471032074746678326760777562068626758786493378833570594813354252422299847280214393072425539284457992444120956088926825957873599834114497506875465883343025578867270384714629507071003402235125237529565373523748077686265959552494089768426060841494656217411034481744540626532778538657549667741238261506418371053174722635526773785021242881966704737392966299648978271769088516861654329702110065028816504471781072975236177697523951007574938727526167449673078498542887784823420920429805679539466082273691543424418003263211038827449886176331612488529432418434425860530983204299829202356188117426290864691607420159544384126315415139135630807561871844397821347400152622804240755340011269696423287025285485292302088384934357237755035699366638189625531181125193383389723830647589472946191712555406867309285705445919620272097183713726168843715724243016765761155374715660926057575081049634530830629730713712369345989962781901018514331036536005677436835769699128278780798200465397519276260301561350997605373628722268778968548647449512690233131798443444670247513654881929426065588883967298299917741178950187580286494695210552534928465990408111784875163326728834788138910877454901213548058873028414733338836488347773054613049041996658206599513569782525681110439198286359249052633610681951120409379259552719022828783447832344212431741938521003295548117641298227626053960971955731910566050122072558679844314861994830797095997963457493340055158622397686339415683180777837165777972979030831959494656326547055633289670832464154676341601098017831805971347507171832566100868147771903203153822356281849151063886504039586410790226177118926760505755407745662375562229586789005412980292840056240442114594228302958524544907980087806122217153561319258812689978452799943936238249700636956924629330514134067997760016840369573412828754248257152755089643902983024183219409057507281331813285253940605396591570925809308570548614747916596593749607785201389863663178476019837598752677260389592214179469652664007023942906368778091550213326319084705051572819227409649805948085343238382671203070735697339901504023351537723607367929202708516791075582458602933717669812894991344482493558126921433251572938017046558949699430171906672206090545199250643433984479875587439114566223311894793120858376188058387387345804749599538648445521143907871771924818398534217242865162634534433482118101115501403774591344811230907328917289612821722754807316022352442306096443193438012383354958869370021264693159012494646608307899130024017503563146335546183133255155920937413840986232020496425459013547901019263839508435740106969164217538914132168380990210632594780684672556432827481460885342128564983920575848146191345922629358878839154220237358501160366713657892625911733131435878086377970749321346703536617481524435402018093527925555433412750776286251811363515399174677633324800254403961657639211254223928651452505341767410406901468312052432896
Exemple 3
entrée :
996 997 998 999 1000 142857
sortie :
7971292236047049006546482329597401402330895786512028195474027982099559718786827319212711408464179148722044480723710279820963196954725088318653942610492387945280381058067124038054064574556883969432540983638757902105511454251903073479371988944140677221269685742204564567441976228684890707288708667628792220581564994811888535294788773458599423679606560472201605872239173034978022721054875769256062544358134196577286565669725479588868122157333164698608173243526073131420763236286652870615258541601906887053522578440272973802578636015863023956948586443872157998178366119806625807702029517975757629677367914882697463813264796960672983215001827856237781938478823190048989639012865680757144764985790174169291264035687547913318458789647742020171123146871610991495148227715868472064169760051388542410741881911334738321800186613675030711880737762606801516917679702294600805940364855144403364010168179248740217218366096593042350160841408286686884483336621407889442831901419277510717793166011339703239877782123816101206558170685056237840641798627442745694436269945951351620275481365175900041266193766187547281134200456452867063298952238409911765935672993640574478237242220473094234301608889962857939208569824691471462014836179493657806509800804531847260422947274283764111886860967278756157607532564333618234564724031497414211147367385990357771343178944094725455302047882702490654022643714862778479732009076369495359529015945992383877027072823199943609671416742277833642905857926255234155235532804206105902037023313934321820241753527490422903997974230081074391951001735100881210674442077951620988485498360656051711078561238312125343444710128298180376712356706869585362955870014910858388907854011903923477361154070575877300611155951595769184726546874608011772904552756405876092390227454767957969175247933855234481699255434375100844517202964176414612750126014312129518720297572461310048498690239318772172548326987570570229267673515357293080347259717989591898952399390948310393587270999159844342224970581206121383565139642389240402366695683355884646348490780057044444019431831013737203763404533639276916211836088181844316437562288771663645444334512298790250532476094960464455757715324001774402642609211838287689587481941140974436715623475952461621774075714382670776617779181236368010570325157059060133217120444548097720158486487148208186742855396663089362879707807398761402224812457676946976468525655609018392798895704099622230348927633691025348641856066171656953466120239813985569593936145769670100656368100620332002966223081542166489821220185090430546156139222785792287121675347724098306488965263248576893409749041880903732720391401359469044938414711559715305369660487865190213964222165070479732651293278954652703053119299427966512362471154579239835201327572983461340136956619692544664042249659928946137172509866278506586869400830794542980037896521776746427898839642394981321681376495688385996883213430262993865147952513189629712323429845558387820191418257668071494719950668864792061812119670030903987363676538907018627616453029996308531131390911797037207282048678797802487777272368980020984300462574620287910703054143857046712936586555203135073350127726314768974617858752470734768755506697908863962457115830323347923683324285065007802379289012147435607957568851085098922046268999961838618161645477950496576254058088489556014373379719320273824011842295848538944162381787691671601038471612280317601848441439012149325687467145008490231910052901358452824107225212782417777615569137443992766171216943297594205033114433260700932280271811170146417216331581868228658510302279131244256498580874027022655541804007281114263136842348177346031850027584932742299710010674561200744227980727730905985540683864363130240315044927453907514798578186419287696552940571645627486993548585706746691346267743014542909898142446095241985257511971908909577072094303825252844754913112460812449665838318339096682618703600459818385686376611053391269528339938458137070634485700598134985955390977763771744673090323207580653234395386609444286190419833449922815185970668412067342027126057960934533402224877979323256117207296987185902546361474737987389762043278321622680077273817437733283164070694598081842476748165170446201994070804403223446495074723190015201314765626477528003437939513417471279495694334953084870483079854876715294855246644325784473392668020063712425896801309468009151764651972078127118108073377686254358726058149127666272741302296327483013662684946898374712399582042777973232426004715737740823929677302955949090652741677848117976082009759411297057056552964327242885256616294988349670110567059271213290568363018628429819567007162792839644450037024235751322000630825960328310012515375732754304281797974895058829976814313811343934001041905936618953685371652495556830126032288762689021008198795634867624435727999431652895623782863231940936983871302179040085526685214390466717775942704857630653685591006082535388373003403994010822572590673687659647530018547423089467784339441685200711584788951748337154402533979952819876777170095699535710480259301011312452631046509494876509941710995079510388023099938377439917787733257082904932029016368022559833328904565304884293978663340917359247125402101
Commentaires
Squelettes de codes :
[GROUPFULL:skeleton]Vous devez être connecté(e) pour résoudre ce problème.
L'inscription ne prendra qu'une minute et vous pourrez alors résoudre les exercices puis faire valider automatiquement vos solutions.
Une fois identifié(e), vous pourrez demander sur cette page des conseils pour résoudre le sujet ou demander de l'aide sur le forum d'entraide.
Lorsque vous serez connecté(e), vous pourrez voir vos actions ici.
Une correction détaillée sera disponible lorsque vous aurez résolu le sujet.