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

@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 и список его инстансов. Я пока эту тему не изучал глубоко в Пайтоне.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

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

Опции темы