Codeforces Round #804 (Div. 2)
22:55:55 |
Educational Codeforces Round 131 (Rated for Div. 2)
4 өдрийн дараа |
Codeforces Round #805 (Div. 3)
6 өдрийн дараа |
Codeforces Round #806 (Div. 4)
8 өдрийн дараа |
B. Дзи химид дуртай
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Дзи химид дуртай бөгөөд тэр химийн бодисуудыг холих дуртай.
Дзид $n$ химийн бодис байгаа бөгөөд тэднээс $m$ нь хос хосоороо урвалд ордог. Тэр химийн бодисуудыг дурын дарааллаар туршилтын хоолой руу нэг нэгээр нь хийж холих гэж байна.
Туршилтын хоолойн эрсдлийг авч үзье. Хоосон туршилтын хоолойн эрсдэл $1$ байна. Дзиг бодис нэмэх бүрд хэрвээ хоолойд энэ бодистой урвалд ордог бодис байвал хоолойн эрсдлийг 2-р үржүүлнэ. Эсрэг тохиолдолд эрсдэл нь хэвээрээ байна.
Бүх химийн бодисуудыг ямар нэг дарааллаар туршилтын хоолой руу нэг нэгээр нь хийсний дараах хамгийн их эрсдлийг ол.
Оролт
Эхний мөр нь зайгаар тусгаарлагдсан $n$, $m$ ($1 ≤ n ≤ 50; 0 ≤ m ≤ \frac{n(n-1)}{2}$) бүхэл тоонуудыг агуулна.
Дараагийн $m$ мөр бүр нь зайгаар тусгаарлагдсан $x_{i}$, $y_{i}$ $(1 ≤ x_{i} < y_{i} ≤ n)$ бүхэл тоонуудыг агуулна. Эдгээр бүхэл тоонууд нь $x_{i}$ химийн бодисыг $y_{i}$ химийн бодистой урвалд оруулж болохыг илэрхийлнэ. Химийн бодисын хос бүр хамгийн ихдээ нэг удаа оролтонд гарч ирж болно.
Бодисуудыг $1$-с $n$ хүртэл дугаарлагдсан гэж үзнэ.
Гаралт
Боломжит хамгийн их эрсдэл болох нэг бүхэл тоо хэвлэнэ.
Орчуулсан: Даариймаа
Жишээ тэстүүд
Оролт
1 0
Гаралт
1
Оролт
2 1 1 2
Гаралт
2
Оролт
3 2 1 2 2 3
Гаралт
4
Тэмдэглэл
Эхний жишээнд зөвхөн нэг аргаар холих ба эрсдэл өсөхгүй.
Хоёр дахь жишээнд, бид эхлээд $1$-р химийн бодисыг хийх, эсвэл $2$-р химийн бодисыг хийсэн ч хариулт ялгаагүй $2$ байна.
Гурав дахь жишээнд, хамгийн их эрсдэлд хүрэх дөрвөн арга байгаа: 2-1-3, 2-3-1, 1-2-3 ба 3-2-1 (химийн бодисуудыг холих дарааллын тоо).