[C/C++] BOJ #1038 - Decreasing Number

This problem is one I solved back when I was working through a lot of Baekjoon problems. At that time, I used to solve around 20 problems a day, but now the difficulty level of the problems has increased, and they require more thinking, so I can’t solve as many anymore.

A “decreasing number” is a number where the digits strictly decrease, such as 31, 7543, or 941. The goal is to list all such numbers in increasing order and output the number at a specific position. If you read the problem carefully, you’ll notice there’s a hidden trap. This problem is classified as a Gold IV level problem.

---

Objective

The goal of this problem is to find the N-th decreasing number. A decreasing number is a number whose digits are strictly decreasing from left to right. That means each digit in the number is smaller than the one before it. For example, 321, 950, and 41 are all decreasing numbers. However, 332, 123, or 9000 are not decreasing numbers.

The decreasing numbers are ordered in increasing numerical order, and you are given an integer N (0 ≤ N ≤ 1022). You have to output the N-th number in that ordered list. If N is too large and there are not that many decreasing numbers, you should print -1.

---

If you catch the trick in this problem, you’ll realize that the actual number of required decreasing numbers is 1022.

The total number of decreasing numbers is the sum of combinations of choosing k digits out of 10:

$$\sum _{k=1}^{10}(\genfrac{}{}{0ex}{}{10}{k})$$

This gives a total of 1023 decreasing numbers. If you were to sum combinations from 0 to 10, the total would be 1024, but selecting zero digits does not constitute a number. For example, if you chose 4 digits: 0, 3, 7, 9 — the only decreasing number you can make from these is 9730. So, by using combinations, you can determine the total number of valid decreasing numbers.

If you want to solve this problem in a textbook-style approach, you can progressively subtract from the total starting from combinations where one digit is selected. Since the total count is just 1023, it’s safe to use a simple combination function without worrying about overflow.

As for me, I used a little trick to solve this. Since the problem setter gave a number range up to 1,000,000 to mislead you, I stored all 1023 decreasing numbers directly in an array. After all, storing 1023 numbers only takes about 4KB of memory.

---

decreasing numbers

So the final code I wrote is based on this method. Please just use the code as a reference.

//----------------------------------------------------------
//    baekjoon #1038 - Decreasing Number
//    - by Aubrey Choi
//    - created at 2019-11-08
//----------------------------------------------------------
#include <stdio.h>
/*
#include <algorithm>
bool cmp(int a, int b)
{
    int ac=0, bc=0;
    for(int i=0;i<10;i++) ac+=(a>>i)&1,bc+=(b>>i)&1;
    if(ac==bc) return a<b; return ac<bc;
}
void gen()
{
    int v[1023];
    for(int i=0;i<1023;i++) v[i]=i+1;
    std::sort(v,v+1023,cmp);
    for(int i=0;i<1023;i++) { printf("%d,", v[i]); if(i%16==15) putchar('\n'); }
}
*/

const int d[]= { 1,2,4,8,16,32,64,128,256,512,3,5,6,9,10,12,
    17,18,20,24,33,34,36,40,48,65,66,68,72,80,96,129,
    130,132,136,144,160,192,257,258,260,264,272,288,320,384,513,514,
    516,520,528,544,576,640,768,7,11,13,14,19,21,22,25,26,
    28,35,37,38,41,42,44,49,50,52,56,67,69,70,73,74,
    76,81,82,84,88,97,98,100,104,112,131,133,134,137,138,140,
    145,146,148,152,161,162,164,168,176,193,194,196,200,208,224,259,
    261,262,265,266,268,273,274,276,280,289,290,292,296,304,321,322,
    324,328,336,352,385,386,388,392,400,416,448,515,517,518,521,522,
    524,529,530,532,536,545,546,548,552,560,577,578,580,584,592,608,
    641,642,644,648,656,672,704,769,770,772,776,784,800,832,896,15,
    23,27,29,30,39,43,45,46,51,53,54,57,58,60,71,75,
    77,78,83,85,86,89,90,92,99,101,102,105,106,108,113,114,
    116,120,135,139,141,142,147,149,150,153,154,156,163,165,166,169,
    170,172,177,178,180,184,195,197,198,201,202,204,209,210,212,216,
    225,226,228,232,240,263,267,269,270,275,277,278,281,282,284,291,
    293,294,297,298,300,305,306,308,312,323,325,326,329,330,332,337,
    338,340,344,353,354,356,360,368,387,389,390,393,394,396,401,402,
    404,408,417,418,420,424,432,449,450,452,456,464,480,519,523,525,
    526,531,533,534,537,538,540,547,549,550,553,554,556,561,562,564,
    568,579,581,582,585,586,588,593,594,596,600,609,610,612,616,624,
    643,645,646,649,650,652,657,658,660,664,673,674,676,680,688,705,
    706,708,712,720,736,771,773,774,777,778,780,785,786,788,792,801,
    802,804,808,816,833,834,836,840,848,864,897,898,900,904,912,928,
    960,31,47,55,59,61,62,79,87,91,93,94,103,107,109,110,
    115,117,118,121,122,124,143,151,155,157,158,167,171,173,174,179,
    181,182,185,186,188,199,203,205,206,211,213,214,217,218,220,227,
    229,230,233,234,236,241,242,244,248,271,279,283,285,286,295,299,
    301,302,307,309,310,313,314,316,327,331,333,334,339,341,342,345,
    346,348,355,357,358,361,362,364,369,370,372,376,391,395,397,398,
    403,405,406,409,410,412,419,421,422,425,426,428,433,434,436,440,
    451,453,454,457,458,460,465,466,468,472,481,482,484,488,496,527,
    535,539,541,542,551,555,557,558,563,565,566,569,570,572,583,587,
    589,590,595,597,598,601,602,604,611,613,614,617,618,620,625,626,
    628,632,647,651,653,654,659,661,662,665,666,668,675,677,678,681,
    682,684,689,690,692,696,707,709,710,713,714,716,721,722,724,728,
    737,738,740,744,752,775,779,781,782,787,789,790,793,794,796,803,
    805,806,809,810,812,817,818,820,824,835,837,838,841,842,844,849,
    850,852,856,865,866,868,872,880,899,901,902,905,906,908,913,914,
    916,920,929,930,932,936,944,961,962,964,968,976,992,63,95,111,
    119,123,125,126,159,175,183,187,189,190,207,215,219,221,222,231,
    235,237,238,243,245,246,249,250,252,287,303,311,315,317,318,335,
    343,347,349,350,359,363,365,366,371,373,374,377,378,380,399,407,
    411,413,414,423,427,429,430,435,437,438,441,442,444,455,459,461,
    462,467,469,470,473,474,476,483,485,486,489,490,492,497,498,500,
    504,543,559,567,571,573,574,591,599,603,605,606,615,619,621,622,
    627,629,630,633,634,636,655,663,667,669,670,679,683,685,686,691,
    693,694,697,698,700,711,715,717,718,723,725,726,729,730,732,739,
    741,742,745,746,748,753,754,756,760,783,791,795,797,798,807,811,
    813,814,819,821,822,825,826,828,839,843,845,846,851,853,854,857,
    858,860,867,869,870,873,874,876,881,882,884,888,903,907,909,910,
    915,917,918,921,922,924,931,933,934,937,938,940,945,946,948,952,
    963,965,966,969,970,972,977,978,980,984,993,994,996,1000,1008,127,
    191,223,239,247,251,253,254,319,351,367,375,379,381,382,415,431,
    439,443,445,446,463,471,475,477,478,487,491,493,494,499,501,502,
    505,506,508,575,607,623,631,635,637,638,671,687,695,699,701,702,
    719,727,731,733,734,743,747,749,750,755,757,758,761,762,764,799,
    815,823,827,829,830,847,855,859,861,862,871,875,877,878,883,885,
    886,889,890,892,911,919,923,925,926,935,939,941,942,947,949,950,
    953,954,956,967,971,973,974,979,981,982,985,986,988,995,997,998,
    1001,1002,1004,1009,1010,1012,1016,255,383,447,479,495,503,507,509,510,
    639,703,735,751,759,763,765,766,831,863,879,887,891,893,894,927,
    943,951,955,957,958,975,983,987,989,990,999,1003,1005,1006,1011,1013,
    1014,1017,1018,1020,511,767,895,959,991,1007,1015,1019,1021,1022,1023 };
int main()
{
    int n;
    scanf("%d",&n);
    if(n>=1023) { puts("-1"); return 0; }
    for(int i=9;i>=0;i--) if((d[n]>>i)&1) putchar(i+'0'); putchar('\n');
}