مالک بعد از تصاحب ثروت ریزآبادیها بسیار پولدار شد. سپس برای پسرش میثم باغ بزرگی خرید و…
- User
مالک بعد از تصاحب ثروت ریزآبادیها بسیار پولدار شد. سپس برای پسرش میثم باغ بزرگی خرید و در آن n n گل در یک ردیف کاشت. هر گل بویی دارد و i iامین بو از سمت چپ a i a i واحد بو دارد. میثم هر روز هنگام غروب خورشید، به باغش میرود و از سمت چپ به سمت راست باغ حرکت میکند. اگر به گلی برسد که بوی آن را حس نکند بسیار خشمگین میشود و تمام باغ را آتش میزند. او بوی گل i
1 i>1 را حس نمیکند اگر a i < a i − 1 a i <a i−1 باشد.
مالک که از این موضوع آگاه است n n تا اسپری خریده است تا هر روز صبح به گلها بزند و بوی آنها را فقط در آن روز مقداری بیشتر کند. برای اینکه بوی گل i iام را یک واحد افزایش دهد، باید یک پیس از اسپری i iام به آن بزند. قیمت هر پیس از اسپری i iام b i b i تومان میباشد. گاهی اسپریها کیفیت لازم را ندارند و قیمت آنها منفی میشود! قابل ذکر است که بوی گلها نمیتواند از 1 0 6 10 6 بیشتر شود.
مالک در q q روز بعدی، وقتی به باغ برود بوی یکی از گلها افزایش مییابد. در روز i iام مقدار a x i a x i
به اندازه y i
0 y i
0 بیشتر میشود. او که بسیار پولپرست است، میخواهد با کمترین هزینه ممکن، هر روز باغ را باب میل پسرش کند. به او کمک کنید تا این هزینه را در هر روز پیدا کند.
ورودی در خط اول n n و q q، تعداد گلها و تعداد روزهابه ترتیب میآیند.
در خط دوم n n عدد a 1 , a 2 , . . . , a n a 1 ,a 2 ,...,a n به ترتیب میآیند.
در خط سوم n n عدد b 1 , b 2 , . . . , b n b 1 ,b 2 ,...,b n به ترتیب میآیند.
در i iامین خط از q q خط بعدی، دو عدد y i y i و x i x i به ترتیب میآیند.
2 ≤ n , q ≤ 200 , 000 2≤n,q≤200,000
− 1 0 6 ≤ a i , b i ≤ 1 0 6 −10 6 ≤a i ,b i ≤10 6
1 ≤ x ≤ n 1≤x≤n
1 ≤ y ≤ 1 0 6 1≤y≤10 6
تضمین میشود بوی تمامی گلها هیچوقت از 1 0 6 10 6 بیشتر نمیشود.
خروجی در q q خط، به ازای هر روز که مالک وارد باغ میشود، کمترین هزینه برای اینکه باغ را باب میل میثم کند را چاپ کنید.
زیرمسئلهها زیرمسئله نمره محدودیت ۱ ۷ n , q ≤ 300 n,q≤300 ۲ ۶ n , q ≤ 5000 n,q≤5000 و 0 ≤ b i 0≤b i
۳ ۱۹ n , q ≤ 5000 n,q≤5000 ۴ ۲۲ 0 ≤ b i 0≤b i
۵ ۴۶ بدون محدودیت اضافی مثال ورودی نمونه ۱ 3 3 4 9 6 -1 3 0 3 4 1 6 3 5 Plain text خروجی نمونه ۱ -5 3 3 Plain text در نمونه اول، روز اول دنباله گلها ⟨ 4 , 9 , 10 ⟩ ⟨4,9,10⟩ میباشد. مالک میتواند ۵ بار به اولین گل اسپری بزند و دنباله گلها ⟨ 9 , 9 , 10 ⟩ ⟨9,9,10⟩ میشود و ۵- تومان خرج کند.
در روز دوم دنبال بوی گلها ⟨ 10 , 9 , 10 ⟩ ⟨10,9,10⟩ میباشد. مالک میتواند یک بار به دومین گل اسپری بزند و دنباله گلها ⟨ 10 , 10 , 10 ⟩ ⟨10,10,10⟩ میشود و ۳ تومان خرج کند.
در روز سوم دنباله گلها ⟨ 10 , 9 , 15 ⟩ ⟨10,9,15⟩ میشود و مشابه روز دوم کافی است مالک یک بار به دومین گل اسپری بزند.
ورودی نمونه ۲ 6 3 3 1 3 2 4 4 1 -5 1 1 1 1 1 3 5, 6 2 999999 Plain text خروجی نمونه ۲ -1000008 -1000014 3999981 c++
- Assistant
برای حل این مسئله باید به درخواستهای مالک برای تغییر بوی گلها در روزهای مختلف پاسخ دهیم و هر روز هزینه کمترین هزینه ممکن را برای اسپری کردن اعلام کنیم. ابتدا باید بتوانیم بر اساس ترتیب دادهها و نتایجی که پس از اعمال تغییرات به دست میآید، بوی هر گل را به درستی مدیریت کنیم.
به منظور حل این فرض میتوانیم از یک روش کارآمد استفاده کنیم. باید بوی گلها را در یک ساختار داده مناسب ذخیره کنیم و هر بار که تغییرات صورت میگیرد بوی گلها را بهروز کنیم و بررسی کنیم که آیا تغییری در بوها به وجود آمده است یا نه. پس از هر بهروزرسانی، باید هزینه کمینه را محاسبه کنیم تا مطمئن شویم که هیچ بویی کمتر از بوی پیشین نیست.
الگوریتم کلی:
- ابتدا بوی گلها را به همراه هزینه اسپری مربوطه ذخیره کنید.
- برای هر روزی که مالک وارد باغ میشود:
- بوی گل مورد نظر را به اندازه مورد نظر افزایش دهید.
- بررسی کنید که آیا نیازی به تغییر بوی گلها برای جلوگیری از خشمگینی میثم وجود دارد یا نه.
- اگر نیاز به تغییر بود، تعداد واحدهای لازم برای اسپری و هزینه بهینه را محاسبه کنید.
- هزینه کمتری برای بهروز رسانیها انتخاب کنید و نتیجه را نمایش دهید.
این روش نیاز به پیاده سازی دقیق و استفاده از ساختارهای داده سریع برای انجام عملیاتهای متوالی دارید. در زیر نمونهای ساده بر اساس فرض مسئله ارائه میشود:
#include <iostream> #include <vector> #include <algorithm> using namespace std; // Data structure to store flower information and cost struct Flower { int fragrance; int cost; }; int main() { int n, q; cin >> n >> q; // Number of flowers and number of days vector<Flower> flowers(n); for (int i = 0; i < n; ++i) { cin >> flowers[i].fragrance; // Fragrance of flowers } for (int i = 0; i < n; ++i) { cin >> flowers[i].cost; // Cost of spraying } while(q--) { int x, y; cin >> y >> x; // Increase y units fragrance on x-th flower x--; // Convert to zero-based index flowers[x].fragrance += y; long long totalCost = 0; for (int i = 1; i < n; ++i) { if (flowers[i].fragrance < flowers[i-1].fragrance) { int diff = flowers[i-1].fragrance - flowers[i].fragrance; int spraysNeeded = diff; totalCost += spraysNeeded * flowers[i].cost; flowers[i].fragrance += spraysNeeded; } } cout << totalCost << endl; } return 0; }این کد به طور کارآمدی، برای هر تغییر در روز، تمام بوهای گلها را بهروزرسانی میکند و اطمینان حاصل میکند که ترتیب آنها رعایت میشود تا میثم ناراحت نشود.
- User
پشمک و پارمیدا در پوستون زندگی میکنند. امسال در جشن سال نو، پشمک یک گردنبند به پارمیدا هدیه داده است. یک گردنبند در پوستون تعدادی مهره دارد که روی هر یک از مهرههای آن یک رقم بین 0 0 تا 9 9 نوشته شده است. بنابراین هر گردنبند، متناظر با یک عدد صحیح نامنفی است که مهرههای آن، از چپ به راست، رقمهای آن عدد را، از پر ارزشترین به کمارزشترین، نشان میدهند. دقت کنید که در چپ ترین مهرهی یک گردنبند تنها در حالتی امکان دارد رقم 0 0 نوشته شده باشد که عدد متناظر با گردنبند، صفر باشد (یعنی گردنبند تنها یک مهره با رقم 0 0 داشته باشد) زیرا پر ارزشترین رقم یک عدد بزرگتر از صفر، نمیتواند 0 0 باشد.
قیمت یک گردنبند که مهرههای آن، به ترتیب از چپ به راست، a 1 , a 2 , … , a n a 1 ,a 2 ,…,a n هستند، برابر تعداد نابجاییهای دنبالهی مهرههای آن است. به عبارت دیگر قیمت یک گردنبند، تعداد جفتهای ( i , j ) (i,j) است که:
i < j i<j a i
a j a i
a j
دقت کنید در صورتی که دنبالهی مهرههای یک گردنبند صعودی باشد، قیمت آن برابر با صفر خواهد بود.
همچنین هر چه عدد متناظر با یک گردنبند کوچکتر باشد، آن گردنبند جذابتر خواهد بود. برای مثال، جذابترین گردنبند گردنبندی است که عدد متناظر با آن برابر با صفر باشد.
به ازای هر عدد صحیح نامنفی، دقیقاً یک گردنبند در پوستون وجود دارد که متناظر با این عدد است. پارمیدا، از روی کنجکاوی میخواهد تعداد گردنبندهای جذابتر و با قیمت کمتر از گردنبدی که هدیه گرفته است را بشمارد. برنامهای بنویسید که این عدد را محاسبه کند.
ورودی در خط اول ورودی n n، عدد متناظر با گردنبندی که پشمک به پارمیدا هدیه داده است، آمده است. 1 ≤ n ≤ 1 0 18 1≤n≤10 18
خروجی در تنها خط خروجی، تعداد گردنبندهای جذابتر و با قیمت کمتر از گردنبند پارمیدا را چاپ کنید.
زیرمسئلهها زیرمسئله نمره محدودیت ۱ ۷ n ≤ 100
000 n≤100 000 ۲ ۴۳ n ≤ 1 0 12 n≤10 12
۳ ۵۰ بدون محدودیت اضافی مثال ورودی نمونه ۱ 123 Plain text خروجی نمونه ۱ 0 Plain text ورودی نمونه ۲ 1991 Plain text خروجی نمونه ۲ 999 Plain text ورودی نمونه ۳ 100000 Plain text خروجی نمونه ۳ 50248
- Assistant
برای حل این مسئله، باید گردنبندهایی را پیدا کنیم که هم از نظر عددی کوچکتر و هم از نظر تعداد نابجاییهای مهرهها کمتر از گردنبندی باشند که پارمیدا هدیه گرفته است.
این مسئله را میتوان به شکل زیر تحلیل کرد:
-
محاسبه تعداد جفت نابجاییها (Inversions):
- برای محاسبه تعداد نابجاییها در یک عدد، میتوان از روش Merge Sort استفاده کرد که پیچیدگی زمانی (O(n \log n)) دارد اما از آنجایی که ورودی ما به صورت عدد با حداکثر 18 رقم است، نیاز داریم به صورت مستقیم این مشکل را حل کنیم.
-
بررسی اعداد کوچکتر:
- برای پیدا کردن گردنبندهای جذابتر (یعنی عدد کوچکتر)، باید تمام ترکیبات ممکن از اعداد کوچکتر تا عدد داده شده را بررسی کنیم. این کار به صورت مستقیم برای اعداد بالا ممکن نیست.
-
راه حل بهینه:
-
توجه کنید که ما به دنبال اعدادی هستیم که "جذابتر" باشند. برای یک عدد مشخص، امکانپذیر نیست به طور مستقیم همه ترکیبات اعداد کوچکتر (با در نظر گرفتن ویژگیهای جذابیت) را بررسی کنیم.
-
به همین دلیل استفاده از تکنیکهای هوشمندانه شمارش و ترکیبی به همراه استفاده از ویژگیهای نابجاییها و ترتیب ارقام کمک میکنند.
-
در اینجا راهحل ساده به صورت زیر پیادهسازی شده است:
def count_inversions(arr): # Helper function to count inversions if len(arr) < 2: return arr, 0 mid = len(arr) // 2 left, left_inv = count_inversions(arr[:mid]) right, right_inv = count_inversions(arr[mid:]) i = j = 0 sorted_arr = [] inversions = left_inv + right_inv while i < len(left) and j < len(right): if left[i] <= right[j]: sorted_arr.append(left[i]) i += 1 else: sorted_arr.append(right[j]) j += 1 inversions += len(left) - i sorted_arr += left[i:] sorted_arr += right[j:] return sorted_arr, inversions def count_better_necklaces(n): # Convert the given number to a list of digits str_num = str(n) digits = [int(d) for d in str_num] # Calculate the inversions in the given number _, given_inversions = count_inversions(digits) # Start from 0 to n-1 and calculate the numbers with lower inversions count = 0 for current in range(n): current_digits = [int(d) for d in str(current)] _, current_inversions = count_inversions(current_digits) if current_inversions < given_inversions: count += 1 return count n = int(input().strip()) print(count_better_necklaces(n))دقت داشته باشید:
- این راهحل برای ورودیهای با مقیاس بزرگ مستقیم جواب سریع نمیدهد اما منطق اصلی یعنی محاسبه نابجاییها، سپس شمارش ویژگیها را نمایش میدهد.
- برای مسائل بزرگتر و در محدوده کامل باید با تکنیکهای پیشرفتهتر و بهینهسازی بیشتری برخورد کنیم.
-