Вообще говоря, герцог втайне сочувствовал барону мюнхгаузену. конечно, он тоже не был уверен, к примеру, что барон разогнать облака, но полагал, что утверждать обратное, глядя
на чистое небо, определённо не стоит. хотя ультиматум герцог всё-таки счёл перебором.
периодически герцог интересуется, какие новые появились у мюнхгаузена, и ему их
рассказывают. не так давно ему рассказали очередные n . каждая характеризуется
мерой фантастичности. в какие-то из этих герцог поверил, а в какие-то нет; так что для
каждой #j известна реакция герцога aj : t — если герцог решил, что правдива,
f — если герцог решил, что выдумана.
изначально доверие герцога к рассказам барона мюнхгаузена составляло d. после каждой очередной это доверие могло изменяться. однако совершенно точно известно, что оно никогда
не становилось отрицательным: в этом случае герцог попросту перестал бы слушать . опишем правила изменения доверия герцога.
пусть после прослушивания k − 1 доверие герцога к рассказам барона составляет dk−1.
пусть мера фантастичности следующей #k равна fk. герцог поверит в барона,
если fk 6 dk−1 + p, где p — параметр повышения доверия. в этом случае ak = t. если же это
неравенство не будет выполнено, то герцог сочтёт выдуманной, и ak будет равно f.
если герцог поверит в барона, то его доверие будет определяться формулой
dk = max(dk−1, fk).
если же герцог сочтёт выдуманной, то его доверие будет определяться формулой
dk = dk−1 − max(b, fk − dk−1 − p), где b — параметр понижения доверия.
в этой вам известно всё, кроме значений f1, f2, . . , fn. ваша — предложить такую
последовательность этих значений, которая к заданной последовательности a1, a2, . . , an
и при этом будет сохранять значение доверия неотрицательным. среди возможных последовательностей f1, f2, . . , fn нужно выбрать ту, в которой максимальное среди всех значений fk будет минимально возможным.
формат входных данных
в первой строке содержатся целые числа n, d, p, b (1 6 n 6 3·105
, 1 6 d, p, b 6 5000) — количество
, исходное значение доверия герцога, а также параметры повышения и понижения доверия.
во второй строке содержится n символов t и f. если на позиции #k располагается символ t,
то #k герцог счёл правдивой; если же на позиции #k располагается символ f, то
#k герцог счёл выдуманной.
формат выходных данных
в первой строке выведите y es, если последовательность возможно построить, и no, если такой
последовательности не существует.
если последовательность существует, выведите ещё две строки.
во второй строке выведите целое число fmax — максимальное значение среди всех значений fk.
страница 5 из 10
окружной этап всероссийской олимпиады школьников по информатике, 2019 - 2020
россия, самара, 09.11.2019
в третьей строке выведите n целых чисел через пробел f1, f2, . . , fn (0 6 fk 6 fmax) — подходящие значения мер фантастичности.