C. Бѳмбѳгүүдийн дараалал

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

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

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

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

Танд багш тус бүр нь Латин цагаан толгойн 'a'-'z' жижиг үсгээр тэмдэглэгдсэн бѳмбѳгнүүдийн дараалал $A$-г ѳгсѳн. Танд ѳгсѳн дараалал таалагдаагүй. Та үүнийг илүү дээр санагдсан $B$ гэсэн шинэ дарааллаар солихыг хүсчээ. Тэгэхээр танд дѳрвѳн үйлдэл хийхийг зѳвшѳѳрѳгдсѳн:

  • Та ямар ч ѳнгийн бѳмбѳгийг дарааллын дуртай газар нь байрлуулж болно.
  • Аль ч байрлалаас ямар ч бѳмбѳгийг устгаж (гаргаж) болно.
  • Аль ч бѳмбѳгийг ѳѳр бѳмбѳгѳѳр сольж болно.
  • Зэрэгцээ хоёр бѳмбѳгийн байрыг сольж болно.

Танай багш үйлдэл бүрийг хийхэд зарцуулагдах хугацааг тавив, энэ нь тухайн үйлдлийг хийвэл яг тийм хугацаа ѳнгѳрнѳ гэсэн үг. Эхний үйлдэл $t_i$, хоёрдугаар үйлдэл $t_d$, гуравдугаар үйлдэл $t_r$, дѳрѳвдүгээр үйлдэл $t_e$ хугацаа авна. Бас $2 · t_e ≥ t_i + t_d$ байхаар ѳгѳгдсѳн.

$A$ дарааллаас $B$ дараалал руу шилжүүлэх хамгийн бага хугацааг ол.

Оролт

Эхний мѳр зайгаар тусгаарлагдсан $t_i$, $t_d$, $t_r$, $t_e$ ($0 < t_i, t_d, t_r, t_e ≤ 100$) дѳрвѳн бүхэл тоог агуулна. Дараагийн хоёр мѳр $A$, $B$ дарааллыг агуулна. Мѳр бүрийн урт $1$-ээс $4000$-ийн хооронд урттай байна.

Гаралт

$A$ дарааллаас $B$ дараалал руу шилжүүлэх хамгийн бага хугацааг илэрхийлэх бүхэл тоог хэвлэ.

Орчуулсан: Sugardorj

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

Оролт
1 1 1 1
youshouldnot
thoushaltnot
Гаралт
5
Оролт
2 4 10 3
ab
ba
Гаралт
3
Оролт
1 10 20 30
a
za
Гаралт
1

Тэмдэглэл

In the second sample, you could delete the ball labeled 'a' from the first position and then insert another 'a' at the new second position with total time 6. However exchanging the balls give total time 3.

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