E. Аваргуудын лиг

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Энэ намар ОХУ-н хоёр баг дэлхийн хамгийн нэр хүндтэй хөлбөмбөгийн клубын тэмцээн болох UEFA аваргуудын лигийн группийн шатанд өрсөлдөхөөр ирж байна. Одоо уг багууд групп шатанд тоглоод эхэлсэн ба хасагдах шатанд өрсөлдөхөөр тэмцэж байна. Энэ бодлогод бид багуудыг группүүдэд эрэмбэлэх үйл явц буюу сугалааны үеийг сонирхоно.

Сугалах үйл явц нь дараах байдлаар явагддаг (энэ бодлогод тодорхойлогдсон дүрмүүд бодит амьдрал дээрхтэй харьцуулахад илүү хялбар болно). Групп шатанд $n$ баг оролцоно гэж үзье ($n$ нь дөрөвт хуваагдана). Багууд дөрвөн группт хуваагдах ёстой. Групп дахь багуудын тоог $m$ () гэж тэмдэглэе. Баг бүр өмнөх амжилтыг нь тодорхойлох бүхэл тоо буюу зэрэглэлтэй. Багууд зэрэглэлийнхээ буурах дарааллаар эрэмбэлэгдэнэ (ямар ч хоёр баг ижил зэрэглэлтэй байхгүй).

Үүний дараа тус бүртээ $m$ баг агуулах дөрвөн сагс үүсгэнэ. Өндөр зэрэглэлтэй эхний $m$ баг эхний сагсанд, дараагийн $m$ баг хоёр дахь сагсанд гээд цааш үргэлжилнэ.

Ингээд дараах үйл явц $m - 1$ удаа давтагдана. Сагс бүрээс нэг багийг буюу эхлээд эхний сагс, тэгээд хоёрдугаар сагс, гуравдугаар сагс, дөрөвдүгээр сагс бүрээс нэг багийг санамсаргүйгээр сонгоно. Сонгогдсон багууд нэг групп үүсгэх ба үүний дараа уг багуудыг сагснаас хасна.

Яг ийм $(m - 1)$ үйлдэл хийгдсэний дараа сагснуудад дөрвөн баг үлдэх ба эдгээр багууд сүүлийн группийг үүсгэнэ.

Бодит сугалаанд сагснаас санамсаргүйгээр багуудыг сонгох ажлыг өмнөх үеийн алдартай хөлбөмбөгчид гүйцэтгэдэг. Харин бид дараах бүтэцтэй санамсаргүй тоо үүсгэгч ашиглана. Энэ үүсгэгчийн параметрууд нь эерэг дөрвөн бүхэл тоо $x, a, b, c$ байна. Санамсаргүй тоо үүсгэгчийг дуудах бүрт дараах үйлдлүүдийг боловсруулна:

  • тооцоолно;
  • $x$ параметрийг $y$ утгаар солино ( оноох);
  • санамсаргүй үүсгэсэн $x$ тоог буцаана.

үйлдэл нь хуваалтын дараах үлдэгдлийг авна гэсэн үг: , .

Санамсаргүй тоо үүсгэгчийг сугалаанд дараах байдлаар ашиглана: сагснаас санамсаргүйгээр баг сонгох шаардлага гарах бүрт үүсгэгч санамсаргүй тоо $k$-г үүсгэнэ. Сагсанд үлдэж буй багуудыг зэрэглэлийнх нь буурах дарааллаар $0$-c $s - 1$ хүртэл дугаарлагдсан гэж үзнэ, энд $s$ нь сагсны одоо байгаа хэмжээ байна. Тэгээд дугаартай багийг сагснаас сонгоно.

Багуудын жагсаалт болон санамсаргүй үүсгэгчийн параметрууд өгөгдсөн бол сугалааны үр дүнг тодорхойл.

Оролт

Оролтын эхний мөрөнд бүхэл тоо $n$ ($4 ≤ n ≤ 64$, $n$ нь дөрөвт хуваагдана) байх ба эрэмбэлэлтэнд оролцох багуудын тоо юм. Хоёр дахь мөрөнд зайгаар тусгаарлагдсан дөрвөн бүхэл тоо $x, a, b, c$ ($1 ≤ x, a, b, c ≤ 1000$) байх буюу санамсаргүй тоо үүсгэгчийн параметрууд юм. Дараагийн $n$ мөр бүрт нэг багийг тодорхойлно. Нэг тодорхойлолт нь багийн нэр болон зэрэглэлээс тогтох ба зайгаар тусгаарлагдана. Багийн нэр нь Англи цагаан толгойн том болон жижиг үсгээс бүрдэх ба 1-с 20 хүртэлх тэмдэгтийн урттай байна. Багийн зэрэглэл нь 0-с 1000 хүртэлх бүхэл тоо байна. Бүх багуудын нэр болон зэрэглэл нь ялгаатай байна.

Гаралт

Багуудыг группүүдэд хуваасан хуваалтыг хэвлэ. Группүүдийг эрэмбэлэлтээс үүссэн дарааллар нь хэвлэ. Группүүдийг $'A'$-с эхлээд Англи цагаан толгойн дараалласан том үсгүүдээр дугаарла. Групп бүрийн дотор багуудын нэрийг зэрэглэлийнх нь буурах дарааллаар хэвлэх ба нэг мөрөнд нэг нэр байна. Гаралтын форматыг илүү сайн ойлгохын тулд жишээнүүдийг харна уу.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
8
1 3 1 7
Barcelona 158
Milan 90
Spartak 46
Anderlecht 48
Celtic 32
Benfica 87
Zenit 79
Malaga 16
Гаралт
Group A:
Barcelona
Benfica
Spartak
Celtic
Group B:
Milan
Zenit
Anderlecht
Malaga

Тэмдэглэл

Өгөгдсөн жишээн дээр санамсаргүй тоо үүсгэгчийг дөрвөн удаа дуудна:

  • ,
  • ,
  • ,
  • .
Сэтгэгдлүүдийг ачааллаж байна...