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

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

حل

CodeForces Round #238 Div.1 & Div.2

سوال A. Gravity Flip

سوال می گفت یه نفر یه جعبه طراحی کرده که میشه توش جاذبه رو از بالا به پایین به چپ به راست تغییر داد .

یه نفر میاد n ستون مربع رو توی این جعبه می زاره و جاذبه رو تغییر میده .

به عنوان خروجی وضعیت نهایی مربع هارو از ما می خواست .

n < 100

سوال B. Domino Effect

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

تو هر ثانیه هر دومینوی در حال افتادن به سمت مورد نظر میوفته و دومینوی کناری رو تحت تاثیر خودش قرار میده .

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

n < 3000

سوال Div1 A & Div2 C. Unusual Product

سوال می گفت یه ماتریس n*n داریم که درایه هاش فقط می تونن 0 یا 1 باشن .

سوال یه عمل ضرب روی این ماتریس تعریف می کنه که به هر ماتریس یه عدد ( 0 یا 1 ) نسبت میده .

سوال به ما q تا query می داد .

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

1. درایه های یک سطر داده شده flip بشه

2. درایه های یک ستون داده شده flip بشه

3. حاصل ضرب ماتریس تو خروجی چاپ بشه

n < 10³ و q < 10⁶

سوال Div1 B & Div2 D. Toy Sum

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

به این صورت که معلم از بین اعداد 1 تا 10⁶ n تا عدد رو انتخاب می کرد .

حالا نوبت شاگرد بود تا m تا عدد از بین 1 تا 10⁶ که تا به حال انتخاب نشدن انتخاب کنه تا تساوی زیر اتفاق بیوفته

اگر اعداد معلم Xi ها باشن و اعداد شاگرد Yi

SUM( Xi - 1 ) = SUM( 106 - Yj )

سوال Div1 C & Div2 E. Graph Cutting

سوال می گفت می خوایم یالهای یک گراف رو یه صورت جفت جفت کنار هم بزاریم به صورتی که

از همه یالها استفاده شده باشه

هر یال فقط در یک جفت اومده باشه

یالهای هر جفت تو یک سر مشترک باشند

n , m < 10⁵

سوال Div1 D. Hill Climbing

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

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

1. شماره قله بزرگتر از شماره قله فعلی باشه

2. از این نقطه بشه قله مقصد رو دید ( هیچ قله دیگه ای روی مسیر نباشه )

3. بین تمام قله هایی که می تونه بره ، همیشه قله با بزرگترین شماره رو انتخاب می کنه .

سوال به ما m تا query می داد تو هر query می گفت 2 نفر روی قله های شماره a و b هستند و می خواست ، کوچکترین شماره قله ای رو بدید که هردو نفر بتونن به اونجا برسند .

به عنوان ورودی محل قرار گیری مرکز تپه روی محور x ها و ارتفاع قله ی اون رو به ما میدن .

همچنین تو هر query دو شماره قله a , b

n , m < 10⁵ . Xi < 10⁷  . Yi < 10¹¹

سوال Div1 E. Hamming Triples

سوال به ما m تا رشته از 0 , 1 میده . به این صورت که هر رشته فقط می تونه به صورت صعودی یا نزولی باشه .

همچنین Hamming Distance رو بین دو رشته ، تعداد اندیس هایی تعریف می کنیم که کاراکتر متناظر اونها با هم فرق داره .

حالا سوال از ما تعداد سه تایی هایی مثل ( a , b , c ) رو می خواد که

( H(a , b ) + H( b , c ) + H( c , a ماکزیمم باشه .

n < 10⁹ , m < 10⁵ 

CodeForces Round #234 Div.2

سوال A. Inna and Choose Options

سوال می گفت یه نفر میاد 12 تا کاراکتر از {X , O} انتخاب می کنه و می خواد این کاراکترهارو به ترتیب توی یه ماتریس به سایز a*b بچینه ؛ تمام سطر های ماتریس باید کامل باشند .

سوال تمام زوج مرتب هایی مثل (a,b) رو می خواد که اگر کاراکترهارو توی ماتریسی به اندازه a*b بچینیم ، یه ستون کاملا شامل X داشته باشه .

سوال B. Inna and New Matrix of Candies

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

این بازی روی یک صفحه مستطیل به ابعاد n و m انجام میشه .

روی هر سطر دقیقا یک کوتوله و یک آبنبات قرار گرفته .

تو هر دور از بازی یه تعداد ( شاید همه ) از سطر هارو انتخاب می کنیم .

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

تو هر لحظه یک خونه به سمت راست میرن .

اولین زمانیکه یکی از کوتوله ها به یه خونه شامل آبنبات برسه یا اینکه یکی به انتهای سطر خودش برسه ، همه حرکت خودشون رو متوقف می کنن و این دور از بازی تموم میشه .

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

سوال به عنوان ورودی وضعیت صفحه بازی رو به ما میده . خونه های شامل کوتوله با حرف G و خونه های شامل آبنبات با حرف S و بقیه خونه ها با * مشخص میشن .

n,m < 1000

سوال C. Inna and Huge Candy Matrix

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

یه نفر دیگه میاد این ماتریس رو x بار 90 درجه در جهت عقربه های ساعت دوران میده و بعد از اون y مرتبه اون رو نسبت به محور تقارن عمودی بازتاب می کنه و در آخر اون رو z مرتبه 90 درجه خلاف جهت عقربه های ساعت دوران میده .

ما محل قرارگیری قبل از دوران هارو داریم و محل جدید اونها رو می خوایم .

به عنوان ورودی سایز ماتریس رو داریم n , m < 10^9

همچنین مختصات اولیه p نقطه .

سوال D. Dima and Bacteria

سوال میگه  n تا باکتری داریم که از k نوع مختلف هستند . 

n < 10^5 , k < 500

باکتری هارو با شماره های 1 تا n شماره گذاری کردیم .

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

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

در کل سوال به ما m نوع انتقال رو معرفی می کنه به این صورت که از باکتری با شماره u میشه انرژی رو به باکتری شماره v منتقل کرد با هزینه x .

یه توزیع از باکتری رو خوب میگیم اگر بشه انرژی رو بین باکتری های مشابه با هزینه صفر منتقل کرد .

به عنوان خروجی سوال از ما کمترین هزینه برای انتقال انرژی بین باکتری با انواع مختلف رو می خواد ، در صورتی که توزیع انرژی خوب باشه و در غیر این صورت No .

سوال E. Inna and Binary Logic

این سوال میگه از یه لیست شامل n عضو ، n لیست جدید می سازیم که عناطر لیست k ام معادل با انجام عمل AND روی k عضو متوالی از آرایه اولیه است .

یعنی :

A[k][i] = AND( a[i] , a[i+1] , ... , a[i+k-1] )

منظور از AND عمل منطقی ِAND است .

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

ُسوال به ما m تا query میده که تو هر کدوم مقدار یکی از اعداد آرایه اصلی تغییر می کنه .

برای هر query باید حاصل جمع جدید رو محاسبه و چاپ کنیم .

n, m , a[i] < 10^5

حل سوالات

CodeForces Round #101 Div.2

سوال A. Amusing Joke

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

زمانی که می خوابن ، یه نفر میاد و این حروف رو میاره پایین و جا به جا می کنه ( ممکنه یه کاراکتر حذف بشه و چیزه دیگه ای به جاش بیاد ) و دوباره اونها رو آویزون می کنه .

صبح که بیدار میشن می بینن که حروف به هم ریخته !

اون ها می خوان بدونن با حروفی که الان آویزون شده میشه اسمشون رو دوباره درست کنند یا نه ؟

سوال به عنوان ورودی 3 رشته به شما میده ، رشته اول اسم صاحب خونه ، رشته دوم اسم مهمان و رشته سوم ، حروفی هستند که صبح آویزون هستند .

طول رشته ها حداکثر 100 هستند .

به عنوان خروجی اگر میشه با حروف رشته سوم ، رشته اول و دوم رو ساخت ( با هم ) YES و در غیر این صورت NO رو چاپ کنید .

سوال B. Hopscotch

سوال میگه یه نفر خواب می بینه که داره "لی لی" بازی می کنه .

زمان بازی براش این سوال پیش میاد که اگر سنگ رو پرت کنه تو خونه (x , y ) ، شماره خونه ای که سنگ توش افتاده چنده ؟

همه مربع ها طول برابر a دارند .

اگر سنگ تو یه خونه افتاده بود ، شماره اون خونه چنده ؟

اگر سنگ رو مرز یه خونه باشه ، بیرون خونه فرض میشه .

سوال به عنوان ورودی اعداد صحیح x , y , a رو میده .

x| , y <= 1000000| و a < 100 خواهد بود .

به عنوان خروجی اگر سنگ تو یه خونه افتاده ، شماره اون خونه ، در غیر این صورت -1 رو چاپ کنید .

سوال C. Queue

سوال میگه n نفر تو یه بانک تو صف وایسادن و هر کسی می دونه Ai نفر بلندتر از خودش توی صف جلوتر ازش وایسادن .

کارمند بانک میره ناهار بخوره ، برای همین همه افراد از صف خارج میشن .

زمانی که دوباره کارمند شروع به کار می کنه ، افراد می خوان برگردند سر جای خودشون اما همه افراد یادشون رفته که کجا وایساده بودن . فقط مقدار Ai یادشون میاد .

سوال به عنوان ورودی اسم هر فرد و مقدار Ai رو برای اون فرد میده .

باید به هر نفر یه "قد" نسبت بدید که شرایط مساله حفظ بشه .

n < 3000 , Ai < n-1

به هر نفر باید قد Hi رو نسبت بدید .

Hi باید بین 1 تا 1,000,000,000 باشه .

Hi ها می تونن برابر باشن .

به عنوان خروجی n خط شامل اسم و قد اون فرد رو چاپ کنید .

اگر نمیشه این کار رو کرد ، -1 رو چاپ کنید .

سوال : D. Take-off Ramps

یه مسابقه اسکی برگزار شده که مسیر مسابقه یه خط مستقیم و موازی محور x هاست .

طول مسیر L متر و از 0 تا L تو جهت مثبت محور x خواهد بود .

یه نفر تو مسابقه شرکت کرده که می تونه هر متر رو تو 1 ثانیه طی کنه .

در طول مسیر n تا ramp وجود داره .

i امین ramp تو محل x قرار گرفته .

اگر از Pi متر قبل از i امید ramp دور خیز کنیم ، می تونیم به اندازه Di متر رو بپریم ، این پرش Ti ثانیه طول می کشه .

ramp ها فقط تو جهت مثبت محور x کارایی دارن ، یعنی از X-Pi باید شروع به دورخیز کنیم و از محل X تا X+Di رو بپریم .

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

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

برای هر ramp می دونیم که X+Di از L بیشتر نخواهد شد .

به عنوان ورودی n , L و مشخصات ramp هارو بگیرید .

به عنوان خروجی کمترین زمان برای طی کردن مسیر و همچنین تعداد ramp هایی که استفاده کردید و شماره ramp هارو چاپ کنید .

سوال E. Clearing Up

سوال میگه 2 نفر میرن مسافرت نوروزی و وقتی بر می گردن به شهرشون ، می بینن که برف اومده و همه جاده ها بسته شده .

تو شهر n تا کلبه وجود داره ، این 2 نفر تصمیم می گیرن برف یه تعداد از این جاده هارو پاک کنن ، به طوری که از هر کلبه فقط بشه با یه مسیر ساده به هر کلبه دیگه ای رفت .

تو شهر 2 نوع جاده وجود داره ، باریک و پهن .

نفر اول فقط می تونه جاده های پهن رو تمیز کنه و نفر دوم جاده های باریک .

این دو نفر می خوان ببینن که میشه این کار رو کرد ، به طوری که تعداد جاده هایی که هر کسی تمیز می کنه ، برابر باشه .

به عنوان ورودی n و m تعداد کلبه ها و تعداد جاده ها رو میده .

تو m خط بعدی ، مشخصات هر جاده رو میده .

n < 1000 , m < 100,000

به عنوان خروجی اگه میشه این کار رو کرد تعداد جاده ها و همچنین شماره جاده ها رو چاپ کنید ، در غیر این صورت -1 رو چاپ کنید .

حل سوالات