المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۸:عملی:سوال ۱۲

زی

یک دانشمند نیمه‌دیوانه به نام ‎«زی»‎ در یک جزیره‌ی دورافتاده زندگی می‌کند. پس از سال‌ها تلاش و تحقیق، او موفق شده است که فرمول ‎«اکسیر جوانی»‎ را بیابد‎!‎ برای تهیه‌ی این اکسیر او به ‎۳‎ ماده‌ی ‎$B$‎، ‎$A$‎ و ‎$C$ (به‌ترتیب به‌اندازه‌ی ‎$r_B$‎، ‎$r_A$‎ و ‎$r_C$‎)احتیاج دارد.‎‎

پس از جست‌وجو در جزیره او موفق شده است ‎$s_A$‎ واحد از ماده‌ی $A$ ،$s_B$ تا از ‎$B$‎ و ‎$s_C$‎ تا از ‎$C$‎ پیدا بکند؛ اما این مقدار از مقدار لازم برای تهیه‌ی اکسیر کم‌تر است. از این رو، با روشن کردن آتش و فریاد زدن، او موفق شد با یک قایقران به‌نام ‎«کا»‎ آشنا بشود که می‌تواند مواد لازم را برای ‎«زی»‎ تهیه کند.

‎«کا»‎ هر روز صبح با قایقش از کنار جزیره‌ی ‎«زی»‎ رد می‌شود و تعدادی ‎«پیشنهاد معامله»‎ برای ‎«زی»‎ دارد. هر پیشنهاد به‌صورت یک ‎۳تایی مرتّب ‎$\langle O_a‎, ‎O_b‎, ‎O_c \rangle$‎ است که اگر ‎$O_i$‎ منفی باشد به‌معنی دریافت از ‎«زی»‎ و اگر مثبت باشد به معنی پرداخت به ‎«زی»‎ است. برای مثال ‎۳تایی ‎$\langle 2‎, -4, ‎5 \rangle$‎ به‌این معناست که ‎«کا»‎ حاضرست تا دقیقاً ‎۴‎ واحد از ماده‌ی ‎$B$‎ از ‎«زی»‎ بگیرد و به‌جای آن ‎۲‎ واحد از ماده‌ی ‎$A$‎ و ‎۵‎ واحد از ماده‌ی ‎$C$‎ به ‎«زی»‎ بدهد.

‎«کا»‎ هر روز تعدادی پیشنهاد برای ‎«زی»‎ می‌آورد و ‎«زی»‎ می‌تواند برخی (بین صفر تا همه) از آن‌ها را انتخاب کرده و طبق آن پیش‌نهادات با ‎«کا»‎ معامله کند. دقت کنید که از هر ‎«پیشنهاد»‎ در هر روز حداکثر یک‌بار می‌توان استفاده کرد. هم‌چنین پیشنهادات الزاماً باید به همان ترتیب گفته‌شدنشان قبول یا رد شوند؛ یعنی اگر ‎«کا»‎ در یک روز سه پیشنهاد برای ‎«زی»‎ بیاورد، ‎«زی»‎ نمی‌تواند اوّل پیشنهاد دوم را قبول و معامله کند، بعد پیشنهاد اوّل را.

واضح است که برای انجام یک پیشنهاد، مقدار ماده‌ای که ‎«زی»‎ دارد باید همواره بیش‌تر یا مساوی مقدار ماده‌هایی باشد که ‎«کا»‎ می‌خواهد. برای مثال، در پیشنهاد گفته شده در بالا اگر ‎«زی»‎ تنها ‎$3$‎ واحد از ماده‌ی ‎$B$‎ داشته باشد، قادر به انجام این معامله نیست؛ چرا که مقدار منفی از یک ماده (در پایان معامله) کاملاً بی‌معنی است‎!‎

از سوی دیگر، چون تنها محل مناسب برای نگه‌داری این مواد در جزیره، یک غار کوچک است، ‎«زی»‎ نمی‌تواند از هیچ یک از این سه ماده، به‌اندازه‌ی بیش‌تر از ‎$V$‎ داشته باشد. دقت کنید که ممکن‌ست با انجام یک معامله مقدار یک از ماده‌ها از ‎$V$‎ بیش‌تر شود، اما ‎«زی»‎ باید بلافاصله (و پیش از شروع معامله‌ی بعدی) این مقدار اضافه را بیرون بریزد. به‌عبارت بهتر، پیش از شروع هر معامله، مقدار ماده‌ی ‎$A$‎، ماده‌ی ‎$B$‎ و ماده‌ی ‎$C$‎ در دست ‎«زی»‎ باید کم‌تر یا مساوی ‎$V$‎ باشد.

می‌دانیم ‎«کا»‎ یک برنامه‌ی ماهیانه دارد؛ بدین معنی که اگر هر ماه دقیقاً ‎$M$‎ روز باشد، ‎«پیشنهاد»های روز ‎$i$،‎اُمِ ‎«کا»‎ با «‎پیشنهاد»های روز ‎«$M+i$»،‎اُمِ او برابرست.

نهایتاً می‌دانیم ‎«زی»‎ تنها تا ‎$D$‎ روز دیگر زنده است و پس از پایان روز ‎$D$اُم اگر به اکسیر جوانی دست نیافته باشد از دنیا می‌رود‎!‎

به ‎«زی»‎ کمک کنید و با دریافت پارامترهای مسئله، مقادیر اوّلیه و برنامه‌ی زمانی «‎کا»، برنامه‌ای بنویسید که زودترین زمانی را که ‎«زی»‎ می‌تواند به مواد لازم برای ‎«اکسیر جوانی»‎ برسد، مشخص کند.

‎ورودی

  • در سطر اوّل ورودی، ‎$V$‎، حداکثر مقدار هر کدام از ماده‌ها آمده است.
  • در سطر دوم به‌ترتیب از چپ به راست مقادیر ‎$s_A$‎، سپس ‎$s_B$‎ و نهایتاً ‎$s_C$‎ آمده است.
  • مشابهاًدر سطر سوم، مقادیر ‎$r_A‎, ‎r_B‎, ‎r_C$ (بالطّبع، اوّل ‎$r_A$‎) نوشته شده است.
  • در سطر چهارم، ‎$M$ (تعداد روزهای تمام ماه‌ها) آمده است و در ادامه، در ‎$M$‎ بلوک مشخّصات ‎«پیشنهاد»‎ های روزهای یکم تا ‎$M$‎اُم ماه آمده است. ابتدای بلوک ‎$i$‎ با یک عدد ‎$n_i$‎ در یک سطر مشخّص می‌شود. سپس در ‎$n_i$‎ سطر بعدی در هر سطر یک پیشنهاد به‌صورت ‎$O_a‎, ‎O_b‎, ‎O_c$‎ نوشته می‌شود که شرایط گفته شده در بالا را دارد. دقت کنید که پیشنهادهای هر روز باید الزاماً به همان ترتیبی که در ورودی گفته می‌شود مورد بررسی قرار گرفته و اِعمال یا رد بشوند.
  • نهایتاً در آخرین سطر ورودی ‎$D$‎ نوشته می‌شود.
  • دقّت کنید که اوّلین روز داستان، صبح روز یکم ماه است و برای مثال اگر ‎$D=1$‎ باشد، در آن‌صورت ‎«زی»‎ یک‌روز برای معامله وقت دارد.
  • تمام اعداد ورودی صحیح‌اند.
  • $1 \le M \le 30$‎ و برای تمام روزهای ماه ‎$0 \le n_i \le 7$‎ و هم‌چنین ‎$0 \le D \le 365$‎.
  • در هر کدام از سه‌تایی‌های گفته شده ‎$0 \le r_i‎, ‎s_i \le V$‎ و هم‌چنین در هر معامله ‎$-V \le O_i \le V$‎.
  • $0 \le V \le 30$‎؛ اما در ‎۸۰‎ درصد تست‌ها ‎$V < 10$‎.

خروجی

  • در تنها سطر خروجی در صورتی که ‎«زی»‎ می‌تواند پس از ‎$d \le D$‎ روز به مواد لازم برای ‎«اکسیر جوانی‎» برسد، مقدار ‎$d$‎ را چاپ کنید.
  • در غیر این‌صورت اگر پس از گذشت ‎$D$‎ روز ‎«زی»‎ نمی‌تواند به ‎«اکسیر»‎ برسد، در خروجی ابتدا یک کلمه‌ی «‎«No (با ‎N‎ بزرگ و ‎o‎ کوچک)، سپس یک فاصله و در ادامه حداکثر مجموع مقدار ماده‌ای که ‎«زی»‎ می‌تواند پیش از مرگ داشته باشد را بنویسید. بالطبع این مقدار کم‌تر از ‎$3V$‎ است‎!‎
  • توجه داشته باشید که در اوّلین لحظه‌ای که مقدار ماده‌های ‎$B$‎، ‎$A$‎ و ‎$C$‎ بیش‌تر مساوی (و نه لزوماً مساوی) ‎$r_A$‎، ‎$r_B$‎ و ‎$r_C$‎ بشود، ‎«اکسیر جوانی‎» ساخته می‌شود.

محدودیت‌ها

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

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
3
3 0 0
1 1 1
3
1
0‎ -‎1 1
‎1
-1 1 0
1
1 1‎ -‎1
‎5‎
‎5‎
1
1 1 1
1 0 0
1
0
‎0‎
‎0‎‎
3
3 0 0
1 1 2
3
1
0‎ -‎1 1‎
‎1
-1 1 0
‎1
1 1‎ -‎1
‎6‎
‎No 4‎‎‎

ابزار صفحه