Problem:


Score : 400 points

Problem Statement

A positive integer X is said to be a lunlun number if and only if the following condition is satisfied:

In the base ten representation of X (without leading zeros), for every pair of two adjacent digits, the absolute difference of those digits is at most 1.

For example, 1234, 1, and 334 are lunlun numbers, while none of 31415, 119, or 13579 is.

You are given a positive integer K. Find the K-th smallest lunlun number.

Constraints

1 \leq K \leq 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

K

Output

Print the answer.

Sample Input 1

15

Sample Output 1

23

We will list the 15 smallest lunlun numbers in ascending order:

1,
2,
3,
4,
5,
6,
7,
8,
9,
10,
11,
12,
21,
22,
23.

Thus, the answer is 23.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

13

Sample Output 3

21

Sample Input 4

100000

Sample Output 4

3234566667

Note that the answer may not fit into the 32-bit signed integer type.



Sample input:
15


Sample output:
23

Submission status: Time Limit Exceeded

Solution code:
d={0: 0, 100: 878, 200: 4445, 300: 8788, 400: 21122, 500: 33322, 600: 45434, 700: 56776, 800: 76667, 900: 88888, 1000: 110111, 1100: 122345, 1200: 221122, 1300: 233322, 1400: 323234, 1500: 343211, 1600: 432332, 1700: 444444, 1800: 456556, 1900: 545676, 2000: 565566, 2100: 655543, 2200: 667655, 2300: 765432, 2400: 776767, 2500: 788989, 2600: 887765, 2700: 987777, 2800: 1001012, 2900: 1101111, 3000: 1122111, 3100: 1212233, 3200: 1232232, 3300: 2101234, 3400: 2122234, 3500: 2221010, 3600: 2233211, 3700: 2322345, 3800: 2334544, 3900: 3210122, 4000: 3223212, 4100: 3234555, 4200: 3332332, 4300: 3344444, 4400: 3434343, 4500: 3445677, 4600: 4321222, 4700: 4333344, 4800: 4345456, 4900: 4443211, 5000: 4454545, 5100: 4544443, 5200: 4556555, 5300: 4567889, 5400: 5443345, 5500: 5455543, 5600: 5545433, 5700: 5556767, 5800: 5654444, 5900: 5666556, 6000: 5677899, 6100: 6545667, 6200: 6565565, 6300: 6655456, 6400: 6667654, 6500: 6678999, 6600: 6776766, 6700: 6788988, 6800: 7665434, 6900: 7676777, 7000: 7766767, 7100: 7778889, 7200: 7877666, 7300: 7889987, 7400: 8767676, 7500: 8787667, 7600: 8877789, 7700: 8898789, 7800: 8998887, 7900: 9887656, 8000: 9987676, 8100: 10000121, 8200: 10101001, 8300: 10121223, 8400: 11010111, 8500: 11110123, 8600: 11123221, 8700: 11221212, 8800: 11233334, 8900: 12111123, 9000: 12123344, 9100: 12222122, 9200: 12234321, 9300: 12323455, 9400: 12343432, 9500: 21010010, 9600: 21110101, 9700: 21122343, 9800: 21221112, 9900: 21233234, 10000: 22111101, 10100: 22123322, 10200: 22222100, 10300: 22233443, 10400: 22323433, 10500: 22343332, 10600: 23211223, 10700: 23223444, 10800: 23321212, 10900: 23333334, 11000: 23345454, 11100: 23434567, 11200: 23454543, 11300: 32110010, 11400: 32122323, 11500: 32221100, 11600: 32233222, 11700: 32323212, 11800: 32334555, 11900: 33211001, 12000: 33223223, 12100: 33234566, 12200: 33332343, 12300: 33344455, 12400: 33434432, 12500: 33454322, 12600: 34321233, 12700: 34333433, 12800: 34345545, 12900: 34443222, 13000: 34454556, 13100: 34544454, 13200: 34556566, 13300: 43210000, 13400: 43222321, 13500: 43234434, 13600: 43332211, 13700: 43344323, 13800: 43433444, 13900: 43445556, 14000: 44321101, 14100: 44333223, 14200: 44344565, 14300: 44434456, 14400: 44454432, 14500: 44544322, 14600: 44555656, 14700: 44567776, 14800: 45443232, 14900: 45454566, 15000: 45544456, 15100: 45556654, 15200: 45654323, 15300: 45665665, 15400: 45677778, 15500: 54323432, 15600: 54343323, 15700: 54433222, 15800: 54444556, 15900: 54456676, 16000: 54554344, 16100: 54565678, 16200: 55433434, 16300: 55445554, 16400: 55543222, 16500: 55554556, 16600: 55566676, 16700: 55656567, 16800: 55676544, 16900: 56543456, 17000: 56555654, 17100: 56567766, 17200: 56665443, 17300: 56676778, 17400: 56766776, 17500: 56778898, 17600: 65433232, 17700: 65444566, 17800: 65456678, 17900: 65554432, 18000: 65566544, 18100: 65655665, 18200: 65667777, 18300: 66543332, 18400: 66555444, 18500: 66566778, 18600: 66656677, 18700: 66676654, 18800: 66766566, 18900: 66778766, 19000: 67654543, 19100: 67666655, 19200: 67678777, 19300: 67776545, 19400: 67788766, 19500: 67878888, 19600: 67899987, 19700: 76554445, 19800: 76566565, 19900: 76655678, 20000: 76667876, 20100: 76765567, 20200: 76777766, 20300: 77654322, 20400: 77665656, 20500: 77677777, 20600: 77767767, 20700: 77787766, 20800: 77877888, 20900: 77898888, 21000: 78767898, 21100: 78787889, 21200: 78878876, 21300: 78899888, 21400: 78999987, 21500: 87665556, 21600: 87677677, 21700: 87767667, 21800: 87787666, 21900: 87877788, 22000: 87898788, 22100: 88767876, 22200: 88787789, 22300: 88878776, 22400: 88898998, 22500: 88999878, 22600: 89887778, 22700: 89987876, 22800: 98765666, 22900: 98777787, 23000: 98876565, 23100: 98888778, 23200: 98988876, 23300: 99877776, 23400: 99898776, 23500: 99998788, 23600: 100012110, 23700: 100112122, 23800: 101000100, 23900: 101100112, 24000: 101121210, 24100: 101212111, 24200: 101232110, 24300: 110001112, 24400: 110101210, 24500: 110122210, 24600: 111011110, 24700: 111111122, 24800: 111123343, 24900: 111222121, 25000: 111233456, 25100: 112112110, 25200: 112210001, 25300: 112222322, 25400: 112234443, 25500: 112332212, 25600: 112344332, 25700: 121011001, 25800: 121111100, 25900: 121123321, 26000: 121221234, 26100: 121233434, 26200: 122111223, 26300: 122123444, 26400: 122222222, 26500: 122234343, 26600: 122332112, 26700: 122343454, 26800: 123212210, 26900: 123232123, 27000: 123322121, 27100: 123333456, 27200: 123345654, 27300: 123443323, 27400: 123455443, 27500: 210011001, 27600: 210111100, 27700: 210123321, 27800: 211012222, 27900: 211112234, 28000: 211211010, 28100: 211223232, 28200: 211234567, 28300: 212121011, 28400: 212211212, 28500: 212223433, 28600: 212321123, 28700: 212333323, 28800: 212345443, 28900: 221012122, 29000: 221112212, 29100: 221210112, 29200: 221223210, 29300: 221234545, 29400: 222112343, 29500: 222211112, 29600: 222223333, 29700: 222321101, 29800: 222333223, 29900: 222344565, 30000: 223221112, 30100: 223233234, 30200: 223323232, 30300: 223334567, 30400: 223432322, 30500: 223444434, 30600: 223456554, 30700: 232112122, 30800: 232210100, 30900: 232222334, 31000: 232234455, 31100: 232332232, 31200: 232344344, 31300: 233212322, 31400: 233232321, 31500: 233322233, 31600: 233334432, 31700: 233432101, 31800: 233443443, 31900: 233455555, 32000: 234323323, 32100: 234343222, 32200: 234432343, 32300: 234444455, 32400: 234456567, 32500: 234554321, 32600: 234565655, 32700: 321010012, 32800: 321110111, 32900: 321122345, 33000: 321221122, 33100: 321233322, 33200: 322111111, 33300: 322123332, 33400: 322222110, 33500: 322233445, 33600: 322323443, 33700: 322343334, 33800: 323211233, 33900: 323223454, 34000: 323321222, 34100: 323333344, 34200: 323345456, 34300: 323443211, 34400: 323454545, 34500: 332110012, 34600: 332122333, 34700: 332221110, 34800: 332233232, 34900: 332323222, 35000: 332334565, 35100: 333211011, 35200: 333223233, 35300: 333321000, 35400: 333332345, 35500: 333344543, 35600: 333434434, 35700: 333454332, 35800: 334322100, 35900: 334333443, 36000: 334345555, 36100: 334443232, 36200: 334454566, 36300: 334544456, 36400: 334556654, 36500: 343210010, 36600: 343222323, 36700: 343234444, 36800: 343332221, 36900: 343344333, 37000: 343433454, 37100: 343445566, 37200: 344321111, 37300: 344333233, 37400: 344344567, 37500: 344434544, 37600: 344454434, 37700: 344544332, 37800: 344555666, 37900: 344567778, 38000: 345443234, 38100: 345455432, 38200: 345544544, 38300: 345556656, 38400: 345654333, 38500: 345665667, 38600: 345677788, 38700: 432111233, 38800: 432123454, 38900: 432222232, 39000: 432234345, 39100: 432332122, 39200: 432343456, 39300: 433212212, 39400: 433232211, 39500: 433322123, 39600: 433334322, 39700: 433345656, 39800: 433443333, 39900: 433455445, 40000: 434323221, 40100: 434334556, 40200: 434432233, 40300: 434444345, 40400: 434456543, 40500: 434545655, 40600: 434565545, 40700: 443211223, 40800: 443223444, 40900: 443321212, 41000: 443333334, 41100: 443345454, 41200: 443434567, 41300: 443454543, 41400: 444322233, 41500: 444334432, 41600: 444432101, 41700: 444443443, 41800: 444455555, 41900: 444545445, 42000: 444556787, 42100: 445432321, 42200: 445444433, 42300: 445456545, 42400: 445545665, 42500: 445565555, 42600: 445655454, 42700: 445666788, 42800: 445678989, 42900: 454332334, 43000: 454344454, 43100: 454434345, 43200: 454454321, 43300: 454543433, 43400: 454555545, 43500: 454567665, 43600: 455434565, 43700: 455454455, 43800: 455544345, 43900: 455556543, 44000: 455567877, 44100: 455665554, 44200: 455677667, 44300: 456545443, 44400: 456556777, 44500: 456654454, 44600: 456666566, 44700: 456678766, 44800: 456767899, 44900: 456787898, 45000: 543221010, 45100: 543233211, 45200: 543322345, 45300: 543334544, 45400: 543432221, 45500: 543444333, 45600: 543455667, 45700: 544323443, 45800: 544343334, 45900: 544433233, 46000: 544444567, 46100: 544456765, 46200: 544554433, 46300: 544566545, 46400: 545433445, 46500: 545445565, 46600: 545543233, 46700: 545554567, 46800: 545566765, 46900: 545656656, 47000: 545676555, 47100: 554322123, 47200: 554334322, 47300: 554345656, 47400: 554443333, 47500: 554455445, 47600: 554544565, 47700: 554556677, 47800: 555432211, 47900: 555444323, 48000: 555455665, 48100: 555545555, 48200: 555565445, 48300: 555654566, 48400: 555666678, 48500: 555678878, 48600: 556554345, 48700: 556566543, 48800: 556655656, 48900: 556667776, 49000: 556765545, 49100: 556777666, 49200: 556789987, 49300: 565443343, 49400: 565455455, 49500: 565544567, 49600: 565556765, 49700: 565654434, 49800: 565666554, 49900: 565677889, 50000: 566545665, 50100: 566565555, 50200: 566655454, 50300: 566666788, 50400: 566678989, 50500: 566776678, 50600: 566788899, 50700: 567665432, 50800: 567676767, 50900: 567766765, 51000: 567778887, 51100: 567877656, 51200: 567889898, 51300: 654323322, 51400: 654343221, 51500: 654432334, 51600: 654444454, 51700: 654456566, 51800: 654545678, 51900: 654565654, 52000: 655433332, 52100: 655445444, 52200: 655456778, 52300: 655554454, 52400: 655566566, 52500: 655656543, 52600: 655667877, 52700: 656543432, 52800: 656555544, 52900: 656567656, 53000: 656656777, 53100: 656676676, 53200: 656766666, 53300: 656778788, 53400: 665432344, 53500: 665444456, 53600: 665456654, 53700: 665554322, 53800: 665565656, 53900: 665655555, 54000: 665667667, 54100: 666543222, 54200: 666554556, 54300: 666566676, 54400: 666656567, 54500: 666676544, 54600: 666765678, 54700: 666777877, 54800: 667654433, 54900: 667666545, 55000: 667677888, 55100: 667767878, 55200: 667787877, 55300: 667878778, 55400: 667899876, 55500: 676554343, 55600: 676565677, 55700: 676655654, 55800: 676667766, 55900: 676765543, 56000: 676777656, 56100: 676789898, 56200: 677665554, 56300: 677677667, 56400: 677767665, 56500: 677787656, 56600: 677877778, 56700: 677898778, 56800: 678767788, 56900: 678787787, 57000: 678878766, 57100: 678898988, 57200: 678999876, 57300: 765443233, 57400: 765454567, 57500: 765544543, 57600: 765556655, 57700: 765654332, 57800: 765665666, 57900: 765677787, 58000: 766545555, 58100: 766565445, 58200: 766654566, 58300: 766666678, 58400: 766678878, 58500: 766776654, 58600: 766788789, 58700: 767656766, 58800: 767676665, 58900: 767766655, 59000: 767778777, 59100: 767876776, 59200: 767888998, 59300: 776544556, 59400: 776556676, 59500: 776654345, 59600: 776666543, 59700: 776677878, 59800: 776767876, 59900: 776787789, 60000: 777656545, 60100: 777667887, 60200: 777765656, 60300: 777777777, 60400: 777876555, 60500: 777888776, 60600: 778766565, 60700: 778778765, 60800: 778876678, 60900: 778888899, 61000: 778988998, 61100: 787655667, 61200: 787667787, 61300: 787765556, 61400: 787777677, 61500: 787789998, 61600: 787887889, 61700: 788766543, 61800: 788777878, 61900: 788876656, 62000: 788888877, 62100: 788988889, 62200: 789877789, 62300: 789898789, 62400: 789998887, 62500: 876545667, 62600: 876565565, 62700: 876655456, 62800: 876667654, 62900: 876678999, 63000: 876776766, 63100: 876788988, 63200: 877665434, 63300: 877676777, 63400: 877766767, 63500: 877778889, 63600: 877877666, 63700: 877889987, 63800: 878767676, 63900: 878787667, 64000: 878877789, 64100: 878898789, 64200: 878998887, 64300: 887656778, 64400: 887676677, 64500: 887766667, 64600: 887778789, 64700: 887876788, 64800: 887889878, 64900: 888767654, 65000: 888778999, 65100: 888877767, 65200: 888898767, 65300: 888998787, 65400: 889878988, 65500: 889987654, 65600: 898765444, 65700: 898776787, 65800: 898789877, 65900: 898887777, 66000: 898987789, 66100: 899876776, 66200: 899888998, 66300: 899989878, 66400: 987656543, 66500: 987667877, 66600: 987765654, 66700: 987777767, 66800: 987876545, 66900: 987888766, 67000: 988766555, 67100: 988777898, 67200: 988876676, 67300: 988888889, 67400: 988988988, 67500: 989877887, 67600: 989898887, 67700: 989998899, 67800: 998776544, 67900: 998788765, 68000: 998878887, 68100: 998899899, 68200: 998999998, 68300: 999887889, 68400: 999988766, 68500: 1000001223, 68600: 1000110000, 68700: 1000122321, 68800: 1001011221, 68900: 1001111233, 69000: 1001123454, 69100: 1001222232, 69200: 1001234345, 69300: 1010012221, 69400: 1010112233, 69500: 1011001001, 69600: 1011101100, 69700: 1011122100, 69800: 1011212222, 69900: 1011232221, 70000: 1012101223, 70100: 1012122223, 70200: 1012212345, 70300: 1012232344, 70400: 1012322334, 70500: 1012334455, 70600: 1100000111, 70700: 1100100123, 70800: 1100121221, 70900: 1101010101, 71000: 1101110121, 71100: 1101123211, 71200: 1101221210, 71300: 1101233332, 71400: 1110011121, 71500: 1110111211, 71600: 1110123432, 71700: 1111012333, 71800: 1111112345, 71900: 1111211122, 72000: 1111223343, 72100: 1112100111, 72200: 1112121123, 72300: 1112212110, 72400: 1112232101, 72500: 1112321234, 72600: 1112333434, 72700: 1112345554, 72800: 1121012233, 72900: 1121112323, 73000: 1121211100, 73100: 1121223321, 73200: 1122100010, 73300: 1122121101, 73400: 1122211223, 73500: 1122223444, 73600: 1122321212, 73700: 1122333334, 73800: 1122345454, 73900: 1123221223, 74000: 1123233345, 74100: 1123323343, 74200: 1123343234, 74300: 1123433211, 74400: 1123444545, 74500: 1123456665, 74600: 1210012233, 74700: 1210112323, 74800: 1211001100, 74900: 1211101112, 75000: 1211122112, 75100: 1211212234, 75200: 1211232233, 75300: 1212110000, 75400: 1212122321, 75500: 1212221011, 75600: 1212233212, 75700: 1212323210, 75800: 1212334545, 75900: 1221000123, 76000: 1221101011, 76100: 1221121233, 76200: 1221212212, 76300: 1221232211, 76400: 1222101221, 76500: 1222122221, 76600: 1222212343, 76700: 1222232334, 76800: 1222322332, 76900: 1222334445, 77000: 1223210101, 77100: 1223222343, 77200: 1223234456, 77300: 1223332233, 77400: 1223344345, 77500: 1223434322, 77600: 1223445656, 77700: 1232100123, 77800: 1232121221, 77900: 1232212122, 78000: 1232232121, 78100: 1232322111, 78200: 1232333454, 78300: 1232345566, 78400: 1233222122, 78500: 1233234321, 78600: 1233323455, 78700: 1233343432, 78800: 1233433323, 78900: 1233445443, 79000: 1233456777, 79100: 1234332332, 79200: 1234344444, 79300: 1234434343, 79400: 1234445677, 79500: 1234543345, 79600: 1234555543, 79700: 1234567655, 79800: 2100012121, 79900: 2100112211, 80000: 2101000111, 80100: 2101100123, 80200: 2101121221, 80300: 2101212122, 80400: 2101232121, 80500: 2110001123, 80600: 2110101221, 80700: 2110122221, 80800: 2111011121, 80900: 2111111211, 81000: 2111123432, 81100: 2111222210, 81200: 2111234323, 81300: 2112112121, 81400: 2112210012, 81500: 2112222333, 81600: 2112234454, 81700: 2112332223, 81800: 2112344343, 81900: 2121011012, 82000: 2121111111, 82100: 2121123332, 82200: 2121222110, 82300: 2121233445, 82400: 2122111234, 82500: 2122123455, 82600: 2122222233, 82700: 2122234432, 82800: 2122332123, 82900: 2122344321, 83000: 2123212221, 83100: 2123232212, 83200: 2123322210, 83300: 2123334323, 83400: 2123345665, 83500: 2123443334, 83600: 2123455454, 83700: 2210011012, 83800: 2210111111, 83900: 2210123332, 84000: 2211012233, 84100: 2211112323, 84200: 2211211100, 84300: 2211223321, 84400: 2212100010, 84500: 2212121101, 84600: 2212211223, 84700: 2212223444, 84800: 2212321212, 84900: 2212333334, 85000: 2212345454, 85100: 2221012211, 85200: 2221112223, 85300: 2221210123, 85400: 2221223221, 85500: 2221234556, 85600: 2222121000, 85700: 2222211123, 85800: 2222223344, 85900: 2222321112, 86000: 2222333234, 86100: 2222345432, 86200: 2223221123, 86300: 2223233323, 86400: 2223323321, 86500: 2223343212, 86600: 2223432333, 86700: 2223444445, 86800: 2223456565, 86900: 2232112211, 87000: 2232210111, 87100: 2232222345, 87200: 2232234544, 87300: 2232332321, 87400: 2232344433, 87500: 2233212333, 87600: 2233232332, 87700: 2233322322, 87800: 2233334443, 87900: 2233432112, 88000: 2233443454, 88100: 2233455566, 88200: 2234323334, 88300: 2234343233, 88400: 2234433210, 88500: 2234444544, 88600: 2234456656, 88700: 2234554332, 88800: 2234565666, 88900: 2321010110, 89000: 2321110122, 89100: 2321123212, 89200: 2321221211, 89300: 2321233333, 89400: 2322111122, 89500: 2322123343, 89600: 2322222121, 89700: 2322233456, 89800: 2322323454, 89900: 2322343345, 90000: 2323212101, 90100: 2323232100, 90200: 2323321233, 90300: 2323333433, 90400: 2323345545, 90500: 2323443222, 90600: 2323454556, 90700: 2332110110, 90800: 2332122344, 90900: 2332221121, 91000: 2332233321, 91100: 2332323233, 91200: 2332343210, 91300: 2333211101, 91400: 2333223322, 91500: 2333321011, 91600: 2333333212, 91700: 2333344554, 91800: 2333434445, 91900: 2333454343, 92000: 2334322111, 92100: 2334333454, 92200: 2334345566, 92300: 2334443321, 92400: 2334455433, 92500: 2334544545, 92600: 2334556665, 92700: 2343210100, 92800: 2343222334, 92900: 2343234455, 93000: 2343332232, 93100: 2343344344, 93200: 2343434321, 93300: 2343445655, 93400: 2344321122, 93500: 2344333322, 93600: 2344345434, 93700: 2344434555, 93800: 2344454445, 93900: 2344544343, 94000: 2344555677, 94100: 2344567789, 94200: 2345443323, 94300: 2345455443, 94400: 2345544555, 94500: 2345556667, 94600: 2345654344, 94700: 2345665678, 94800: 2345677877, 94900: 3210012101, 95000: 3210112121, 95100: 3211000012, 95200: 3211100111, 95300: 3211121123, 95400: 3211212110, 95500: 3211232101, 95600: 3212101111, 95700: 3212122111, 95800: 3212212233, 95900: 3212232232, 96000: 3212322222, 96100: 3212334343, 96200: 3212345677, 96300: 3221100010, 96400: 3221121101, 96500: 3221211223, 96600: 3221223444, 96700: 3222101010, 96800: 3222121232, 96900: 3222212211, 97000: 3222232210, 97100: 3222322122, 97200: 3222334321, 97300: 3222345655, 97400: 3223222211, 97500: 3223234332, 97600: 3223332101, 97700: 3223343443, 97800: 3223433334, 97900: 3223445454, 98000: 3223456788, 98100: 3232121010, 98200: 3232211211, 98300: 3232223432, 98400: 3232321122, 98500: 3232333322, 98600: 3232345434, 98700: 3233221211, 98800: 3233233333, 98900: 3233323323, 99000: 3233343222, 99100: 3233432343, 99200: 3233444455, 99300: 3233456567, 99400: 3234332122, 99500: 3234343456, 99600: 3234433433, 99700: 3234445545, 99800: 3234543221, 99900: 3234554555,100000:3234566667}


def runrun(n):
    n=str(n)
    for i in range(len(n)-1):
        if abs(int(n[i])-int(n[i+1]))>1:
            return False
    return True

K=int(input())
K+=1

sep=1000

i=d[(K//sep)*sep]
count=(K//sep)*sep
while True:
    if count==K:
        break
    if runrun(i):
        count+=1
    i+=1

print(i-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    K = int(input())

    lunlun_number_memo = {}

    def is_lunlun(str_n):
        while True:
            if lunlun_number_memo.get(str_n):
                return True
            elif len(str_n) == 1:
                return True
            else:
                if abs(int(str_n[0]) - int(str_n[1])) <= 1:
                    str_n = str_n[1:]
                else:
                    return False


    lunlun_number_count = 0
    i = 0
    while lunlun_number_count < K:
        i += 1
        if is_lunlun(str(i)):
            lunlun_number_memo[str(i)] = True
            lunlun_number_count += 1
            # print(i)
            # print(lunlun_number_count)
            # print("running")

    print(i)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
K = int(input())

count = 9

i = 10
while True:
    if K<=9:
        ans = K
        break
    
    for j in range(1,len(str(i))):
        num1 = str(i)[j-1]
        num2 = str(i)[j]

        #print(j, len(str(i)))

        if abs(int(num1)-int(num2))>1:
            break

        if j == len(str(i))-1:
            count +=1
           # print(i)

    if count == K:
        ans = i
        break
    else:
        i+=1
   

print(ans)

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
i = 1 #数回す用
c = 0 #ルンルン数カウント

if k > 13000:
    i = 34454557
    c = 13000

while c < k:
  j = str(i)
  if i < 13: #13未満なら
    c = c + 1 #ルンルン数
    #print(c, i)
  else: #それ以外なら
    x = 0
    for n in range(len(j)-1): #ルンルン数判定を行う
      if abs(int(j[n]) - int(j[n+1])) > 1:#桁の差が1より大きかったら
        x = 1
        break
    if x == 0:
      c = c + 1
      #print(c, i)
  i = i + 1 #iに1を足す

print(i-1)

Submission status: Time Limit Exceeded

Solution code:
K = int(input())

def is_runrun(N,bool_runrun):  
    s = str(N)
    s_array = list(map(int, s))  
    
    if(len(s_array)==1):
        return bool_runrun
    
    for i in range(len(s_array)-1):
        diff = s_array[i] - s_array[i+1]
        if not (diff==-1 or diff ==1 or diff ==0):
            bool_runrun = False
            return bool_runrun
    return bool_runrun

count = 0
i = 0
while(count<=K-1):
    i += 1
    
    if(is_runrun(i,bool_runrun = True)):
        count += 1

print(i)

Submission status: Time Limit Exceeded

Solution code:
K = int(input())
p = [1,2,3,4,5,6,7,8,9]
q = 1
t = 10
r = 0
while t <= 3234566667 and len(p) < K+1:
        q = 1
        r = 0
        a = list(str(t))
        for i in range(len(a)):
            a[i] = int(a[i])
        while r < len(a)-1:
            if abs(a[r] - a[r+1]) <= 1:
                q = q*1
                r = r + 1
            else:
                q = q*0
                if a[r] < a[r+1]:
                    a[r] = a[r] + 1
                    for i in range(r+1,len(a)):
                        a[i] = 0
                    Tlist = ''.join(map(str, a))
                    t = int(Tlist)
                    break 
                else:
                    t = t + 1
                    r = r + 1
        if q == 1:
            p.append(t)
            t = t + 1
print(p[K-1])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())


def check(a):
    s = str(a)
    if len(s) == 1:
        return True
    
    for i in range(1, len(s)):
        if abs(int(s[i-1]) - int(s[i])) > 1:
            return False
    return True
    
def solve(N):
    m = 10**5
    ct = 0
    i = 1
    while True:
        if check(i):
            ct += 1
            if ct == N:
                return i
        i+=1

print(solve(N))

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
num = 10


def is_lala(num):
    flg = True
    _num = str(num)
    for i in range(len(_num) - 1):
        if 1 < abs(int(_num[i]) - int(_num[i + 1])):
            flg = False
            break
    if flg:
        return num


while len(arr) < k:
    if is_lala(num):
        arr.append(num)
    num += 1

ans = k if k < 10 else arr[-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
d={0: 0, 1000: 110111, 2000: 565566, 3000: 1122111, 4000: 3223212, 5000: 4454545, 6000: 5677899, 7000: 7766767, 8000: 9987676, 9000: 12123344, 10000: 22111101, 11000: 23345454, 12000: 33223223, 13000: 34454556, 14000: 44321101, 15000: 45544456, 16000: 54554344, 17000: 56555654, 18000: 65566544, 19000: 67654543, 20000: 76667876, 21000: 78767898, 22000: 87898788, 23000: 98876565, 24000: 101121210, 25000: 111233456, 26000: 121221234, 27000: 123322121, 28000: 211211010, 29000: 221112212, 30000: 223221112, 31000: 232234455, 32000: 234323323, 33000: 321221122, 34000: 323321222, 35000: 332334565, 36000: 334345555, 37000: 343433454, 38000: 345443234, 39000: 432234345, 40000: 434323221, 41000: 443333334, 42000: 444556787, 43000: 454344454, 44000: 455567877, 45000: 543221010, 46000: 544444567, 47000: 545676555, 48000: 555455665, 49000: 556765545, 50000: 566545665, 51000: 567778887, 52000: 655433332, 53000: 656656777, 54000: 665667667, 55000: 667677888, 56000: 676777656, 57000: 678878766, 58000: 766545555, 59000: 767778777, 60000: 777656545, 61000: 778988998, 62000: 788888877, 63000: 876776766, 64000: 878877789, 65000: 888778999, 66000: 898987789, 67000: 988766555, 68000: 998878887, 69000: 1001123454, 70000: 1012101223, 71000: 1101110121, 72000: 1111223343, 73000: 1121211100, 74000: 1123233345, 75000: 1211122112, 76000: 1221101011, 77000: 1223210101, 78000: 1232232121, 79000: 1233456777, 80000: 2101000111, 81000: 2111123432, 82000: 2121111111, 83000: 2123212221, 84000: 2211012233, 85000: 2212345454, 86000: 2222333234, 87000: 2232210111, 88000: 2233443454, 89000: 2321110122, 90000: 2323212101, 91000: 2332233321, 92000: 2334322111, 93000: 2343332232, 94000: 2344555677, 95000: 3210112121, 96000: 3212322222, 97000: 3222232210, 98000: 3223456788, 99000: 3233343222,100000:3234566667}


def runrun(n):
    n=str(n)
    for i in range(len(n)-1):
        if abs(int(n[i])-int(n[i+1]))>1:
            return False
    return True

K=int(input())
K+=1

sep=1000

i=d[(K//sep)*sep]
count=(K//sep)*sep
while True:
    if count==K:
        break
    if runrun(i):
        count+=1
    i+=1

print(i-1)

Submission status: Time Limit Exceeded

Solution code:
# coding : utf-8

s = input()

digit = len(s)
K = int(s)

count = 0

if digit==1:
    count=0
    x=0
elif digit==2:
    count=9
    x=9
elif digit==3:
    count=35
    x=99
elif digit==4:
    count=110
    x=999
elif digit==5:
    count=326
    x=9999
else:
   count = K
   x = 3234566667
    
while count != K:
    x = x+1
    s = str(x)
    s_list = [int(s_i) for s_i in s]
    flag = 0
    for i in range(len(s_list)-1):
        if( abs(s_list[i]-s_list[i+1]) > 1 ):
            flag = 1
            break
    if(flag == 0):
        count+=1
        
print(x)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    K = int(input())

    cnt = 0
    X = 1
    while cnt<K:
        if X<=9:
            # print(X)
            cnt += 1
        else:
            ok = True
            Xstr = str(X)
            for i in range(len(Xstr)-1):
                if abs(int(Xstr[i])-int(Xstr[i+1]))>1:
                    ok = False
            if ok:
                # print(X)
                cnt += 1
        X += 1
    print(X-1)

# 32 33 34 43 44 45 87 88 89 98 99 
# 100 101 110 111 112 121 122 123
# 210 211 212 221 222 223 232 233 234
# 321 322 323 332 333 334 343 344 345
# 876 877 878 887 888 889 898 899 
# 987 988 989 998 999

# 9
# 26 (3*9-1)
# 75 (6*9+21)
    # ans = []
    # def dfs(n):
    #     if len(ans)==K:
    #         ans.append(n)
    #     else:

    #         last = int(n[-1])
    #         for i in range(last-1, last, last+1):
    #             if 0<=i<10:
    #                 dfs(n+[i])
    # dfs('0')
    # print(ans)
    # print(ans[K-1])

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
K = int(input())

def runrunConfirm(num):
    flag=True
    str_num=str(num)
    strlen=len(str_num)
    if strlen==1:
        return True

    for i in range(strlen):
        if i==0:
            tmp=int(str_num[i])-int(str_num[i+1])
            if abs(tmp)>1:
                flag=False
                break
        elif i==len(str_num)-1:
            tmp=int(str_num[i-1])-int(str_num[i])
            if abs(tmp)>1:
                flag=False
                break
        else:
            tmp=int(str_num[i])-int(str_num[i+1])
            if abs(tmp)>1:
                flag=False
                break
            tmp=int(str_num[i-1])-int(str_num[i])
            if abs(tmp)>1:
                flag=False
                break
    return flag

# print(runrunConfirm(K))

number=1
runrunlist=[]
while True:
    if runrunConfirm(number):
        runrunlist.append(number)
    if len(runrunlist)==K:
        print(runrunlist[K-1])
        exit()
    number+=1

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
a = list(map(str, list(range(1, 10))))
ans = a + []
illist = []
for i in range(10):
    if i == 0:
        illist.append(["0","1"])
    elif i == 9:
        illist.append(["8","9"])
    else:
        illist.append([str(i-1),str(i),str(i+1)])
while len(ans) < k:
    b = []
    for i in a:
        if i == "323456667":
            break
        intil = int(i[-1])
        c = [i + j for j in illist[intil]]
        b = b + c
    a = b
    ans = ans + b

print(ans[k-1])

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
def judge_Lunlun(x):
    if (x in list(range(12+1))):return True
    x_str = str(x)
    tmp_rs = []
    lunlun_js = [ abs(int(x_str[i]) - int(x_str[i+1])) for i in range(len(x_str)-1)]
    return sum(list(map(lambda x:True if x<=1 else False, lunlun_js))) == len(lunlun_js)

lunlun_numbers = []
n = 1
while len(lunlun_numbers) != k:
    if(judge_Lunlun(n)):
        lunlun_numbers.append(n)
    n += 1
print(lunlun_numbers[-1])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

K = int(stdin.readline())

if K < 50000:
    count = 0
    for _ in range(1, 3234566667):
        i = str(_)
        L = len(i)
        for j in range(1, L):
            if abs(ord(i[j]) - ord(i[j - 1])) > 1:
                break
        else:
            count += 1
            if count == K:
                print(_)
                quit()
else:
    count = 100001
    for _ in range(1, 3234566668)[::-1]:
        i = str(_)
        L = len(i)
        for j in range(1, L):
            if abs(ord(i[j]) - ord(i[j - 1])) > 1:
                break
        else:
            count -= 1
            if count == K:
                print(_)
                quit()

Submission status: Time Limit Exceeded

Solution code:
d={0: 0, 10000: 22111101, 20000: 76667876, 30000: 223221112, 40000: 434323221, 50000: 566545665, 60000: 777656545, 70000: 1012101223, 80000: 2101000111, 90000: 2323212101, 100000:3234566667}


def runrun(n):
    n=str(n)
    for i in range(len(n)-1):
        if abs(int(n[i])-int(n[i+1]))>1:
            return False
    return True

K=int(input())
K+=1

i=d[(K//10000)*10000]
count=(K//10000)*10000
while True:
    if count==K:
        break
    if runrun(i):
        count+=1
    i+=1

print(i-1)

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
ans = [str(i) for i in range(1,10)]
c = 0
while len(ans)!=k:
    now = ans[c]
    t = int(now[-1])
    if t != 0:
        ans.append(str(now) +str(t-1))

    ans.append(str(now) +str(now)[-1])

    if t != 9:
        ans.append(str(now) +str(t+1))

    c += 1
print(ans[k-1])

Submission status: Time Limit Exceeded

Solution code:
K=int(input())
A=[0]*K
i=0
j=1
while i<K:
    if j<=9:
        A[i]=j
        i+=1
    else:
        j=str(j)
        l=0
        while l+1<=len(j):
            if l+1==len(j):
                A[i]=int(j)
                i+=1
                j=int(j)
                break
            elif int(j[l+1])-1<=int(j[l])<=int(j[l+1])+1:
                l+=1
            else:
                j=int(j)
                break
    j+=1
print(A[K-1])