Codeforces Round #696 (Div. 2)
13:57:44 |
C. Массив ба үйлдлүүд
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Танд цаасан дээр бичсэн $n$ ширхэг эерэг бүхэл тоонуудын $a[1], a[2], ..., a[n]$ массив болон $m$ ширхэг бүхэл тоон $(i_{1}, j_{1}), (i_{2}, j_{2}), ..., (i_{m}, j_{m})$ сайн хосууд байна. Сайн хос $(i_{k}, j_{k})$ бүр дараах нөхцлүүдийг хангана: $i_{k} + j_{k}$ сондгой тоо байх ба $1 ≤ i_{k} < j_{k} ≤ n$ байна.
Нэг үйлдлээр та дараах үйл ажиллагаануудыг гүйцэтгэж чадна:
- $(i_{k}, j_{k})$ сайн хосуудаас нэгийг, мөн $a[i_{k}]$, $a[j_{k}]$ тоонуудыг хоёуланг нь хуваадаг ямар нэг бүхэл $v$ ($v > 1$) тоо авна;
- Хоёр тоог хоёуланг нь $v$-д хуваана. Өөрөөр хэлбэл дараах үйлдлийг гүйцэтгэнэ:
ба
.
Та өгөгдсөн массив дээр хамгийн ихдээ хэдэн үйлдэл дараалан гүйцэтгэж чадах вэ? Дээр тайлбарласан үйлдэлд нэг хосыг хэд хэдэн удаа хэрэглэж болно гэдгийг анхаарна уу.
Оролт
Эхний мөр нь зайгаар тусгаарлагдсан $n$, $m$ ($2 ≤ n ≤ 100$, $1 ≤ m ≤ 100$) эерэг бүхэл тоонуудыг агуулна.
Хоёр дахь мөр нь тодорхойлсон массив болох $n$ ширхэг $a[1], a[2], ..., a[n]$ ($1 ≤ a[i] ≤ 10^{9}$) бүхэл тоонуудыг агуулна.
Дараагийн $m$ мөрүүд нь сайн хосуудын тодорхойлолтыг агуулна. $k$-р мөр нь зайгаар тусгаарлагдсан $i_{k}$, $j_{k}$ ($1 ≤ i_{k} < j_{k} ≤ n$, $i_{k} + j_{k}$ нь сондгой тоо байна) бүхэл тоонуудаас бүрдэнэ.
Бүх сайн хосууд хоорондоо ялгаатай байна.
Гаралт
Бодлогын хариуг хэвлэнэ.
Орчуулсан: Даариймаа
Жишээ тэстүүд
Оролт
3 2 8 3 8 1 2 2 3
Гаралт
0
Оролт
3 2 8 12 8 1 2 2 3
Гаралт
2