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

اعداد را می‌توان به صورت‌های مختلفی نمایش داد. مثلاً می‌توان به صورت ده‌دهی٬ رومی٬ مبنای دو و ... نشان داد!

در این سوال ما با دو نوع نمایش علمی و نمایش روی صفحه‌ی دیجیتال ۷ سگمنت seven segment سروکار داریم.

• در نمایش علمی عدد به صورت دو بخش نوشته می‌شود یک بخش یک عدد اعشاری است که دقیقاً یک رقمِ بیشتر از صفر قبل از ممیز دارد (و اگر ممیز نداشته باشد یک رقمی است) بخش اول و بخش دوم توسط یک کاراکتر $e$ جدا می‌شوند و بخش دوم یک عدد صحیح نامنفی است. در این صورت اگر بخش اول عدد $a$ باشد و بخش دوم عدد $b$ باشد٬ عدد واقعی‌مان $a \times 10^b$ است. طبق این تعریف $0.3e10$ یک نمایش علمی نیست‌ و باید به صورت $3e9$ نوشته شود و همچنین $2e0$ بیانگر عدد $2$ و $2.33e3$ بیانگر عدد $2330$ می‌باشد.

• در نمایش seven segment که روی صفحات دیجیتال وجود دارد ۷ عدد چراغ LED به صورت شکل زیر گذاشته شده‌است که می‌تواند ارقام مختلف را از ۰ تا ۹ نمایش دهد و برای نمایش یک عدد $k$ رقمی باید از $k$ تا از این ۷ سگمنت‌ها استفاده شود.

میزان برق مورد نیاز برای نمایش یک عدد را برابر تعداد چراغ‌هایی تعریف می‌کنیم که برای نمایش آن لازم است.

در این سوال به شما عددی طبیعی بیشتر از ۰ در نمایش علمی معتبر داده می‌شود و شما باید بگویید اگر این عدد را روی یک صفحه ی دیجیتال نمایش دهیم٬ چند واحد برق مصرف می‌شود.

ورودی🔗

به شما رشته‌ی $s$ در ورودی داده می‌شود که یک نمایش علمی معتبر از عددی طبیعی ‌است.

$3 \le |s| \le 10$

خروجی🔗

در تنها خط خروجی میزان برق مصرف شده برای نمایش ۷ سگمنت را خروجی دهید.

مثال🔗

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

2.3e10

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

64

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

8e10000000

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

60000007

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

9e0

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

6

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

شنگدباو و دوستش درحال "سنگ-کاغد-قیچی" بازی کردن هستند! می‌دانیم شنگدباو $P$ بازی اول کاغذ، $R$ بازی بعد سنگ و $S$ بازی اخر قیچی می‌آورد.

اگر دوستش بخواهد $a$ بار کاغد، $b$ بار سنگ و $c$ بار قیچی بیاورد، دوستش ماکسیمم امتیازی که می‌تواند به دست بیاورد چند است؟

دوستش می‌تواند به هرترتیبی کاغذ، سنگ و قیچی بیاورد.

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

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

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

ورودی🔗

در تنها خط ورودی به ترتیب ۶ عدد $P$ ،$R$ ،$S$ ،$a$ ،$b$ و $c$ آمده است.

$0 \le P,R,S,a,b,c \le 10^{9}$

$P+R+S = a+b+c$

خروجی🔗

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

مثال🔗

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

3 3 3 3 3 3

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

9

توضیح : دوستش می‌تواند ۳ بازی اول قیچی و ۳ بازی دوم کاغد و ۳ بازی اخر سنگ بیاورد و همه بازی‌ها را ببرد.

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

10 0 2 7 5 0

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

-1

توضیح : بهترین حالت این است که ۷ بازی اول کاغذ و ۵ بازی اخر سنگ بیاورد که چون شنگدباو ۱۰ بازی اول کاغد و ۲ بازی اخر قیچی می‌آورد ۳ بازی را می‌بازد و ۲ بازی را می‌برد.

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

شنگدباو روی ساختمان‌داده‌‌ای جدید به نام درخت تقسیم دارد کار می‌کند این درخت از $n$ راس تشکیل شده‌است و هر رأس بجز رأس شماره $1$ یک پدر دارد یعنی رأس $i$ ام پدرش $p_i$ است و $p_i < i$ می‌باشد. شنگدباو قرار است روی هر راس برچسبی بنویسد به طوریکه:

• برچسب هر رأس از برچسب رأس پدرش بیشتر یا مساوی باشد.
• باقیمانده‌ی تقسیم $i$ بر برچسب رأس $i$ام صفر باشد.

با توجه به اینکه تعداد حالت‌های برچسب گذاری ممکن است خیلی زیاد باشد٬‌ شنگدباو گیج شده‌است و می‌خواهد بداند چند حالت مختلف برچسب گذاری هست که این شرایط را داشته باشد. به شنگدباو کمک کنید!

با توجه به اینکه تعداد حالات ممکن است زیاد باشد باقیمانده‌ی جواب را بر $10^9 + 7$ خروجی دهید.

ورودی🔗

در خط اول ورودی به شما عدد $n$ یعنی تعداد رئوس درخت داده می‌شود و سپس در خط بعدی $n-1$ عدد ورودی داده می‌شود که عدد $i$ام $p_{i+1}$ است.

$1\le n \le 500\ 000$

$1 \le p_i < i \le n$

خروجی🔗

در یک خط تنها تعداد حالات جواب را به پیمانه ی $10^9 + 7$ خروجی دهید.

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

4
1 1 1

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

12

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

5
1 2 2 3

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

11

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

شنگدباو در دوران طفولیت کانتست‌هایی جمع آوری و برگزار می‌کرد و خودش شرکت کننده‌ی اول و آخر این کانتست‌ها بود! بعضی اوقات تعداد معدودی از دوستانش، که معمولاً از دو نفر بیشتر نمی‌شدند، همراه او شرکت می‌کردند. در سری ۱۴۳‌ام از این مسابقات سخت و نفسگیر سؤال زیر مطرح شده بود‌. شما سعی کنید آن را حل کنید:

دو دنباله عدد داریم به طول $n$ اولی $a_1 , ... , a_n$ و دومی $b_1 , ... , b_n$ هر سری می‌توانیم یک زیر بازه (عناصر متوالی) از آرایه‌ی اولی انتخاب کنیم و همه‌ی اعدادش را به اضافه‌ی $x$ (که عددی دلخواه است) کنیم. هدفمان این است که در کمترین تعداد مرحله دو آرایه به پیمانه‌ی ۵ برابر شوند یعنی به ازای هر $i$ داشته باشیم: $a_i = b_i \space mod \space 5$

ورودی🔗

در خط اول ورودی عدد $n$ قرار دارد که اندازه‌ی دنباله است و در خط دوم به ترتیب $a_i$ ها قرار دارند که با فاصله از همدیگر جدا شده اند. در خط سوم نیز $b_i$ ها قرار دارند که با فاصله از هم جدا شده اند.

$1 \le n \le 10^6$ $1 \le a_i , b_i \le 10^9$

خروجی🔗

در خروجی تنها یک عدد برابر کمینه تعداد تغییرات لازم برای انجام این تبدیل خروجی دهید.

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

2
1 2
3 4

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

1

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

4
1 2 3 4
11 12 13 14

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

0

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

در یک رستوران $k$ آش‌پز کار می‌کنند. $n$ پاستا پنه آلفردو باید آماده شود. هر حاضرسازی ۳ مرحله دارد و برخی مراحل حاضرسازی می‌تواند هم‌زمان انجام شود. برای حاضر کردن $i$امین آن‌ها باید ابتدا یکی از آش‌پزها $a_i$ دقیقه پاستای آن را حاضر کند و روی میز ۱ بگذارد. سپس یکی از آش‌پزها پاستای آن را از روی میز ۱ بردارد و در $b_i$ دقیقه پاستا پنه‌ی آن را حاضر کند و روی میز ۲ بگذارد. سپس یکی از آش‌پزها پاستا پنه‌ی آن را از روی میز ۲ بردارد و در $c_i$ دقیقه پاستا پنه آلفردو را حاضر کند و تحویل مشتری دهد. یک محدودیت مهم، این است که روی میز ۱ حداکثر $x$ پاستا و روی میز ۲ حداکثر $y$ پاستا پنه جا می‌شود. برنامه‌ای برای کار کردن آش‌پزها ارائه دهید که زمان آماده‌سازی این $n$ پاستا پنه آلفردو به وسیله‌ی $k$ آش‌پز رستوران کمینه شود.

آش‌پز‌ها با اندیس‌های ۱، ۲، ۳، ... $k$ شماره‌گذاری شده‌اند.

مدت زمان برداشتن یا گذاشتن پاستا‌ها روی میز و تحویل دادن آن به مشتری ناچیز است و می‌توان آن را ۰ در نظر گرفت.

دقت کنید که بعد از اینکه آش‌پزی حاضرسازی را انجام داد باید پاستا را روی میز بگذارد یعنی اگر در زمان $t$ آش‌پزی پاستا را حاضر کرد، آن را روی میز می‌گذارد و ممکن است آش‌پز دیگری در همان لحظه پاستا را از روی میز بردارد ولی نباید در زمان $t$ بیشتر از حد مجاز پاستا روی میز باشد. به عبارت دیگر در زمان $t$، پاستا روی میز است مستقل از اینکه آش‌پز دیگری آن را درلحظه $t$ بردارد.

اگر آش‌پزی در زمان $t$ پاستا را بردارد و حاضرسازی آن $m$ دقیقه طول بکشید در دقیقا زمان $t+m$ باید پاستا را روی میز بگذارد و نمی‌تواند دیرتر یا زودتر آن را روی میز بگذرد.

آش‌پز‌ها تنها در زمان‌هایی که به دقیقه حسابی هستند می‌توانند شروع به انجام کاری کنند. (یعنی زمان ۰، ۱، ۲، ۳، ...)

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

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

ورودی🔗

در خط اول ورودی به ترتیب چهار عدد $n$ (تعداد پاستا‌ها)، $k$ (تعداد آش‌پز‌ها)، $x$ (تعداد پاستا ای که روی میز ۱ جا می‌شود)، $y$ (تعداد پاستا پنه ای که روی میز ۲ جا می‌شود). و سپس در $n$ خط بعدی در هر خط ۳ عدد $a_i, b_i, c_i$ آمده است که به ترتیب زمان مورد نیاز برای حاضر کردن پاستا، پاستا پنه و پاستا پنه آلفردو $i$ ام است.

$1 \le n,x,y,k \le 1\ 000$ $1 \le a_i , b_i , c_i \le 1\ 000 \ 000$

خروجی🔗

خروجی شما ترتیب حاضر سازی‌ها است که باید شامل $3n$ خط باشد که در خط $i$ ام شما باید سه عدد $t_i, s_i, f_i$ خروجی دهید که به این معناست که در دقیقه $t_i$ آش‌پز $s_i$ به حاضر سازی $f_i$ امین غذا می‌پردازد (اگر پاستا آن حاضر بود آن را به پاستا پنه تبدیل می‌کنید و اگر پاستا پنه‌ آن حاضر بود به پاستا پنه آلفردو تبدیل می‌کند و گرنه پاستا آن را حاضر می کند) . خروجی شما باید معتبر باشد یعنی شرط‌های زیر برای آن برقرار باشد:

$0 \le t_i \le 3\times10^{9}$ $1 \le s_i \le k$ $1 \le f_i \le 1\ 000$

در لحظه $t_i$ پاستا $f_i$ درحال آماده سازی نباشد و آش‌پز مشغول آماده سازی پاستا دیگری نباشد. (ممکن است در لحظه $t_i$ کار آش‌پز تمام شود و کار دیگری را شروع کند و یا در آن لحظه پاستا به مرحله بعدی آماده سازی برود و آش‌پز پاستا را در همان لحظه از روی میز بردارد)

نباید پاستا ای را بیشتر از ۳ بار در خروجی چاپ کنید.

هیچ گاه روی میزی بیشتر از حد مجازش پاستا نباشد.

برای هر $2 \le i$ : $t_{i-1} \le t_i$

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

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

3 2 1 2
1 5 5
2 1 1
3 2 5

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

0 1 1
0 2 2
1 1 1
2 2 2
3 2 3
6 1 3
6 2 2
7 2 1
8 1 3

زمانی که طول می‌کشد تا همه پاستا‌ پنه آلفردو‌‌ها حاضر شود ۱۳ دقیقه است و زودتر از این زمان نمی‌شود تمام پاستا پنه آلفردو‌ها را حاضر کرد.