در جستجوی ترب


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

علی عاشق ترب شده و ترب روی محور اعداد گم شده‌... علی دل توی دلش نیست تا اون رو پیدا کنه...

در ابتدا علی و ترب در دو نقطه مختلف از محور اعداد ایستاده‌اند. علی در نقطه x1x_1 و ترب در نقطه x2x_2 قرار دارد. بعد از آمدن یک صدای جیغ، در یک لحظه به صورت همزمان هر دوی آن‌ها شروع به حرکت می‌کنند. علی با سرعت‌ ثابت v1v_1 و ترب با سرعت ثابت v2v_2 تا ابد حرکت می‌کنند.

از شما می‌خواهیم سرنوشت حرکت آن‌ها را مشخص کنید! در واقع می‌خواهیم بدانیم آیا لحظه‌ای وجود دارد که علی و ترب به هم برسند؟! اگر هرگز به هم نمی‌رسند آیا فاصله آن‌ها از هم زیاد می‌شود یا فاصله‌شان همواره ثابت می‌ماند؟!

منظور از به هم رسیدن علی و ترب یعنی لحظه‌ای پس از آغاز حرکت وجود داشته باشد که هر دوی آن‌ها در یک نقطه از محور اعداد قرار داشته باشند.

توجه کنید که اگر سرعت یک نفر عددی مثبت باشد به سمت راست محور اعداد و اگر منفی باشد به سمت چپ و اگر برابر صفر باشد سر جای خود ثابت می‌ماند. همچنین حرکت به صورت پیوسته است و لحظه و محل برخورد لزوماً عددی صحیح نیست.

ورودی🔗

ورودی تنها چهار سطر دارد و در هر کدام یک عدد صحیح آمده است. در سطر اول x1x_1 که نشان دهنده مکان اولیه علی است. در سطر دوم v1v_1 که نشان دهنده سرعت علی است. در سطر سوم x2x_2 که نشان دهنده مکان اولیه ترب است. در سطر چهارم v2v_2 که نشان دهنده سرعت ترب است. −1 000≤x1≠x2≤1 000-1\ 000 \le x_1 \neq x_2 \le 1\ 000 −100≤v1,v2≤100-100\le v_1, v_2 \le 100 تضمین می‌شود مکان اولیه علی و ترب یکسان نیست.

خروجی🔗

در تنها سطر خروجی، در صورت به هم رسیدن علی و ترب، عبارت SEE YOU، در صورتی که فاصله آن‌ها زیاد می‌شود عبارت BORO BORO و در صورتی که فاصله آن‌ها همواره ثابت می‌ماند، عبارت WAIT WAIT را چاپ کنید.

دقت کنید بزرگ یا کوچک بودن حروف انگلیسی مهم است.

مثال🔗

ورودی نمونه ۱🔗

1
5
10
6
Plain text

خروجی نمونه ۱🔗

BORO BORO
Plain text

علی ابتدا در نقطه ۱ از محور اعداد قرار دارد و با سرعت ثابت ۵ (به سمت راست) در حرکت است و ترب ابتدا در نقطه ۱۰ از محور مختصات قرار دارد و با سرعت ثابت ۶ (به سمت راست) در حرکت است. چون در ابتدا ترب سمت راست علی قرار دارد و با سرعت بیشتری نسبت به علی به سمت راست می‌رود فاصله آن‌ها همواره زیاد می‌شود.

ورودی نمونه ۲🔗

1
-5
-10
-5
Plain text

خروجی نمونه ۲🔗

WAIT WAIT
Plain text

علی ابتدا در نقطه ۱ از محور اعداد قرار دارد و با سرعت ثابت ۵ (به سمت چپ) در حرکت است و ترب ابتدا در نقطه ۱۰- از محور اعداد قرار دارد و با سرعت ثابت ۵ (به سمت چپ) در حرکت است. بنابراین فاصله علی و ترب همواره برابر ۱۱ خواهد بود.

ورودی نمونه ۳🔗

1
6 
10
-5
Plain text

خروجی نمونه ۳🔗

SEE YOU
Plain text

علی ابتدا در نقطه ۱ از محور مختصات قرار دارد و با سرعت ثابت ۶ (به سمت راست) در حرکت است و ترب ابتدا در نقطه ۱۰ از محور مختصات قرار دارد و با سرعت ثابت ۵ (به سمت چپ) در حرکت است. بنابراین بعد از گذشت یک واحد زمان از آغاز حرکت علی و ترب بالاخره روی محور اعداد به هم می‌رسند.

قسمت آموزشی🔗

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

راهنمایی ۱

ابتدا به سرعت دو نفر توجه کنیم. می‌دانیم که تنها اختلاف سرعت دو نفر مهم است و نه بزرگی‌ آن‌ها. برای مثال با فرض بیشتر بودن سرعت علی نسبت به امین و مثبت بودن سرعت هر دو، اگر سرعت علی aa و سرعت ترب bb باشد، علی در هر ثانیه a−ba - b واحد بیشتر به سمت راست حرکت می‌کند.

راهنمایی ۲

بر اساس شهودی که در راهنمایی قبل پیدا کردیم، اکنون فرض می‌کنیم که سرعت نفر اول برابر صفر است و ثابت سر جایش ایستاده است. حال سرعت نفر دوم را نسبت به نفر اول حساب می‌کنیم و بر اساس علامت عدد حاصل، مسئله را حل می‌کنیم.

اگر سرعت اول برابر xx و سرعت نفر دوم برابر yy باشد، سرعت نفر دوم نسبت به نفر اول برابر y−xy - x خواهد بود.

راهنمایی ۳

حال سرعت نفر دوم نسبت به نفر اول را vv در نظر می‌گیریم. اگر vv برابر صفر باشد، از آن‌جایی که این دو نفر مکان اولیه‌شان متفاوت است، هیچ‌گاه به‌ هم نمی‌رسند و فاصله‌شان نیز همواره ثابت است.

همچنین برای رسیدن هر دو نفر به هم، اگر نفر دوم سمت راست نفر اول است، باید vv منفی و در غیر این صورت باید مثبت باشد. اگر این شرط برقرار بود،‌ به هم می‌رسند و اگر نبود، فاصله‌شان همواره زیاد می‌شود.

زمین ترب


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

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

زمینی که علی خریده است یک مستطیل n×mn \times m است. این زمین دارای nmnm قطعه است. قطعات این زمین به صورت یک جدول با nn سطر و mmستون است. در هر قطعه از این زمین می‌توان یک ترب کاشت یا آن را خالی گذاشت.

علی می‌خواهد دقیقاً در ss قطعه از این زمین ترب بکارد. علی دچار وسواس تقارن شده و می‌خواهد این کار را طوری انجام دهد، که جدول زمین کشاورزی متقارن باشد. یعنی حداقل یکی از دو محور تقارن افقی یا عمودی وجود داشته باشد که زمین کشاورزی نسبت به آن متقارن باشد.

به علی کمک کنید تا روشی برای کاشت ss ترب در زمین پیدا کند و اگر این کار ممکن نیست این خبر بد را به او اطلاع دهید.

ورودی🔗

در تنها سطر ورودی سه عدد صحیح nn و mm و ss با فاصله از هم آمده است که نشان دهنده ابعاد زمین علی و تعداد قطعاتی است که می‌خواهد در آن‌ها ترب بکارد. 1≤n,m≤1001 \le n, m \le 100 0≤s≤nm0 \le s \le nm

خروجی🔗

در خط اول خروجی در صورت امکان پذیر بودن این کار کلمه possible و در صورت ممکن نبودن کلمه impossible را چاپ کنید.

در صورت امکان پذیر بودن باید در nn سطر بعدی و در هر سطر یک رشته از mm کاراکتر بدون فاصله چاپ شود.اگر در قطعه سطر iiام ستون jjام ترب کاشته شود کاراکتر T و در صورت خالی بودن آن کاراکتر E را چاپ کنید.

توجه کنید که در صورت وجود جواب، می‌توانید هر جواب دلخواهی را چاپ کنید و مساله جواب یکتا ندارد.

مثال🔗

ورودی نمونه ۱🔗

3 3 5
Plain text

خروجی نمونه ۱🔗

possible
TTT
ETE
ETE
Plain text

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

ورودی نمونه ۲🔗

4 4 1
Plain text

خروجی نمونه ۲🔗

impossible
Plain text

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

ورودی نمونه ۳🔗

2 3 1
Plain text

خروجی نمونه ۳🔗

possible
EEE
ETE
Plain text

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

ورودی نمونه ۴🔗

2 2 2
Plain text

خروجی نمونه ۴🔗

possible
TE
TE
Plain text

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

قسمت آموزشی🔗

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

راهنمایی ۱

با کمی بررسی متوجه می‌شویم که اگر حداقل یکی از nn و mm فرد باشند، علی همواره می‌تواند روشی برای کاشت ترب در زمین پیدا کند. حال اگر هر دو بعد مستطیل زوج باشند، در می‌یابیم که تعداد ترب‌های کاشته شده هم باید زوج باشد وگرنه زمین ما نمی‌تواند نسبت به هیچ یک از محورهای تقارن قرینه باشد. دلیل آن هم این است که محورهای تقارن ما در یک طرف خود زوج و در طرف دیگر فرد ترب کاشته شده دارند که شرط تقارن را نقض می‌کند.

راهنمایی ۲

اگر nn و mm زوج باشند، می‌دانیم که حتما ss هم باید زوج باشد تا بتوانیم جدول مورد نظر را بسازیم. در این صورت می‌توانیم سطرها را به دو نیمه بالا و پایین تقسیم کنیم و به هر قسمت، نیمی از ترب‌ها را اختصاص دهیم.

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

راهنمایی ۳

حال به بررسی حالاتی می‌پردازیم که حداقل یکی از nn و mm فرد است. فرض کنیم nn فرد است (اگر نبود، همه این کارها را به صورت ستونی انجام دهید).

در ابتدا سطر وسط را در نظر می‌گیریم و شروع به پر کردن آن می‌کنیم. اگر ترب‌ها در سطر وسط جا می‌شدند که همه را همان‌جا می‌گذاریم. در غیر این صورت،‌ بیشترین تعداد ترب را در آن‌جا می‌گذاریم به‌طوری که تعداد ترب‌های باقی‌مانده زوج باشد (این تعداد بسته به زوجیت ss تعیین می‌شود و برابر mm یا m−1m - 1 است).

حال بدون در نظر گرفتن سطر وسط، نیمه بالای سطرهای جدول و نیمه پایین آن را با ترب‌های باقی‌مانده پر می‌کنیم به صورتی که نصف ترب‌ها به نیمه پایین و نصف دیگر به نیمه بالا برسد و این‌کار را همانند روش گفته شده در پایان راهنمایی قبل انجام می‌دهیم. با این الگوریتم، جدول نسبت به محور افقی متقارن خواهد شد.

استخدام در ترب


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

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

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

در این سوال یک دنباله از اعداد طبیعی مانند a1,a2,a3,...,an a_1, a_2, a_3, ..., a_n\ آمده است و از تربچه خواسته شده تا حاصل عبارت زیر را محاسبه کند. ∑i=1n∑j=1n⌊aiaj⌋ \sum_{i=1}^{n}\sum_{j=1}^{n}\lfloor\frac{a_i}{a_j}\rfloor

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

ورودی🔗

در سطر اول ورودی عدد صحیح nn که نشان دهنده تعداد اعداد دنباله است و در سطر دوم nn عدد صحیح با فاصله آمده که عدد iiام نشان دهنده مقدار aia_i است.

1≤n,ai≤100 0001 \le n, a_i \le 100\ 000

خروجی🔗

در تنها سطر خروجی، یک عدد صحیح که پاسخ مسئله است را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

3
1 2 3
Plain text

خروجی نمونه ۱🔗

9
Plain text

حاصل عبارت برابر است با: ⌊11⌋+⌊12⌋+⌊13⌋+⌊21⌋+⌊22⌋+⌊23⌋+⌊31⌋+⌊32⌋+⌊33⌋=\lfloor\frac{1}{1}\rfloor + \lfloor\frac{1}{2}\rfloor + \lfloor\frac{1}{3}\rfloor + \lfloor\frac{2}{1}\rfloor + \lfloor\frac{2}{2}\rfloor + \lfloor\frac{2}{3}\rfloor + \lfloor\frac{3}{1}\rfloor + \lfloor\frac{3}{2}\rfloor + \lfloor\frac{3}{3}\rfloor = 1+0+0+2+1+0+3+1+1=9 1 + 0 + 0 + 2 + 1 + 0 + 3 + 1 + 1 = 9

ورودی نمونه ۲🔗

4
1 1 1 1
Plain text

خروجی نمونه ۲🔗

16
Plain text

چون همه مقادیر باهم برابر است حاصل عبارت برابر است با: 4×4×⌊11⌋=164 \times 4 \times \lfloor\frac{1}{1}\rfloor = 16

قسمت آموزشی🔗

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

راهنمایی ۱

فرض کنید مقدار ⌊aiaj⌋=k\lfloor\frac{a_i}{a_j}\rfloor = k در این صورت داریم k≤aiaj<k+1⇒kaj≤ai≤(k+1)ajk \leq \frac{a_i}{a_j} < k + 1 \Rightarrow k a_j \leq a_i \leq (k + 1) a_j

مقدار MM را بزرگ ترین عدد آمده در دنباله در نظر بگیرید یعنی: M=max⁡1≤i≤n{ai}M = \max_{1 \le i \le n}\{ a_i \}

مقدار cntkcnt_k را تعریف می‌کنیم تعداد همه aia_i هایی که ai<ka_i < k باشد.

به راحتی می‌توان مقدار cntkcnt_k را برای همه 1≤k≤max{ai}1 \le k \le max\{a_i\} از مرتبه زمانی O(M)O(M) با استفاده از ایده جمع تجمعی یا partial sum محاسبه کرد.

راهنمایی ۲

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

∑i=1n∑j=1n⌊aiaj⌋=∑j=1n∑k=1max{ai}k(cnt(k+1)aj−cntkaj)\sum_{i=1}^{n}\sum_{j=1}^{n} \lfloor\frac{a_i}{a_j}\rfloor = \sum_{j=1}^{n} \sum_{k=1}^{max\{a_i\}} k(cnt_{(k + 1)a_j} - cnt_{ka_j})

با کمی مشاهده متوجه می‌شویم نیازی نیست مجموع دوم تا انتهای کار محاسبه شود (چرا؟).

و همین که k≤Majk \leq \frac{M}{a_j} باشید کافی است پس داریم : =∑j=1n∑k=1Majk(cnt(k+1)aj−cntkaj) = \sum_{j = 1}^{n}\sum_{k = 1}^{\frac{M}{a_j}} k(cnt_{(k + 1)a_j} - cnt_{ka_j})

راهنمایی ۳

به جای مجموع روی اندیس aja_j روی مقدار aja_j مجموع را حساب می‌کنیم یعنی اگر aj=la_j = l باشد داریم:

=∑l=1M∑k=1Mlk(cnt(k+1)aj−cntkaj) = \sum_{l = 1}^{M}\sum_{k=1}^{\frac{M}{l}} k(cnt_{(k + 1)a_j} - cnt_{ka_j})

همانطور که می‌دانیم دو مجموع فوق مشابه الگوریتم غربال-اراتستن از مرتبه زمانی O(Mlog⁡M)O(M \log{M}) بنابراین کل مسئله از مرتبه زمانی O(n+Mlog⁡M)O(n + M \log{M}) حل می‌شود.

تربچین


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

علی توانست شرکتش را توسعه دهد و یک زمین که به صورت یک جدول نامتناهی خریده و در هر خانه آن یک ترب کاشته است. همچنین یک دستگاه تربچین دارد که می‌خواهد با کمک آن ترب‌ها را برداشت کند...

علی از تربچه خواسته ابتدا تربچین را در قطعه (0,0)(0, 0) زمین قرار ‌دهد. تربچه برای آغاز کار یک رشته از حروف {L,R,U,D,?}\{L, R, U, D, ?\} دریافت می‌کند و طبق آن روی قطعه‌های زمین حرکت می‌کند و در هر قطعه که قرار بگیرد ترب داخل آن را می‌چیند.

همچنین اگر در یک خانه از جدول بیش از یک بار قرار بگیرد دیگر تربی برداشت نمی‌کند.

اگر رشته داده شده به تربچین s1s2s3...sn s_1s_2s_3...s_n\ باشد. تربچین با توجه به این رشته nn حرکت انجام می‌دهد.اگر تربچین در خانه (x,y)(x, y) باشد بعد از انجام حرکت iiام :

  • اگر si=Ls_i=L باشد به خانه (x−1,y)(x-1, y)
  • اگر si=Rs_i=R باشد به خانه (x+1,y)(x+1, y)
  • اگر si=Us_i=U باشد به خانه (x,y+1)(x, y+1)
  • اگر si=Ds_i=D باشد به خانه (x,y−1)(x, y-1)
  • اگر si=?s_i=? باشد به یکی از چهار قطعه مجاور ضلعی

می‌رود.

علی رشته s1s2s3...sn s_1s_2s_3...s_n\ را به ترب داده و او ترتیب عناصر این رشته را به هم ‌می‌ریزد. توجه کنید او نمی‌تواند حرفی به رشته اضافه یا کم کند!

علی که پیش‌بینی برایش خیلی مهم است؛ می‌خواهد بداند برای همه حالت‌های مختلف که ممکن است اتفاق بیفتد حداقل و حداکثر چند ترب توسط تربچین برداشت خواهد شد.

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

ورودی🔗

در خط اول ورودی عدد tt داده می‌شود. در هر یک از tt سطر بعدی هر کدام یک رشته از حروف {L,R,U,D,?}\{L, R, U, D, ?\} داده می‌شود. تضمین می‌شود مجموع طول همه رشته‌ها از 100 000100\ 000 بیشتر نمی‌شود.

خروجی🔗

خروجی باید شامل tt سطر باشد که در سطر iiام دو عدد aia_i و bib_i چاپ می‌شود که نشان دهنده حداقل و حداکثر تعداد ترب‌های برداشت شده توسط تربچین است.

مثال🔗

ورودی نمونه ۱🔗

5
L
L?
UDU
????
LRURLDURDDD
Plain text

خروجی نمونه ۱🔗

2 2
2 3
2 3
2 5
4 12
Plain text

ترتیب‌های بیشینه و کمینه به ترتیب در هر مورد به صورت زیر است:

L→min=max=2L \to min = max = 2

LU→max=3,LR→min=2LU \to max = 3, LR \to min = 2

UDU→min=2,UDU→max=3UDU\to min = 2, UDU\to max = 3

LRLR→min=2,DDDD→max=5LRLR \to min = 2, DDDD \to max = 5

RLRLRDUDUDD→min=4RLRLRDUDUDD \to min = 4

LLUURRRDDDD→max=12LLUURRRDDDD \to max = 12

قسمت آموزشی🔗

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

راهنمایی ۱

فرض کنید در رشته ورودی تعداد حرکت‌های از نوع L برابر LL، نوع R برابر RR، نوع U برابر UU، نوع D برابر DD و تعداد ؟ برابر QQ باشد.

در ابتدا برای سادگی فرض کنید هیچ ؟ در ورودی به شما داده نمی‌شود.

اگر بخواهیم حالت‌ کمینه را محاسبه کنیم. در این وضعیت حرکت‌های بالا و پایین و حرکت‌های چپ راست مستقل از هم هستند.

اگر بخواهیم حالت بیشینه را محاسبه کنیم در اکثر حالت‌ها می‌تونیم به اندازه طول رشته خانه جدید برویم و ترب برداشت کنیم.

راهنمایی ۲

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

اگر حداقل یک حرکت چپ یا راست داشته باشیم حداقل max⁡(∣R−L∣,1)\max(|R - L|, 1) ترب برداشت می‌کنیم.

به طور مشابه برای حرکت های بالا و پایین نیز می‌توان این را محاسبه کرد. یعنی اگر حداقل یک حرکت بالا یا پایین داشته باشیم حداقل max⁡(∣U−D∣,1)\max(|U - D|, 1) ترب برداشت می‌کنیم.

برای محاسبه بیشینه اگر هیچ حرکت چپ یا راست نداشته باشیم حداکثر خانه‌ای که به جز خانه ابتدایی از آن ترب برداشت می‌کنیم برابر است با max(U,D)max(U, D)

به طور مشابه اگر هیچ حرکت بالا و پایین نداشته باشیم حداکثر خانه‌ای که به جز خانه ابتدایی از آن ترب برداشت می‌کنیم برابر است با max(L,R)max(L, R)

حال اگر از هر دو نوع بالا حداقل یک حرکت داشته باشند می‌توان در اکثر حالت‌ها به جز خانه ابتدایی از L+R+U+DL+R+U+D خانه جدول ترب برداشت کنیم.

راهنمایی ۳

حال فرض کنید QQ نیز ناصفر باشد برای حالت کمینه می‌توان QQ واحد از اختلاف ∣R−L∣|R - L| و ∣U−D∣|U - D| کاهش داد.

برای حالت بیشینه می‌توان QQ ترب اضافه برداشت کرد.

اما تنها حالت خاصی که در شرایط صدق نمی‌کند حالتی است که Q=0,L=R,U=DQ = 0, L = R, U = D این تنها حالتی است که ما به خانه ابتدایی باز می‌گردیم و یک ترب کمتر برداشت می‌کنیم.

گراف سفید و سیاه


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

علی برای افزایش روحیه تیم ترب تصمیم گرفته آن‌ها را به اسکیپ روم ببرد... آن‌ها باید سوال زیر را حل کنند تا وارد مرحله بعد شوند... به آن‌ها کمک کنید تا این گردش برایشان جذاب شود

یک گراف ساده مانند GG با nn راس با شماره‌های ۱ تا nn و mm یال دو طرفه داریم. بین هر دو راس حداکثر یک یال وجود دارد. هر یال دو راس مختلف را به هم وصل می‌کند. توجه کنید لزوماً این گراف همبند نیست!

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

در هر عملیات می‌توانیم یک زیر مجموعه از رئوس مانند SS، انتخاب کنیم و رنگ هر راس در مجموعه SS و همه رئوسی که به حداقل یک راس از SS یال دارند را عوض کنیم. (رنگ سفید را به سیاه و رنگ سیاه را به سفید)

می‌خواهیم با حداکثر n+1n + 1 عملیات کل رئوس گراف را سفید کنیم. اگر چنین کاری ممکن است یک روش برای انجام این کار ارائه دهید در غیر اینصورت بگویید این کار ممکن نیست.

ورودی🔗

در خط اول ورودی دو عدد صحیح nn و mm با فاصله از هم آمده است. 0≤n≤15000 \le n \le 15000≤m≤n(n−1)2 0 \le m \le \frac{n(n - 1)}{2}

در سطر بعدی یک رشته از 00 و 11 به طول nn آمده است که اگر عدد iiام آن 00 باشد یعنی راس شماره ii سفید و اگر 11 باشد یعنی رنگ راس شماره ii سیاه است.

در mm سطر بعدی هر کدوم دو عدد uu و vv آمده است. که نشان دهنده یال‌های گراف است. 1≤u≠v≤n 1 \le u \neq v \le n

خروجی🔗

در صورت امکان پذیر بودن در سطر اول kk که تعداد مراحلی که نیاز دارید تا رنگ همه رئوس را سفید کنید چاپ کنید. 0≤k≤n+10 \le k \le n + 1 در kk سطر بعدی در هر سطر یک رشته از 00 و 11 چاپ کنید که عدد iiام آن 11 است اگر راس شماره ii در مرحله iiام در مجموعه SS باشد و در غیر اینصورت 00 خواهد بود.

در صورت امکان پذیر نبودن در تنها سطر خروجی -1 را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

4 3
0110
1 2
2 3
3 4
Plain text

خروجی نمونه ۱🔗

3
0100
0010
1001
Plain text

ورودی نمونه ۲🔗

3 3
110
1 2
2 3
3 1
Plain text

خروجی نمونه ۲🔗

-1
Plain text

قسمت آموزشی🔗

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

راهنمایی ۱

اول بیاییم یک شرط برای -1 شدن جواب پیدا کنیم.

فرض کنید دو تا راس uu و vv که به هم وصل هستند و مجموعه همسایه های یکسانی دارند، رنگشان فرق دارد. این‌جوری هیچ مجموعه‌ای که دقیقا یکی از این دو راس را شامل شود، نداریم. پس جواب برابر -1 است.

راهنمایی ۲

ابتدا به ازای هر uu و vv که با هم همسایه‌اند و مجموعه همسایه‌هایشان برابر است، یکی را حذف کنید چون رنگ این دو همیشه برابر است و در انتها هر دو سفید می‌شوند. حال راس‌های گراف را بر حسب درجه مرتب کنید. فرض کنید برای هر راس vv می‌توانیم با تعدادی عملیات رنگ vv را عوض کنیم طوری که برای هر uu که degv≤degudeg_v \le deg_u رنگ uu ثابت بماند. حال راس هارا به ترتیب درجه از بزرگ بررسی کنید و به هرکس که رسیدید، رنگ او را با عملیات گفته شده تغییر دهید.

راهنمایی ۳

ادعا میکنیم عملیات گفته شده در قبل برای راس vv اینگونه انجام میشود: یکبار SS را برابر تمام ریوس غبر از vv قرار دهید که با vv مجاور نیستند. و یکبار هم SS را برابر با تمام ریوس قرار دهید. بدیهتا عملیات دوم رنگ تمام ریوس را تغییر میدهد پس بیایید عملیات اول را بررسی کنیم: بدیهتا هر راس غیر همسایه vv تغییر میکند و خود vv نیز تغییر نمیکند. پس فقط همسایه های vv میمانند. اگر راس uu داشتیم که degu>degvdeg_u>deg_v رنگ uu تغییر میکند چون به حداقل یک راس غیر همسایه vv وصل است. اگر هم راس uu با درجه برابر vv داشتیم باز هم uu همسایه ای در SS دارد وگرنه مجموعه همسایه های uu و vv برابر بود.

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

با این روش به ازای هر راس حداکثر 2 عملیات انجام داده ایم که یکی از انها روی تمام ریوس بوده است. چون از هر نوع عملیات فقط زوجیت تعداد دفعات ان مهم است پس در مجموع n+1n+1 عملیات داریم.

زمان اجرای این راه حل از O(n3)O(n^3) است که با std::bitset در زمان مطلوب اجرا میشود

افراز توان دار


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

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

برای هر عدد طبیعی فرض کنید PnP_n مجموعه همه دنباله‌هایی از اعداد طبیعی باشد که جمع اعضای این دنباله برابر nn است. به عبارت دیگر: Pn={(a1a2a3…am)∣a1+a2+a3+⋯+am=n}P_n = \{ (a_1a_2a_3\dots a_m) | a_1+a_2+a_3+\dots+a_m=n\} اکنون ترب می‌خواهد عبارت زیر را محاسبه کند. ∑(a1a2a3…am)∈Pna1ka2ka3k…amk \sum_{(a_1a_2a_3\dots a_m) \in P_n} {a_1}^k{a_2}^k{a_3}^k\dots{a_m}^k به ترب کمک کنید تا این عبارت را محاسبه کند چون ممکن است پاسخ شما بسیار عدد بزرگی باشد باقی‌مانده آن را به پیمانه 109+710^9+7 حساب کنید.

ورودی🔗

ورودی تنها شامل یک خط است که در آن دو عدد طبیعی nn و kk با فاصله از هم آمده است. 1≤k≤100,1≤n≤1091 \le k\le 100,1 \le n\le 10^9

خروجی🔗

در تنها سطر خروجی پاسخ مسئله را به پیمانه 109+710^9+7 چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

1 1
Plain text

خروجی نمونه ۱🔗

1
Plain text

ورودی نمونه ۲🔗

4 2
Plain text

خروجی نمونه ۲🔗

63
Plain text

تمام اعضای مجموعه P4P_4 عبارت است از: P4={(1,1,1,1),(2,1,1),(1,2,1),(1,1,2),(2,2),(3,1),(1,3),(4)}P_4=\{ (1,1,1,1), (2,1,1), (1,2,1), (1,1,2), (2,2), (3,1), (1,3), (4) \} بنابراین حاصل مجموع فوق برابر است با: 1+4+4+4+16+9+9+16=63 1 + 4 + 4 + 4 + 16 + 9 + 9 + 16 = 63

قسمت آموزشی🔗

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

راهنمایی ۱

اولین نکته‌ای که توجه به آن برای حل مسئله ضروری می‌باشد، این است که افرازهایمان ترتیب دارند و برای مثال افراز 1 2 با افراز 2 1 فرق دارد. حال بر اساس این نکته می‌توان دریافت که تعداد افرازهای ترتیب‌دار عدد nn برابر 2n−12^{n - 1} می‌باشد چرا که می‌توانیم nn توپ در یک ردیف در نظر بگیریم و هر افراز را با یک حالت دیوار گذاشتن در n−1n - 1 جایگاه خالی بین‌ توپ‌ها متناظر کنیم.

حال برای عبارت جواب، مسئله‌ای ترکیبیاتی تعریف می‌کنیم و تلاش می‌کنیم تا با شمارش مضاعف، آن را به روش دیگری محاسبه کنیم:

در یک ردیف، nn جعبه متوالی با شماره ۱ تا nn داریم. می‌خواهیم آن‌ها را بلوک‌بندی کنیم و در هر بلوک، به ازای همه رنگ‌های ۱ تا kk، دقیقا یک توپ با آن رنگ را در یکی از جعبه‌های این بلوک قرار دهیم. اگر ترتیب قرار دادن توپ‌ها در جعبه‌ها اهمیتی نداشته باشد، به چند طریق این کار ممکن است؟

راهنمایی ۲

برای حل مسئله مطرح شده در انتهای راهنمایی قبل، از برنامه‌نویسی پویا استفاده می‌کنیم یا به عبارت دیگر dpdp می‌زنیم :) ابتدا به تعریف dpdp می‌پردازیم. dp[i][j]dp[i][j] یعنی تعداد روش‌های چیدن توپ‌ها در ii جعبه اول به گونه‌ای که بلوک آخرمان برای تکمیل شدن،‌ به jj توپ رنگی دیگر نیاز داشته باشد. دقت کنید که تعداد بلوک‌ها برایمان اهمیتی ندارد و نه در مولفه و نه در پاسخ هر خانه آرایه، به آن اشاره‌ای نمی‌کنیم.

حالت پایه که تقریبا واضح است، dp[0]0]=1dp[0]0] = 1.

برای اپدیت کردن یک استیت، بر روی تعداد توپ‌های رنگی خانه iiام حالت می‌بندیم. به ازای همه rrهایی که j≤r≤kj \le r \le k، از dp[i−1][r]dp[i - 1][r] اپیدت می‌شوم و ضریب این اپدیت هم برابر حاصل انتخاب jj از rr می‌باشد چرا که قرار است از rr توپ رنگی باقی‌مانده در مرحله قبل، jj تا را برای ادامه بلوک انتخاب کنیم و بقیه را در جعبه ii ام قرار دهیم.

همچنین یک حالت دیگر هم وجود دارد و آن هم اینکه خانه iiام اولین خانه بلوک جدید باشد که در این حالت dp[i][j]dp[i][j] باید از dp[i−1][0]dp[i - 1][0] با ضریب jj از kk اپدیت شود.

با توجه به راه‌حل تعداد خانه‌های آرایه dpdp که باید پر شوند، nknk می‌باشد و برای اپدیت کردن هر خانه هم O(k)O(k) عملیات انجام می‌دهیم. بنابراین پیچیدگی زمانی راه‌حل فعلی از O(nk2)O(nk^2) می‌باشد.

راهنمایی ۳

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

به این صورت که یک ماتریس یک بعدی به طول k+1k + 1 را به عنوان پایه در نظر می‌گیریم و از یک ماتریس دو بعدی (k+1)×(k+1)(k + 1) \times (k + 1) برای اپدیت کردن آن استفاده می‌کنیم، به این صورت که اگر ماتریس دو بعدی ما در ماتریس یک بعدی ما که نشان‌دهنده مقادیر خانه‌های سطر iiام است ضرب شود، حاصل ماتریس یک بعدی خواهد شد که مقادیر سطر i+1i + 1 را داراست. ساختن این ماتریس نیز بر اساس ضرایب اپدیت dpdp است و تعدادی انتخاب و به علاوه یک خواهد بود.

حال می‌دانیم که مقادیر سطر صفر را در ماتریس پایه‌ بریزیم، برای داشتن سطر پایانی باید nn بار در ماتریس اپدیت ضرب شویم و از آن‌جایی که ضرب ماتریس به صورت بالا خاصیت شرکت‌پذیری دارد، ابتدا ماتریس اپدیت را در O(k3lgn)O(k^3lg_n) به توان nn می‌رسانیم و سپس حاصل را در ماتریس پایه ضرب می‌کنیم تا سطر nnام dpdp به دست آید و خانه اول آن یعنی dp[n][0]dp[n][0] پاسخ مسئله ما خواهد بود.

نوشابه خنک


  • محدودیت زمان: ۴ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

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

فرض کنید GG یک گراف وزن دار بدون جهت همبند باشد. GG دارای nn راس و mm یال است. هر یال GG دو راس مختلف را به هم متصل می‌کند.

همچنین راس‌های این گراف با ۱ تا nn شماره گذاری شده‌اند. روی راس شماره ii عدد aia_i نوشته شده است.

از ما تعدادی سوال پرسیده می‌شود. در هر سوال سه عدد vv و xx و kk داده می‌شود و از ما کوچک‌ترین مقدار ww را می‌خواهند که حداقل kk راس وجود داشته باشند که فاصله آن‌ها از vv فاصله حداکثر ww باشد و عدد نوشته شده روی آن نسبت به xx اول باشد.

منظور از وزن یک مسیر بزرگ ترین عددی است که روی یال‌های آن مسیر وجود دارد.

منظور از فاصله دو راس مانند uu و vv کمینه مقدار وزن تمام مسیرهای ممکن بین uu و vv است.

ورودی🔗

در سطر اول ورودی سه عدد طبیعی nn و mm وqq با فاصله از هم آمده است که به ترتیب نشان دهنده تعداد رئوس، یال‌ها و سوالاتی است که باید به آن‌ها پاسخ بدهیم. 1≤n,m,q≤100 0001 \le n, m, q \le 100\ 000 در سطر دوم nn عدد مانند a1,a2,a3,...,ana_1, a_2, a_3,..., a_n با فاصله آمده که نشان دهنده اعداد نوشته شده روی رئوس گراف است.

در iiامین سطر از mm سطر بعدی، سه عدد viv_i و uiu_i و wiw_i عدد آمده است که نشان‌دهنده وجود یالی با وزن wiw_i بین دو راس viv_i و uiu_i است. دقت کنید که لزومی ندارد گراف ساده باشد و ممکن است طوقه یا یال چندگانه داشته باشیم. 1≤ui,vi≤n1 \le u_i, v_i \le n 1≤wi≤1091 \le w_i \le 10^9

در jjامین سطر از qq سطر بعدی، سه عدد vjv_j و xjx_j و kjk_j آمده است که نشان دهنده سوال علی از شماست؟1≤ai,xj≤500 0001 \le a_i, x_j \le 500\ 000 1≤vj≤n1 \le v_j \le n 2≤kj≤n2 \le k_j \le n

خروجی🔗

در qq سطر خروجی در سطر iiام پاسخ سوال iiام را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

3 3 2
6 9 5
1 2 10
2 3 20
1 3 30
3 7 2
1 25 2
Plain text

خروجی نمونه ۱🔗

20
10
Plain text

ورودی نمونه ۲🔗

4 3 4
1 2 3 4
1 2 10
2 3 1
3 4 2
3 3 2
4 5 3
4 5 4
1 2 4
Plain text

خروجی نمونه ۲🔗

2
2
10
-1
Plain text

قسمت آموزشی🔗

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

راهنمایی ۱

در ابتدا برای حل مسئله، mst گراف را در نظر می‌گیریم. برای این کار از الگوریتم kruskal با dsu استفاده میکنیم. حال درخت باینری TT را بدین‌شکل می‌سازیم که nn برگ و n−1n-1 غیر برگ داشته باشد و هر برگ آن متناظر یکی از رئوس گراف اولیه و هر غیر برگ آن متناظر یکی از یال های mst بوده و دقیقا 2 بچه داشته باشد.

اگر در TT برگ های هر زیردرخت را بگیریم، در mst تشکیل یک زیرگراف همبند می‌دهند که زمانی یکی از مولفه های همبندی dsu بوده است. این درخت را همزمان با پیدا کردن mst می‌سازیم بدین‌صورت که برای هر مولفه در dsu شماره راس ریشه آن را نگه می‌داریم و موقع ادغام کردن دو مولفه، یک راس ریشه جدید ساخته و parent ریشه‌های دو مولفه قبلی را راس جدید می‌گذاریم و valuevalue راس جدید را هم برابر وزن یال متناظرش در mst قرار می‌دهیم.

راهنمایی ۲

فرض کنید جعبه‌ای داریم که دو عملیات زیر را در O(26)O(2^6) برای دامنه xx موجود در صورت مسئله انجام می‌دهد.

  • add x عدد xx را به دنباله AA اضافه می‌کند.
  • get x تعداد اعضای AA که نسبت به xx اول هستند را برمی‌گرداند.

برای این کار cntxcnt_x را تعریف می‌کنیم را تعداد اعداد AA که مضرب xx هستند. حال برای پرسش نوع دوم از اصل شمول و عدم شمول استفاده می‌کنیم. به ازای هر مجموعه از عوامل اول xx مانند SS که ضرب اعضایش yy است، مقدار (−1)∣S∣∗cnty(-1)^{|S|}*cnt_y را به جواب اضافه می‌کنیم. چون همه xx ها حداکثر 500 000500\ 000 اند، پس حداکثر ۶ عامل اول متفاوت دارند و هر درخواست در O(26)O(2^6) انجام می‌شود.

حال به سوال اصلی باز گردیم. برای جواب دادن کوئری‌های ورودی، می‌توانیم از Binary Search روی جواب استفاده کنیم.

پاسخ درخواستی که به شکل v x w داده می‌شود، تعداد رئوسی است که عدد نوشته شده بر روی آن‌ها، نسبت به xx اول است و فاصله‌شان تا vv حداکثر wwاست. همچنین می‌دانیم تمام راس‌هایی که شرط فاصله برایشان برقرار است، برگ های یک زیردرخت از TT هستند. پس می‌توانیم همه آن‌ها را به جعبه اضافه کرده و در انتها جواب را از جعبه بپرسیم ولی پیچیدگی زمانی این راه بیش از حد مطلوب ماست.

راهنمایی ۳

برای بهتر کردن راه قبل میتوان از Parallel Binary Search یا باینری سرچ موازی استفاده کرد. میخواهیم همزمان جواب کوئری‌های سوال را حساب کنیم. برای اینکار روی انها همزمان باینری سرچ میزنیم و O(log(n))O(log(n)) بار جواب همه کوئری‌ های v x subtree را حساب میکنیم. برگ های TT را بر حسب starting time مرتب کنید. حال هر کویری معادل برگ های یک بازه است که هر کدام معادل دو کویری پریفیکس است. برای جواب دادن کویری های پریفیکس هم برگ ها را به ترتیب به جعبه اضافه کنید و به هر کویری که رسیدید xx آن کویری را از جعبه بپرسید.

پیچیدگی زمانی: O((n+q).log(n).26)O((n+q).log(n).2^6)