F3. Чадал сорьсон бөмбөлгүүд

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

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

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

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

Марта бол дэлхийн хэмжээний тэмцээнд бодлого дэвшүүлдэг мэргэжлийн бодлого зохиогч юм. Түүний дэвшүүлсэн бодлого:

Маргааш Надиагын төрсөн өдөр болох учраас түүний ах Бардиа бөмбөлгүүдийг үлээж бэлэн болгох үүрэг хүлээгээд байна!

Нийт $n$ (үлээгээгүй) бөмбөлөг байгаа ба тэдгээр бөмбөлгүүдийг шулуун шугамын дагуу $x_{1}, x_{2}, ..., x_{n}$ байрлалуудад уясан байна. Бардиа бөмбөлгүүдийг зүүнээс нь баруун тийш дарааллаар нэг нэгээр нь хийлнэ. $i$-р бөмбөлөгний даралтын тэсвэр нь $p_{i}$ хүртэл, эсвэл өмнө нь хийлсэн өөр бөмбөлгөнд хүрэх хүртэл нь $i$-р бөмбөлгийг томруулна.

Бардиа бөмбөлөг хийлээд завгүй байх зуураа "Бүх бөмбөлгийг хийлсний дараа тэдгээр бөмбөлгүүдийн радиусын нийлбэр хэд байх бол?" гэж боджээ. Залуугийн толгой жаахан манарсан байгаа тул тэр одоо энэ бодлогын талаар бодож байхын оронд дүүгийнхээ төрсөн өдөрт бэлтгэж байна. Надиагийн төрсөн өдрийн бөмбөлөг цөөхөн байж болохгүй учраас Бардиагын бодлогын хариуг олно уу.

Artha — Martha's student — claimed his solution got accepted. Martha (being his teacher for a long time!) knew he couldn't have solved the problem for real and thus thinks there is something wrong with the testcases. Artha isn't anyhow logical, which means there is no way for Martha to explain the wrong point in his algorithm. So, the only way is to find a testcase to prove him wrong!

Арта бол Мартагийн сурагч юм. Хэдийгээр Артагийн бодолт шалгагч програмыг давсан боловч бодолт нь бүрэн гүйцэд биш байсан бөгөөд шалгагч тестүүд асуудалтай байснаас болж шалгалтыг давсан байлаа. Арта учир аливаа зүйлийн шалтгааныг ойлгохдоо маруухан учраас түүнд алгоритмынх нь буруу гэдгийг тайлбарлах нь Мартагийн хувьд боломжгүй зүйл байлаа. Тиймээс цорын ганц боломжит арга бол түүний бодолтыг буруу гэдгийг харуулах тест олох болов.

Артагийн алгоритмын псевдо кодыг доор үзүүлэв:

Та Артагийн алгоритм нь алдаатай хариу гаргаж байх тест хэвлэх ёстой. Хэрвээ алгоритмын хариу нь жинхэнэ хариунаас $1$-ээс багаар зөрж байвал зөв гэж тооцогдоно.

Оролт

Анхаарлаа хандуулна уу! Энэ бодлогын хувьд таны програмд өгөгдөх ямар ч оролт байхгүй. Тиймээс та ямар ч оролт уншуулах шаардлагагүй юм.

Гаралт

Та жишээ тест (Артагийн алгоритм буруу ажилладаг) хэвлэх ёстой. Энэ нь дараах хэлбэртэй байх ёстой:

  • Эхний мөрөнд зөвхөн $n$ ($1 ≤ n ≤ 500$) тоо байна.
  • Дараагийн $n$ мөрүүдийн $i$-р мөрөнд $i$-р бөмбөлөгний тодорхойлолт байна. Энэ нь зайгаар тусгаарлагдсан $x_{i}, p_{i}$ ($1 ≤ p_{i} ≤ 10^{6}$, $0 ≤ x_{1} < x_{2} < ... < x_{n} ≤ 10^{6}$) бүхэл тоонууд байна.

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

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

Тэмдэглэл

Жишээ зурагны хувьд гаралт ямар байхыг харуулав. Гэхдээ энэ нь зөвхөн гаралт ямар форматтай байхыг харуулж байгаа гэдгийг анхаарна уу.

4
0 9
6 3
12 7
17 1
Сэтгэгдлүүдийг ачааллаж байна...