Voir les cours et résoudre les problèmes en :
Le C est un langage de programmation impératif conçu pour la programmation système. Inventé au début des années 1970 avec UNIX, C est devenu un des langages les plus utilisés. De nombreux langages plus modernes se sont inspirés de sa syntaxe. Il privilégie la performance sur la simplicité de la syntaxe. [En savoir plus]
Le C++ est un langage de programmation impératif. Inventé au début des années 1980, il apporte de nouveaux concepts au langage C (les objets, la généricité), le modernise et lui ajoute de nombreuses bibliothèques. C++ est devenu l'un des langages les plus utilisés. Sa performance et sa richesse en font le langage de prédilection pour les concours. [En savoir plus]
Pascal est un langage de programmation impératif inventé dans les années 1970 dans un but d'enseignement. Quoiqu'encore utilisé à cette fin, l'absence de bibliothèque standard en limite son utilisation malgré une grande efficacité. Sa syntaxe a été reprise par d'autres langages plus modernes avec plus ou moins de succès. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
OCaml est un langage de programmation fonctionnel inventé au milieu des années 1990. Il permet aussi une programmation impérative ou objet. Il permet d'écrire des programmes courts et faciles à vérifier et est ainsi utilisé pour certains systèmes embarqués très sensibles comme ceux des avions. Il est utilisé dans l'enseignement en classes préparatoires aux grandes écoles. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
Java est un langage de programmation impératif et orienté objet. Inventé au début des années 1990, il reprend en grande partie la syntaxe du langage C++ tout en la simplifiant, au prix d'une performance un peu moins bonne. S'exécutant dans une machine virtuelle, il assure une grande portabilité et ses très nombreuses bibliothèques en font un langage très utilisé. On lui reproche toutefois la « verbosité » de son code. [En savoir plus]


Remarque : Pour un débutant souhaitant apprendre Java, nous conseillons fortement de commencer par JavaScool, plus facile à apprendre, bien que fortement similaire.
Java's Cool (alias JavaScool) est conçu spécifiquement pour l'apprentissage des bases de la programmation. Il reprend en grande partie la syntaxe de Java sur laquelle il s'appuie, mais la simplifie pour un apprentissage plus aisé. La plateforme JavaScool est accompagnée d'un ensemble d'activités diverses de découverte de la programmation. [En savoir plus]
Python est un langage de programmation impératif inventé à la fin des années 1980. Il permet une programmation orientée objet et admet une syntaxe concise et claire qui en font un langage très bien adapté aux débutants. Étant un langage interprété, il n'est cependant pas aussi performant que d'autres langages. [En savoir plus]

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é pour résoudre cet exercice.

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.

Correction en cours de chargement…