0w1

Monthly Training Farm - May 2017 D. oeis1 ( Offline )

Monthly Training Farm Offline

https://oj.icpc.tw/contest/5/problem/D

Problem Description:
Define f( x ) as sum of digits of x, g( x ) as product of digits greater than 0 of x.
Let D[ 1 ] = 8.
D[ i ] = sum( f( D[ j ] ) + g( D[ j ] ) + 10 for j in range( 1, i ) ).
Print D[ X ].

Constraints:
1 ≤ X ≤ 8.7e8

Solution:
A brute force solution obviously can be done with O( 1 ) in both time and space.
Therefore we precompute all values of possible D[ i ] where i % 1e6 == 1, storing it in a static array.
Now we can start from the term of the nearest smaller stored index of x, so we can calculate no more than 1e6 times to retrieve any D[ x ].

Time Complexity:
O( 1e6 )

#include <bits/stdc++.h>
using namespace std;

#define int unsigned long long

int X;

int F( int x ) {
  int res = 0;
  for( int i = x; i; i /= 10 ) {
    res += i % 10;
  }
  return res;
}

int G( int x ) {
  int res = 1;
  for( int i = x; i; i /= 10 ) {
    res *= max( 1ULL, i % 10 );
  }
  return res;
}

int dict[] = { 26ULL, 11214756105887ULL, 100109103333253ULL, 112321332614932ULL, 203114016636054ULL, 404409304036708ULL, 1001012778760022ULL, 1019302331457852ULL, 1102101202684232ULL, 1121430249352215ULL, 1216051011115952ULL, 1512122246750191ULL, 2020100352176083ULL, 2201712083436421ULL, 3023105446135922ULL, 4011120141502074ULL, 5301121147717626ULL, 8126386864463905ULL, 10013011117126224ULL, 10101121991208593ULL, 10120030221166599ULL, 10211021110060455ULL, 10437288789512356ULL, 11002141609143322ULL, 11022072365212753ULL, 11102311331258280ULL, 11123011604330152ULL, 11230101145815842ULL, 11600370593813612ULL, 12040231073450651ULL, 12242404437916058ULL, 13103015767035350ULL, 14101010451873091ULL, 16021151115329590ULL, 19071047126554648ULL, 20111012101527119ULL, 20610111200219087ULL, 21102207937384022ULL, 21413106708179555ULL, 22441202912004694ULL, 25410412930954745ULL, 30111222194156150ULL, 31100319215438153ULL, 32144150208207680ULL, 40012012912164383ULL, 41106113092661534ULL, 45025002028944730ULL, 51171412613583343ULL, 60133142263389962ULL, 68410508648506850ULL, 80102223036586709ULL, 90804710916245570ULL, 100013015493131914ULL, 100101125313791126ULL, 100120051959497775ULL, 100211030117752543ULL, 100440286330665844ULL, 101002182001350236ULL, 101022104162086429ULL, 101102356536806905ULL, 101123090465972937ULL, 101230120677663449ULL, 101600963352248741ULL, 102041011210309336ULL, 102245626245682415ULL, 103103110410330701ULL, 104101020120233338ULL, 106022018216825526ULL, 109090013116926663ULL, 110020111033404974ULL, 110101206218149853ULL, 110120161354234098ULL, 110213180035379256ULL, 110510122209193786ULL, 111003151208210032ULL, 111027300170429267ULL, 111110121014154636ULL, 111145068937186721ULL, 111305123949646138ULL, 111811103116358741ULL, 112108391887619978ULL, 112511031116438904ULL, 113261078006138888ULL, 114532927397200676ULL, 116320813267746473ULL, 120011011007717407ULL, 120142820112633177ULL, 121003109216667199ULL, 121120031010360682ULL, 122006331130807111ULL, 123691153593265764ULL, 130031159507523939ULL, 131011121172806049ULL, 132012132156544059ULL, 137656711885038300ULL, 141041011101666139ULL, 143603111594961817ULL, 151003802311019321ULL, 160011110307130712ULL, 163111112540879174ULL, 174411223315035574ULL, 191000112019767008ULL, 200062321332868281ULL, 200300020114004251ULL, 201021121012314610ULL, 201211133220462699ULL, 202110220117338626ULL, 204110126072334156ULL, 210011121052438259ULL, 210160701178595188ULL, 211007312114383862ULL, 211121220196357466ULL, 212011101115142611ULL, 214010112652024846ULL, 220070121416013923ULL, 221124113096244386ULL, 226221304686083662ULL, 233011228675052142ULL, 246308120175433614ULL, 264334154194201547ULL, 300082096160298001ULL, 301012122012140143ULL, 302061120930945010ULL, 309011115318607111ULL, 310411031417540722ULL, 311520954458836981ULL, 315121201268703862ULL, 322012333212952519ULL, 332922148736711239ULL, 361008430451028073ULL, 400122462143244484ULL, 401320298632690725ULL, 410061811706051388ULL, 411120823797566049ULL, 416111421195907290ULL, 430001221149639598ULL, 453022028546739198ULL, 501002126155765057ULL, 507020252309214870ULL, 511202223849442197ULL, 521112010021950761ULL, 555351214882874576ULL, 601211503278631572ULL, 611031326103792078ULL, 621041201118200574ULL, 671304213007008966ULL, 710101112113387057ULL, 722011022906157733ULL, 800213113060101728ULL, 811013016062978076ULL, 842019016607761562ULL, 910104063965977943ULL, 934220113341084929ULL, 1000232112053378618ULL, 1000610949571548629ULL, 1001010140603370933ULL, 1001042510686928382ULL, 1001110151101130620ULL, 1001150011384761309ULL, 1001309330460811324ULL, 1001811226101996923ULL, 1002108212320907143ULL, 1002501102216238770ULL, 1003162203126008210ULL, 1004211591053917664ULL, 1006386043245698479ULL, 1010006121309591396ULL, 1010031151214166941ULL, 1010107215103460366ULL, 1010131950711038489ULL, 1010282110232328507ULL, 1010701071128501412ULL, 1011010311635437570ULL, 1011052011111832815ULL, 1011111332058223155ULL, 1011201011012211348ULL, 1011401221478746523ULL, 1012005012694465954ULL, 1012121411132959867ULL, 1013009311278050018ULL, 1013926012013273459ULL, 1015101311006368026ULL, 1017121324551947705ULL, 1020031111308958604ULL, 1020223411102751058ULL, 1021018312121334092ULL, 1021201713443471027ULL, 1022110911434460134ULL, 1024716524032226540ULL, 1030111240341886432ULL, 1031105003822754985ULL, 1032331121440477906ULL, 1040102001294084825ULL, 1041152031166396375ULL, 1047202121432381000ULL, 1051122832103362219ULL, 1060302221136679793ULL, 1070103000261321621ULL, 1081063306374478910ULL, 1092712724524100915ULL, 1100016940879352350ULL, 1100101102102318378ULL, 1100118112213467224ULL, 1100211232101162978ULL, 1100500706077034232ULL, 1101002130121435700ULL, 1101022110412739998ULL, 1101110030710564100ULL, 1101140200139887688ULL, 1101301062979255764ULL, 1101750241905204601ULL, 1102102282115046714ULL, 1102412335323018563ULL, 1103211057405488486ULL, 1104340192676437816ULL, 1106203009424207816ULL, 1110007112325796257ULL, 1110031441066985534ULL, 1110110810131175422ULL, 1110161705150291377ULL, 1110313031187999385ULL, 1110910610019288871ULL, 1111012272111013804ULL, 1111101001111142680ULL, 1111113111514110890ULL, 1111210120046640336ULL, 1111430001003709386ULL, 1112018116441091589ULL, 1112210113255325653ULL, 1113100623232852837ULL, 1114101034044810673ULL, 1115495078851120750ULL, 1118112874130963525ULL, 1120131111599253781ULL, 1121005030202197815ULL, 1121123101124374257ULL, 1122012302124616363ULL, 1124001818015601316ULL, 1130009222131835977ULL, 1131001312883280211ULL, 1132000227038231746ULL, 1136921145448090252ULL, 1141041011613856885ULL, 1144009111280362587ULL, 1151100723240447896ULL, 1160104020337750642ULL, 1164413749328413372ULL, 1173322100593529837ULL, 1188030545680949767ULL, 1200011010034604173ULL, 1200143064711770400ULL, 1201003111217223286ULL, 1201120039158449533ULL, 1202007055168895939ULL, 1203702211035283263ULL, 1210030011202001087ULL, 1210220040731451372ULL, 1211022162206811788ULL, 1211213007035474598ULL, 1212121140145820758ULL, 1215100617422892159ULL, 1220120397194128637ULL, 1221532091543014643ULL, 1230209112784376798ULL, 1240009201156178968ULL, 1251009229674464471ULL, 1271103491925303147ULL, 1300685345184496042ULL, 1301503646794826842ULL, 1305110233216249303ULL, 1310304923300145682ULL, 1311302024589836680ULL, 1314142195869744499ULL, 1321110402029990890ULL, 1331200213242271234ULL, 1351130103483426286ULL, 1401005195466717817ULL, 1403099522105209041ULL, 1410308129443283559ULL, 1412070231191007631ULL, 1420820811394467861ULL, 1437111323283414672ULL, 1490203812544745584ULL, 1501201420998015003ULL, 1510120243433403530ULL, 1513024136523476263ULL, 1531112245257586341ULL, 1600110402066930381ULL, 1607116543432113111ULL, 1612210122430877118ULL, 1631501158133555460ULL, 1701111211037574186ULL, 1712101020919983838ULL, 1750208588943057613ULL, 1810011911949836864ULL, 1821712469819813574ULL, 1901111222626000948ULL, 1915128211344827773ULL, 2000410230505634597ULL, 2001100701211446518ULL, 2001320324517382150ULL, 2002232327313167778ULL, 2005071112300021088ULL, 2010030224216065250ULL, 2010221143360679671ULL, 2011016114201510716ULL, 2011201122148261505ULL, 2012110203082814862ULL, 2014526482445921507ULL, 2020130023004162843ULL, 2021402236094075660ULL, 2030141012233414509ULL, 2038110241768398894ULL, 2050602134253299089ULL, 2071116069232629815ULL, 2100107111104337802ULL, 2100500202452810081ULL, 2101100950291901012ULL, 2101320703145947412ULL, 2102411135435605648ULL, 2106157441735478979ULL, 2110120022193121948ULL, 2111001130110216472ULL, 2111114905227066737ULL, 2111870739412164909ULL, 2113311857634355278ULL, 2120000963499078555ULL, 2121101447134264514ULL, 2125174235375224687ULL, 2132011751893970507ULL, 2142111121255265896ULL, 2161110481888900878ULL, 2191103517424871836ULL, 2201416515461581015ULL, 2210101041314160192ULL, 2211134117389328013ULL, 2217062006266368896ULL, 2230051141118258509ULL, 2258143747237456376ULL, 2301120071121840527ULL, 2310300325712818187ULL, 2320201121221112588ULL, 2380122029362187243ULL, 2411105714709998811ULL, 2441300849186931535ULL, 2510207117799819333ULL, 2580100410900781346ULL, 2650024410933604136ULL, 2723011417635053666ULL, 2910001112529883305ULL, 3001022221622165763ULL, 3002110202627205576ULL, 3010001050111202937ULL, 3010524150375036450ULL, 3011780137011354540ULL, 3016012612162214709ULL, 3022120150504711620ULL, 3034147183339119504ULL, 3061217641035237306ULL, 3100111503020441700ULL, 3101130210826222686ULL, 3103091217736712625ULL, 3110111261614772661ULL, 3111110311318736073ULL, 3112600690274010045ULL, 3120211410826596624ULL, 3128627441123888247ULL, 3141462224320767006ULL, 3180110373876430188ULL, 3204015216987353157ULL, 3211808034202180875ULL, 3230002232143701567ULL, 3301108426150816632ULL, 3321011913009806757ULL, 3406411658436093558ULL, 3481606299653802831ULL, 3605231432051922324ULL, 3732305631963356754ULL, 4001121722610128872ULL, 4006712112108874623ULL, 4011050524744391724ULL, 4013872357802597638ULL, 4022458480715365230ULL, 4045062146497651761ULL, 4100111020481505987ULL, 4101230111163855488ULL, 4110021003074666150ULL, 4111201102420155703ULL, 4120001136581284648ULL, 4130833052644581646ULL, 4171104411965388152ULL, 4204832210520832326ULL, 4220102041394141218ULL, 4301138061268489966ULL, 4340108100610958752ULL, 4461151519160994670ULL, 4612100636684857584ULL, 4864122406115624162ULL, 5001118104361228806ULL, 5010234108157953557ULL, 5014100104233603563ULL, 5032111517747400475ULL, 5100101263044604327ULL, 5103724067523622894ULL, 5111120043269905945ULL, 5121014111185168961ULL, 5160211233696689854ULL, 5210320555368494141ULL, 5270312125503905653ULL, 5358241015295389657ULL, 5513122213964549592ULL, 5831113027407044203ULL, 6003101897070056640ULL, 6011560516712121663ULL, 6030011611461796665ULL, 6100811122389840513ULL, 6110110317107988006ULL, 6115101172754387031ULL, 6141311103570501060ULL, 6210115613651952618ULL, 6301501681017931425ULL, 6467654436238722471ULL, 6911081305633409892ULL, 7010010018283314254ULL, 7020101013799261191ULL, 7091420502965615833ULL, 7110190024995098520ULL, 7121112020086015338ULL, 7201129310992864271ULL, 7300411050766681742ULL, 7481401986897451684ULL, 8002013411872702820ULL, 8020102311115602462ULL, 8101110701921574444ULL, 8112202094167346181ULL, 8180266106737825504ULL, 8282100226420473105ULL, 8600106888449783025ULL, 9001202163033354454ULL, 9020071027649195284ULL, 9101089118331404692ULL, 9113011111029192535ULL, 9201010233173174923ULL, 9321101478673857052ULL, 9831163520573294104ULL, 10001001335143870596ULL, 10001020810212034755ULL, 10001101503215657533ULL, 10001121020446064285ULL, 10001220011116754160ULL, 10001514094695346040ULL, 10002021780477418972ULL, 10002212011164177647ULL, 10003094005111435736ULL, 10004021110769819368ULL, 10006001110132384227ULL, 10008400203055314770ULL, 10010015100453453913ULL, 10010101022011689593ULL, 10010115510748904541ULL, 10010211051540914905ULL, 10010444032995592683ULL, 10011002011333784606ULL, 10011021220311531431ULL, 10011109421367286315ULL, 10011133223303326123ULL, 10011300114151524172ULL, 10011713330525937348ULL, 10012101413103938668ULL, 10012401410437190616ULL, 10013202211818522164ULL, 10014301180852294752ULL, 10016130110328770789ULL, 10020006042614619639ULL, 10020122312601968249ULL, 10021001090120186194ULL, 10021111701445242309ULL, 10021820041062994730ULL, 10023213826804662423ULL, 10029029389566898338ULL, 10031001128421182511ULL, 10031701829979302661ULL, 10036210194415526598ULL, 10041011211414372547ULL, 10043102815928944828ULL, 10050511001451656928ULL, 10056314648450557524ULL, 10062162110723578958ULL, 10073101112972953379ULL, 10090140724676845637ULL, 10100011017103367030ULL, 10100065272508955647ULL, 10100111021511238602ULL, 10100172200368208394ULL, 10100320123697799721ULL, 10101000112113045959ULL, 10101012018460426394ULL, 10101101111102104257ULL, 10101119674134745521ULL, 10101211421733266006ULL, 10101502914665895441ULL, 10102020412079610210ULL, 10102209000883838436ULL, 10103101111017146945ULL, 10104090287719489038ULL, 10105390536421108831ULL, 10108122509041538473ULL, 10110015131406366254ULL, 10110102110907164595ULL, 10110122020471057620ULL, 10110222423095654436ULL, 10110601030235355302ULL, 10111010131601073078ULL, 10111049121654884682ULL, 10111110301280933865ULL, 10111160181569082828ULL, 10111312111211019138ULL, 10111931119426601941ULL, 10112112203834863037ULL, 10112763407270004672ULL, 10113530128255101339ULL, 10115021019090758857ULL, 10117059020817256574ULL, 10120103011102780282ULL, 10120423049505709144ULL, 10121101721231320234ULL, 10121410029424326997ULL, 10122831012806576851ULL, 10127011001023306377ULL, 10130221150084034193ULL, 10131181103111168205ULL, 10133310223114318569ULL, 10140240281760408511ULL, 10142017412091101872ULL, 10150164040335098854ULL, 10153081017540539890ULL, 10161311424111798738ULL, 10171111523074160535ULL, 10181189040567635632ULL, 10194281912092214943ULL, 10200110103073479277ULL, 10200510543108993810ULL, 10201101103005751766ULL, 10201333020261559982ULL, 10202520245115176146ULL, 10206241105409212054ULL, 10210121031403425095ULL, 10211001453448446603ULL, 10211119321151312142ULL, 10211929030349664595ULL, 10213410555405051610ULL, 10220001300512375674ULL, 10221104550216165665ULL, 10225722892881539934ULL, 10232106445729863986ULL, 10242211212450779790ULL, 10261128213242893999ULL, 10291170858039874248ULL, 10301122119614654496ULL, 10303027129047392088ULL, 10310111110031107284ULL, 10311110041555547832ULL, 10312500208896132291ULL, 10320201569033300928ULL, 10328010247214720271ULL, 10341301121752277250ULL, 10380011209300181217ULL, 10401485993021895621ULL, 10410050178226649169ULL, 10411141129901369399ULL, 10417090244494300990ULL, 10430021128845271240ULL, 10461101411160345864ULL, 10501001111123212396ULL, 10506030113613749057ULL, 10511191046241308305ULL, 10521301852354154868ULL, 10561131265492883253ULL, 10601705445442170286ULL, 10611101103784972258ULL, 10621260932237854546ULL, 10700020050139577634ULL, 10711001410152701522ULL, 10726215510816474198ULL, 10801322512505147094ULL, 10812350535943785834ULL, 10881601160637563886ULL, 10911021690133875678ULL, 10951606007167639827ULL, 11000524363486531191ULL, 11001010010021141340ULL, 11001034100334543620ULL, 11001111011112936473ULL, 11001171014511908617ULL, 11001320124388600113ULL, 11001932311345370229ULL, 11002111280831814487ULL, 11002804332324015221ULL, 11003413021392651968ULL, 11005010104203917723ULL, 11007010510447129334ULL, 11010010327417019085ULL, 11010052113054824775ULL, 11010111401159288914ULL, 11010201012140042639ULL, 11010401455183054728ULL, 11011001130011430423ULL, 11011020101138384344ULL, 11011101485585424359ULL, 11011120444151487105ULL, 11011218332077442740ULL, 11011541115730664588ULL, 11012060306782662159ULL, 11012300501061178327ULL, 11013113417561738866ULL, 11014138434175145580ULL, 11016100041383582583ULL, 11019014201089175519ULL, 11020202071226413162ULL, 11021012334317750369ULL, 11021201200078158296ULL, 11022103412017083877ULL, 11024261114423645573ULL, 11030033623330731643ULL, 11031022016015579221ULL, 11032104612071952715ULL, 11040010150160648867ULL, 11041115415375870540ULL, 11046259684701018876ULL, 11051203111442226767ULL, 11060315126913787324ULL, 11070015474901034328ULL, 11080004296034574259ULL, 11090220021810502651ULL, 11100003160640492730ULL, 11100027341608622237ULL, 11100110121032950834ULL, 11100145108201571679ULL, 11100305171933714979ULL, 11100811110062867579ULL, 11101011501118705012ULL, 11101100131101552874ULL, 11101112019111468971ULL, 11101202121524952665ULL, 11101410275549935846ULL, 11102011338108809210ULL, 11102180213339487934ULL, 11103033171636152703ULL, 11104025182221003035ULL, 11105212052195446806ULL, 11108011195700396084ULL, 11110101010170576067ULL, 11110113562051863476ULL, 11110210282910090457ULL, 11110437122084272524ULL, 11111006140797308250ULL, 11111031160311347396ULL, 11111110031109557762ULL, 11111140833432454546ULL, 11111300412277835422ULL, 11111707301118580356ULL, 11112103003035321015ULL, 11112417128328026648ULL, 11113170111433986327ULL, 11114301028664920709ULL, 11116511427523981974ULL, 11120001092268971740ULL, 11120113010737025769ULL, 11120802760575283516ULL, 11121121170292847091ULL, 11122010144143473515ULL, 11123213102440738669ULL, 11128301990410424141ULL, 11130301113438001258ULL, 11131201216124965255ULL, 11133260409649610476ULL, 11140302116011704281ULL, 11142032111562115772ULL, 11150118111332940390ULL, 11153102126180273893ULL, 11161212120918466638ULL, 11171010410158497047ULL, 11181030155523246413ULL, 11192028637443233013ULL, 11200201013216053850ULL, 11201011803112010073ULL, 11201191004134527582ULL, 11202101140325729343ULL, 11204160120150102728ULL, 11210011061067467245ULL, 11210151950532359785ULL, 11211012004240031119ULL, 11211201154045019239ULL, 11212104231027022860ULL, 11214101041039480079ULL, 11220010521315172756ULL, 11221110211241756367ULL, 11224913060874702474ULL, 11231270417566402993ULL, 11241203124266989448ULL, 11260023161021264317ULL, 11281141032179869347ULL, 11300160617336181329ULL, 11301111408904872233ULL, 11302911102694627292ULL, 11310101301153748607ULL, 11311024064154257033ULL, 11312109131102783549ULL, 11320012046454899876ULL, 11323772673577552286ULL, 11340456214608399926ULL, 11372014905714251486ULL, 11400402110459051485ULL, 11402117171025845342ULL, 11410210111143063688ULL, 11411913155796479083ULL, 11421001113029683226ULL, 11434133208507662142ULL, 11491101230277821202ULL, 11501416357354711313ULL, 11510471237523252070ULL, 11516301898587321065ULL, 11540115013011789045ULL, 11601003146323432977ULL, 11610110039154147363ULL, 11614319114316242196ULL, 11641134641062430148ULL, 11701170104803453599ULL, 11711219093802520733ULL, 11741101111509045462ULL, 11802110299106869925ULL, 11818024159352151310ULL, 11901019264776620270ULL, 11919242351428191953ULL, 12000017320244448845ULL, 12000203184926194614ULL, 12001011053242027926ULL, 12001148178069293709ULL, 12002040311326427691ULL, 12004111323120116797ULL, 12010091122965043729ULL, 12010311011106687503ULL, 12011070582720133172ULL, 12011301620541035385ULL, 12012241126555585176ULL, 12016010059924238625ULL, 12020220132067161252ULL, 12022120084035555355ULL, 12030910541137450265ULL, 12040140762174891020ULL, 12051430321044055618ULL, 12073141012117857002ULL, 12100612001995800208ULL, 12101112125560385501ULL, 12101743573846507965ULL, 12103211129696626000ULL, 12109212567610622922ULL, 12110111121837999017ULL, 12110631230614271552ULL, 12111116110119139767ULL, 12112001065043826153ULL, 12113130560248338598ULL, 12118018308081207034ULL, 12121001621195806600ULL, 12122502294427309314ULL, 12131002142863664044ULL, 12140210314672590589ULL, 12151200113389096615ULL, 12172010332544123661ULL, 12200111101214212710ULL, 12201315196244725670ULL, 12210107499267803355ULL, 12211211100202026332ULL, 12219011172533181430ULL, 12230401545228422304ULL, 12264112126619732620ULL, 12301120150348409809ULL, 12310750514127397642ULL, 12320821611112279366ULL, 12370111120461367273ULL, 12410306233179192903ULL, 12430172920077300871ULL, 12510033344018143970ULL, 12560111331807167609ULL, 12620300909062507249ULL, 12712327122365584099ULL, 12813120201213924600ULL, 12941165650752604069ULL, 13001015450916236719ULL, 13002102112140524827ULL, 13009101051211529299ULL, 13011011201840674837ULL, 13012011200100272764ULL, 13017871597384507708ULL, 13022112682259429716ULL, 13035303725806214962ULL, 13061207162873518843ULL, 13101110211883417498ULL, 13102307620707874567ULL, 13110011112018854023ULL, 13111001400320058763ULL, 13111510321056866221ULL, 13115311279386832627ULL, 13121402212711908655ULL, 13132110718629054154ULL, 13156105146839315569ULL, 13200313020278778370ULL, 13210011012121171228ULL, 13213423249361668672ULL, 13240312112360909185ULL, 13304815634984262070ULL, 13328169412105586248ULL, 13411042429970294872ULL, 13502668079517138700ULL, 13610101015273120984ULL, 13742172294958738675ULL, 13955010105287823835ULL, 14001111914465436166ULL, 14005718153017034195ULL, 14011091130510814555ULL, 14015104231941588982ULL, 14024198940867158771ULL, 14057011815230816884ULL, 14100450036349198212ULL, 14102112146150632238ULL, 14110110210162382822ULL, 14111301341313317036ULL, 14120017321500977589ULL, 14131110100944863013ULL, 14170725499139830199ULL, 14206111220745099267ULL, 14221102113069094860ULL, 14306120201523498932ULL, 14401016831681598749ULL, 14504145142170066066ULL, 14702246022571246478ULL, 15000932060667308245ULL, 15006213005415560866ULL, 15011203461312037475ULL, 15021114160849623834ULL, 15064132587707205729ULL, 15101114121387175100ULL, 15110121126567543514ULL, 15113111030225503923ULL, 15131111101328059518ULL, 15200211165114008645ULL, 15215231836896581647ULL, 15311015083995691650ULL, 15420613121581116152ULL, 15701101229511434643ULL, 16001112151204909152ULL, 16010411810223887040ULL, 16020101072976056952ULL, 16060135644080345961ULL, 16101351068167771299ULL, 16111071307968405954ULL, 16121617114078184874ULL, 16183314443164332000ULL, 16221811218331501491ULL, 16330217942544948147ULL, 16570104242510786490ULL, 17001104101283642140ULL, 17011116072075965697ULL, 17033456472603589603ULL, 17101190410914354070ULL, 17111218216083481212ULL, 17133141250056037829ULL, 17211101251174495777ULL, 17321130784350135385ULL, 17641014337217993341ULL };

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> X;
  --X;
  if( X == 0 ) {
    cout << 8 << endl;
    exit( 0 );
  }
  int d = dict[ ( X - 1 ) / 1000000 ];
  int prev = d;
  for( int i = ( X - 1 ) / 1000000 * 1000000; i < X; ++i ) {
    d = prev;
    prev += F( d ) + G( d ) + 10;
  }
  cout << d << endl;
  return 0;
}