مسابقات سراسری برنامه نویسی حلی نت - مرحله مقدماتی (سوالات، راهنمایی و راه حل)

سلام به تمامی دوستان.

مسابقات حلی نت هم از روز دوشنبه ۲۷ خرداد با شروع مسابقه آزمایشی کلید خورد. در این مسابقه که تا ساعت ۱۷ سه شنبه ادامه داشت از سوال های مرحله حضوری ششمین دوره حلی نت استفاده شد تا گروه ها با محیط مسابقه آشنایی پیدا کنند. پس از آن مسابقه اصلی مرحله اول برگزار شد که طی آن گروه های رده ب روز چهارشنبه ۲۹ خرداد و گروه های رده الف روز پنجشنبه ۳۰ خرداد به رقابت پرداختند. گروه NCP نیز رتیه ۴ رده الف را به خود اختصاص داد.

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

سوال اول - حیاط مدرسه

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

کد برنامه را می توانید از اینجا دریافت کنید.

سوال دوم - برادر علی

بزودی

سوال سوم - گردنبند

اعداد ۱ تا ۴ به ترتیب روی محیط یک دایره نوشته شده اند. فردی از یک نقطه واقع بر محیط دایره شروع به گردش می کند و طی حرکت خود اعداد دیده شده را به ترتیب دیده شدن یادداشت می نماید و پس از گردش کامل به مکان اولیه خود باز می گردد. مسئله دنباله ای تشکیل شده از اعداد ۱ تا ۴ را به شما می دهد. شما باید تشخیص دهید که آیا این دنباله می تواند جزو دنباله های یادداشت شده باشد.

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

کد برنامه را می توانید از اینجا دریافت کنید.

سوال چهارم - ساختمانها و تیر

n ساختمان در یک صفحه وجود دارد که ارتفاع و عرض و در نتیجه محل قرارگیری آنها مشخص است. تیری به نقطه ای از صفحه برخورد می کند. وظیفه ما تشخیص خانه ایست که تیر به آن اصابت کرده است.

از خانه اول شروع کرده و تا خانه nام پیش میرویم. در هر مرحله چک می کنیم که آیا تیر به خانه iام اصابت کرده است یا خیر.

کد برنامه را می توانید از اینجا دریافت کنید.

سوال پنجم - مامور خواب آلود

برای حل مسئله برای هر دو سطر متوالی شرط زیر را چک میکنیم. اگر این شرط حداقل یکبار برقرار شود جواب yes و در غیر انصورت no است.

250 - P1 + 205 - P2 <= T2 - T1

کد برنامه را می توانید از اینجا دریافت کنید.

سوال ششم - کک جهش یافته

عمل A برای یک مجموعه به اینصورت تعریف می شود: یک عدد از مجموعه را انتخاب کرده و آنرا در -1 ضرب میکنیم.

مجموعه ای از اعداد به شما ارائه شده است. شما باید کمترین تعداد عمل A را بیابید در صورتی که پس از انجام آن هر عدد با عدد قبلی و بعدی خود در مجموعه بیشترین تفاضل مثبت را دارا باشد. (معیار عدد قبلی و بعدی ترتیب گرفتن ورودی است)

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

کد برنامه را می توانید از اینجا دریافت کنید.

سوال هفتم - فاکتوریل

دو عدد A و B به شما داده شده است. خواسته شده است ب.م.م A! و B

B, A < 100

مشخص است که جواب بین بازه ۱ تا B است. از اینرو در [1, B] به دنبال بزرگترین عددی میگردیم که هم بر A! و هم بر B بخش پذیر باشد.

اما از آنجا که 100! (بزرگترین حالت A!) عددی بسیار بزرگ است برای تشخیص بخش پذیری بر A! از لم باقی مانده ها استفاده میکنیم.

کد برنامه را می توانید از اینجا دریافت کنید.

سوال هشتم - سربازان

یک عدد k و یک رشته حاوی ۰ و ۱ به شما داده شده است. مسئله از شما طول کوتاهترین زیر رشته ای را میخواهد که حداقل k تا ۱ و حداقل k تا ۰ داشته باشد.

فرض کنید کوتاهترین زیررشته که شرط فوق را داراست و به کاراکتر iام رشته اصلی ختم میشود موجود است. در این حالت a اندیس (در رشته اصلی) کاراکتر ابتدایی این زیررشته و t0 تعدادصفر های زیررشته و t1 تعداد یک های آن است. برای پیدا کردن کوتاهترین زیررشته که شرط فوق را داراست و به کاراکتر (i + 1)ام ختم میشود به اینصورت عمل میکنیم: اگر کاراکتر (i + 1) رشته اصلی مساوی یک است به t1 و اگر مساوی با صفر است به t0 یک واحد اضافه میکنیم.

در این مرحله عمل زیر را تا هنگامی که شرط سوال (تعداد یکها و صفرها) بهم نخورد انجام میدهیم: اگر کاراکتر aام رشته اصلی مساوی یک است از t1 و اگر مساوی با صفر است از t0 یک واحد کم میکنیم. سپس یک واحد به a می افزاییم.

با اتمام مرحله پیش کوتاهترین زیررشته ای که شرط موردنظر را داراست و به کاراکتر (i + 1)ام ختم میشود به دست می آید به طوری که a ابتدای آن زیررشته است. به همین ترتیب میتوان زیررشته موردنظر که به i + 2 ختم میشود را یافت و به این شکل ادامه داد.

پس نتیجه میگیریم با داشتن کوتاهترین اولین زیررشته (به ترتیب صفتها دقت شود) کوتاهترین زیررشته موردنظر  که به کاراکتر دلخواه jام ختم میشود را به دست آورد. بدین شکل میان زیررشته های به دست آمده باید به دنبال کوتاهترین آنها باشیم. این برنامه را میتوان با پیاده سازی صحیح با order طول رشته حل کرد.

کد برنامه را می توانید از اینجا دریافت کنید.

تهیه شده توسط کیارش گل زردی و حسن پزشک

سوالات را نیز می توانید از اینجا دریافت نمائید.

اصلاحیه سوالات: 

۱. در سوال ۸ حداکثر طول رشته ۱۰ به توان ۶ است.

۱. در تست اول سوال ۸ طول رشته ۱۴ است.

اگر نظری راجع به راه حلهای ارائه شده و یا راه حل خود دارید در فسمت نظرات مطرح کنید.

موفق و سربلند باشید.