Альцгеймер
Та N ширхэг ачтай ба ач нартаа төрсөн өдрөөр нь настай нь тэнцүү тооны доллар өгдөг (шинэ төрсөн ач нартаа 0 доллар өгдөг).
Элли гэдэг нэг ач чинь төрсөн өдрөөр өгөх долларын шинэ схем бодож олсон: “Хэрэв дурын хоёр ач өөрсдийн авсан долларын хэмжээг харьцуулж үзвэл хоёулаа К тоонд хуваагддаг байна. К-гаас их бөгөөд хоёуланг нь хуваадаг бүхэл тоо олдохгүй”.
Ингэснээр ач бүр дор хаяж хуучин схемээр авч байсан доллараа авна.
0 гэдэг тоо бусад бүх тоондоо хуваагдана.
Та хөгшрөөд альцгеймерийн өвчтэй болсон тул эдгээрийг тооцоолох програм ашиглахаар шийдсэн.
Оролт
Эхний мөрөнд тестийн тоо болох Т бүхэл тоо байрлана.
Тест бүрийн эхний мөрөнд N болон K тоонууд байрлана.
Дараагийн мөрөнд ач нарын чинь насууд болох N бүхэл тоо байрлана: A1, A2, ..., AN.
Гаралт
i – р тест бүрийн хувьд “Case #i: “ гээд настай нь тэнцүү мөнгө өгч байсан дээр хамгийн багадаа ямар хэмжээний мөнгө нэмж болохыг харуулсан бүхэл тоог гаргана.
Хязгаарлалтууд
1 ≤ T ≤ 20
2 ≤ N ≤ 20
1 ≤ K ≤ 20
0 ≤ Ai ≤ 50
Жишээ
Эхний жишээн дээр та хэн нэгэнд 2-ыг өгөөд нөгөөд нь 3-ыг өгнө. Нийт 5 болно. Хуучин схемээр бол хоёулаа 2-ыг аваад нийт 4 болох байсан. Хариу нь 5-4=1 юм. Та хоёуланд нь 2-ыг өгч чадахгүй ба учир нь тэр хоёрын мөнгө хоёулаа 1-ээс гадна 2-т хуваагдах болно.
Хоёр дахь жишээн дээр нэг боломжит шийд нь 3, 7, 5, 16-г өгөх ба нийт 31 болно. Хуучин схемээр бол 28-ыг өгөх байсан тул хариу нь 31-28=3.
Гурав дахь жишээн дээр бүх мөнгө 3-т хуваагдаж байх ёстой. Нэг боломжит шийд нь 6, 21, 51 юм. Энэ нь тэдний насны нийлбэрээс 6-гаар их юм. 6, 18, 51 нь гуравт хуваагдах боловч 6, 18 хоёр нь 6-д ч бас хуваагдах тул энэ нь зөв шийд биш юм.
5
2 1
2 2
4 1
2 7 5 14
3 3
5 18 49
3 1
1 2 3
4 2
0 0 1 2
Case #1: 1
Case #2: 3
Case #3: 6
Case #4: 0
Case #5: 3
Tuesday, December 10, 2013
Facebook Hacker Cup 2013. Бодлого АААААА
AAAAAA
Элийн тоглоомын газрыг AAAAAA гэдэг ба хүмүүс маш ихээр ирдэг.
Үйлчлүүлэгчид машины зогсоол дээр урт дараалал үүсгэн зогсдог. Эл аль болох олон хүнийг зогсоол дээрээ багтаахыг хүсч байгаа. Харин хүмүүс хэтэрхий их мушгиралдсан дараалалд зогсохыг хүсдэггүй.
Зогсоолыг тэгш өнцөгт хэлбэртэй бөгөөд нүднүүдээс тогтоно гэж үзэж болно. Орох хаалга нь зүүн дээд талын буланд байрлана. Бүх дараалал эндээс эхэлнэ. Зогсоол дээр машинууд байж болох ба тэдгээрийг ‘#’ тэмдгээр тэмдэглэнэ. Үйлчлүүлэгчид машин дээр гарч чадахгүй. Бусад нүднүүдэд ‘.’ тэмдэгт байрлана. Хэрэглэгчдийн хүсэлтээр дараалал үргэлж доош болон баруун чиглэлд үргэлжилнэ. Мөн хэрэглэгчид нь нэг буулт хийсэн нь нэг дараалалд ганц ширхэг, үргэлжилсэн дээш чиглэсэн хэсэг эсвэл ганц ширхэг зүүн тийш чиглэсэн үргэлжилсэн хэсгийн аль нэг нь байж болно гэсэн нөхцөл юм. Энэ хоёр үргэлжилсэн хэсэг нэг дараалалд хоёулаа байж болохгүй.
Дараалал нь эдгээр дөрвөн чиглэлд л үргэлжилнэ. Диагоналиар явахгүй.
Сул зай бүрт ганц л үйлчлүүлэгч багтах ба дараалсан хоёр үйлчлүүлэгч хоорондоо хөрш нүднүүдэд байрлана. Дараалсан хоёр үйлчлүүлэгч хоорондоо зайтай, тасарсан байж болохгүй.
Оролт
Эхний мөрөнд тестийн тоо болох Т бүхэл тоо байрлана.
Тест бүрийн эхний мөрөнд тэгш өнцөгтийн мөр болон баганын тоог илэрхийлэх N, M бүхэл тоонууд өгөгдөнө.
Дараагийн N ширхэг мөрөнд яг M ширхэг тэмдэгт бүхий тэмдэгт мөр байрлана.
Гаралт
i-р тест бүрийн хувьд зүүн дээд өнцгөөс эхлэн байрлуулж болох хамгийн урт дарааллын хэмжээг “Case #i: “ гэсний дараа гаргана.
Хязгаарлалт
1<=T<=20 1<=N, M<=500 Тэгш өнцөгт дэх тэмдэгтүүд ‘#’ эсвэл ‘.’ байна. Зүүн дээд булангийн тэмдэгт дандаа ‘.’ байна.
Жишээ оролт
5
5 5
.....
.....
.....
.....
.....
1 10
..........
5 5
...#.
...#.
...#.
...#.
.....
3 3
..#
#.#
...
3 8
........
#.#.#.#.
#.#.#.#.
Жишээ гаралт
Case #1: 17
Case #2: 10
Case #3: 17
Case #4: 5
Case #5: 10
Элийн тоглоомын газрыг AAAAAA гэдэг ба хүмүүс маш ихээр ирдэг.
Үйлчлүүлэгчид машины зогсоол дээр урт дараалал үүсгэн зогсдог. Эл аль болох олон хүнийг зогсоол дээрээ багтаахыг хүсч байгаа. Харин хүмүүс хэтэрхий их мушгиралдсан дараалалд зогсохыг хүсдэггүй.
Зогсоолыг тэгш өнцөгт хэлбэртэй бөгөөд нүднүүдээс тогтоно гэж үзэж болно. Орох хаалга нь зүүн дээд талын буланд байрлана. Бүх дараалал эндээс эхэлнэ. Зогсоол дээр машинууд байж болох ба тэдгээрийг ‘#’ тэмдгээр тэмдэглэнэ. Үйлчлүүлэгчид машин дээр гарч чадахгүй. Бусад нүднүүдэд ‘.’ тэмдэгт байрлана. Хэрэглэгчдийн хүсэлтээр дараалал үргэлж доош болон баруун чиглэлд үргэлжилнэ. Мөн хэрэглэгчид нь нэг буулт хийсэн нь нэг дараалалд ганц ширхэг, үргэлжилсэн дээш чиглэсэн хэсэг эсвэл ганц ширхэг зүүн тийш чиглэсэн үргэлжилсэн хэсгийн аль нэг нь байж болно гэсэн нөхцөл юм. Энэ хоёр үргэлжилсэн хэсэг нэг дараалалд хоёулаа байж болохгүй.
Дараалал нь эдгээр дөрвөн чиглэлд л үргэлжилнэ. Диагоналиар явахгүй.
Сул зай бүрт ганц л үйлчлүүлэгч багтах ба дараалсан хоёр үйлчлүүлэгч хоорондоо хөрш нүднүүдэд байрлана. Дараалсан хоёр үйлчлүүлэгч хоорондоо зайтай, тасарсан байж болохгүй.
Оролт
Эхний мөрөнд тестийн тоо болох Т бүхэл тоо байрлана.
Тест бүрийн эхний мөрөнд тэгш өнцөгтийн мөр болон баганын тоог илэрхийлэх N, M бүхэл тоонууд өгөгдөнө.
Дараагийн N ширхэг мөрөнд яг M ширхэг тэмдэгт бүхий тэмдэгт мөр байрлана.
Гаралт
i-р тест бүрийн хувьд зүүн дээд өнцгөөс эхлэн байрлуулж болох хамгийн урт дарааллын хэмжээг “Case #i: “ гэсний дараа гаргана.
Хязгаарлалт
1<=T<=20 1<=N, M<=500 Тэгш өнцөгт дэх тэмдэгтүүд ‘#’ эсвэл ‘.’ байна. Зүүн дээд булангийн тэмдэгт дандаа ‘.’ байна.
Жишээ оролт
5
5 5
.....
.....
.....
.....
.....
1 10
..........
5 5
...#.
...#.
...#.
...#.
.....
3 3
..#
#.#
...
3 8
........
#.#.#.#.
#.#.#.#.
Жишээ гаралт
Case #1: 17
Case #2: 10
Case #3: 17
Case #4: 5
Case #5: 10
Subscribe to:
Posts (Atom)