A. Лимак баавгай Урвуу Рэйдвүүш хоёр

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

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

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

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

Лимак, Рэйдвүүш нар алгоритмын тэмцээнд харилцан өрсөлдөхөөр болжээ. Тэд чадварын хувьд эн тэнцүү боловч бодлогуудаа ижил дарааллаар бодохгүй.

$n$ ширхэг бодлого өгөгдөнө. $i$-р бодлого $p_i$ анхдагч оноотой ба бодоход $t_i$ хугацаа шаардлагатай. Бодлогууд хүндрэлийн түвшнээрээ эрэмбэлэгдсэн буюу дараах нөхцөл биелнэ: $p_i < p_{i+1}$ ба $t_i < t_{i+1}$

Мөн бодлогуудын оноо алдах хурдцыг илтгэх тогтмол тоо $c$ өгөгдөнө. $i$ дэх бодлогыг тэмцээн эхэлснээс хойш $x$ хугацаанд илгээхэд $max(0, p_i - c \cdot x)$ оноо авдаг.

Лимак бодлогуудыг $1, 2, \dots, n$ ($p_i$ өсөх) дарааллаар бодох бол харин Рэйдвүүш $n, n-1, \dots, 1$ ($p_i$ буурах) дарааллаар бодолтоо илгээх юм. Тэмцээний эцэст хэн өндөр оноо авч ялагч болохыг тогтоож тогтоож нэрийг нь хэвлэнэ үү. Хэрэв тэнцээ гарах бол "Tie" гэж хэвлэнэ.

Тэмцээн үргэлжлэх хугацаа бүх $t_i$-үүдийн нийлбээр багагүй буюу Лимак Рэйдвүүш нар бүх бодлогыг бодож амжина.

Оролт

Эхний мөрөнд $n$ ба $c$ $(1 \le n \le 50)$ хоёр тоо өгөгдөнө, харгалзан бодлогын тоо болон оноо буурах хурдыг илтгэнэ.

Удаах мөрөнд бодлогуудын анхдагч оноог илтгэх $n$ ширхэг $p_1, p_2, \dots, p_n$ ($1 \le p_i \le 1000$, $p _i < p_{i+1}$) тоо өгөгдөнө.

Гурав дах мөрөнд бодлого бодоход зарцуулах хугацааг илтгэх $n$ ширхэг $t(1) \le t(2) \le \dots \le t_n, t_i < t_{i+1}$ тоо өгөгдөнө.

Гаралт

Нийлбэр оноогоор Лимак давуу байвал "Limak", Рэйдвүүш илүү байвал "Radewoosh", харин тэнцүү байвал "Tie" гэж тус тус хэвлэнэ үү.

Орчуулсан: Төрбат

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

Оролт
3 2
50 85 250
10 15 25
Гаралт
Limak
Оролт
3 6
50 85 250
10 15 25
Гаралт
Radewoosh
Оролт
8 1
10 20 30 40 50 60 70 80
8 10 58 63 71 72 75 76
Гаралт
Tie

Тэмдэглэл

Эхний жишээнд гурван бодлого өгөгдсөн байна. 1. Лимак энхий бодлогод $10$ минут зарцуулж $50 - c \cdot 10 = 50 - 2 \cdot 10 = 30$ оноо авна. 2. Хоёр дах бодлогод $15$ минут зарцуулах ба тэмцээн эхэлснээс хойш $10 + 15 = 25$ минутанд илгээнэ. Иймд 2-р бодлогоос $85 - 2\cdot 25 = 35$ оноо авна. 3. Гурав дах бодлогод $25$ минут зарцуулж тэмцээн эхэлснээс хойш $10 + 15 + 25 = 50$ минутын дараа илгээнэ. Иймд энэ бодлогоос $250 - 2\cdot 50 = 150$ оноо авна..

Лимак нийт $30 + 35 + 150 = 215$ оноо цуглуулна.

Рэйдвүүш урвуу дарааллаар бодно:

  1. $3$-р бодлогыг $25$ минутанд бодож $250 - 2\cdot 25 = 200$ оноо авна.
  2. $2$-р бодлогод $15$ минут зарцуулах тул тэмцээн эхэлснээс хойш $25 + 15 = 40$ минутын дараа бодолтоо илгээж $85 - 2\cdot 40 = 5$ оноо авна.
  3. $1$-р бодлогод $10$ минут зориулж, эхэлснээс хойш $25 + 15 + 10 = 50$ минутын дараа бодолтоо илгээнэ. Ингэснээр $max(0, 50 - 2\cdot 50) = max(0,  - 50) = 0$ оноо цуглуулна.

Рэйдвүүш нийт $200 + 5 + 0 = 205$ оноотой бол харин Лимак has $215$ оноотой тул Лимак ялна.

Хоёр дах жишээнд Лимак бүх бодлогоос $0$ оноо түүх бол Рэйдвүүш эхэнд хамгийн хүнд бодлогоо бодсоноор $250 - 6\cdot 25 = 100$ оноо авч, хэдий үлдсэн хоёр бодлогоос оноо авахгүй ч гэсэн дийлнэ.

Гурав дах жишээнд Лимак эхний бодлогоос $2$, хоёр дах бодлогоос $2$ оноо авна. Рэйдвүүш найм дах бодлогоос $4$ оноо хүртэх ба хэн хэн нь бусад бодлогоос оноо авахгүй. Иймд энэ тохиолдолд тэд тэнцэх юм.

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