CodeForces Round #236 Div.1 & Div.2

سوال Div2 A. Nuts

سوال میگه یه نفر می خواد a تا آیتم رو توی یه سری جعبه بزاره که تو هر قسمت از جعبه حداکثر v تا آیتم باشه .

در شروع کار طرف b تا divisor ( جداکننده ) داره . اگر در جعبه ای x جداکننده بزاره ، جعبه به x+1

قسمت تقسیم میشه . (تو حالت اولیه فرض میشه که جعبه 1 قسمت داره )

تو هر جعبه حداکثر میشه k تا جداکننده گذاشت .

سوال به ما مقادیر k , a , b , v رو میده و کمترین تعداد جعبه هایی که لازمه تا همه آیتم هارو توش قرار بدیم رو می خواد .

k , a , b , v < 1000

سوال Div2 B. Trees in a Row

سوال به ما یه دنباله از اعداد به طول N میده و میگه می خوایم تبدیلش کنیم به یه تصاعد حسابی با قدرنسبت K تبدیل کنیم .

تو هر لحظه می تونیم یک عدد رو به هر اندازه ای کاهش یا افزایش بدیم ( بعد از انجام عمل باید عدد مثبت باقی بمونه )

سوال از ما کمترین تعداد عمل لازم برای تبدیل دنباله به تصاعد رو می خواد .

N , K , a_i < 1000

سوال Div1 A & Div2 C. Searching for Graph

یک گراف با n راس رو p-interesting میگیم اگر

1. دقیقا p+2*n یال داشته باشه

2. گراف طوقه و یال موازی نداشته باشه

3. به ازای هر زیر گراف با k راس از گراف ، زیرگراف حاصله حداکثر p+2*k یال داشته باشه

سوال به ما عددهای n , p رو میده و از ما می خواد یه گراف با شرایط فوق تولید و چاپ کنیم .

سوال Div1 B & Div2 D. Upgrading Array

یه دنباله N عضوی داریم .

برای یه دنباله تابع f رو به این صورت تعریف می کنیم .

f( a₁ , ... , a_n ) = SUM( f( a_i ) )

f( a_i ) = تعداد عوامل اول خوب - تعداد عوامل اول بد

سوال به ما یه لیست از اعداد اول بد میده ؛ بقیه خوب فرض میشن .

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

تو هر بار اندیسی مثل i رو انتخاب می کنیم و i عضو اول دنباله رو به ( GCD( a₁ , ... , a_i تقسیم می کنیم .

سوال از ما بیشترین مقدار ممکن برای تابع f رو می خواد .

N < 5000

سوال Div1 C & Div2 E. Strictly Positive Matrix

سوال به ما یه ماتریس n*n به درایه های نامنفی میده و می خواد ببینه که آیا عددی مثل k وجود داره که توان k ام از ماتریس درایه هایی تماما مثبت داشته باشه ؟

n < 2000

سوال Div1 D. Beautiful Pairs of Numbers

سوال از ما تعداد دنباله های k عضوی از جفت ها رو می خواد که

1. 1 <= a₁ <= b₁ < a₂ <= b₂ < ... < a_k <= b_k <= n

2. b_i - a_i ها همگی متمایز باشند

سوال به ما t تست میده تا پردازش کنیم .

تو هر تست n , k رو میده و تعداد دنباله رو می خواد .

t < 2 * 105 و n , k < 1000

سوال Div1 E. Two Rooted Trees

هنوز حلش نکردم !

حل