UVa12172

UVa12172
smallestはDP
largestは貪欲

// Uva12172
#include <iostream>
#include <algorithm>

using namespace std;

string mn[101];
string mx[101];

void make_max(void)
{
  for (int i = 2; i < 101; ++i) {
    int n = i;
    while (n) {
      if (n == 3) {
        n -= 3;
        mx[i] = "7" + mx[i];
      } else {
        n -= 2;
        mx[i] = "1" + mx[i];
      }    
    }
  }
  return ;
}

string ret_min(string a, string b)
{
  if (a.size() != b.size()) {
    return a.size() < b.size() ? a : b;
  }
  return a < b ? a : b;
}

void make_min(void)
{
  fill(mn, mn + 101, string(60, '9'));
  mn[0] = "";

  const int C = 11;
  const char c[C] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
  const int cost[C] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

  for (int m = 0; m < 101; ++m) {
    for (int i = 0; i < C; ++i) {
      if (m + cost[i] < 101) {
        if (mn[m] != "0") {
          mn[m + cost[i]] = ret_min(mn[m + cost[i]], mn[m] + c[i]);
          if (c[i] != '0') {
            mn[m + cost[i]] = ret_min(mn[m + cost[i]], c[i] + mn[m]);
          }
        } 
      }
    }
  } 
  mn[6] = "6";
  return ;
}

int main(void)
{
  make_max();
  make_min();
  
  int tc, n;
  cin >> tc;
  while (tc--) {
    cin >> n;    
    cout << mn[n] << ' ' << mx[n] << endl;
  }
  return 0;
}