پاسخ - SGU 101
متن اصلی سوال : http://acm.sgu.ru/problem.php?contest=0&problem=101
ترجمه متن سوال :
تعدادی مستطیل 1*2 داریم (دمینو) که در هر خانه آن یک عدد نوشته شده . می خواهیم این دمینو ها را جوری کنار هم بچینیم که خانه های مجاور دمینو های مختلف یک عدد داشته باشند .
1- مجاز به چرخاندن دمینو ها هم هستیم
2- عدد های رو دمینو ها از 0 تا 6 هستند .
وظیفه ما این است که جوری دمینو ها را در یک خط کنار هم بچینیم که هز دو دمینوی مجاور عدد های برابری داشته باشند ...
ورودی :
در خط اول ورودی N ، تعداد دمینو ها داده می شود
ور در N خط بعدی عدد ها ی نوشته شده روی دومینو ها به ترتیب می آید (در خط i+1 عدد های دمینوی iام می آید)
خروجی :
در صورتی که این کار غیر ممکن بود بود “No solution”را چاپ کنید در غیر این صورت شماره ی دمینو ها را به ترتیب مناسب بیان کنید و اگر دمینوایی را نچرخانده بودید "+" ور غیر این صورت "-" را چاپ کنید .
مثال(مهم) :
ورودی نمونه :
5 1 2 2 4 2 4 6 4 2 1
خروجی نمونه :
2 - 5 + 1 + 3 + 4 -
شرح راه حل : با بهره گیری از الگوریتم تور اویلری (Eulerian trail) سوال را حل می کنیم ...
