پاسخ پرسش CF-111-D

Codeforces / Round #111 / Problem D: Edges in MST

صورت اصلی سوال :http://www.codeforces.com/contest/160/problem/D

ترجمه :

درخت پوشای کمینه (MST) : یک درخت پوشای کمینه از یک گراف وزن دار ، یک زیر درخت پوشا از آن است که مجموع وزن یال های آن کمینه باشد . واضح است که یک گراف همواره حداقل یک MST دارد و نیز می تواند چند MST داشته باشد .

یک گراف همبند وزن دار ساده به شما داده می شود . شما باید برای هر یال تعیین کنید این یال در همه MST های گراف ظاهر می شود یا در حداقل یکی از آنها ظاهر می شود یا در هیچکدام از آنها ظاهر نمی شود .

ورودی :
در خط اول ورودی دو عدد n و m داده می شود (تعداد راس ها و یال های گراف)
( , )
سپس در m خط بعدی ، مشخصات یال های گراف می آید ، در خظ i+1 ام سه عدد a_i,b_i,w_i می آید که به ترتیب دو سر یال i ام و وزن آن هستند .
 

خروجی :
m خط چاپ کنید ، در خط i ام اگر یال i ام در همه ی MST ها ظاهر میشود "any" را  ، اگر در حداقل یکی از MST ها ظاهر می شود "at least one" را و اگر در هیچکدام ظاهر نمی شود "none" را چاپ کنید .

پاسخ پرسش CF-197-C

Codeforces / Contest 197 / Problem C : Lexicographically Maximum Subsequence

صورت اصلی سوال :http://codeforces.com/contest/197/problem/C

ترجمه :
رشته s ار حروف کوچک انگلیسی داده شده ، بزرگترین زیر رشته lexicographically این رشته را بیابید .

یک زیر رشته از s تعدادی از حروف s است که به ترتیب ظاهر شدنشان در رشته در زیر رشته می آیند .

یک زیر رشته x از زیر رشته y بزرگتر است اگر اندازه x بزرگتر از y باشد در حالی که همه کاراکتر های ۱ تا |y| در دو رشته مساوی باشند یا اینکه یک مقدار r وجود داشته باشد به طوری که همه ی کاراکت های ۱ تا r در دو رشته برابر باشند و کاراکتر  r+1 ام x بزرگتر از کارکتر r+1 ام y باشد .

پاسخ پرسش CF-157-E

Codeforces / Contest 157 / Problem E : Cipher

صورت اصلی سوال : http://codeforces.com/contest/157/problem/E

ترجمه :

یک رشته ی s از حرف کوچک لاتین به ما داده می شود ، در هر مرحله می توانیم دو حرف مجاور در رشته را انتخاب کنیم و یکی را به حرف قبلی خودش و دیگری با حرف بعد از خودش تغییر دهیم . واضح است که نمی توانیم حرف a را به حرف قبل از خودش و حرف z را به حرف بعد از خودش تبدیل کنیم .

برای مثال رشته ی abc را می توانیم به رشته ی bac ، acb و یا bbb (در دو مرحله) تبدیل کنیم .

می خواهیم به ازای رشته ی s تعداد رشته هایی را بیابیم که می توان این رشته را به آن ها تبدیل کرد .

توجه کنید این رشته ها شامل خود این رشته نمی شوند .

پاسخ پرسش CF-169-C

Codeforces / Contest 169 / Porblem C : Substring and Subsequence

صورت اصلی سوال : http://codeforces.com/contest/169/problem/C

ترجمه :

دو رشته با نام های s و t داریم.

می خواهیم تعداد زوج های x و y را پیدا کنیم که دارای شرایط زیر باشند :

• x زیر رشته ی s باشد
  
• y زیر مجموعه ی t باشد
• مقادیر x و y یکسان باشند
  

توجه کنید که تعریف زیر مجموعه و زیر رشته کاملا مجزا از هم است .

زیر رشته : یعنی بخشی از یک رشته به صورت پیوسته (از کاراکتر i ام تا کاراکتر j ام).

زیر مجموعه : یعنی تعدادی از کاراکتر های یک رشته (که البته می تواند شامل کاراکتر تکراری نیز باشد)

توجه کنید که در زیر مجموعه حروف زیر مجموعه ترتیب قرار گرفتن خود در t را حفظ می کنند.