Задача
Один из способов мошенничества, разработанных О. Бендером, заключался в следующем. Он вырезал полоску бумаги, содержащую несколько цифр из суммы чека (можно вырезать и крайние цифры), разрезал ее на две части, переставлял эти две части местами и аккуратно подклеивал обратно. Напишите программу, определяющую максимальное число, которое может быть получено в результате указанной манипуляции.
Входные данные
Во входном файле в первой строке содержится одно целое положительное число не более чем из $100$ цифр.
Выходные данные
В выходной файл вывести одно число – максимальное число, которое можно получить в результате указанной манипуляции, или исходное число, если увеличить число невозможно.
Тесты
| Входные данные | Выходные данные |
| $123321$ | $332121$ |
| $7888778888878888788878878777887$ | $8888878888788878887778878777887$ |
| $1091$ | $9100$ |
| $26364$ | $64263$ |
| $98765$ | $98765$ |
Код программы
String
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include <iostream> using namespace std; int main() { string s; cin >> s; string maxS = s; int start = s.size() - 1; bool found = false; for(int i = 0; i < s.size() and !found; i++){ for(int j = i; j < s.size() and !found; j++){ if(s[j] > s[i]){ start = i; found = true; } } } for(int j = start + 1; j < s.size(); j++){ if(s[j] >= s[start]) { string curMax = s; for (int k = j; k < s.size(); k++) { curMax.insert(start + k - j, 1, s[k]); curMax.erase(k + 1, 1); maxS = max(curMax, maxS); } } } cout << maxS; return 0; } |
C-String
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <iostream> #include <cstring> using namespace std; const int MAX_LENGTH = 101; int main() { char s[MAX_LENGTH]; cin >> s; char maxS[MAX_LENGTH]; strcpy(maxS, s); int size = strlen(s); int start = size - 1; bool found = false; for(int i = 0; i < size and !found; i++){ for(int j = i; j < size and !found; j++){ if(s[j] > s[i]){ start = i; found = true; } } } for(int j = start + 1; j < size; j++){ if(s[j] >= s[start]) { char curMax[MAX_LENGTH]; strcpy(curMax, s); for (int k = j; k < size; k++) { char temp = s[k]; for(int i = k; i > start + k - j; i--){ curMax[i] = curMax[i - 1]; } curMax[start + k - j] = temp; if(strncmp(curMax, maxS, size) > 0){ strcpy(maxS, curMax); } } } } cout << maxS; return 0; } |
Решение задачи
Пусть заданы два числа: $a = \overline{a_1a_2 \ldots a_k},\ b = \overline{b_1b_2 \ldots b_k}$. Тогда $a > b \Leftrightarrow \exists i: \ \forall j < i \ a_j = b_j \ \wedge \ a_i = b_i$. Отсюда получаем необходимое условие получения максимального числа при перестановке в записи числа $a$ групп цифр $\overline{a_ia_{i+1} \ldots a_l}$ и $\overline{a_ja_{j+1} \ldots a_m} \ l<j$ местами: $i = \min_{1 < s < k} s: \ \exists t>s: \ a_t \gt a_s$. Если такое $i$ существует, то далее мы делаем перебор по всем возможным перестановкам, таким что первая группа чисел начинается с индекса $i$ и таким образом находим максимально возможное число. В противном случае данное число уже является максимальным.
Ссылки
Условие задачи на e-olymp
Решение на e-olymp. String
Решение на e-olymp. C-String
Код решения на Ideone. String
Код решения на Ideone. C-String