Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
B. Сэрэжа ба давталтууд
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Нэгэн тэмдэглэгээ танилцуулъя:
$$[x, n] = x + x + ... + x = \sum\limits_{i=1}^{n}x$$
Энд $x$ нь тэмдэгт мөр, $n$ нь эерэг бүхэл тоо ба "+" нь тэмдэгт мөрийг араас нь залгах үйлдэл юм. Жишээлбэл $[abc, 2] = abcabc$ байна.
Хэрэв бид $t$ тэмдэгт мөрийн зарим тэмдэгтүүдийг арилгах замаар $s$ тэмдэгт мөрийг гаргаж чаддаг бол $s$-ийг $t$-ээс гардаг гэе. Жишээ нь "ab" ба "aсba" нар нь "xacbac"-аас гардаг боловч "bx" ба "aaa" нар нь гардаггүй юм.
Сэрэжад $w = [a, b]$ ба $q = [c, d]$ гэсэн хоёр тэмдэгт мөр байгаа. Тэрээр $[q, p]$ нь $w$-аас гардаг байхаар хамгийн том $p$ $(p > 0)$ тоог олохыг хүсжээ.
Оролт
Эхний мөрөнд $b$, $d$ $(1 ≤ b, d ≤ 10^{7})$ бүхэл тоонууд байна. Хоёр дахь мөрөнд $a$ тэмдэгт мөр байна. Гурав дахь мөрөнд $c$ тэмдэгт мөр байна. Өгөгдсөн тэмдэгт мөрүүд Англи цагаан толгойн жижиг үсгүүдээс тогтох ба хоосон биш байна. Мөн уртууд нь $100$-аас хэтрэхгүй.
Гаралт
Хамгийн том $p$-ийн утгыг хэвлэ. Хэрэв нөхцөлийг хангах $p$ тоо олдохгүй бол "0" гэж хэвлэ.
Орчуулсан: Бат-Од
Жишээ тэстүүд
Оролт
10 3 abab bab
Гаралт
3