IOI 2010. Жишээ бодлого - 2. Телешоу

Джек Джилл хоёр телешоунд оролцож байгаа тэднийг хоёр тусдаа өрөөнд оруулан тус бүрт нь 1-ээс N хүртлэх тооноос нэг нэгийг өгчээ.
Өрөө бүрт улаан ба ногоон товч байх ба улаан товчийг дарахад нөгөө өрөөнд улаан гэрэл, ногоон товчийг дарахад нөгөө өрөөнд ногоон гэрэл асна.
Джек эхний үйлдлийг хийнэ. Тэр улаан, ногоон хоёр товчны аль нэгийг дарахад Джиллийн байгаа өрөөнд харгалзан өнгийн гэрэл асна. Үүний дараа Джилл өөрийн хоёр товчны нэгийг дарах гэх мэтээр шоу үргэлжилнэ.
Джек Джилл хоёрын аль аль нь хоёулаа ижил тоо авсан эсэхийгээ тодорхойлох зорилготой. Джек Джилл хоёрын аль нэг нь Ижил! эсвэл Ялгаатай! гэж хашгирсан тохиолдолд тоглоом дуусна.
Таны хийх ажил бол уг тоглоомыг хоорондоо тоглох jack ба jill гэсэн хоёр дэд програм бичих явдал юм. Телевизийн хөтлөгчийн үүргийг gameshow програм гүйцэтгэх ба уг програмыг IOI-ын зохион байгуулагчид бэлдсэн байгаа.
Джек jackstart(N,K) ба jacksturn(C) гэсэн хоёр үйлдлийг гүйцэтгэнэ(ДжекЭхлэх, ДжекийнЭэлж). Джилл мөн jillstart(N,L) ба jillsturn(C) гэсэн хоёр үйлдлийг гүйцэтгэнэ (ДжиллЭхлэх, ДжиллийнЭэлж). jackstart(N,K) процедурыг шалгагч тоглолтын эхэнд ганц удаа дуудах ба N тоо нь дээр өгүүлсэн тоо, К нь Джекийн нууц дугаар бөгөөд утга нь 1-ээс N-ийн хооронд байна. jillstart(N,L) процедурыг мөн тоглоомын эхэнд дуудах ба N болон Джиллийн нууц дугаар L-ийг зааж өгнө. Үүний дараа jacksturn(C) болон jillsturn(C) процедурууд jacksturn(C)-ээс эхлэн ээлжлэн дуудагдана.
C параметр нь бүхэл тоо ба нөгөө тоглогчийн дарсан товчны өнгийг илэрхийлнэ. C=0 гэдэг нь ямар ч товч дараагүй гэсэн үг ба энэ нь зөвхөн jacksturn(C) процедурын хамгийн эхний дуудалтан дээр хэрэглэгдэнэ. C=1 нь ногоон, C=2 нь улаан товч дарсан гэсэн үг.
jacksturn ба jillsturn процедурууд дараах утгуудыг буцаах ёстой:
- ногоон товчийг дарсан бол 1
- улаан товчийг дарсан бол 2
- Хэрэв Джек, Джилл хоёрын нэг нь K, L хоёр ижил гэдгийг мэдсэн бол 3
- Хэрэв Джек, Джилл хоёрын нэг нь K, L хоёр ялгаатай гэдгийг мэдсэн бол 4
Тайлбар: Джек, Джилл хоёр дээр тайлбарласан аргаар л хоорондоо харилцана. Хувьсагчаар, файлаар болон сүлжээ ашиглан хоорондоо харилцахыг хориглоно. С, С++ хэлэнд тогтмол хувьсагчдыг static гэж зарласнаар уг хувьсагчийг процедур хооронд ашиглахаас сэргийлэх ба Джек болон Джиллд өмнөх утгыг нь сануулж болно. Паскаль хэлэнд тогтмол хувсагчдыг бодолтын файлынхаа implementation хэсэгт зарлаж болно.
Даалгавар 1
N=10 үед ямар нэг зөв стратегийг хэрэгжүүл. Доор байгаа жишээ бодолтонд энэ даалгаврыг биелүүлсэн байгаа.
Даалгавар 2
N=10 үед jacksturn болон jillsturn процедуруудын дуудалтын нийт тоо 10-аас бага байхаар ямар нэг зөв стратегийг хэрэгжүүл.
Даалгавар 3
N=10 үед jacksturn болон jillsturn процедуруудын дуудалтын нийт тоо 5-аас бага байхаар ямар нэг зөв стратегийг хэрэгжүүл.
Даалгавар 4
N≤1,000,000,000 үед 10 секундын дотор хариугаа гаргах ямар нэг зөв стратегийг хэрэгжүүл.
Заавар
- Програмчлалын болон тестчлэлийн RunC орчныг хэрэглэнэ
- Бодолтоо /home/ioi2010-contestant/gameshow/ хавтсанд хадгална. Энд дарж жишээ бодолтыг татаж авна.
- Бодолтын файлын нэрүүд:
--jack.cpp, jack.c эсвэл jack.pas
--jill.cpp, jill.c эсвэл jill.pas
- Оролцогчийн сан
--jack.h эсвэл jack.pas
--jill.h эсвэл jill.pas
- Шалгагчийн сан: байхгүй
- Жишээ шалгагч: grader.c, grader.cpp эсвэл grader.pas
- Жишээ шалгагчийн оролт: grader.in.1 grader.in.2 ...
Тайлбар: Шалгагч нь N, K, L-ийг гараас авна.
- Жишаа шалгагчийн гаралт: grader.expect.1 grader.expect.2 ...
- Хөрвүүлээд ажиллуулах(командын мөрнөөс): runc grader.c эсвэл runc grader.cpp эсвэл runc grader.pas
- Хөрвүүлээд ажиллуулах(gedit плаг-ин дотроос): gedit плаг-ин дотор програмаа бичиж дуусаад Control-R товчуудыг дарна.
- Бодолт илгээх (командын мөрнөөс): submit grader.c эсвэл submit grader.cpp эсвэл submit grader.pas
- Бодолт илгээх (gedit плаг-ин дотроос): Програмаа бичиж дуусаад Control-J товчийг дарна.
- Процессорын хугацааны хязгаарлалт: 10 секунд
- Санах ойн хязгаарлалт: 256 Мб