Задача "Волшебный мост"

@MikoSmile · Регистрация: 19.10.2014

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

Крестьянин, возвращаясь с ярмарки, увидел на мосту странную картину. Какой-то человек сначала считал деньги в кошельке, затем бросал в реку несколько монеток, бежал на другой конец моста, снова считал деньги в кошельке, и опять бросал несколько монеток и шел на другой конец моста. Наконец, пересчитав свои деньги, он явно обрадовался и отправился в дальнейший путь. – Что ты делал? Зачем ты бросал деньги в воду? – спросил крестьянин, догнав странного человека. Видя, что свой секрет скрыть не удастся, человек рассказал, что мост волшебный, что, если бросить с моста ровно 29 копеек, то, как только перейдешь мост, количество рублей в оставшейся сумме денег превращаются в новой сумме в количество копеек, а копейки – в рубли, что, перейдя мост несколько раз, можно получить сумму, намного большую первоначальной.

– Самое важное – вовремя остановиться, – сказал человек и ушёл.

Крестьянин задумался, достал кошелек и пересчитал свои деньги. У него было 46 рублей 47 копеек. «29 копеек – не деньги, дай-ка попробую». После первого прохода у него получилось 18р.46к., после второго прохода – 17р.18к., а после третьего – 89р.16к. «Ух-ты! А еще больше можно получить?» – обрадовался крестьянин. После четвертого прохода у него стало 87р.88к., после пятого – 59р.87к., после шестого – 58р.59к., после седьмого – 30р.58к., после восьмого – 29р.30к., после девятого – 1р.29к., а после десятого осталась 1 копейка.

«Эх, дурачина, надо было после третьего раза остановиться!» – расстроился крестьянин.

Напишите программу, которая по начальной сумме денег у крестьянина определит оптимальное число проходов по мосту для получения наибольшей конечной суммы.

Входные данные
Во входном файле в первой строке содержится целое число M – количество копеек, которые нужно бросать с моста (1≤M≤50). Во второй строке содержатся два целых числа R и K через пробел – начальная сумма денег у крестьянина, выраженная в рублях и копейках (0≤R≤99, 0≤K≤99).

Выходные данные
В выходной файл вывести наименьшее количество проходов по мосту для получения максимально возможной суммы.

Задача вроде бы легкая, ничего сложного. Но есть одно НО. Ограничение по времени выполнения - 1 секунда. Моя же программа работает в 1.5 раза медленней, чем надо. И оптимизировать ее не могу. Уже 2 недели думаю над этой задачей. Есть тут знатоки Python? Помогите простому смертному

Вот мое решение:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def main():
    
  m=int(input())
  r,k=input().split()
  r=int(r)
  k=int(k)
 
  max_money=r*100+k
  money=max_money
    
  kol=0
  max_kol=kol
 
  while money>m:
      money-=m
      money=money%100*100+money//100
      if max_money<money:
          max_money=money
          max_kol=kol+1
      kol+=1
  print(max_kol)
 
main()

@Somebody · 19.10.2014, 23:57

Сначала надо подумать, можно ли как-то определить этот момент, не пройдя цепочку до конца при наличии такового.

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

Моя же программа работает в 1.5 раза медленней, чем надо.

На каком тесте в 1,5? При (2, 34, 56), например, в бесконечное число, потому что там образуется цикл из сумм...

@Vtulhu · 20.10.2014, 13:24

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
import sys
 
minus = -int(sys.argv[1])
ruble = int(sys.argv[2])
kopek = int(sys.argv[3])
 
i = 0
max_i = 0
max_ruble = ruble
max_kopek = kopek
 
while True:
    new_ruble = kopek + minus
    if new_ruble < 0:
        new_ruble = new_ruble + 100
        kopek = ruble - 1
        if kopek == -1:
            break
    else:
        kopek = ruble
    ruble = new_ruble
    i = i + 1
    if ruble > max_ruble or (ruble == max_ruble and kopek > max_kopek):
        max_i = i
        max_ruble = ruble
        max_kopek = kopek
 
print("iterations = %d, max account = %drub %dkop" % (max_i, max_ruble, max_kopek))

@Somebody · 20.10.2014, 13:47

Vtulhu, тоже на бесконечных последовательностях виснет.
Мой вариант:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def money_sums(r, k, m):
    already_had = set()
    while (r, k) not in already_had:
        already_had.add((r, k))
        yield r, k
        k -= m
        if k < 0:
            r, k = r - 1, k + 100
        if r < 0:
            return
        r, k = k, r
 
m = int(input())
r, k = map(int, input().split())
steps = enumerate(money_sums(r, k, m))
print(max(steps, key=lambda x: x[1])[0])

@Vtulhu · 20.10.2014, 14:21

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

Vtulhu, тоже на бесконечных последовательностях виснет.

Задача стояла создать оптимизированный вариант. В нормальной ситуации я сделал бы и мемоизацию, и ООП.

@Somebody · 20.10.2014, 17:43

Задача состояла в том, чтобы создать программу, которая укладывается в 1 секунду. Я не знаю, сколько работает мой вариант, так как не знаю, какие входные данные дают наибольшую последовательность различных сумм. Но если программа работает бесконечное количество времени на некотором тесте, то и в худшем случае, и в среднем она работает ровно столько же, сколько и исходный вариант, - бесконечно долго.

@grizlik78 · 20.10.2014, 22:03

Со словарём:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
M = int(input())
rub, kop = map(int, input().split())
 
max_total = total = rub*100+kop
count = {}
i = 0
 
while not (total in count) and total > M:
    count[total] = i
    i += 1
    total -= M
    total = 100 * (total % 100) + total // 100
    if total > max_total:
        max_total = total
 
if not (total in count): count[total] = i
 
print count[max_total]

@Somebody · 20.10.2014, 22:30

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

Python
1
2
3
while not (total in count) and total > M:
...
if not (total in count):

Есть замечательный оператор not in.

@grizlik78 · 20.10.2014, 23:53

Да, да. Просто пользуясь языком от случая к случаю то одно забудется, то другое)

Добавлено через 1 час 21 минуту

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

Я не знаю, сколько работает мой вариант, так как не знаю, какие входные данные дают наибольшую последовательность различных сумм.

"Если повар нам не врёт", то получается, что максимальное количество переходов равно 197. Вариантов таких много и при этом начальное количество копеек всегда равно 99. Интересненько...

@Vtulhu · 21.10.2014, 00:02

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
def purses(total, minus):
    p = [ total ]
    while True:
        rubles, kopek = total // 100, total % 100
        kopek = kopek - minus
        if kopek < 0:
            kopek = kopek + 100
            rubles = rubles - 1
            if rubles == -1: break
        total = 100 * kopek + rubles
        if total in p: break
        p.append(total)
    return p
 
import sys
 
minus = int(sys.argv[1])
total = int(sys.argv[2]) * 100 + int(sys.argv[3])
 
steps = purses(total, minus)
print(steps)
max_total = max(steps)
max_step = steps.index(max_total)
print("max_total = %d, max_steps = %d" % (max_total, max_step))

Буду неимоверно благодарен, если кто-то решит эту задачу с применением ООП, чтобы был класс Purse и список его инстансов. Я пока эту тему не изучал глубоко в Пайтоне.

Новые блоги и статьи Все статьи Все блоги /
Загрузка PNG-файла с альфа-каналом с помощью библиотеки SDL3_image на Android 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом

@Somebody 2838 / 1647 / 254 Регистрация: 03.12.2007 Сообщений: 4,222
	20.10.2014, 17:43
	Задача состояла в том, чтобы создать программу, которая укладывается в 1 секунду. Я не знаю, сколько работает мой вариант, так как не знаю, какие входные данные дают наибольшую последовательность различных сумм. Но если программа работает бесконечное количество времени на некотором тесте, то и в худшем случае, и в среднем она работает ровно столько же, сколько и исходный вариант, - бесконечно долго. 0