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

مقدمه:

چهارمین دوره مسابقات شریف کدجم توسط گروه فناوری اطلاعات شریف “Sharif ICT Group”  با حمایت معاونت علمی و فناوری ریاست جمهوری، پارک علم و فناوری دانشگاه صنعتی شریف، مجموعه داتین، شرکت همراه کسب‌ و کارهای هوشمند و مجموعه ایران تلنت و مجموعه امید تک با هدف حمایت از تولید ملی، شناسایی برنامه نویسان با استعداد، افراد توانمند در کسب و کار های مبتنی بر فناوری اطلاعات، ایجاد خودباوری، اعتماد به نفس و اتصال نخبگان برنامه نویس کشور به بازار کار به تاریخ ۲۴ و ۲۵ اسفند ماه سال ۱۴۰۲ به صورت مجازی و غیر حضوری برگزار شد.

آمار و اطلاعات کلی رویداد:

• در این رویداد ۱۵۰۰ نفر از برنامه نویسان از کل کشور ثبت نام کردند گه پس از بررسی های انجام شده حدود ۱۰۰۰ نفر جهت شرکت در مسابقات پذیرش شدند.
• ۸ سوال اصلی در مسابقات مطرح شد که همه سوالات حداقل یک بار حل شد
• در کل ۳۲۰۰ کد ارسال شد و ۱۶۶۹۵ تست کیس اجرا شد
• از ۱۰۰۰ نفر شرکت کننده در مسابقات ۸۰۰ نفر کد ارسال کردند
• ۴۵۰ نفر حداقل یک سوال به یک سوال پاسخ دادند
• ۵ نفر همه سوالات را به صورت کامل و صحیح پاسخ دادند
• داوران در حدود ۱۵ ساعت آنلاین بودند و حدود ۷۹۰۰ عدد سوال که از طرف شرکت کنندگان مطرح شده بود را پاسخ دادند
• میانگین سنی شرکت کنندگان بین ۲۰ الی ۳۰ سال و حدود ۷۰ درصد آقایان و ۳۰ درصد خانم ها
• تحصیلات شرکت کنندگان: به صورت میانگین ۵۰ درصد کارشناسی، ۳۵ درصد کارشناسی ارشد و ۱۵ درصد دکتری
• ۸۵ درصد از شرکت کنندگان تمایل به بررسی موقعیت های شغلی و همکاری با حامیان رویداد را داشتند

اختتامیه و معرفی نفرات برتر

ارائه نفرات برتر، مرحله صحت سنجی

فیلم کامل افتتاحیه

نفرات راه یافته به مرحله نهایی مسابقات

ارشیا عطایی، امیر پارسا موبد، علی صفری، علیرضا کشاورز، محمد پارسا الهی منش، امیررضا پوراخوان، علی شفیعی، علی گلزار طزرجانی، دیبا رشیدی، سیدعلی الهی، مهدی وکیلی نی ریزی، محمد وحدانی، صالح الحسین ذریه، محمدحسین علی‌پور، مهدی حسینی، نیکان زمانی

نفرات برتر مسابقات:

مقام اول مشترک چهارمین دوره مسابقات برنامه نویسی آنلاین شریف کدجم، این افراد امتیازات مشابه داشتند و به صورت مشترک مقام اول مسابقات را کسب کردند

ارشیا عطایی
(دانشجو کارشناسی مهندسی کامپیوتر از دانشگاه تهران)

امیر پارسا موبد
(دانشجو کارشناسی مهندسی کامپیوتر از دانشگاه تهران)

علی صفری
(دانشجو کارشناسی مهندسی کامپیوتر از دانشگاه صنعتی شریف)

علیرضا کشاورز
(دانشجو کارشناسی مهندسی کامپیوتر از دانشگاه صنعتی شریف)

محمد پارسا الهی منش
(دانشجو کارشناسی علوم کامپیوتر از دانشگاه صنعتی شریف)

سوالات مسابقه:

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

• سوال یک: دزد
  شما می خواهید از یک جواهر فروشی سرقت کنید.
  فروشگاه جواهرات n نوع مختلف جواهر را به فروش می‌رساند و برای هر نوع از آنها ۱۰۹ جواهر یکسان دارد. یک جواهر از نوع iم، i گرم وزن و ai یورو ارزش دارد. برنامه شما دزدیدن دقیقا k جواهر با وزن کل w گرم است (شما می توانید چندین جواهر از یک نوع بدزدید).
  بیشینه ارزش ممکن کل جواهرات مسروقه به یورو چقدر است؟
  ورودی
  خط اول به ترتیب عدد صحیح n (تعداد انواع جواهرات)، عدد صحیح k (تعداد جواهراتی دزدی) و عدد صحیح w (وزن کل جواهرات دزدی) که با فاصله از هم جدا شده اند.
  خط دوم شامل n عدد صحیح که با فاصله از هم جدا شده و بیانگر ارزش یورویی هر نوع از جواهرات است.
  خروجی
  در صورتی که سرقت محدودیت های شرح داده شده در بیانیه را برآورده کند، حداکثر ارزش کل ممکن برای جواهرات مسروقه را به یورو چاپ کنید. در غیر اینصورت ۰ چاپ کند.

 

• سوال دوم: جابه جایی
  شما یک جایگشت از n عدد a1, a2, …, an دارید. همچنین یک عدد صحیح دیگر بنام x که بین ۱ و n داده می‌شود.
  در هر حرکت، می‌توانید عنصر x را با یک عنصر در فاصله فرد از سمت چپ یا راست آن جابجا کنید. به عنوان مثال، اگر x در موقعیت i باشد، می‌توانید آن را با a(i+3), a(i+1), … و a(i-3), a(i-1), … جابجا کنید.
  وظیفه شما این است که آرایه را حداکثر در ۱۰n حرکت مرتب کنید یا تصمیم بگیرید که مرتب کردن آرایه غیرممکن است.
  ورودی
  خط اول دو عدد صحیح n و x که با فاصله از هم جدا شده اند.
  خط دوم شامل n عدد صحیح a1, a2, …, an که با فاصله از هم جدا است.
  خروجی
  خط اول شامل عبارت YES اگر امکان پذیر باشد یا NO اگر امکان پذیر نباشد.
  اگر امکان مرتب کردن آرایه وجود داشت، در خط بعدی تعداد حرکات (m) را خروجی دهید.
  سپس m خط خروجی دهید، که شامل دو شاخص i و j برای جابجایی هستند. (توجه کنید که یا i یا j باید ایندکس x باشد).

 

• سوال سوم: جنگ

در جنگ جهانی دوم، متفقین مین‌های خود را بر روی زمینی که می‌توان آن‌ها را به عنوان شبکه‌ای با ابعاد N * M در نظر گرفت کاشته اند. سطرها با اعداد صحیح از ۱ تا N و ستون‌ها با اعداد صحیح از ۱ تا M شماره گذاری شده اند. هر خانه (i،j) دارای مین است اگر (i+j) بر ۲ بخش‌پذیر باشد. سایر خانه‌ها خالی هستند.
دو خانه با هم همسایه هستند اگر یک طرف و یا یک گوشه مشترک داشته باشند.  هدف شما این است که با استفاده از قوانین خاصی که سیستم مین گذاری خودکار از آنها پیروی می کند، از ردیف اول به ردیف آخر حرکت کنید.
اگر قوانین زیر رعایت شود، مین ها منفجر نمی شوند:
اگر شماره ردیف فعلی شما فرد باشد، از یک سلول با مین (یعنی سلولی که دارای مین است) تنها می‌توانید به سلول‌های مجاور با مین در ردیف بعدی حرکت کنید و به همین ترتیب، از یک سلول بدون مین (یعنی یک سلول خالی) تنها می‌توانید به سلول‌های بدون مین مجاور در ردیف بعدی حرکت کنید.
اگر شماره ردیف فعلی شما زوج باشد، می‌توانید به هر سلول مجاور در ردیف بعدی حرکت کنید، بدون توجه به وجود مین.
شما باید تعداد راه های رسیدن از ردیف ۱ به N را در مد (modulo) 109+7 بیابید. دو راه متفاوت هستند اگر حداقل یک خانه متفاوت در مسیر آنها وجود داشته باشد.
ورودی
دو عدد صحیح N و M که با فاصله از هم جدا شده اند.
خروجی
عدد صحیح تعداد راه ها با کیفیت بیان شده.

 

• سوال چهارم: درخت

به شما یک درخت داده میشود. اگر دو گره متمایز را به صورت تصادفی انتخاب کنیم احتمال اینکه فاصله بین این دو گره یک عدد اول باشد چقدر است؟
ورودی
خط اول عدد صحیح N (تعداد گره های درخت)
N-1 خط بعدی جفت عددهای صحیح a[i]  و b[i]، نشان دهنده وجود یک یال به طول ۱ بین a[i] و b[i]
خروجی
یک عدد اعشاری تا حداکثر دو رقم اعشار، گرد به نزدیک (سمت راست اعشار و سمت چپ عدد صحیح صفر ندارد.)

 

• سوال پنجم: هست و نیست

برای آرایه A با N عدد صحیح تعریف شده است:
آرایه‌های P و S را با طول N تعریف کنید، به طوری که P[i] تعداد عناصر متمایز در زیرآرایه A[1:i] و S[i] تعداد عناصر متمایز در زیرآرایه A[i:N] است.
با توجه به آرایه های داده شده P و S، تعیین کنید آیا یک آرایه A متناظر با آرایه‌های داده شده P و S وجود دارد یا خیر؟
ورودی
خط اول عدد صحیح N
خط دوم شامل P1, P2 … PN که با فاصله جدا شده اند.
خط سوم شامل S1, S2 … SN که با فاصله جدا شده اند.

 

• سوال ششم: مسیریابی

شما یک درخت دارید که از N رأس، با شماره‌گذاری ۱ تا N تشکیل شده است.
اول باید M1 عملیات انجام دهید و سپس به M2 پرسش پاسخ دهید.
توجه داشته باشید که ابتدا باید تمام عملیات‌ها را انجام دهید و سپس پس از انجام تمام عملیات‌ها، به تمامی پرسش‌ها پاسخ دهید. همچنین در ابتدا، هر یال دارای مقدار صفر است.
عملیات‌ها به صورت زیر تعریف می‌شوند:
A B C D: در مسیر بین رأس‌هایی که با شماره‌های A و B شماره‌گذاری شده‌اند، مقدار هر یال را یک واحد افزایش دهید، به جز آن‌هایی که در مسیر بین C و D واقع شده‌اند. توجه داشته باشید که بین هر زوج رأس مسیر منحصر به فردی وجود دارد، یعنی برای پیدا کردن مسیر مقادیر روی یال‌ها را در نظر نمی‌گیریم. همه چهار مقدار داده شده در ورودی متمایز خواهند بود.
پرسش‌ها به صورت زیر است:
E F: مجموع مقادیر تمام یال‌ها را در مسیر بین دو رأس متمایز با شماره‌های E و F چاپ کنید. دوباره توجه داشته باشید که مسیر منحصر به فردی وجود دارد.
ورودی:
در خط اول، سه عدد صحیح N و M1 و M2 داده خواهد شد.
در خطوط بعدی، N-1 جفت عدد صحیح جدا شده با فاصله و نشان دهنده وجود یال بین دو راس u و v، ارائه می گردد.
در M1 خط بعد، چهار عدد صحیح Ai و Bi و Ci و Di را برای عملیات ها و در M2 خط بعد از آن، دو عدد صحیح Ei و Fi را برای پرسش‌ها دریافت خواهید کرد.
توجه داشته باشید که اعداد یک خط با فاصله از هم جدا شده اند.
خروجی:
برای هر پرسش پاسخ مورد نیاز را در یک خط چاپ کنید.

• سوال هفتم: حلزون مختصاتی

شکل زیر، یک حلزون مختصاتی را نشان می‌دهد. هر حلزون مختصاتی با اندازه‌ی n از شماره‌ی یک در مرکز مختصات شروع می‌شود و طبق تصویر زیر طی مسیر می‌کند.

می خواهیم برنامه‌ای بنویسید که عدد n را از کاربر دریافت کند و سپس مختصات آن نقطه را به کاربر تحویل دهد.
ورودی:
در یک خط عدد n یا ورودی به شما داده میشود.
خروجی:
در تنها خط خروجی مختصات را جدا شده با فاصله چاپ کنید

 

• سوال هشتم: ارفاق

شما از دانشجویان ممتاز دانشگاه هستید. اما تنها در یک درس نمره قبولی نگرفته اید. استاد این درس اما با توجه به سابقه درخشان شما و شناخت کافی از احوالات تحصیل شما، قبول کرده است در صورتی که یک مسئله الگوریتمی را حل کنید، نمره قبولی مورد نیاز شما را ثبت کند.
پس تمام تلاشتان را به کار ببندید، چه بسا سرنوشت این مسابقه هم در گرو همین سوال باشد.
به شما آرایه A از اعداد صحیح و عدد صحیح K داده خواهد شد. هدف شما تقسیم آرایه به K گروه غیرخالیِ متوالیِ متمایز است به طوری که هر عنصر آرایه تنها متعلق به یک گروه باشد.
هر گروه را میتوان با دو عدد صحیح L و R به طوری که L کوچکتر مساوی R باشد مشخص کرد به این معنی که گروه شامل تمامی عناصر از Lمین تا Rمین (شامل L و R) عنصر آرایه داده شده است. هزینه چنین گروهی برابر با مقدار OR بیتی تمام عناصر گروه است.
در نهایت، هزینه یک آرایه بر اساس نحوه تقسیم بندی آن محاسبه می شود. به این گونه که برای هر تقسیم بندی، هزینه آرایه برابر است با جمع هزینه های تمام گروه های حاصل از آن تقسیم بندی.
ورودی:
عدد صحیح N و عدد صحیح K که خط اول که با فاصله از هم جدا شده اند و به ترتیب نشان دهنده اندازه آرایه و تعداد گروه است.
خط دوم شامل N عدد صحیح A₁, A₂, …, A_N که فاصله از هم جدا شده اند.