Задача
Один из способов мошенничества, разработанных О. Бендером, заключался в следующем. Он вырезал полоску бумаги, содержащую несколько цифр из суммы чека (можно вырезать и крайние цифры), разрезал ее на две части, переставлял эти две части местами и аккуратно подклеивал обратно. Напишите программу, определяющую максимальное число, которое может быть получено в результате указанной манипуляции.
Входные данные
Во входном файле в первой строке содержится одно целое положительное число не более чем из $100$ цифр.
Выходные данные
В выходной файл вывести одно число – максимальное число, которое можно получить в результате указанной манипуляции, или исходное число, если увеличить число невозможно.
Тесты
| Входные данные | Выходные данные |
| $123321$ | $332121$ |
| $7888778888878888788878878777887$ | $8888878888788878887778878777887$ |
| $1091$ | $9100$ |
| $26364$ | $64263$ |
| $98765$ | $98765$ |
Код программы
|
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 |
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException{ BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); String s = bufferedReader.readLine(); String maxS = s; int start = s.length() - 1; boolean found = false; for (int i = 0; i < s.length() && !found; i++) { for (int j = i; j < s.length() && !found; j++) { if (s.charAt(j) > s.charAt(i)) { start = i; found = true; } } } for (int j = start + 1; j < s.length(); j++) { StringBuilder curMax = new StringBuilder(s); if (s.charAt(j) >= s.charAt(start)) { for (int k = j; k < s.length(); k++) { curMax.insert(start + k - j, s.charAt(k)); curMax.delete(k + 1, k + 2); String curMaxString = curMax.toString(); if (curMaxString.compareTo(maxS) > 0) { maxS = curMaxString; } } } } System.out.println(maxS); } } |
Решение задачи
Пусть заданы два числа: $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
Код решения на Ideone. String