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).
LAIKO IR ATMINTIES RIBOJIMAI (Python)
- Laiko ribojimas: 1 sek., procesorius: 1GHz.
- Atmintis: 8,000 KB.
PRADINIAI DUOMENYS
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).
REZULTATAI
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
PAVYZDYSs
PAVYZDYS NR. 1
pradiniai duomenys:
0 1 3 5
rezultatai:
131
PAVYZDYS NR. 2
pradiniai duomenys:
2048 1234
rezultatai:
10314473393184679736869298135856868318837274800666285917699525506489711515683426144545388948855924836610603373058799281849682651065988858782417538649301179102873828149409699413583084797951635780398778447732215611870761221393264523486002711233415134476171948872576575778768058011869312394591433671496879353256738653311677337099147038801178802825724209634362823173593923386084549067434085830227178209239457137723321770731042777558081406940147139667990254228174094508419077175917973307871411709893603768521725352746054623497685665327201622303372424658312521419745237362576122972550411123177530637072736945420602737409247085086197444880905363205329115498242538864156716516004470724097605836056043034133474693083990402162129452692576896540277875176000967208481663008305270779098122334262775595417270282185179548580515206247779118774906786183050811702471674146166149803311182972416699829540706588938052114725525166333700534024163518525835705844865095812434193830300810584567348339063060254784935172886897905368793945036837060678840784377623212307066293478248259199295086890845629779939516438001812731583068743144024869568176657542850823599628676354743022896101288541512338254692855856491413860404584618384121873303041378456656136366688754986770014955682983791917100352816811205498775881167027933860193337903855936566654695289705441485007450284401317541731400163085203202464038923977133729728444995448705501059566776050331467672460234435651696388567462253236613657556602492244386233370516692785049936212947187784092471105265363251362482079054595394088226079396643428440406046715199288972892667246824803025777050765153050158207185599316188815127235269005260845180224938784405752344000196617139022210902941870017230276852467661686273842434092129772043778649314239341843067737377741465354324338647802050252602973668592651879269931432960377904833702477294624579415798930596149523156395532402286585254141623180332293099332498635969118752013374800761843730343195851520798792002080860894194327163823932070017035680389655943108043707866824600318114763717790263778165435145708022450049443792979191757650574366528343895054081735118627208952467449626867677088042416506202076189774198997817001248570852909547095338289285053111855941099875518334686280494716391040289318425253683527142114431604340907441422236144080530900382772341689844103805677753237058580274967498853385372790838312705823615800044575538898621019951035085917874388422204024549141803950182994201831369099198598374090124626190118774284700729042114162959165413089474734086716292643850700400406340750242321507070619133318635396559323917849164333871996535653848937867702658108518399835143962001793078739201468119223976682639904731309585203997453784169831700998500778160634548765947944279233550582146181695398959909547691025726626714869810471970739115983438642038653385682415429105002688522228682162612436744486672814171552673109044377400019892612275501152777559320067108877299876750768168850326730019461670989804870020003038373990122722474508992394073677540034473391984833231719453945877501937042759481310393639709816188872244716857492268872833102982078465185312761755684203508245448381208254842095952815314087257537969774766056295247186230697371093839657730397637544168916216667810424012567555201394649859106251176301599020289407279821492798749147519888069572684645064480836781516428385507845669975519975928489762754862433196224664092561466669521053210690184290115694686304047801672007360745755877798083249471032074746678326760777562068626758786493378833570594813354252422299847280214393072425539284457992444120956088926825957873599834114497506875465883343025578867270384714629507071003402235125237529565373523748077686265959552494089768426060841494656217411034481744540626532778538657549667741238261506418371053174722635526773785021242881966704737392966299648978271769088516861654329702110065028816504471781072975236177697523951007574938727526167449673078498542887784823420920429805679539466082273691543424418003263211038827449886176331612488529432418434425860530983204299829202356188117426290864691607420159544384126315415139135630807561871844397821347400152622804240755340011269696423287025285485292302088384934357237755035699366638189625531181125193383389723830647589472946191712555406867309285705445919620272097183713726168843715724243016765761155374715660926057575081049634530830629730713712369345989962781901018514331036536005677436835769699128278780798200465397519276260301561350997605373628722268778968548647449512690233131798443444670247513654881929426065588883967298299917741178950187580286494695210552534928465990408111784875163326728834788138910877454901213548058873028414733338836488347773054613049041996658206599513569782525681110439198286359249052633610681951120409379259552719022828783447832344212431741938521003295548117641298227626053960971955731910566050122072558679844314861994830797095997963457493340055158622397686339415683180777837165777972979030831959494656326547055633289670832464154676341601098017831805971347507171832566100868147771903203153822356281849151063886504039586410790226177118926760505755407745662375562229586789005412980292840056240442114594228302958524544907980087806122217153561319258812689978452799943936238249700636956924629330514134067997760016840369573412828754248257152755089643902983024183219409057507281331813285253940605396591570925809308570548614747916596593749607785201389863663178476019837598752677260389592214179469652664007023942906368778091550213326319084705051572819227409649805948085343238382671203070735697339901504023351537723607367929202708516791075582458602933717669812894991344482493558126921433251572938017046558949699430171906672206090545199250643433984479875587439114566223311894793120858376188058387387345804749599538648445521143907871771924818398534217242865162634534433482118101115501403774591344811230907328917289612821722754807316022352442306096443193438012383354958869370021264693159012494646608307899130024017503563146335546183133255155920937413840986232020496425459013547901019263839508435740106969164217538914132168380990210632594780684672556432827481460885342128564983920575848146191345922629358878839154220237358501160366713657892625911733131435878086377970749321346703536617481524435402018093527925555433412750776286251811363515399174677633324800254403961657639211254223928651452505341767410406901468312052432896
PAVYZDYS NR. 3
pradiniai duomenys:
996 997 998 999 1000 142857
rezultatai:
7971292236047049006546482329597401402330895786512028195474027982099559718786827319212711408464179148722044480723710279820963196954725088318653942610492387945280381058067124038054064574556883969432540983638757902105511454251903073479371988944140677221269685742204564567441976228684890707288708667628792220581564994811888535294788773458599423679606560472201605872239173034978022721054875769256062544358134196577286565669725479588868122157333164698608173243526073131420763236286652870615258541601906887053522578440272973802578636015863023956948586443872157998178366119806625807702029517975757629677367914882697463813264796960672983215001827856237781938478823190048989639012865680757144764985790174169291264035687547913318458789647742020171123146871610991495148227715868472064169760051388542410741881911334738321800186613675030711880737762606801516917679702294600805940364855144403364010168179248740217218366096593042350160841408286686884483336621407889442831901419277510717793166011339703239877782123816101206558170685056237840641798627442745694436269945951351620275481365175900041266193766187547281134200456452867063298952238409911765935672993640574478237242220473094234301608889962857939208569824691471462014836179493657806509800804531847260422947274283764111886860967278756157607532564333618234564724031497414211147367385990357771343178944094725455302047882702490654022643714862778479732009076369495359529015945992383877027072823199943609671416742277833642905857926255234155235532804206105902037023313934321820241753527490422903997974230081074391951001735100881210674442077951620988485498360656051711078561238312125343444710128298180376712356706869585362955870014910858388907854011903923477361154070575877300611155951595769184726546874608011772904552756405876092390227454767957969175247933855234481699255434375100844517202964176414612750126014312129518720297572461310048498690239318772172548326987570570229267673515357293080347259717989591898952399390948310393587270999159844342224970581206121383565139642389240402366695683355884646348490780057044444019431831013737203763404533639276916211836088181844316437562288771663645444334512298790250532476094960464455757715324001774402642609211838287689587481941140974436715623475952461621774075714382670776617779181236368010570325157059060133217120444548097720158486487148208186742855396663089362879707807398761402224812457676946976468525655609018392798895704099622230348927633691025348641856066171656953466120239813985569593936145769670100656368100620332002966223081542166489821220185090430546156139222785792287121675347724098306488965263248576893409749041880903732720391401359469044938414711559715305369660487865190213964222165070479732651293278954652703053119299427966512362471154579239835201327572983461340136956619692544664042249659928946137172509866278506586869400830794542980037896521776746427898839642394981321681376495688385996883213430262993865147952513189629712323429845558387820191418257668071494719950668864792061812119670030903987363676538907018627616453029996308531131390911797037207282048678797802487777272368980020984300462574620287910703054143857046712936586555203135073350127726314768974617858752470734768755506697908863962457115830323347923683324285065007802379289012147435607957568851085098922046268999961838618161645477950496576254058088489556014373379719320273824011842295848538944162381787691671601038471612280317601848441439012149325687467145008490231910052901358452824107225212782417777615569137443992766171216943297594205033114433260700932280271811170146417216331581868228658510302279131244256498580874027022655541804007281114263136842348177346031850027584932742299710010674561200744227980727730905985540683864363130240315044927453907514798578186419287696552940571645627486993548585706746691346267743014542909898142446095241985257511971908909577072094303825252844754913112460812449665838318339096682618703600459818385686376611053391269528339938458137070634485700598134985955390977763771744673090323207580653234395386609444286190419833449922815185970668412067342027126057960934533402224877979323256117207296987185902546361474737987389762043278321622680077273817437733283164070694598081842476748165170446201994070804403223446495074723190015201314765626477528003437939513417471279495694334953084870483079854876715294855246644325784473392668020063712425896801309468009151764651972078127118108073377686254358726058149127666272741302296327483013662684946898374712399582042777973232426004715737740823929677302955949090652741677848117976082009759411297057056552964327242885256616294988349670110567059271213290568363018628429819567007162792839644450037024235751322000630825960328310012515375732754304281797974895058829976814313811343934001041905936618953685371652495556830126032288762689021008198795634867624435727999431652895623782863231940936983871302179040085526685214390466717775942704857630653685591006082535388373003403994010822572590673687659647530018547423089467784339441685200711584788951748337154402533979952819876777170095699535710480259301011312452631046509494876509941710995079510388023099938377439917787733257082904932029016368022559833328904565304884293978663340917359247125402101
KOMENTARAI
Squelettes de codes :
[GROUPFULL:skeleton]Tik užsiregistravę ir prisijungę galite pateikti šio uždavinio sprendimą.
Registravimasis užims vos keletą minučių, tuomet galėsite svetainėje spręsti uždavinius, juos testuoti bei pateikti jų sprendimus.
Prisijungę gausite iš anksto paruoštas užuominas arba galėsite kreiptis pagalbos į forumą.
Lorsque vous serez connecté(e), vous pourrez voir vos actions ici.
Išsamų sprendimą galėsite pamatyti tik išsprendę uždavinį.