D. Хивс будах

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

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

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

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

Хэдий цагаан байвгай ч гэсэн Алиса баавгай мөсөн дээр хэвтэхдээ даардаг. Алиса хивс хийхээр болжээ. Хивс нь $h$ өндөртэй $w$ өргөнтэй тэгш өнцөгт шиг харагддаг. Тиймээс тэгш өнцөгтийг $h × w$ ширхэг нүднүүдэд хуваажээ. Алиса $k$ ширхэг өөр өнгөнөөс сонгон нүд болгоныг будах байлаа. Өнгөнүүд $1$-ээс $k$ хүртэл дугаарлагджээ. Тэрээр бүх өнгийг оролцуулах албагүй.

Харин энд зарим хязгаарлалт бий. Зэргэлдээ хоёр нүд $x$ ба $y$ болгоны хувьд дараах $2$ хязгаарлалтын аль нэг нь тавигдана:

  • $color(x) = color(y)$, эсвэл
  • $color(x) ≠ color(y)$.

Өнгөний хязгаарлалтын жишээг зурагт үзүүлжээ:

Алиса бүх өнгөний хязгаарлалтыг биелүүлэхийг хүсч байвч Арктикийн амьдрал бодсоноос ярвигтай. Гэхдээ хэрвээ бүх өнгөний хязгаарлалтын $\frac{3}{4}$ нь хангагдсан тохиолдолд тэрээр хангалттай баярлах юм.

Хэрвээ түүнд $4$ ширхэг өнгө байвал хивсийг дараах байдлаар будаж болно:

Тэр баяртай байгаа бөгөөд бүх өнгөний хязгаарлалтын $\frac{13}{17}$ нь хангагдсан буюу $\frac{13}{17} \geq \frac{3}{4}$. Таны даалгавар бол түүнд хивсээ будахад туслах юм.

Оролт

Эхний мөрөнд $h, w, k$ $(2 ≤ h, w ≤ 1000, 1 ≤ k ≤ w*h)$ бүхэл тоонууд өгөгдөнө.

Дараагийн $2h - 1$ мөрөнд өнгөний хязгаарлалтуудыг дээрээс доош нь болон зүүнээс баруун тийш тэмдэгтээр өгөгдөнө. Эдгээр мөрнүүд харгалзан $w - 1, w, w - 1, w, ..., w - 1$ ширхэг тэмдэгтүүд агуулна. Өнгөний хязгаарлалт болгон $E$ эсвэл $N$ гэсэн тэмдэгтээр өгөгдөнө. Энд $E$ гэдэг нь "$ = $", $N$ гэдэг нь "$ ≠ $" төрлийн өнгөний хязгаарлалтыг илэрхийлнэ.

Гаралт

Хэрвээ бүх өнгөний хязгаарлалтын $\frac{3}{4}$ нь хангагдаж чадаж байвал "YES" гэж эхний мөрөнд хэвлэнэ үү. Дараагийн $h$ ширхэг мөрөнд нүднүүдийн өнгийг илэрхийлсэн $w$ ширхэг бүхэл тоо хэвлэнэ үү.

Харин хангаж чадахгүй бол "NO" гэж хэвлэнэ үү.

Орчуулсан: Энхлут

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

Оролт
3 4 4
ENE
NNEE
NEE
ENEN
ENN
Гаралт
YES
1 1 2 2
3 4 1 1
3 3 2 4
Сэтгэгдлүүдийг ачааллаж байна...