پاسخ - SGU 155

متن اصلی سوال : http://acm.sgu.ru/problem.php?contest=0&problem=155

 

ترجمه :

یک درخت BST ، یک درخت ریشه دار است که هر راس در آن حداکثر دو فرزند دارد و کلید تمام راس های زیر درخت سمت چپ هر راس از کلید آن راس کوچکتر و کلید تمام راس های زیر درخت سمت راست هر راس از آن بزرگتر اند .

درخت cartesian یک نوع خاص از درخت های BST است که در آن هر راس دو کلید دارد و کلید دوم هر راس از کلید دوم همه راس هایی که در زیر درخت آن هستند کوچک تر است .

به عبارت دیگر اگر کلید اول راس شماره i را a_i و کلید دوم راس شماره i را b_i بنامیم شرط های زیر در درخت cartesian برقرار است :

1. به ازای هر راس j در زیر درخت سمت چپ راس i‌ :

a_i>a_j

2. به ازای هر راس j در زیر درخت سمت راست راس i :

a_i<a_j

3. به ازای هر راس j در زیر درخت راس i :

b_i<b_j

 

به شما n راس داده می شود ، اگه ممکن است یک درخت cartesian با این راس های بسازید آن را در خروجی چاپ کنید در غیر این صورت در خروجی اعلام کنید این کار غیر ممکن است .

 

ورودی :

در خط اول ورودی عدد n داده می شود

در n خط بعدی در خط i ام دو عدد کلید های اول و دوم راس i-1 ام داده می شود .

هیچ دو کلیدی عدد یکسان ندارد .

 

خروجی :

اگر نمی توان با راس های داده شده یک درخت cartesian ساخت در تنها خط خروجی عبارت NO را چاپ کنید در غیر این صورت در خط اول خروجی عبارت YES و در n خط بعدی در خط i ام سه عدد شماره راس پدر راس i ، فرزند سمت چپ و فرزند سمت راست راس i را چاپ کنید .

اگر راس i هیچ پدر یا هیچ فرزندی نداشت به جای عدد آنها صفر چاپ کنید .

 

ورودی نمونه :

7 
5 4 
2 2 
3 9 
0 5 
1 3 
6 6 
4 11 

خروجی نمونه :

YES 
2 3 6 
0 5 1 
1 0 7 
5 0 0 
2 4 0 
1 0 0 
3 0 0 

 

---

راهنمایی :

1 . همیشه می توان یک درخت با شرایط مسئله ساخت.

2 . راس ای که کلید دوم آن از بقیه راس ها کمتر است به عنوان ریشه قرار می گیرید .

 

شرح راه حل :

به زودی ...

کد ++C