C. Жорж ба тоо

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

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

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

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

Жорж муур тоглох үнэхээр дуртай. Эерэг бүхэл $b$ тоонуудын массиваар тоглох бүр ч их дуртай. Тоглоомын туршид Жорж гайхалтай өөрчлөлтүүдийг ашиглан массивыг өөрчилнө. Жоржийн одоогийн массивыг $b_{1}, b_{2}, ..., b_{|b|}$ ($|b|$ нь массивын одоогийн уртыг илэрхийлнэ) гэж тэмдэглэе. Тэгээд нэг өөрчлөлтийн үйлдлийн дараалал нь:

  • $b_{i} ≥ b_{j}$ байх ялгаатай $i$ ба $j$ $(1 ≤ i, j ≤ |b|; i ≠ j)$ индексүүд сонгоно.
  • $v = concat(b_{i}, b_{j})$ тоог авна, $concat(x, y)$ бол $x$ тооны төгсгөлд $y$ тооны аравтын бичилтийг нэмсэнийг илэрхийлнэ. Жишээлбэл: $concat(500, 10) = 50010$, $concat(2, 2) = 22$.
  • Массивын төгсгөлд $v$ тоог нэмнэ. Ингээд массивын урт нэгээр нэмэгдэнэ.
  • $i$ ба $j$ индекстэй тоонуудыг массиваас устгана. Массивын урт хоёроор буурсан ба массивын элементүүд нь $1$-с массивын одоогийн урт хүртэл дахин дугаарлагдана.

Жорж өөрийн $b$ массиваар удаан тоглосон ба $b$ массиваас яг нэг $p$ тооноос бүрдсэн массив авсан. Одоо Жорж мэдэхийг хүссэн: анхны $b$ массивын агуулж болох элементүүдийн хамгийн их тоо хэд вэ? Энэ тоог олоход түүнд тусал. Анхны массив нь зөвхөн эерэг бүхэл тоонуудаас бүрдэхийг анхаарна уу.

Оролт

Оролтын эхний мөр $p$ ($1 ≤ p < 10^{100000}$) бүхэл тоог агуулсан нэг мөрөөс бүрдэнэ. Энэ $p$ тоо тэгээр эхлээгүй гэдэг нь баталгаатай болно.

Гаралт

Нэг бүхэл тоо хэвлэнэ. Энэ нь анхны $b$ массивын агуулж болох элементүүдийн хамгийн их тоо.

Орчуулсан: Даариймаа

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

Оролт
9555
Гаралт
4
Оролт
10000000005
Гаралт
2
Оролт
800101
Гаралт
3
Оролт
45
Гаралт
1
Оролт
1000000000000001223300003342220044555
Гаралт
17
Оролт
19992000
Гаралт
1
Оролт
310200
Гаралт
2

Тэмдэглэл

Жишээг авч үзье:

  • Анхны $b$ массив ${5, 9, 5, 5}$ байж болно. Жоржийн хийсэн байж болох өөрчлөлтийн дараалал : ${5, 9, 5, 5} -> {5, 5, 95} -> {95, 55} -> {9555}$.
  • Анхны $b$ массив ${1000000000, 5}$ байж болно. $b$ массив тэгүүдийг агуулж болохгүйг анхаараарай.
  • Анхны $b$ массив ${800, 10, 1}$ байж болно.
  • Анхны $b$ массив ${45}$ байж болно. ${4, 5}$ байж болохгүй, учир нь Жорж нэг үйлдлээр энэ массиваас зөвхөн ${54}$ массивыг авах боломжтой юм.

Тоонууд маш их байж болохыг анхаарна уу.

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