Yerzhan Utkelbayev

Есеп №1. (Айырмашылық)

Ограничение по времени:

1 second

Ограничение по памяти:

256 megabytes

Сізде $S$ мультижиыны бар. Мультижиынның жиыннан айырмашылығы: мультижиында сан бірнеше рет кездесуі мүмкін, ал жиында тек қана бір рет. Алғашында, мультижиында $1$-ден $n$-ге дейінгі барлық бүтін сандар бір рет кездеседі. Бір операцияға сіз мультижиыннан екі $a$ және $b$ сандарын таңдап алып, олардың абсолют айырмашылығын |$a$ - $b$| қоса аласыз. Мультижиында тек қана бір $x$ саны болуы үшін сіз кейбір операцияларды орындағыңыз келеді.

Формат входного файла

Бірінші жолда бір бүтін сан $T$ ($1 \le T \le 100$) — тесттердің саны берілген. Келесі $T$ жолда әр тесттің сипаттамасы көрсетілген: екі бүтін сандар $n$ және $x$ ($2 \le n \le 10^5, 0 \le x \le n$) беріледі. Тесттердегі барлық $n$-дердің қосындысы $5 \cdot 10^5$-нен аспайды.

Формат выходного файла

Әр тест үшін: егер $x$ санын алу мүмкін емес болса, "NO" (тырнақшасыз) шығарыңыз. Әйтпесе, ол тест үшін: егер $x$ санын алу мүмкін болса, "YES" (тырнақшасыз) шығарыңыз. Келесі $n$-$1$ жолда операцияларды орындау тәртібімен шығарыңыз. Әр операция үшін мультижиыннан таңдалатын екі бүтін санды $a$ және $b$ сандарын шығарыңыз.

Система оценки

Берілген тапсырма төрт бөліктен тұрады:

$2 \le n \le 4$. Бағалануы $12$ ұпай.
$n$ тақ сан және $x = (n + 1) / 2$. Бағалануы $15$ ұпай.
$0 \le x \le 1$. Бағалануы $23$ ұпай.
$2 \le n \le 10^5$. Бағалануы $50$ ұпай.

Пример:

Вход

2
5 1
5 0

Ответ

YES
2 3
4 5
1 1
1 0
NO

( Yerzhan Utkelbayev )
комментарий/решение олимпиада

Есеп №2. (Қараңғы бөлмелер)

Ограничение по времени:

2 seconds

Ограничение по памяти:

256 megabytes

Сізде $n$-$1$ дәліз арқылы қосылған $n$ бөлме бар. Әр бөлмеден, әр бөлмеге жетуге болатыны белгілі. Әр бөлмеде бір шам бар. $1$-ден $m$-ға дейін нөмірленген $m$ батырма бар. $i$-ші батырма $v_i$ бөлмесінен $u_i$ бөлмесіне дейінгі жолында шамдарды өшіреді немесе қосады. Әр бөлменің күйі бір санмен көрсетіледі: $0$ немесе $1$, осында $0$ шамның өшірілгенін, ал $1$ шамның қосылып тұрғанын көрсетеді. Сіздің үйіңізге Алан қонаққа келді. Нөмірлері $1$-ден $n$-ға дейінгі бөлмелердің күйлері $a_1$, $a_2$, ..., $a_n$ тең болған жағдайда, Алан өзін үйіндегіндей сезінеді. Алан өз үйіндегіндей сезінуі үшін батырмаларды қандай ретпен басу керектігін табуыңыз қажет. Және де қонақты көп күттірмес үшін осы реттің ұзындығы $10^5$ батырмадан аспауы қажет. Егер де ретті құрау мүмкін болмаса, -$1$ деп шығарыңыз. Ең алғашында барлық шамдар өшірулі тұр.

Формат входного файла

Бірінші жолда бір бүтін сан $n$ ($1 \le n \le 10^4$) — бөлмелер саны беріледі. Екінші жолда $n$ сан беріледі: $a_1$, $a_2$, ..., $a_n$ ($0 \le a_i \le 1$) тілекті бөлмелердің күйі. Келесі $n$-$1$ жол әр дәлізді екі $v$ және $u$ ($1 \le u, v \le n$) бөлмелердің нөмірлері арқылы бейнелейді, $v$ және $u$ бөлмелері арасында дәліз бар. Келесі жолда бір бүтін сан $m$ ($1 \le m \le 10^4$) — батырмалар саны беріледі. Келесі $m$ жолда батырмалар бейнеленеді. $i$-ші жол $i$-ші батырманы үш саннан $u_i$, $v_i$ және $t_i$ беріледі. $u_i$ мен $v_i$ ($1 \le u_i, v_i \le n$) бөлмелердің нөмірлері, батырманың істейтін бөлмелерін бейнелейді. Егер $t_i$ $0$-ға тең болса, бастырма шамдарды өшіреді, $1$-ге тең болғанда қосады.

Формат выходного файла

Батырмалар ретін құрау мүмкін болмаған жағдайда `-$1$'(жақшасыз) шығарыңыз. Мүмкін болған жағдайда, реттегі батырмалардың саны $l$ және келесі жолда $l$ сан — реттегі батырмалардың нөмірлерін шығарыңыз.

Система оценки

Бұл есеп бес бөлімнен тұрады:

$1 \le n \le 100, 1 \le m \le 8$. Бөлім $11$ ұпайға бағаланады.
$1 \le n,m \le 2000$ және барлық батырма үшін $t_i = 1$. Бөлім $15$ ұпайға бағаланады.
$1 \le n,m \le 500$. Бөлім $19$ ұпайға бағаланады.
$1 \le n,m \le 10^4$ және $i$-ші дәліз $i$ және $i + 1$ бөлмелерді қосады. Бөлім $25$ ұпайға бағаланады.
$1 \le n,m \le 10^4$. Бөлім $30$ ұпайға бағаланады.

Пример:

s Вход

6
1 1 0 0 1 1
1 2
1 3
3 4
3 5
4 6
4
1 2 1
2 5 1
3 4 0
1 6 1

Ответ

3
4 2 3

Вход

Ответ

-1

\Note { \center \includegraphics[width=1.0\textwidth]{samplee.eps}
} ( Yerzhan Utkelbayev )
комментарий/решение олимпиада