Как отправить смайлики за минимальное количество операций?

Парень решил послать своей девушке N смайликов.
После того, как набрал M смайликов, он подумал, что быстрее будет получить N смайликов с помощью определенной комбинации следующих операций:
1. Стереть последний смайлик [операция - "D"]
2. Скопировать все смайлики [операция - "C"]
3. Вставить смайлики из буфера обмена [операция - "V"]

Нужно помочь парню справиться с задачей за минимальное количество операций.

Вывести на экран символьный алгоритм.

Пример: N = 12; M = 5;
Вывод: DCVV
Пояснение (5-1) = 4; 4 + 4 + 4 = 12;
  • Вопрос задан
  • 3276 просмотров
Решения вопроса 1
adugin
@adugin Куратор тега Python
Код на Python для расчёта "в лоб" (перебором) и выявления закономерностей:
# -*- coding: utf-8 -*-

import matplotlib.pyplot as plt
from itertools import product

def process(existing, required):
    for opcount in xrange(existing+required):
        for combo in product('dcv', repeat=opcount):
            buffer = 0
            smiles = existing
            data_y = [existing]
            for char in combo:
                if char == 'd':
                    smiles -= 1
                elif char == 'v':
                    smiles += buffer
                else:
                    buffer = smiles
                data_y.append(smiles)
            if smiles == required:
                data_x = xrange(opcount+1)
                plt.plot(data_x, data_y, linewidth=1)
                print required, data_y
                return ''.join(combo)
    return '-'

for required in xrange(2, 101):
    plt.clf()
    plt.grid(True)
    plt.title('Target: %s' % required)
    plt.autoscale(enable=True, axis='both', tight=False)
    for existing in xrange(1, (required//2)+1):
        result = process(existing, required)
    plt.savefig('{:02d}.png'.format(required), dpi=96, bbox_inches='tight')

Задача распадается на 2:
1) Если M >= N div 2, то нужно удалить всё до половины, скопипастить, и по необходимости удалить 1 смайл.
2) Если п.1 не выполняется, то нужно рассчитать делители N (если N простое - то взять следующие несколько чисел больше N) и спуститься к ближайшему наибольшему делителю N, который меньше M. Удалять смайлы, чтобы попадать в наблюдаемые на картинках горизонтальные уровни, соответствующие делителям.

В общем случае решение не единственное - например, соседние группы D и V можно смешивать в любых последовательностях: DDVVV = VVVDD = VDVDV = ...

N=12. Для M=5 видим DCVV (фиолетовая линия). Уровни (делители) - 6, 4, 3, 2, 1:
042d326f2b1a45d2916c5ce012fca2f6.png
N=28:
c832673197de486aa072d81b56de27c4.png
N=29:
4e0ee3d81d9b47e38127cf8211c2c48f.png
N=30:
2629d000169449c1896414c348b61874.png
N=71:
5037b1d5028b4330aed51516ec81887f.png
N=72:
89fd833e066f423993665d4c54e8f6cc.png
PDF со всеми картинками: dugin.org/dropbox/toster_188303.pdf (11 Mb)

P.S. https://ru.wikipedia.org/wiki/Задача_о_ранце
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
@Eddy_Em
ceil(12/5) = 3 -> Npastes=3-1=2
floor(12/3) = 4 -> copyOn = 4
12-4*2=4 -> Ndeletes = 5-4 = 1

Аналогично с любыми другими числами. Скажем, N=14, M=5:
ceil(14/5) = 3 -> Npastes = 2
floor(14/2) = 7 -> copyOn = 5 (т.к. мы до семи догнать не можем)
14 - 5*2 = 4 -> Ndeletes = 1
Ответ: CDVV
Как определить, когда писать DC, а когда CD, понять несложно.
А то ведь вообще получится, что я забесплатно домашнюю работу решил!
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы