سوال ۳ . «برنامه نویسی»

دنباله از ۰ و ۱ به طول n داریم و k  بازه مانند (a_i , a_j) داده می شود . در هر حرکت می توان یکی از k بازه را انتخاب و تمام اعداد این بازه در دنباله را از ۱ به ۰ و از ۰ به ۱ تبدیل کرد. به هر دو عدد نا برابر مجاور در دنباله نا صافی گفته می شود. حال با گرفتن N , K  و دنباله و k بازه و با توجه به عملیات های تعریف شده ٬ دنباله ی با کمترین تعداد ناصافی ایجاد شده به وسیله ی عملیات ها از دنباله اول  را در نظر بگیرید . در خروجی تعداد ناصافی های این دنباله را چاپ کنید. (n , k ≤ 10⁶)

 

راهنمایی در ادامه مطلب...

 

دنباله b را چنین تعریف میکنیم که  b_{i =} a_i XOR a_i-1 باشد. حال با هر بار تغیر دنباله ی (a_{i ,} a_j) در دنباله b تنها b_i  و b_j+1 تغییر می کنند . حال گرافی با راس های متناظر با گذاره های دنباله b تشکیل می دهیم طوری که راس متناظر با b_i تنها وقتی به b_j وصل باشد که بازه ی (a­_i , a_j-1) در بین بازه ها موجود باشد. حال هر یال نشان دهنده ی یکی از بازه هاست. و هر راس که در دنباله b برابر ۱ باشد نشان دهنده ی یک ناصافی است ٬ ‌پس حال می خواهیم با تغییر عدد دو سر یک یال تعداد راس هایی که عددشان ۱ است را کمینه کنیم... حالا با حل کردن این مساله ٬‌ مساله اصلی حل شده است. (چقد تایپش سخت بود ٬ مردم از بس alt+shift زدم!!!)