IOI 2010. Жишээ бодлого - 3. Жимс

Джек Джилл хоёр Ниагарын хүрхээнээс Ватерлоо хүртэл машинаар явж байгаа. Тэдний замд хэд хэдэн жимсний лангуунууд дайралдсан. Жимсний лангуу бүрт нэг сагс интоорыг нэг үнээр нэг сагс тоорыг бас нэг үнээр зардаг. Джек нэг сагс интоор, Джилл нэг сагс тоор авах гэж байгаа. Мөн тэд замдаа ганц л жимсний лангуун дээр зогсохыг хүсч байгаа. Нийт зардал хамгийн бага байхын тулд тэд аль жимсний лангуун дээр зогсох ёстой вэ?
Та stopat(N,C,P)гэсэн процедур бичих ёстой. N - жимсний лангуунуудын тоо. Жимсний лангуунууд 0-оос N-1 хүртлэх тоонуудаар дугаарлагдсан. C ба P нь жимсний лангуу бүр дэх интоор болон тоорын үнийг доллараар илэрхийлсэн хүснэгтүүд. C[i] нь i дугаартай лангуун дээрх нэг сагс интоорын үнэ. P[i] нь i дугаартай лангуун дээрх нэг сагс тоорын үнэ. stopat(N,C,P) процедур нь нэг нэг сагс интоор болон тоорын нийт үнэ хамгийн бага байх хамгийн эхний жимсний лангууны дугаарыг буцаах ёстой.
Даалгавар 1 [50 оноо]
N≤10 гэж үзнэ. Нэг сагс интоор болон тоорын үнэ 1-ээс 100 долларын хооронд байна.
Даалгавар 2 [50 оноо]
N≤1000 гэж үзнэ. Нэг сагс интоор болон тоорын үнэ 1-ээс 1000 долларын хооронд байна.
Заавар
- Програмчлалын болон тестчлэлийн RunC орчныг хэрэглэнэ
- Бодолтоо /home/ioi2010-contestant/fruit/ хавтсанд хадгална. Жишээг эндээс татаж авна.
- Бодолт нь дараах файлууд байж болно: fruit.c, fruit.cpp эсвэл fruit.pas
- Оролцогчийн сан: fruit.h эсвэл fruit.pas
- Шалгагчийн сан: байхгүй
- Жишээ шалгагч: grader.c, grader.cpp эсвэл grader.pas болон graderlib.pas
- Жишээ оролт: grader.in.1 grader.in.2
Шалгагч нь (C[0],P[0]), (C[1],P[1]), ... (C[N-1],P[N-1]) гэсэн хос тоонуудыг уншиж авна. Энд N нь хэдэн хос тоо байхыг заана.
- Жишээ гаралт: grader.expect.1 grader.expect.2
- Хөрвүүлэх команд: runc grader.c эсвэл runc grader.cpp эсвэл runc grader.pas
- Хөрвүүлээд ажиллуулах: gedit плаг-ин дотор програмаа бичиж дуусаад Control-R товчуудыг дарна.
- Бодолт илгээх (командын мөрнөөс): submit grader.c эсвэл submit grader.cpp эсвэл submit grader.pas
- Бодолт илгээх (gedit плаг-ин дотроос): Програмаа бичиж дуусаад Control-J товчийг дарна.
- Процессорын хугацааны хязгаарлалт: 10 секунд
- Санах ойн хязгаарлалт: 256 Мб