Требуется за по возможности минимальное количество операций из заданного числа получить 1

@JEHTUNBIRBIKAM · Регистрация: 24.03.2021

Студворк — интернет-сервис помощи студентам

Вам дана десятичная запись целого неотрицательного числа без ведущих нулей. С ней можно делать следующие операции:

'1' - умножить число на 2 (например, 12 преобразуется в 24);

'2' - разделить число на 2, если оно четное (например, 12 преобразуется в 6);

'3' и '4' - поделить запись числа на две половины равной длины и оставить только одну из половин ('3' - первую половину, '4' - вторую половину), если в записи числа четное число знаков (например, 12 можно преобразовать в 1 или 2);

'5' и '6' - поделить запись числа на две половины равной длины и заменить одну из половин другой ('5' - используется первая половина, '6' - используется вторая половину), если в записи числа четное число знаков (например, 12 можно преобразовать в 11 или 22);

Если в результате операции получаются ведущие нули, их надо отбросить.
Требуется за по возможности минимальное количество операций из заданного числа получить 1.

Формат входных данных
В единственной строке ввода размещается десятичная запись целого неотрицательного числа без ведущих нулей. Длина числа не превышает 100 знаков.

Формат результата
В первой строке вывода размещается десятичная запись количества операций по получению 1. В следующей строке необходимо вывести строку из этих операций. Каждая операция выводится в виде одного символа ('1'..'6') без пробелов. Длина строки не должна превышать 10000 символов.

Если число 1 получить невозможно, то выведите единственное число -1.

@saviktor · 06.11.2021, 21:59

Python
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
n = input()
k = 0
count = 0
ans = ''
while int(n) > 1:
    k = len(n)
    count += 1
    if k % 2 == 0:
        if n[:k // 2] < n[k // 2:]:
            n = n[:k // 2]
            ans += '3'
        elif int(n[k // 2:]) == 0:
            n = n[:k // 2]
            ans += '3'
        else:
            n = n[k // 2:]
            ans += '4'
    elif n in ('2', '4', '8'):
        n = str(int(n) // 2)
        ans += '2'
    else:
        n = str(int(n) * 2)
        ans += '1'
print(count)
print(ans)

@JEHTUNBIRBIKAM · 06.11.2021, 22:15 **[ТС]**

Простите, но ваш код проваливается при первом же тесте, при вводе числа 100 он выводит
6
111133
Вместо
4
2313

Добавлено через 1 минуту
Был бы очень благодарен если бы вы реализовали эту задачу ещё раз, но правильно)

@saviktor · 06.11.2021, 22:25

Python
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
n = input()
k = 0
count = 0
ans = ''
while int(n) > 1:
    k = len(n)
    count += 1
    if k % 2 == 0:
        if n[:k // 2] < n[k // 2:]:
            n = n[:k // 2]
            ans += '3'
        elif int(n[k // 2:]) == 0:
            n = n[:k // 2]
            ans += '3'
        else:
            n = n[k // 2:]
            ans += '4'
    elif len(str((int(n) // 2))) % 2 == 0:
        n = str((int(n) // 2))
        ans += '2'
    elif len(str((int(n) // 4))) % 2 == 0:
        n = str((int(n) // 4))
        ans += '22'
    else:
        n = str(int(n) * 2)
        ans += '1'
print(count)
print(ans)

@sdf45 · 06.11.2021, 22:47

Не по теме:

извините, а что это за ЯП такой? :)

@analogov net · 06.11.2021, 23:03

sdf45, это python.
saviktor, похоже, что ввод 2 или 4, например, обработает не правильно. Отсюда и числа, например: 22, 23... 43, 44 и т.д. тоже.

@saviktor · 07.11.2021, 05:53

analogov net, верно, проверку делимости на 2 и 4 нужно добавить

Python
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
n = input()
k = 0
count = 0
ans = ''
while int(n) > 1:
    k = len(n)
    count += 1
    if k % 2 == 0:
        if n[:k // 2] < n[k // 2:]:
            n = n[:k // 2]
            ans += '3'
        elif int(n[k // 2:]) == 0:
            n = n[:k // 2]
            ans += '3'
        else:
            n = n[k // 2:]
            ans += '4'
    elif len(str((int(n) // 2))) % 2 == 0 and int(n) % 2 == 0 or n == '2':
        n = str((int(n) // 2))
        ans += '2'
    elif len(str((int(n) // 4))) % 2 == 0 and int(n) % 4 == 0 or n == '4':
        n = str((int(n) // 4))
        ans += '22'
    else:
        n = str(int(n) * 2)
        ans += '1'
print(count)
print(ans)

@Catstail · 07.11.2021, 09:18

saviktor, никак не научишься тэгами языка пользоваться?

@llo3uTuB4uk · 07.11.2021, 10:19

Можете рассказать идею решения? мне надо перегнать код в c++, либо же идею понять, что бы написать код самому

@eaa · 07.11.2021, 12:09

примеры входных/выходных данных есть?

@JEHTUNBIRBIKAM · 07.11.2021, 12:40 **[ТС]**

Вход
100
Выход
4
2313

@Dimasssssssssss · 08.11.2021, 12:00

JEHTUNBIRBIKAM, это олимпиадная задача, которая была предложена для самостоятельного решения. Если вы настолько беспомощный, что не можете решить даже задачу из отборочного этапа, зачем вы тогда вообще участвуете в олимпиаде.
Цель олимпиады - проявить СВОИ знания.

@VagaColeso · 10.11.2021, 11:46

Сообщение от saviktor

if n[:k // 2] < n[k // 2:]:

Господа, подскажите пожалуйста, что за оператор такой необычный в квадратных скобках? за ради общего развития

@MaMush · 10.11.2021, 16:55

// - нацелоделение, / - деление
10/3 = 3,33333333
10//3 = 3

Новые блоги и статьи Все статьи Все блоги /
Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .
Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .

@JEHTUNBIRBIKAM 4 / 3 / 1 Регистрация: 24.03.2021 Сообщений: 71

	Требуется за по возможности минимальное количество операций из заданного числа получить 1 06.11.2021, 20:39. Показов 8748. Ответов 13 Метки c++, c++ для начинающих (Все метки) Вам дана десятичная запись целого неотрицательного числа без ведущих нулей. С ней можно делать следующие операции: '1' - умножить число на 2 (например, 12 преобразуется в 24); '2' - разделить число на 2, если оно четное (например, 12 преобразуется в 6); '3' и '4' - поделить запись числа на две половины равной длины и оставить только одну из половин ('3' - первую половину, '4' - вторую половину), если в записи числа четное число знаков (например, 12 можно преобразовать в 1 или 2); '5' и '6' - поделить запись числа на две половины равной длины и заменить одну из половин другой ('5' - используется первая половина, '6' - используется вторая половину), если в записи числа четное число знаков (например, 12 можно преобразовать в 11 или 22); Если в результате операции получаются ведущие нули, их надо отбросить. Требуется за по возможности минимальное количество операций из заданного числа получить 1. Формат входных данных В единственной строке ввода размещается десятичная запись целого неотрицательного числа без ведущих нулей. Длина числа не превышает 100 знаков. Формат результата В первой строке вывода размещается десятичная запись количества операций по получению 1. В следующей строке необходимо вывести строку из этих операций. Каждая операция выводится в виде одного символа ('1'..'6') без пробелов. Длина строки не должна превышать 10000 символов. Если число 1 получить невозможно, то выведите единственное число -1. 0

@JEHTUNBIRBIKAM 4 / 3 / 1 Регистрация: 24.03.2021 Сообщений: 71
	06.11.2021, 22:15 [ТС]
	Простите, но ваш код проваливается при первом же тесте, при вводе числа 100 он выводит 6 111133 Вместо 4 2313 Добавлено через 1 минуту Был бы очень благодарен если бы вы реализовали эту задачу ещё раз, но правильно) 0

@sdf45
	06.11.2021, 22:47
	Не по теме: извините, а что это за ЯП такой? :) 0

@analogov net 2532 / 1130 / 494 Регистрация: 17.11.2018 Сообщений: 2,836
	06.11.2021, 23:03
	sdf45, это python. saviktor, похоже, что ввод 2 или 4, например, обработает не правильно. Отсюда и числа, например: 22, 23... 43, 44 и т.д. тоже. 1

@Catstail Супер-модератор 38200 / 21132 / 4310 Регистрация: 12.02.2012 Сообщений: 34,739 Записей в блоге: 14
	07.11.2021, 09:18
	saviktor, никак не научишься тэгами языка пользоваться? 0

@llo3uTuB4uk 0 / 0 / 0 Регистрация: 07.11.2021 Сообщений: 1
	07.11.2021, 10:19
	Можете рассказать идею решения? мне надо перегнать код в c++, либо же идею понять, что бы написать код самому 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	07.11.2021, 12:09
	примеры входных/выходных данных есть? 0

@JEHTUNBIRBIKAM 4 / 3 / 1 Регистрация: 24.03.2021 Сообщений: 71
	07.11.2021, 12:40 [ТС]
	Вход 100 Выход 4 2313 0

@Dimasssssssssss 8 / 7 / 1 Регистрация: 18.03.2020 Сообщений: 24
	08.11.2021, 12:00
	JEHTUNBIRBIKAM, это олимпиадная задача, которая была предложена для самостоятельного решения. Если вы настолько беспомощный, что не можете решить даже задачу из отборочного этапа, зачем вы тогда вообще участвуете в олимпиаде. Цель олимпиады - проявить СВОИ знания. 1

@MaMush 4 / 9 / 2 Регистрация: 05.10.2020 Сообщений: 51
	10.11.2021, 16:55
	// - нацелоделение, / - деление 10/3 = 3,33333333 10//3 = 3 1