ستون اکسل

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

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

همه‌ی ۲۶ حرف انگلیسی (A تا Z) برای عنوان ستون‌ها استفاده می‌شوند. عنوان ستون‌ها بر اساس تعداد حرف‌هایشان و سپس به صورت لغت‌نامه‌ای مرتب می‌شوند. در نتیجه عنوان ۲۶ ستون اول یک حرفی و ۲۶×۲۶ ستون بعدی دو حرفی خواهد بود. در زیر شمایی از ترتیب عنوان‌ها را می‌بینید:

A, B, C, …., Z, AA, AB, AC, …., AZ, BA, BB, …, ZY, ZZ

شماره‌ی ستون‌ها از یک شروع می‌شود. یعنی ستون شماره‌ی یک عنوان A را دارد.

ورودی🔗

ورودی تنها شامل یک خط است که در آن شماره‌ی ستون آمده است. تضمین می‌شود عنوان ستون حتماً بین A تا ZZ باشد، در نتیجه شماره‌ی ستون‌ها بین ۱ تا ۷۰۲ است.

خروجی🔗

در یک خط عنوان ستون مورد نظر را با حروف بزرگ انگلیسی چاپ کنید.

مثال🔗

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

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

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

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

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

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

AA

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

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

DK

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

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

ZZ

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک ماشین حساب ساده با یک نمایشگر و دو دکمه‌ی `-2` و `+3` دارید. هنگامی که یکی از دکمه‌ها را می‌فشارید، آن عمل بر عدد روی نمایشگر اعمال می‌شود. برای مثال اگر نمایشگر عدد `10` را نشان می‌دهد، فشردن دکمه‌ی `-2` عدد روی نمایشگر را به `8` تغییر می‌دهد در حالی که اگر دکمه‌ی `+3` را بفشاریم عدد روی نمایشگر به `13` تغییر می‌کند. دو عدد صحیح $A$ و $B$ به شما داده شده است. نمایشگر در ابتدا عدد $A$ را نمایش می‌دهد. شما می‌خواهید با فشردن دکمه‌های ماشین حساب عدد $A$ را به $B$ تغییر دهید. دست کم چند بار دکمه‌ای را باید فشار دهید تا عدد $A$ به $B$ تبدیل شود؟ # ورودی ورودی تنها شامل یک خط است که در آن دو عدد صحیح $A$ و $B$ با فاصله از هم آمده است. $$1 \le A, B \le 100$$ # خروجی در تنها خط خروجی کمترین تعداد عمل لازم برای تبدیل $A$ به $B$ را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 10 14 ``` ## خروجی نمونه ۱ ``` 3 ``` یک راه فشردن دکمه‌ی `+3` برای رسیدن به ‍`13` و سپس `-2` برای رسیدن به `11` و در نهایت ‍`+3` و رسیدن به ‍`14` است. راه‌های دیگری برای رسیدن به همین نتیجه وجود دارد، اما هیچکدام به کمتر از سه عمل نیاز ندارند. ## ورودی نمونه ۲ ``` 23 23 ``` ## خروجی نمونه ۲ ``` 0 ``` چون $A = B$ نیاز نیست دکمه‌ای را بفشاریم. ## ورودی نمونه ۳ ``` 18 12 ``` ## خروجی نمونه ۳ ``` 3 ``` تنها راه حل بهینه سه بار فشردن `-2` است. ## ورودی نمونه ۴ ``` 23 62 ``` ## خروجی نمونه ۴ ``` 13 ```

ماشین حساب باینری

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

یک ماشین حساب ساده با یک نمایشگر و دو دکمه‌ی -2 و +3 دارید. هنگامی که یکی از دکمه‌ها را می‌فشارید، آن عمل بر عدد روی نمایشگر اعمال می‌شود. برای مثال اگر نمایشگر عدد 10 را نشان می‌دهد، فشردن دکمه‌ی -2 عدد روی نمایشگر را به 8 تغییر می‌دهد در حالی که اگر دکمه‌ی +3 را بفشاریم عدد روی نمایشگر به 13 تغییر می‌کند.

دو عدد صحیح $A$ و $B$ به شما داده شده است. نمایشگر در ابتدا عدد $A$ را نمایش می‌دهد. شما می‌خواهید با فشردن دکمه‌های ماشین حساب عدد $A$ را به $B$ تغییر دهید. دست کم چند بار دکمه‌ای را باید فشار دهید تا عدد $A$ به $B$ تبدیل شود؟

ورودی🔗

ورودی تنها شامل یک خط است که در آن دو عدد صحیح $A$ و $B$ با فاصله از هم آمده است. $1 \le A, B \le 100$

خروجی🔗

در تنها خط خروجی کمترین تعداد عمل لازم برای تبدیل $A$ به $B$ را چاپ کنید.

مثال🔗

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

10 14

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

یک راه فشردن دکمه‌ی +3 برای رسیدن به ‍13 و سپس -2 برای رسیدن به 11 و در نهایت ‍+3 و رسیدن به ‍14 است. راه‌های دیگری برای رسیدن به همین نتیجه وجود دارد، اما هیچکدام به کمتر از سه عمل نیاز ندارند.

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

23 23

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

چون $A = B$ نیاز نیست دکمه‌ای را بفشاریم.

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

18 12

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

تنها راه حل بهینه سه بار فشردن -2 است.

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

23 62

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مشتق یک دنباله از اعداد، دنباله‌ای است که از تفریق هر عضو دنباله با عضو کناری آن به دست می‌آید. برای مثال مشتق دنباله‌ی $\{5,6,3,9,-1\}$ برابر با $\{6-5,3-6,9-3,-1-9\} = \{1,-3,6,-10\}$ است. مشتق $N$ام دنباله‌ی $A$ حاصل $N$ بار انجام عمل بالا است. برای مثال اگر $A = \{5,6,3,9,-1\}$ دنباله‌ی مشتق دوم آن به شکل زیر است: $\{5,6,3,9,-1\} \rightarrow\{1,-3,6,-10\} \rightarrow \{-3-1,6-(-3),-10-6\} = \{-4,9,-16\}$ به شما دنباله‌ی $A$ و عدد $N$ داده می‌شود. شما باید مشتق $N$ام $A$ را محاسبه کنید. # ورودی در خط اول ورودی دو عدد طبیعی $K$ و $N$ با فاصله از هم آمده است. در خط بعدی $K$ عدد $a_1, \dots, a_K$ با فاصله از هم آمده است که اعضای دنباله‌ی $A$ را نشان می‌دهد. $$1 \le K \le 20$$ $$0 \le N \le K-1$$ $$-100 \le a_i \le 100, (1 \le i \le N)$$ # خروجی در تنها خط خروجی مشتق $N$ام $A$ را با فاصله از هم چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 5 1 5 6 3 9 -1 ``` ## خروجی نمونه ۱ ``` 1 -3 6 -10 ``` مثال اول در صورت سوال. ## ورودی نمونه ۲ ``` 5 2 5 6 3 9 -1 ``` ## خروجی نمونه ۲ ``` -4 9 -16 ``` مثال دوم در صورت سوال. ## ورودی نمونه ۳ ``` 5 4 5 6 3 9 -1 ``` ## خروجی نمونه ۳ ``` -38 ``` ## ورودی نمونه ۴ ``` 8 3 4 4 4 4 4 4 4 4 ``` ## خروجی نمونه ۴ ``` 0 0 0 0 0 ``` پس از مرحله‌ی اول همه‌ی اعداد صفر می‌شوند. ## ورودی نمونه ۵ ``` 2 0 -100 100 ``` ## خروجی نمونه ۵ ``` -100 100 ``` صفرمین مشتق دنباله برابر با خود دنباله است.

مشتق دنباله

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

مشتق یک دنباله از اعداد، دنباله‌ای است که از تفریق هر عضو دنباله با عضو کناری آن به دست می‌آید. برای مثال مشتق دنباله‌ی $\{5,6,3,9,-1\}$ برابر با $\{6-5,3-6,9-3,-1-9\} = \{1,-3,6,-10\}$ است.

مشتق $N$ ام دنباله‌ی $A$ حاصل $N$ بار انجام عمل بالا است. برای مثال اگر $A = \{5,6,3,9,-1\}$ دنباله‌ی مشتق دوم آن به شکل زیر است:

$\{5,6,3,9,-1\} \rightarrow\{1,-3,6,-10\} \rightarrow \{-3-1,6-(-3),-10-6\} = \{-4,9,-16\}$

به شما دنباله‌ی $A$ و عدد $N$ داده می‌شود. شما باید مشتق $N$ ام $A$ را محاسبه کنید.

ورودی🔗

در خط اول ورودی دو عدد طبیعی $K$ و $N$ با فاصله از هم آمده است. در خط بعدی $K$ عدد $a_1, \dots, a_K$ با فاصله از هم آمده است که اعضای دنباله‌ی $A$ را نشان می‌دهد. $1 \le K \le 20$ $0 \le N \le K-1$ $-100 \le a_i \le 100, (1 \le i \le N)$

خروجی🔗

در تنها خط خروجی مشتق $N$ ام $A$ را با فاصله از هم چاپ کنید.

مثال🔗

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

5 1
5 6 3 9 -1

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

1 -3 6 -10

مثال اول در صورت سوال.

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

5 2
5 6 3 9 -1

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

-4 9 -16

مثال دوم در صورت سوال.

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

5 4
5 6 3 9 -1

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

-38

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

8 3
4 4 4 4 4 4 4 4

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

0 0 0 0 0

پس از مرحله‌ی اول همه‌ی اعداد صفر می‌شوند.

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

2 0
-100 100

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

-100 100

صفرمین مشتق دنباله برابر با خود دنباله است.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در سیستم‌های کامپیوتری داده‌ها در قالب **فایل** در حافظه ذخیره می‌شوند. هر فایل ممکن است درون یک **دایرکتوری** باشد و هر دایرکتوری ممکن است درون دایرکتوری‌های دیگر باشد. یک **مسیر** نشان دهنده‌ی یک فایل یا دایرکتوری خاص در این ساختار است. اکثر سیستم عامل‌های شبه یونیکس یک دایرکتوری **ریشه** دارند که شامل تمام فایل‌ها و دایرکتوری‌های دیگر به صورت مستقیم یا غیر مستقیم می‌شود. در این سیستم عامل‌ها ساختار زیر برای آدرس دهی فایل‌ها استفاده می‌شود: ``` /<directory-name>/<directory-name>/.../<directory-name>/<file-name> ``` همچنین ساختار زیر برای آدرس دهی دایرکتوری‌ها استفاده می‌شود: ``` /<directory-name>/<directory-name>/.../<directory-name> ``` برای مثال `/etc/passwd` فایلی به نام `passwd` در دایرکتوری `etc` در دایرکتوری ریشه را نشان می‌دهد. آدرس‌های صحیح دیگر `/home/user/pictures/digikala` و یا فقط `/file` هستند. در این سوال ما فقط فایل‌ها و دایرکتوری‌هایی را در نظر می‌گیریم که نامشان متشکل از حروف کوچک انگلیسی (a تا z) است. دایرکتوری ریشه حالت خاصی است که با `/` نشان داده می‌شود. هنگامی که کاربر در حال کارکردن با چنین سیستم عاملیست یک دایرکتوری به عنوان دایرکتوری فعلی در نظر گرفته می‌شود. اینگونه کاربر می‌تواند بدون مشخص کردن مسیر کامل دایرکتوری فعلی به فایل‌های درون آن دسترسی پیدا کند. به این روش آدرس دهی، **آدرس دهی نسبی** گفته می‌شود. برای مثال اگر دایرکتوری فعلی `/home/user/pictures` باشد، کاربر می‌تواند به فایل `/home/user/pictures/digikala` از طریق آدرس `digikala` دسترسی داشته باشد. توجه کنید که به دلیل عدم وجود `/` در ابتدای آدرس، مشخص می‌شود که مسیر از دایرکتوری فعلی شروع می‌شود. همچنین دایرکتوری‌های داخلی نیز می‌توانند اینگونه آدرس دهی شوند. برای مثال `/home/user/pictures/others/digipay` می‌تواند به صورت `others/digipay` آدرس دهی شود. نکته‌ی جالب‌تر این است که می‌توانیم با این روش به فایل‌های خارج از دایرکتوری فعلی نیز دسترسی داشته باشیم. به طور دقیق‌تر آدرس `..` به معنی دایرکتوری‌ای است که یک سطح از دایرکتوری فعلی بالاتر است. همچنین `../..` به معنی دایرکتوری دو سطح بالاتر از دایرکتوری فعلی است. حال اگر دایرکتوری فعلی `/home/user/pictures` باشد و شما می‌خواهید به `/home/top/data/file` دسترسی پیدا کنید می‌توانید آدرس را به صورت `../../top/data/file` بیان کنید. به شما آدرس یک فایل که می‌خواهید به آن دسترسی پیدا کنید و آدرس دایرکتوری فعلی داده می‌شود. شما باید **کوتاه‌ترین آدرس نسبی** برای دسترسی به آن فایل را پیدا کنید. برای مثال اگر دایرکتوری فعلی `/home/user/pictures` باشد شما باید `../movies/title` را به `../../user/movies/title` در هنگام دسترسی به فایل `/home/user/movies/title‍` ترجیح دهید. بعضی از فایل‌ها و دایرکتوری‌ها ممکن است نام‌های مشترک داشته باشند، اما غیر ممکن است که دو فایل یا دو دایرکتوری یا یک فایل و یک دایرکتوری، با نام یکسان درون یک دایرکتوری وجود داشته باشد. پس کلیه‌ی آدرس‌ها یکتا هستند. ورودی‌های مساله آدرس‌های درست هستند و در مسیرهای داده شده تناقض وجود نخواهد داشت. برای مثال آدرس فعلی `/home/user/digikala/other` و فایل `/home/user/digikala` با هم در تناقض هستند. زیرا همزمان یک دایرکتوری و فایل با نام `digikala` در دایرکتوری `user` وجود دارد. # ورودی در سطر اول ورودی آدرس فایل مورد نظر و در سطر دوم آدرس دایرکتوری فعلی داده شده است. طول هیچ آدرسی بیشتر از ۵۰ کاراکتر نخواهد بود. تضمین می‌شود آدرس‌ها درست و دارای تناقض نخواهند بود. نام فایل‌ها و دایرکتوری‌ها نیز فقط از حروف کوچک انگلیسی (a تا z) تشکیل شده است. # خروجی در تنها خط خروجی آدرس نسبی فایل مورد نظر را از دایرکتوری فعلی چاپ کنید. # مثال ## ورودی نمونه ۱ ``` /home/top/data/file /home/user/pictures ``` ## خروجی نمونه ۱ ``` ../../top/data/file ``` مثال صورت سوال. ## ورودی نمونه ۲ ``` /home/user/movies/title /home/user/pictures ``` ## خروجی نمونه ۲ ``` ../movies/title ``` مثال دیگر صورت سوال. ## ورودی نمونه ۳ ``` /file / ``` ## خروجی نمونه ۳ ``` file ``` دایرکتوری ریشه را فراموش نکنید. ## ورودی نمونه ۴ ``` /a/b/a/b/a/b /a/b/a/a/b/a/b ``` ## خروجی نمونه ۴ ``` ../../../../b/a/b ``` نام برخی فایل‌ها و دایرکتوری‌ها ممکن است یکسان باشد. ## ورودی نمونه ۵ ``` /root/root/root /root ``` ## خروجی نمونه ۵ ``` root/root ``` نام فایل‌ها یا دایرکتوری‌ها ممکن است `root` باشد و به این معنی نیست که دایرکتوری ریشه هستند.

مسیر نسبی

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

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

/<directory-name>/<directory-name>/.../<directory-name>/<file-name>

همچنین ساختار زیر برای آدرس دهی دایرکتوری‌ها استفاده می‌شود:

/<directory-name>/<directory-name>/.../<directory-name>

برای مثال /etc/passwd فایلی به نام passwd در دایرکتوری etc در دایرکتوری ریشه را نشان می‌دهد. آدرس‌های صحیح دیگر /home/user/pictures/digikala و یا فقط /file هستند. در این سوال ما فقط فایل‌ها و دایرکتوری‌هایی را در نظر می‌گیریم که نامشان متشکل از حروف کوچک انگلیسی (a تا z) است.

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

هنگامی که کاربر در حال کارکردن با چنین سیستم عاملیست یک دایرکتوری به عنوان دایرکتوری فعلی در نظر گرفته می‌شود. اینگونه کاربر می‌تواند بدون مشخص کردن مسیر کامل دایرکتوری فعلی به فایل‌های درون آن دسترسی پیدا کند. به این روش آدرس دهی، آدرس دهی نسبی گفته می‌شود. برای مثال اگر دایرکتوری فعلی /home/user/pictures باشد، کاربر می‌تواند به فایل /home/user/pictures/digikala از طریق آدرس digikala دسترسی داشته باشد. توجه کنید که به دلیل عدم وجود / در ابتدای آدرس، مشخص می‌شود که مسیر از دایرکتوری فعلی شروع می‌شود. همچنین دایرکتوری‌های داخلی نیز می‌توانند اینگونه آدرس دهی شوند. برای مثال /home/user/pictures/others/digipay می‌تواند به صورت others/digipay آدرس دهی شود.

نکته‌ی جالب‌تر این است که می‌توانیم با این روش به فایل‌های خارج از دایرکتوری فعلی نیز دسترسی داشته باشیم. به طور دقیق‌تر آدرس .. به معنی دایرکتوری‌ای است که یک سطح از دایرکتوری فعلی بالاتر است. همچنین ../.. به معنی دایرکتوری دو سطح بالاتر از دایرکتوری فعلی است. حال اگر دایرکتوری فعلی /home/user/pictures باشد و شما می‌خواهید به /home/top/data/file دسترسی پیدا کنید می‌توانید آدرس را به صورت ../../top/data/file بیان کنید.

به شما آدرس یک فایل که می‌خواهید به آن دسترسی پیدا کنید و آدرس دایرکتوری فعلی داده می‌شود. شما باید کوتاه‌ترین آدرس نسبی برای دسترسی به آن فایل را پیدا کنید. برای مثال اگر دایرکتوری فعلی /home/user/pictures باشد شما باید ../movies/title را به ../../user/movies/title در هنگام دسترسی به فایل /home/user/movies/title‍ ترجیح دهید.

بعضی از فایل‌ها و دایرکتوری‌ها ممکن است نام‌های مشترک داشته باشند، اما غیر ممکن است که دو فایل یا دو دایرکتوری یا یک فایل و یک دایرکتوری، با نام یکسان درون یک دایرکتوری وجود داشته باشد. پس کلیه‌ی آدرس‌ها یکتا هستند. ورودی‌های مساله آدرس‌های درست هستند و در مسیرهای داده شده تناقض وجود نخواهد داشت. برای مثال آدرس فعلی /home/user/digikala/other و فایل /home/user/digikala با هم در تناقض هستند. زیرا همزمان یک دایرکتوری و فایل با نام digikala در دایرکتوری user وجود دارد.

ورودی🔗

در سطر اول ورودی آدرس فایل مورد نظر و در سطر دوم آدرس دایرکتوری فعلی داده شده است. طول هیچ آدرسی بیشتر از ۵۰ کاراکتر نخواهد بود. تضمین می‌شود آدرس‌ها درست و دارای تناقض نخواهند بود. نام فایل‌ها و دایرکتوری‌ها نیز فقط از حروف کوچک انگلیسی (a تا z) تشکیل شده است.

خروجی🔗

در تنها خط خروجی آدرس نسبی فایل مورد نظر را از دایرکتوری فعلی چاپ کنید.

مثال🔗

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

/home/top/data/file
/home/user/pictures

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

../../top/data/file

مثال صورت سوال.

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

/home/user/movies/title
/home/user/pictures

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

../movies/title

مثال دیگر صورت سوال.

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

/file
/

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

file

دایرکتوری ریشه را فراموش نکنید.

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

/a/b/a/b/a/b
/a/b/a/a/b/a/b

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

../../../../b/a/b

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

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

/root/root/root
/root

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

root/root

نام فایل‌ها یا دایرکتوری‌ها ممکن است root باشد و به این معنی نیست که دایرکتوری ریشه هستند.

قورباغه

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

قورباغه‌ای روی محور اعداد زندگی می‌کند. $N$ جزیره روی محور اعداد وجود دارد و $i$ امین جزیره در نقطه‌ی $a_i$ قرار دارد، ( $1 \le i \le N$ ). قورباغه در ابتدا در نقطه‌ی $a_1$ است. او با هر پرش می‌تواند به جزیره‌ای به فاصله‌ی حداکثر $L$ برود. او نمی‌تواند به نقطه‌ای برود که جزیره‌ای وجود ندارد.

یک جزیره قابل دسترسی است اگر قورباغه بتواند با تعدادی پرش به آن برسد. تعداد جزیره‌های قابل دسترسی چند تاست؟

ورودی🔗

در خط اول ورودی دو عدد طبیعی $N$ و $L$ با فاصله از هم آمده است. در خط دوم ورودی اعداد $a_1, a_2, \dots, a_N$ با فاصله از هم آمده است که بیانگر موقعیت جزیره‌هاست.

خروجی🔗

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

مثال🔗

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

5 1
4 7 1 3 5

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

قورباغه در نقطه‌ی ۴ قرار دارد و حداکثر طول پرشش ۱ است. در نتیجه فقط به جزیره‌های واقع در ۳، ۴ و ۵ می‌تواند برود.

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

5 2
100 101 103 105 107

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

او به تمام ۵ جزیره می‌تواند برود.

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

8 4
17 10 22 14 6 1 2 3

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

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

1 1000
0

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- همکاران بخش مرکز پردازش دیجی‌کالا در حال تکمیل تعدادی سبد‌ خرید هستند و ما می‌خواهیم بدانیم که تکمیل شدن تمام سبد‌ها چه‌قدر طول می‌کشد. برای هر سبد، سرعت تکمیل سبد برحسب تعداد کالاهایی که در هر ساعت اضافه می‌شوند و تعداد دقایق مانده تا تکمیل سبد بر اساس سرعتش داده شده است. مجموع سرعت تمام سبد‌ها برابر با توان تمام همکاران دیجی‌کالا است و تا پایان تکمیل شدن تمام سبد‌ها ثابت باقی خواهد ماند و در هر لحظه به طور کامل استفاده خواهد شد.به این معنی که وقتی یک سبد تکمیل می‌شود، همکاران آزاد شده در بستن سبدهای دیگر کمک خواهند کرد. شیوه‌ی تقسیم شدن همکاران برای تکمیل سبدها در پاسخ نهایی تاثیری نخواهد داشت. برای مثال دو سبد را در نظر بگیرید: + یه سبد اول هر دقیقه سه کالا اضافه می‌شود و ۱۴ دقیقه تا تکمیل آن زمان مانده است. + به سبد دوم هر دقیقه دو کالا اضافه می‌شود و ۹ دقیقه تا تکمیل آن زمان مانده است. بعد از ۹ ثانیه، سبد دوم تکمیل خواهد شد و سبد اول هنوز ۵ دقیقه زمان لازم دارد؛ اما این زمان بر اساس سرعت قبلی محاسبه شده است. همکاران آزاد شده به کمک همکاران سبد اول خواهند رفت و سرعت جدید آن ۲ +‌ ۳ = ۵ خواهد شد و زمان جدید پس از محاسبه برابر با ۳ دقیقه خواهد بود. پس تمام سبد ها پس از ۱۲ دقیقه تکمیل خواهند شد. به شما وضعیت فعلی سبد‌ها داده خواهد شد. شما باید محاسبه کنید چند دقیقه‌ی دیگر تمام سبد‌ها تکمیل خواهند شد. # ورودی خط اول ورودی شامل عدد $n$ نشان دهنده‌ی تعداد سبد‌هاست. در $n$ خط بعدی در هر خط دو عدد $s_i$ و $r_i$ با فاصله از هم آمده است که به ترتیب نشان دهنده‌ی سرعت تکمیل سبد و زمان باقیمانده است. $$ 1 \le N \le 50 $$ $$ 1 \le s_i \le 100, (1 \le i \le N) $$ $$ 1 \le r_i \le 10000, (1 \le i \le N) $$ # خروجی در تنها خط خروجی زمان باقیمانده برای تکمیل شدن تمام سبد‌ها را با سه رقم اعشار چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 2 3 14 2 9 ``` ## خروجی نمونه ۱ ``` 12.000 ``` مثال صورت سوال. ## ورودی نمونه ۲ ``` 2 3 1057 2 1022 ``` ## خروجی نمونه ۲ ``` 1043.000 ``` ## ورودی نمونه ۳ ``` 3 25 1000 5 5000 10 5000 ``` ## خروجی نمونه ۳ ``` 2500.000 ``` ## ورودی نمونه ۴ ``` 3 1 10 1 20 2 40 ``` ## خروجی نمونه ۴ ``` 27.500 ``` ## ورودی نمونه ۵ ``` 8 6 88 39 7057 63 2502 45 2285 28 8749 62 3636 1 5546 49 5741 ``` ## خروجی نمونه ۵ ``` 4414.543 ```

مرکز پردازش دیجی‌کالا

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

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

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

برای مثال دو سبد را در نظر بگیرید:

یه سبد اول هر دقیقه سه کالا اضافه می‌شود و ۱۴ دقیقه تا تکمیل آن زمان مانده است.
به سبد دوم هر دقیقه دو کالا اضافه می‌شود و ۹ دقیقه تا تکمیل آن زمان مانده است.

بعد از ۹ ثانیه، سبد دوم تکمیل خواهد شد و سبد اول هنوز ۵ دقیقه زمان لازم دارد؛ اما این زمان بر اساس سرعت قبلی محاسبه شده است. همکاران آزاد شده به کمک همکاران سبد اول خواهند رفت و سرعت جدید آن ۲ +‌ ۳ = ۵ خواهد شد و زمان جدید پس از محاسبه برابر با ۳ دقیقه خواهد بود. پس تمام سبد ها پس از ۱۲ دقیقه تکمیل خواهند شد.

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

ورودی🔗

خط اول ورودی شامل عدد $n$ نشان دهنده‌ی تعداد سبد‌هاست. در $n$ خط بعدی در هر خط دو عدد $s_i$ و $r_i$ با فاصله از هم آمده است که به ترتیب نشان دهنده‌ی سرعت تکمیل سبد و زمان باقیمانده است.

$1 \le N \le 50$ $1 \le s_i \le 100, (1 \le i \le N)$ $1 \le r_i \le 10000, (1 \le i \le N)$

خروجی🔗

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

مثال🔗

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

2
3 14
2 9

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

12.000

مثال صورت سوال.

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

2
3 1057
2 1022

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

1043.000

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

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

2500.000

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

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

27.500

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

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

4414.543

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک صف دو طرفه شامل $N$ عضو داریم. شما باید چند عضو خاص از این صف را بیرون بیاورید. می‌توانید سه عمل زیر را بر روی صف انجام دهید: 1. عضو اول را بیرون بیاورید. پس از این عمل صف $a_1, \dots, a_K$ تبدیل به $a_2, \dots, a_K$ می‌شود. 2. صف را به سمت چپ بچرخانید. پس از این عمل صف $a_1, \dots, a_K$ تبدیل به $a_2, \dots, a_K, a_1$ می‌شود. 3. صف را به سمت راست بچرخانید. پس از این عمل صف $a_1, \dots, a_K$ تبدیل به $a_K, a_1, \dots, a_{K-1}$ می‌شود. به شما اندازه‌ی صف و اندیس عضو‌های مورد نظر داده شده است. بگویید حداقل چند عمل چرخش برای بیرون آوردن عضو‌های مورد نظر به ترتیب داده شده نیاز است؟ # ورودی در سطر اول ورودی دو عدد طبیعی $N$ و $M$، به ترتیب نشان دهنده‌ی تعداد اعضای صف و تعداد اعضای مورد نظر، با فاصله از هم آمده است. در سطر دوم ورودی اعداد $p_1, \dots, p_M$ ، نشان دهنده‌ی اندیس عضو‌های مورد نظر، با فاصله از هم آمده است. اعضای این دنباله دو به دو متفاوتند. $$1 \le M \le N \le 50$$ $$1 \le p_i \le N $$ # خروجی در تنها سطر خروجی تعداد اعمال چرخش لازم برای بیرون آوردن اعضای مورد نظر به ترتیب داده شده را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 10 3 1 2 3 ``` ## خروجی نمونه ۱ ``` 0 ``` عضو‌ها به همان ترتیبی که در صف ظاهر شده‌اند بیرون می‌آیند و چرخشی لازم نیست. ## ورودی نمونه ۲ ``` 10 3 2 9 5 ``` ## خروجی نمونه ۲ ``` 8 ``` برای بیرون آوردن اولین عضو یک چرخش به چپ نیاز است. سپس برای بیرون آوردن المان دوم سه چرخش به راست نیاز است. المان سوم را نیز می‌توان با چهار چرخش به راست یا چپ بیرون آورد. ## ورودی نمونه ۳ ``` 32 6 27 16 30 11 6 23 ``` ## خروجی نمونه ۳ ``` 59 ``` ## ورودی نمونه ۴ ``` 10 10 1 6 3 2 7 9 8 4 10 5 ``` ## خروجی نمونه ۴ ``` 14 ```

صف دو طرفه

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

یک صف دو طرفه شامل $N$ عضو داریم. شما باید چند عضو خاص از این صف را بیرون بیاورید.

می‌توانید سه عمل زیر را بر روی صف انجام دهید:

عضو اول را بیرون بیاورید. پس از این عمل صف $a_1, \dots, a_K$ تبدیل به $a_2, \dots, a_K$ می‌شود.
صف را به سمت چپ بچرخانید. پس از این عمل صف $a_1, \dots, a_K$ تبدیل به $a_2, \dots, a_K, a_1$ می‌شود.
صف را به سمت راست بچرخانید. پس از این عمل صف $a_1, \dots, a_K$ تبدیل به $a_K, a_1, \dots, a_{K-1}$ می‌شود.

به شما اندازه‌ی صف و اندیس عضو‌های مورد نظر داده شده است. بگویید حداقل چند عمل چرخش برای بیرون آوردن عضو‌های مورد نظر به ترتیب داده شده نیاز است؟

ورودی🔗

در سطر اول ورودی دو عدد طبیعی $N$ و $M$ ، به ترتیب نشان دهنده‌ی تعداد اعضای صف و تعداد اعضای مورد نظر، با فاصله از هم آمده است. در سطر دوم ورودی اعداد $p_1, \dots, p_M$ ، نشان دهنده‌ی اندیس عضو‌های مورد نظر، با فاصله از هم آمده است. اعضای این دنباله دو به دو متفاوتند.

$1 \le M \le N \le 50$ $1 \le p_i \le N$

خروجی🔗

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

مثال🔗

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

10 3
1 2 3

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

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

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

10 3
2 9 5

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

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

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

32 6
27 16 30 11 6 23

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

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

10 10
1 6 3 2 7 9 8 4 10 5

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در سال‌های اخیر تولید کننده‌های CPU، در تلاش بوده‌اند تا پردازنده‌هایی با تعداد هسته‌های پردازشی بیشتری تولید کنند. گاهی اوقات استفاده از چندین هسته برای پردازش‌های حجیم برای برنامه‌نویس‌ها چالش برانگیز می‌شود. معمولا وقتی پردازشی حجیم به چند بخش شکسته می‌شود، هزینه‌ی محاسباتی جدیدی برای شکستن کار و جمع بندی نتایج پردازش به وجود می‌آید. برای مثال انتظار داریم پردازشی که بر روی یک هسته در ۱۰۰۰ میلی‌ثانیه انجام می‌شود، روی دو هسته در ۵۰۰ میلی‌ثانیه انجام شود در حالی که در واقعیت ۶۵۰ میلی‌ثانیه زمان صرف پردازش می‌شود. تیم شما می‌خواهد پردازشی حجیم انجام دهد. برای این پردازش $J$ واحد محاسبه نیاز است انجام شود. اگر از چندین هسته برای انجام پردازش استفاده کنیم، پردازش به صورت برابر بین هسته‌ها تقسیم می‌شود. برای مثال اگر ۱۰۰۰ واحد محاسبه را بین ۳ پردازنده تقسیم کنیم هر پردازنده باید دقیقا $1000/3$ واحد محاسبه انجام دهد. شما تعدادی سیستم در دسترس دارید تا محاسبه را بر روی آن‌ها انجام دهید. هر سیستم تعدادی هسته دارد و سرعت پردازش هسته‌های هر سیستم یکسان است. شما باید یکی از سیستم‌ها را برای پردازش خود انتخاب کنید و تصمیم بگیرید از چند هسته‌ی آن برای پردازش استفاده می‌کنید. سیستم‌ها از ۱ تا $N$ شماره گذاری شده‌اند. سیستم $i$ام $c_i$ هسته دارد و هر هسته‌ی آن می‌تواند در هر میلی‌ثانیه $s_i$ واحد محاسبه انجام دهد. به دلیل سربار پردازش موازی، $P$ واحد محاسبه به ازای هر هسته بعد از اولین هسته به حجم کلی محاسبات اضافه می‌شود. این ثابت برای تمام سیستم‌های شما یکسان است. شما باید کوچک ترین عدد مثبت $T$ را بیابید که پردازش را می‌تواند در $T$ میلی‌ثانیه با تعدادی از پردازنده‌های یکی از سیستم‌ها انجام داد. # ورودی در خط اول ورودی اعداد $N$، $J$ و $P$ با فاصله از هم آمده است. در $N$ خط بعدی به ازای هر پردازنده اعداد $s_i$ و $c_i$ با فاصله از هم آمده است. $$1 \le N \le 50$$ $$1 \le J \le 10^9$$ $$0 \le P \le 10^6$$ $$1 \le s_i \le 10^6$$ $$1 \le c_i \le 10^3$$ # خروجی در تنها خط خروجی عدد $T$ را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 2 2000 5 40 2 20 4 ``` ## خروجی نمونه ۱ ``` 30 ``` توان پردازشی دو سیستم یکسان است ولی به دلیل سربار پردازش موازی از دو پردازنده‌ی سیستم اول استفاده می‌کنیم. ## ورودی نمونه ۲ ``` 2 2000 5 10 2 20 4 ``` ## خروجی نمونه ۲ ``` 40 ``` ## ورودی نمونه ۳ ``` 1 1000 0 10 3 ``` ## خروجی نمونه ۳ ``` 34 ``` ## ورودی نمونه ۴ ``` 3 10000 5 39 8 37 16 44 6 ``` ## خروجی نمونه ۴ ``` 63 ``` مشخصات پردازنده‌های امروزی تقریبا اینگونه است.

پردازش چند هسته‌ای

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

در سال‌های اخیر تولید کننده‌های CPU، در تلاش بوده‌اند تا پردازنده‌هایی با تعداد هسته‌های پردازشی بیشتری تولید کنند. گاهی اوقات استفاده از چندین هسته برای پردازش‌های حجیم برای برنامه‌نویس‌ها چالش برانگیز می‌شود. معمولا وقتی پردازشی حجیم به چند بخش شکسته می‌شود، هزینه‌ی محاسباتی جدیدی برای شکستن کار و جمع بندی نتایج پردازش به وجود می‌آید. برای مثال انتظار داریم پردازشی که بر روی یک هسته در ۱۰۰۰ میلی‌ثانیه انجام می‌شود، روی دو هسته در ۵۰۰ میلی‌ثانیه انجام شود در حالی که در واقعیت ۶۵۰ میلی‌ثانیه زمان صرف پردازش می‌شود.

تیم شما می‌خواهد پردازشی حجیم انجام دهد. برای این پردازش $J$ واحد محاسبه نیاز است انجام شود. اگر از چندین هسته برای انجام پردازش استفاده کنیم، پردازش به صورت برابر بین هسته‌ها تقسیم می‌شود. برای مثال اگر ۱۰۰۰ واحد محاسبه را بین ۳ پردازنده تقسیم کنیم هر پردازنده باید دقیقا $1000/3$ واحد محاسبه انجام دهد.

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

سیستم‌ها از ۱ تا $N$ شماره گذاری شده‌اند. سیستم $i$ ام $c_i$ هسته دارد و هر هسته‌ی آن می‌تواند در هر میلی‌ثانیه $s_i$ واحد محاسبه انجام دهد.

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

شما باید کوچک ترین عدد مثبت $T$ را بیابید که پردازش را می‌تواند در $T$ میلی‌ثانیه با تعدادی از پردازنده‌های یکی از سیستم‌ها انجام داد.

ورودی🔗

در خط اول ورودی اعداد $N$ ، $J$ و $P$ با فاصله از هم آمده است. در $N$ خط بعدی به ازای هر پردازنده اعداد $s_i$ و $c_i$ با فاصله از هم آمده است.

$1 \le N \le 50$ $1 \le J \le 10^9$ $0 \le P \le 10^6$ $1 \le s_i \le 10^6$ $1 \le c_i \le 10^3$

خروجی🔗

در تنها خط خروجی عدد $T$ را چاپ کنید.

مثال🔗

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

2 2000 5
40 2
20 4

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

توان پردازشی دو سیستم یکسان است ولی به دلیل سربار پردازش موازی از دو پردازنده‌ی سیستم اول استفاده می‌کنیم.

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

2 2000 5
10 2
20 4

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

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

1 1000 0
10 3

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

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

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

مشخصات پردازنده‌های امروزی تقریبا اینگونه است.