ای سی ام کار تازه وارد

در این وبلاگ مطالبی در مورد برخی الگوریتم ها و راهنمایی برای حل سوالات ارائه می گردد

ای سی ام کار تازه وارد

در این وبلاگ مطالبی در مورد برخی الگوریتم ها و راهنمایی برای حل سوالات ارائه می گردد

۱ مطلب با کلمه‌ی کلیدی «round 238» ثبت شده است

سوال 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 < 103 و q < 106


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

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

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

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

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

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


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

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

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

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

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


n , m < 105


سوال Div1 D. Hill Climbing

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

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

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

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

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


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


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

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


n , m < 105 . Xi < 107  . Yi < 1011


سوال Div1 E. Hamming Triples

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

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

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

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

n < 109 , m < 105 


۳ نظر موافقین ۰ مخالفین ۰ ۰۳ فروردين ۹۳ ، ۲۱:۲۰
رضا حسینی آشتیانی