خانه توسعه‌دهنده با کوئرا | توسعه‌دهنده مسابقات و رویدادها راهنمایی سؤالات آزمون ورودی سامرکمپ ستون

راهنمایی سؤالات آزمون ورودی سامرکمپ ستون

۲۸ خرداد ۱۴۰۱

زمان مطالعه: 4 دقیقه

1211

سلام!

امیدواریم که از سؤالات آزمون ورودی سامرکمپ ستون لذت برده باشید. در ادامه راه‌حل‌های سؤالات مسابقه توضیح داده شدند.

در صورتی که متوجه راه‌حلی نشدید، می‌تونید در بخش نظرات، سؤالات و ابهام‌های خودتون رو مطرح کنید. همچنین اگه راه‌حل دیگه‌ای برای سؤالات دارید، خوشحال می‌شیم که راه‌حلتون رو در بخش نظرات با ما و دوستانتون به اشتراک بذارید.

فهرست مطالب

قاشق و چنگال

اگر بشقاب‌ها را از $1$ تا $n$ به‌ترتیب شماره‌گذاری کنیم، برای هر $i$ از $1$ تا $n$ ، کنار بشقاب $i$ ام چنگال یا قاشق $t_i$ و $t_{i + n}$ قرار می‌گیرد. پس زمانی کنار بشقاب $i$ هم قاشق و هم چنگال قرار دارد که $t_i \neq t_{i + n}$ باشد. کافی است این مورد را با ایجاد یک حلقه بررسی کنید.

پیچیدگی زمانی:‌ $O(n)$

خودپرداز خراب

فرض کنید $dp_i$ کمترین تعداد عملیاتی باشد که برای نوشتن $i$ رقمِ اولِ عدد $n$ نیاز داریم.

به‌عنوان حالت پایه می‌دانیم $dp_0 = 0$ است. اگر رقمِ $i$ ام عددِ $n$ را با $n_i$ نشان دهیم؛ برای هر $i$ از $0$ تا $n - 1$ و هر $k$ از $1$ تا بزرگ‌ترین پیشوند مشترک $s_{n_{i+1}}$ و $n_{i + 1}, n_{i + 2} \dots$ رابطه‌ی بازگشتی زیر را داریم:

dp_{i + k} = \min\{dp_{i + k}, dp_i + |s_{n_{i+1}}| - k + 1\}

حال به کمک رابطه‌ی بازگشتی بالا می‌توانید مقدار $dp_{|n|}$ را حساب کنید که پاسخ مسئله است.

سالن سینما

هر بازه در هر ردیف از صندلی‌های سینما که حداقل یک جای خالی دارد را به‌صورت یک سه‌تایی $(i, j_l, j_r)$ در نظر بگیرید. (یعنی در سطر $i$ ام همه صندلی‌های ستون $j_l$ ام و $j_r$ ام خالی است و این بازه نیز قابل گسترش نیست.)

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

بنابراین کافی است یک ساختمان داده مثل set در نظر گرفته و همه‌ی بازه‌ها را براساس اینکه کدام‌یک جای مناسب‌تری برای نشستن دارند، در آن ذخیره کنیم. سپس هر بار مناسب‌ترین بازه را برداریم و تماشاچی را در صندلی مورد‌نظر (که همواره یا چپ‌‌ترین یا راست‌ترین یا یکی از صندلی‌های وسطی است) برداریم و این بازه را به حداکثر دو بازه‌ی دیگر تقسیم کرده و مجدداً به set اضافه کنیم.

با این کار خواسته‌ی مسئله را شبیه‌سازی می‌کنیم. باتوجه به اینکه حذف و اضافه کردن در set از مرتبه‌ی $log$ تعداد اعضای داخل آن است و چون این تعداد حداکثر $nm$ است، هر حذف و اضافه حداکثر از مرتبه‌ی

O(\log{nm}) = O(\log{n} + \log{m})

است. پس پیچیدگی زمانی در کل برابر است با:

O((nm + k) \times (\log{n} + \log{m}))

هندسی‌وار

اگر یک دنباله مثل $a_1, a_2, \dots, a_n$ هندسی‌وار باشد. عدد صحیح $A$ و عدد گویای $q$ چنان موجود است که:

a_1 = A,\, a_2 = Aq, \, a_3 = Aq^2, \dots, a_n = A.q^{n - 1}

همچنین می‌توان ثابت کرد که اگر یک جدول $n \times m$ «جذاب‌وار» باشد، عدد صحیح $A$ و اعداد گویای $p$ و $q$ چنان موجودند که:

a_{1, 1} = A, \, a_{1, 2} = A.q, \, a_{1, 3} = A.q^2 \dots, a_{1, m} = A.q^{m - 1} \\ a_{2, 1} = A.p, \, a_{2, 2} = A.p.q, \, a_{2, 3} = A.p.q^2 \dots, a_{2, m} = A.p.q^{m - 1} \\ a_{3, 1} = A.p^2, \, a_{3, 2} = A.p^2.q, \, a_{3, 3} = A.p^2.q^2 \dots, a_{3, m} = A.p^2.q^{m - 1} \\ \dots \\ a_{n, 1} = A.p^{n-1}, \, a_{n, 2} = A.p^{n-1}.q, \, a_{n, 3} = A.p^{n-1}.q^2 \dots, a_{n, m} = A.p^{n-1}.q^{m - 1}

راه‌حل اول

خانه‌ی سطر $i$ ام ستون $j$ ام را در نظر بگیرید. $U[i][j]$ یعنی حداکثر چند خانه باید از خانه‌ی سطر $i$ ام ستون $j$ ام بالا برویم تا دنباله هندسی بماند.

به‌طور مشابه منظور از $L[i][j]$ این است که حداکثر چند خانه از خانه‌ی سطر $i$ ام ستون $j$ ام به سمت چپ برویم تا دنباله هندسی بماند.

حال اگر یک سر مثل $i$ را فیکس کنیم. با درنظر گرفتن $U[i][j]$ های مختلف، انگار یک هیستوگرام داریم که دنبال بزرگ‌ترین زیرمستطیل آن هستیم.

البته اگر بازه‌ی $[j_l, j_r]$ از ستون‌ها یک کاندید بود، باید دو سطر آن را به کمک آرایه‌ی $L$ بررسی کنید و اشتراک بگیرید که آیا این زیرمستطیل ساختنی است یا نه.

پیچیدگی زمانی:‌ $O(nm)$

راه‌حل دوم

توجه کنید اگر یک دنباله‌ی هندسی، ناثابت باشد، طول آن نمی‌تواند از ۳۲ بیشتر باشد. بنابراین همه‌ی زیرمستطیل‌های جذاب‌وار سه حالت دارند.

سطری و ستونی غیرثابت هستند و ابعاد آن‌ها از ۳۲ بیشتر نمی‌شود.
سطری و ستونی یکی ثابت و دیگری غیرثابت است، در این حالت یکی از ابعاد از ۳۲ بیشتر نمی‌شود و تشکیل یک دنباله‌ی هندسی می‌دهد ولی در بعد دیگر صرفاً کپی شده است.
سطری و ستونی ثابت است؛ یعنی یک زیرمستطیل است که همه‌ی اعداد آن برابر است.

بررسی ۳ حالت فوق، مشابه مسئله‌ی پیدا کردن بزرگ‌ترین زیرمستطیل است.

جمع یا ضرب

لم اول. می‌توان فرض کرد ابتدا همه‌ی عملیات‌های جمع را انجام می‌دهیم و سپس به سراغ عملیات‌های ضرب می‌رویم. پس در واقع باید این $n$ عدد را به تعدادی دسته افراز کنیم و مجموع اعداد هر دسته را در هم ضرب کنیم.

لم دوم. اگر $x$ و $y$ دو عددِ صحیح بزرگ‌تر یا مساوی $2$ باشند، می‌توان به‌جای نوشتن جمع آن‌ها ( $x + y$ )، ضرب آن‌ها ( $xy$ ) را نوشت؛ زیرا به عددی بزرگ‌تر یا مساوی می‌رسیم.

لم سوم. اگر همه‌ی اعداد ورودی $1$ باشند، بزرگ‌ترین عددی که می‌توان ساخت از تقریباً سه‌تاسه‌تا دسته‌بندی‌کردنِ این اعداد است. به‌طور دقیق‌تر:

اگر $n$ بر $3$ بخش‌پذیر بود، $\frac{n}{3}$ دسته‌ی سه‌تایی می‌سازیم.
اگر $n$ بر $3$ باقی‌مانده‌ی $1$ داشت، $\frac{n - 4}{3}$ دسته‌ی سه‌تایی و دو دسته‌ی دوتایی می‌سازیم. (حالت $n = 1$ را جدا در نظر بگیرید.)
اگر $n$ بر $3$ باقی‌مانده‌ی $2$ داشت، $\frac{n - 2}{3}$ دسته‌ی سه‌تایی و یک دسته‌ی دوتایی می‌سازیم.

لم چهارم. طبق لم سوم، هر عدد بزرگ‌تر یا مساوی $2$ در یک دسته‌ی جدا قرار می‌گیرد. می‌توان ثابت کرد در حالت بهینه، می‌توان حداکثر یک عدد $1$ در دسته‌ی اعدادِ بزرگ‌تر یا مساوی $2$ قرار داد.

لم پنجم. ساختن یک دسته با $1$ ها الویت کمتری نسبت به اضافه کردن $1$ به یک دسته‌ی دیگر دارد. همچنین اگر بخواهیم یک $1$ به یک دسته اضافه کنیم، بهتر است عدد آن دسته از همه کوچک‌تر باشد.