5 / 5 / 1
Регистрация: 21.02.2019
Сообщений: 38
|
|
1 | |
Получить счастливый билет перестановками22.10.2020, 09:49. Показов 1382. Ответов 2
Метки нет (Все метки)
Здравствуйте!
Решаю задачи на тему переборных алгоритмов и разветвленной рекурсии. Вот условие одной из задач, которая поставила меня в затруднение: Счастливым билетиком называется такой билетик, у которого сумма цифр левой половины номера совпадает с суммой цифр правой половины. Например, билетик с номером 447294 Появилась мысль на счет того, чтобы отсортировать массив цифр и разбить его на пары от начала до конца, в каждой из которых посчитать разность, далее также отсортировать массив разностей и снова посчитать разности и т.д. Причем наблюдать какие цифры относятся к каким разностям и разделять таким образом цифры в каждой из изначальных пар в два множества цифр - левую и правую части. Не факт, что метод работает, но на нескольких примерах я его уже проверил.
0
|
22.10.2020, 09:49 | |
Ответы с готовыми решениями:
2
Счастливый билет! счастливый билет Счастливый билет счастливый билет |
Модератор
|
|
22.10.2020, 10:05 | 2 |
Если количество цифр в номере небольшое, то решайте методом полного перебора во вложенных циклах (или их эквивалентах - в рекурсивных вызовах).
0
|
5 / 5 / 1
Регистрация: 21.02.2019
Сообщений: 38
|
||||||
22.10.2020, 11:14 [ТС] | 3 | |||||
Сообщение было отмечено ФедосеевПавел как решение
Решение
Извините, забыл ограничения на входные данные прикрепить
В единственной строке входного файла записан номер билетика T (10 ≤ T < 10^18). Гарантируется, что запись числа T содержит чётное количество цифр, однако, может содержать Отсюда видно, что на полный перебор может уйти порядка операций, что конечно не впишется в разумные пределы времени работы программы Добавлено через 53 минуты Извините, если кого-то потревожил понапрасну, задача уже решена, получилось экспоненциальное решение 2 в степени n / 2, где n - количество цифр в числе Код для будущих поколений:
1
|
22.10.2020, 11:14 | |
22.10.2020, 11:14 | |
Помогаю со студенческими работами здесь
3
Счастливый билет Задача на счастливый билет Почти счастливый билет Написать код(счастливый билет) Задача про счастливый билет Задача про счастливый билет Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |