Muallif: Обид Синдаров
Enaga Kodirbek
Kodirbek video o'yinlar o'ynashni juda yaxshi ko'radi, lekin u shu bilan birga singlisiga ham qarab turishi kerak. U Kompyuter Ilmlari (CS) yo'nalishi talabasi bo'lgani uchun, Kodirbek ikkala ishni ham bir vaqtda bajarish yo'lini topdi: u uyiga kameralar o'rnatib, singlisi xavfsizligini nazorat qilmoqchi.
Uning uyi $n$ ta tugun va $m$ ta qirradan iborat yo'naltirilmagan graf ko'rinishida. Uning singlisi grafning qirralarida (yo'laklarida) o'ynashni yaxshi ko'radi, shuning uchun u har bir qirraning kamida bitta uchiga kamera o'rnatishi shart (ya'ni, tanlangan tugunlar to'plami vertex cover bo'lishi kerak).
Kodirbek shunday vertex cover tanlamoqchiki, undagi tanlangan tugunlar indekslari orasidagi minimal farq maksimal bo'lsin.
Aytaylik, $a_1, a_2, \dots, a_k$ tanlangan tugunlar (vertex cover) to'plami bo'lsin. Biz ushbu to'plam uchun $\min |a_i - a_j|$ qiymatini (barcha $i \neq j$ uchun) topishimiz kerak. Agar $k=1$ bo'lsa (faqat bitta tugun tanlansa), minimal farqni $n$ deb hisoblaymiz.
Sizning vazifangiz — barcha bo'lishi mumkin bo'lgan vertex cover'lar orasidan ushbu "minimal farq"ning eng katta qiymatini topishdir.
Kiruvchi ma'lumotlar
Chiquvchi ma'lumotlar
Misollar
| # | Input TXT | Output TXT |
|---|---|---|
| 1 |
7 6 1 2 1 3 1 4 1 6 2 3 5 7 |
2 |
| 2 |
3 3 1 2 1 3 1 1 |
3 |
Izoh
Ushbu grafda barcha qirralarni qoplash uchun (vertex cover) biz $\{1, 3, 7\}$ tugunlarni tanlashimiz mumkin.
- Bu to'plamdagi qo'shni tugunlar orasidagi farqlar: $|3-1|=2$, $|7-3|=4$, $|7-1|=6$.
- Minimal farq: $\text{min}(2, 4, 6) = \mathbf{2}$.
Agar biz boshqa vertex cover tanlamoqchi bo'lsak, masalan $\{1, 2, 3, 5, 7\}$ ni tanlasak, u holda $|2-1|=1$ bo'lib qoladi va minimal farq $1$ ga tushib ketadi. Bizga esa minimal farqning eng katta qiymati kerak, shuning uchun javob $2$.
Vertex Cover To'plamlari va Minimal Masofalar jadvali
| № | Vertex Cover to'plami | Minimal farq ($d_{min}$) |
| 1 | $\{1, 2, 5\}$ | $1$ |
| 2 | $\{1, 2, 7\}$ | $1$ |
| 3 | $\{1, 3, 5\}$ | $2$ |
| 4 | $\{1, 3, 7\}$ | $2$ |
| 5 | $\{1, 3, 5, 7\}$ | $2$ |
| 6 | $\{2, 3, 4, 5, 6\}$ | $1$ |
| 7 | $\{2, 3, 4, 6, 7\}$ | $1$ |
Jadvaldan ko'rinib turibdiki, har bir mumkin bo'lgan qoplama (vertex cover) uchun o'zining minimal farq qiymati mavjud. Masala shartiga ko'ra, biz ushbu minimal farqlarning ichidan eng kattasini tanlashimiz kerak:
$\mathbf{\text{max}(1, 1, 2, 2, 2, 1, 1) = 2}$