Я сделал программу для решения этой проблемы из ACM.
Спички являются идеальными инструментами для представления чисел.Обычный способ представления десятичных десятичных цифр с помощью спичек заключается в следующем:
Это идентично отображению чисел на обычном будильнике.С заданным количеством спичек вы можете генерировать широкий диапазон чисел.Нам интересно, какие самые маленькие и самые большие числа могут быть созданы с использованием всех ваших спичек.
Ввод
В первой строке одно положительное число: количество тестовых случаев, самое большее 100.После этого для каждого теста:
Одна строка с целым числом n (2 ≤ n ≤ 100): количество спичек у вас есть.Выходные данные
Для каждого теста:
Одна строка с наименьшим и наибольшим числом, которое вы можете создать, разделенные одним пробелом.Оба числа должны быть положительными и не содержать начальных нулей.Пример ввода
4 3 6 7 15 Пример вывода
7 7 6 111 8 711 108 7111111
Проблема в том, что его решение слишком медленное для100 спичек.Дерево поиска слишком велико, чтобы его можно было обработать.
Вот результаты за первые 10:
2: 1 1
3: 7 7
4: 4 11
5: 2 71
6: 6 111
7: 8 711
8: 10 1111
9: 18 7111
10: 22 11111
Шаблон для максимумов прост, но я не вижу ярлыка для минимумов.Может кто-нибудь предложить лучший способ решить эту проблему?Вот код, который я использовал:
#include <iostream>
#include <string>
using namespace std;
#define MAX 20 //should be 100
//match[i] contains number of matches needed to form i
int match[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
string mi[MAX+1], ma[MAX+1];
char curr[MAX+1] = "";
//compare numbers saved as strings
int mycmp(string s1, string s2)
{
int n = (int)s1.length();
int m = (int)s2.length();
if (n != m)
return n - m;
else
return s1.compare(s2);
}
//i is the current digit, used are the number of matchsticks so far
void fill(int i, int used)
{
//check for smaller and bigger values
if (mycmp(curr, mi[used]) < 0) mi[used] = curr;
if (mycmp(curr, ma[used]) > 0) ma[used] = curr;
//recurse further, don't start numbers with a zero
for (int a = i ? '0' : '1'; a <= '9'; a++) {
int next = used + match[a-'0'];
if (next <= MAX) {
curr[i] = a;
curr[i+1] = '\0';
fill(i + 1, next);
}
}
}
int main()
{
//initialise
for (int i = 0; i <= MAX; i++) {
mi[i] = string(MAX, '9');
ma[i] = "0";
}
//precalculate the values
fill(0, 0);
int n;
cin >> n;
//print those that were asked
while (n--) {
int num;
cin >> num;
cout << mi[num] << " " << ma[num] << endl;
}
return 0;
}
РЕДАКТИРОВАТЬ : я закончил с использованием решения динамического программирования.Я пробовал это с dp раньше, но я возился с двумерным массивом состояний.Решения здесь намного лучше.Спасибо!