АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

N ширхэг элементтэй A, B массивуудыг авч үзье. А массивын элементүүдийг дотор нь, мөн мөн В массивын элементүүдийг дотор нь сэлгэн байрыг өөрчилсний дүнд A’, B’ массивуудыг дараах нөхцөлтэйгээр үүсгэж болох эсэхийг тооцоолох шаардлагатай болсон.  Өөрөөр хэлбэл: A’[i]+B’[i]>=К буюу үүссэн хоёр массивын харгалзах элемент бүрийн нийлбэр нь өгөгдсөн К тооноос бүгд их байхаар үүсч болох эсэхийг тогтоохыг зорьж байгаа.

Жишээлбэл: А=[0,1],  B=[0,2]  K=1 гэж өгөгдсөн гэвэл A’=[0,1], B’=[ 2,0] гэж үүсгэвэл 0+2>=1, 1+0>=1 буюу ийм байдлаар үүсгэж болж байгаа нь харагдаж байна.

Тэгвэл чамд N ширхэг элемент бүхий ижил урттай A, B массивуудаас тогтох Q ширхэг асуулга бүхий тестүүд өгөгдсөн бол тэдгээр асуулга бүрд тухайн массивын элементүүдийг сэлгэн дээрх нөхцөлийг хангах A’, B’ массивыг үүсгэж болж байвал YES, үгүй бол NO гэж хэвлэнэ үү.

Оролтын хэлбэр:

Эхний мөрөнд асуулгын тоо Q тоо өгөгдөнө.

Асуулга бүр нь дараах 3 хэсгээс бүрдэнэ.

• N, K тоонууд асуулгын эхний мөрөнд өгөгдөнө.
• Асуулгын хоёрдугаар мөрөнд A массивын элементүүд
• Асуулгын гуравдугаар мөрөнд B массивын элементүүд болох N ширхэг тоонууд тус тус зайгаар тусгаарлагдан өгөгдөнө.

Хязгаарлалт:

 1<=Q<=10

1<=N<=1000

1<=k<=10^9  (10-ийн 9 зэрэгт)

0<=A[i], B[i] <=10^9

Гаралтын хэлбэр:

Асуулга бүрд харгалзах YES, эсвэл NO гэсэн хариултыг тус бүр шинэ мөрөнд хэвлэнэ.

Жишээ Оролт

2

3 10

2 1 3

7 8 9

4 5

1 2 2 1

3 3 3 4

Жишээ Гаралт

YES

NO

Тайлбар:

Эхний асуулгын хувьд:

N= 3,  A=[2, 1, 3],   B=[7, 8, 9],  K=10 байна. Тэгвэл A’=[1,2,3]  B’=[9,8,7] гэж үүсгэвэл

1+9>=K,  2+8>=K,  3+7>=K гэсэн нөхцөлийг хангаж байгаа тул YES гэж хэвлэсэн байна.

Хоёрдугаар асуулгын хувьд:

N=4  K=5  A=[1, 2, 2, 1]  B=[3, 3, 3, 4]   байгаа тул B массивын 3 тооны ядаж аль нэг дээр А массивын 1 гэсэн тоо нэмэгдэж 4 болох нь гарцаагүй учраас бүх нийлбэр өгсөн нөхцөлийг хангаж чадахгүй болох нь харагдаж байгаа учраас NO гэсэн хариултыг хэвлэж байна.

Орчуулсан : Хөвсгөл аймгийн Ирээдүй сургуулийн багш Д.Батмөнх