E. Тэмдэгт мөрөөр тоглох

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Хоёр хүн дараахь тэмдэгт мөрийн тоглоомыг тоглоно. Эхлээд тоглогчдод $s$ гэсэн тэмдэгт байна. Тоглогчид ээлж ээлжээр нүүх ба нүүдэлгүй болсон тоглогч хожигдоно.

Тоглоом эхлэхээс өмнө тэмдэгт мөр нэгэн цаасан дээр бичигдсэн байх ба тэмдэгт бүр нэг нүдэнд байрлана.

Жишээлбэл $s$ = "$abacaba$" үед дараахь байдалтай байна:

Тоглогчийн нэг нүүдэл дараахь үйлдлүүдийн дараалал байна:

  1. Тоглогч ямар нэгэн цаас сонгон авна. Тэрхүү цаасан дээр $t$ гэсэн тэмдэгт мөр байгаа гэе. Анх нэг л цаас байсан.
  2. Тоглогч $t = t_{1}t_{2}... t_{|t|}$ тэмдэгт мөрөөс ямар нэгэн $l$ $(0 < i - l; i + l ≤ |t|)$ гэсэн эерэг бүхэл тооны хувьд $t_{i - 1} = t_{i + 1}$, $t_{i - 2} = t_{i + 2}$, ..., $t_{i - l} = t_{i + l}$ байх $i$ $(1 ≤ i ≤ |t|)$ дугаарын нүдийг сонгоно.
  3. Тоглогч сонгосон нүдийг хайчилна. Тэгээд цаас гурван хэсэг хуваагдах ба эхнийх нь $t_{1}t_{2}... t_{i - 1}$ тэмдэгт мөрийг, хоёр дахь нь сонгогдсон тэмдэгт болох $t_{i}$-ийг, гуравдахь нь $t_{i + 1}t_{i + 2}... t_{|t|}$ тэмдэгт мөрийг агуулна. Жишээ нь $s$ = «$abacaba$» тэмдэгт мөр дээр $(i = 4)$ дугаарын нүдийг сонговол

Чиний даалгавар бол тоглогчид зөв тогловол хэн нь хожихыг олох юм. Хэрэв нэгдүгээр тоглогч хожвол түүний эхний үйлдлээ хийхдээ сонгох нүдний байрлалыг ол. Хэрэв олон хувилбар байвал аль бага дугаарыг нь хэвлэ.

Оролт

Эхний мөрөнд $s$ ($1 ≤ |s| ≤ 5000$) тэмдэгт мөр өгөгдөнө. $s$ тэмдэгт мөр Англи цагаан толгойн жижиг үсгүүдээс тогтоно.

Гаралт

Хэрэв хоёр дахь тоглогч хожих бол "$Second$" гэж хэвлэ. Бусад тохиолдолд "$First$" гэж хэвлэн хоёр дахь мөрөнд түүний эхний сонгох нүдний дугаар $i$ $(1 ≤ i ≤ |s|)$-ийг хэвлэ.

Орчуулсан: Бат-Од

Жишээ тэстүүд

Оролт
abacaba
Гаралт
First
2
Оролт
abcde
Гаралт
Second

Тэмдэглэл

Эхний жишээнд эхний тоглогч хожих хэд хэдэн боломж бий. Гэхдээ хамгийн цөөн үйлдэлд харгалзах боломж нь $2$ дугаарын нүдэнд буй үсгийг хайчлах юм.

Хоёр дахь жишээнд эхний тоглогч хожих боломжгүй.

Сэтгэгдлүүдийг ачааллаж байна...