Програмчлалын олимпиадын бодлогын архив

Гэрлэж амжаагүй явнаa

Монголчууд эрт дээр үеэс өөр аймгаас эхнэр авдаг байсан уламжлалтай. Зуун аймагт N хүүтэй нэгэн өвгөн амьдардаг байжээ. Мөн баруун аймагт N охинтой нэгэн эмгэн амьдардаг байжээ. Эмгэн өвгөн 2 бие биенийхээ охид хөвгүүдийг хооронд суулгахаар шийдсэн.

Монголчууд ах захаа мэддэг улсууд болохоор тэр 2 дараах дүрмийг баримтлахаар шийджээ.

1) Хэрэв x настай хөвгүүн y настай охинтой гэрлэсэн бол x-ээс бага настай хөвгүүн y-ээс их настай охинтой гэрлэхгүй.

2) Хэрэв x настай хөвгүүн y настай охинтой гэрлэсэн бол x-ээс их настай хөвгүүн y-ээс бага настай охинтой гэрлэхгүй.

Харин нэгэн зартай мэргэч энэ 2 -ийн шийдвэрийг дуулаад хосуудийн ирээдүйг нь мэргэлжээ. Дараах дүгнэлтэнд хүрэв:

Хэрэв аливаа хосын IQ-ин абсолют ялгаа d бол тэр хосын ирээдүйн хүүхдийн IQ дараах томёогоор бодогддог аж.

IQ=15-d хэрэв d<15

IQ=0 хэрэв d>=15

Хос болгон зөвхөн нэг хүүхэдтэй гэж үзнэ. Ингээд таны даалгавар тодорхой болж байнаа. Хосуудийн хүүхдүүдийн IQ-ийн нийлбэрийг хамгийн их байлга. Эхнэр нөхөргүй үлдсэн ганц бие хүмүүс үлдэж болно.

Оролт:

эхний мөр: N

i+1 мөрөнд (i=1..N): a b c d

a- i-р хөвгүүний нас

b- i-р охины нас

c- i-р хөвгүүний IQ

d- i-р охины IQ

Гаралт: хүүхдүүдийн IQ-ийн хамгийн их нийлбэр.

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

1<=N<=1500

1<=a,b<=15005

1<=c,d<= 1000

адилхан настай хоёр хүү эсвэл охин байхгүй.

Жишээ:

Оролт:

3

3 1 10 10

2 2 5 6

1 3 15 15

Гаралт:

34