โจทย์ต้องการให้สร้างจำนวนเต็มบวกที่มีค่ามากที่สุด โดยที่ผลรวมของราคาเลขโดดแต่ละตัวจะต้องไม่เกินเงินที่มีอยู่ ในที่นี้กำหนดให้ $C_i$ หมายถึงราคาในการปักเลขโดด $i$ ($0 \leq i \leq 9$)

ก่อนอื่น เราจะพยายามปักให้ได้จำนวนหลักมากที่สุด สามารถทำได้โดยปักเลขโดดที่ราคาน้อยที่สุดเท่าที่ทำได้ (หากมีราคาเท่ากันหลายค่า ให้เลือกเลขโดดที่มีค่ามากกว่า) พร้อมคำนวณว่าเหลือเงินเท่าใด

ต่อมา ให้พิจารณาทีละหลักตั้งแต่หลักแรก (ด้านหน้าสุด) ไปยังหลักสุดท้าย แต่ละหลักเราจะทดลองเปลี่ยนให้เป็นเลข 9, 8, 7, ... ไล่ลงมา โดยจะต้องตรวจสอบว่าหากแล้วจะยังมีเงินพอหรือไม่ (หากเลขเดิมคือ $x$ และเลขใหม่คือ $y$ เราจะต้องเสียเงินเพิ่ม $C_y - C_x$ บาท) หากพอ เราจะเปลี่ยนเป็นเลขนั้นทันทีแล้วพิจารณาหลักถัดไป เพราะเราต้องการเลขที่มีค่ามากที่สุด

Implementation

ในภาษา C++:

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 110;

int p[10];
int ans[N];

int main() {
  int n;
  scanf("%d", &n);

  int mn = 1;
  for (int i = 1; i <= 9; ++i) {
    scanf("%d", &p[i]);
    if (p[i] <= p[mn])
      mn = i;
  }

  int cnt = 0;
  while (n - p[mn] >= 0) {
    n -= p[mn];
    ans[cnt++] = mn;
  }

  for (int i = 0; i < cnt; ++i) {
    for (int j = 9; j >= mn; --j) {
      if (n - (p[j] - p[mn]) >= 0) {
        n -= p[j] - p[mn];
        ans[i] = j;
        break;
      }
    }
  }

  for (int i = 0; i < cnt; ++i)
    printf("%d", ans[i]);

  return 0;
}