123456Вопрос654321

22.07.2021 03:54 •  Математика

Сын всемирно известного путешественника Валериан Фогг заключил пари, что сможет повторить кругосветное путешествие своего отца. В каждом городе, который он должен посетить, есть либо морской порт, либо аэропорт. Города можно задать как строку s длины n, где si = А, если в i-м городе есть аэропорт, и si=М, если в i-м городе есть морской порт. Сейчас Валериан находится в первом городе (которому соответствует s1), и ему нужно попасть в последний город (которому соответствует sn). Если для двух городов i и j на всех перекрестках i,i+1,…,j−1 есть морской порт, то можно заплатить a дублонов за билет на корабль, и доплыть от i-го города до j-го (в нем порт может и отсутствовать). Формально, заплатив a дублонов, Валериан может добраться из i до j, если st=М для всех i ≤ t < j. То же верно и для аэропортов, но цена билета на дирижабль равна b. Например, если s=«AAМММAМ», a=4 и b=3, то Валериан может: купить билет на дирижабль, чтобы добраться от 1 до 3, купить билет на корабль, чтобы добраться от 3 до 6, купить билет на дирижабль, чтобы добраться от 6 до 7. Так ему нужно потратить 4+3+4=11 дублонов. Обратите внимание, последний город (т.е. символ sn) не влияет на итоговую стоимость. Однако пари Валериан выиграет, только если сможет повторить подвиг отца, и наличных у него всего р, чего может не хватить на весь маршрут. Однако старый друг готов и доставить Валериана в любой город. Но что бы пари считалась выигранным необходимо, чтобы это был ближайший город i к первому так, чтобы ему хватило денег добраться от i-го города до n-го. Напишите программу, которая вычислит минимальный номер города i, до которого Валериана должен доставить друг. Формат ввода В первой строке входных данных даны три целых числа a,b,p — стоимость билета на дирижабль, стоимость билета на корабль, и количество денег у Валериана соответственно (1 ≤ a, b, p ≤105). Во второй строке входных данных дана строка s, в которой si=A, если в i-м городе можно сесть на дирижабль, и si=М, если в i-м городе можно сесть на корабль. (2 ≤ длина строки s ≤ 105). Формат вывода В выходные данные необходимо вывести одно целое число i — минимальный номер города , до которого Валериана должен доставить друг. Пример 1 Ввод Вывод 3 2 8 MM 2 Пример 2 Ввод Вывод 5 3 4 1 Пример 3 Ввод Вывод 2 1 1 AMAAAM 3