* محدودیت زمان: ۰.۵ ثانیه * محدودیت حافظه: ۱۲۸ مگابایت ---------- به سه‌تایی مرتب $(a, b, c)$ می‌گوییم **مثلثی** اگر $a, b, c$ سه عدد مثبت باشند و مثلثی به اضلاع $a, b, c$ وجود داشته باشد. به عنوان مثال $(4, 5, 6)$ و $(5, 4, 6)$ دو سه‌تایی مثلثی متفاوتند. به شما سه عدد طبیعی $A, B, C$ داده می‌شود. تعداد سه‌تایی‌های مثلثی مانند $(a, b, c)$ را به پیمانه $10^9+7$ بیابید طوری که $1 \le a \le A $ و $1 \le b \le B $ و $1 \le c \le C $ باشد. # ورودی ورودی یک خط می‌باشد که شامل سه عدد $A, B, C$ است. $$1 \le A, B, C \le 10^9$$ # خروجی خروجی برنامه تنها یک عدد است که برابر با تعداد سه‌تایی‌های مثلثی با شرایط گفته شده به پیمانه $10^9+7$ است. # زیرمسئله‎ها | زیرمسئله | نمره | محدودیت | |:-------:|:----------:|:-----------:| |۱| ۱۰ | $A \times B \times C \le 10^6 $ | |۲| ۲۰ |$\dfrac{A \times B \times C}{max(A, B, C)} \le 10^6 $| |۳| ۷۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 1 10 20 ``` ## خروجی نمونه ۱ ``` 10 ``` ## ورودی نمونه ۲ ``` 10 10 10 ``` ## خروجی نمونه ۲ ``` 505 ``` ## ورودی نمونه ۳ ``` 1 1 1 ``` ## خروجی نمونه ۳ ``` 1 ``` ## ورودی نمونه ۴ ``` 123456789 987654321 555555555 ``` ## خروجی نمونه ۴ ``` 64296241 ``` ## ورودی نمونه ۵ ``` 2 2 1000000000 ``` ## خروجی نمونه ۵ ``` 6 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۱۲۸ مگابایت ---------- روزی روزگاری $n$ تا از کامیون‌های شرکت باربری بمنثقتفخل بزرگراه امام علی (ع) را طی می‌کنند. همان‌طور که می‌دانید بزرگراه دارای $10^6$ ورودی و $10^6$ خروجی است به این صورت که ورودی $i$-ام روبه‌روی خروجی $i$-ام است. وقتی یک کامیون وارد بزرگراه می‌شود راننده آن یک بلیط سبز دریافت می‌کند که روی آن شماره آن ورودی و یک بلیط قرمز دریافت می‌کند که روی آن شماره خروجی که باید از آن خارج شود ثبت شده است. در هنگام خروج کامیون‌ها باید عوارض به مقدار اختلاف شماره دو عدد روی بلیط سبز و قرمز خود بپردازند. بمنثقتفخل راهی پیدا کرده است تا رانندگانش عوارض کمتری بپردازد.هر دو راننده می‌توانند یکدیگر را در بزرگراه ملاقات کنند و بلیط‌های قرمز خود را با هم عوض کنند، حتی اگر هم مسیر نباشند. به هر حال یک راننده نمی‌تواند از خروجی‌ای که از آن وارد بزرگراه شده است خارج شود زیرا این کار خیلی مشکوک است. شرکت باربری بمنثقتفخل از شما می‌خواهد برایش کمینه مجموع عوارضی که باید رانندگانش بپردازند را حساب کنید. # ورودی خط اول ورودی فقط شامل عدد $n$ است. در $n$ خط بعدی در هر خط دو عدد غیر برابر در بازه $1$ تا $10^6$ وجود دارد که به ترتیب شماره بلیط سبز و قرمز راننده $i$-ام است. هیچ دو راننده‌ای بلیط سبز برابر یا بلیط قرمز برابر ندارند. $$ 1 \le n \le 100\ 000$$ # زیرمسئله‎ها | زیرمسئله | نمره | محدودیت | |:-------:|:----------:|:-----------:| |۱| ۵ | $n\le 10$ | |۲| ۱۵ | $n \le 20$ | |۳| ۸۰ | بدون محدودیت اضافی | # خروجی خروجی برنامه تنها یک عدد است که برابر با کمینه مجموع عوارضی که باید رانندگان بمنثقتفخل بپردازند است. # مثال ## ورودی نمونه ۱ ``` 3 3 65 45 10 60 25 ``` ## خروجی نمونه ۱ ``` 32 ``` اگر راننده اول و سوم بلیط‌های قرمز خود را با هم عوض کنند سپس راننده دوم و سوم اینکار را انجام دهند. بعد از این کار بلیط قرمز رانندگان به ترتیب برابر ۱۰ و ۲۵ و ۶۵ می‌شود و مجموع عوارض پرداختی برابر $|65-60|+|25-45|+|10-3|=32$ می‌شود. ## ورودی نمونه ۲ ``` 3 5 5 6 7 8 8 ``` ## خروجی نمونه ۲ ``` 5 ```

* محدودیت زمان: ۰.۵ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ---------- می‌گوییم دو دایره نسبت به هم اوکی اند اگر و تنها اگر یکی اکیدن داخل دیگری باشد و محیطشان هیچ نقطه‌ی مشترکی نداشته باشد. مجموعه‌ای از دوایر را خوب می‌نامیم اگر و تنها اگر هر دو دایره در این مجموعه نسبت به هم اوکی باشند. $n$ دایره داریم، آن‌ها را به کمینه تعداد مجموعه‌ی خوب افراز کنید. # ورودی در سطر اول ورودی عدد طبیعی $n$ آمده است. در هر کدام از $n$ سطر بعد یک دایره، با سه عدد صحیح $ x_i, y_i, r_i $ (مختصات مرکز و شعاعش) آمده است. $$1 \le n \le 400 $$$$1 \le x_i, y_i, r_i \le 10^9 $$ # خروجی در یک سطر، کمینه تعداد مجموعه‌ها را در افراز بهینه چاپ کنید. # زیرمسئله‎ها | زیرمسئله | نمره | محدودیت | |:-------:|:----------:|:-----------:| |۱| ۵ | $ n \le 16 $ | |۲| ۵ | $ n \le 21 $ | |۳| ۱۰ | همه دایره‌ها هم مرکز اند. | |۴| ۲۰ | $x_1=x_2=...=x_n$ | |۵| ۶۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ``` 3 1 1 5 2 2 5 3 3 1 ``` ## خروجی نمونه ``` 2 ``` دایره‌ها را به دو دسته می‌توان افراز کرد. در یک دسته دایره‌ی ۱ و در دسته‌ی دیگر دایره‌ی ۲ و ۳.