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

در دیجی‌کال‍ا برای ذخیره‌سازی برخی از رشته‌های عددی از نوعی فشرده‌سازی استفاده می‌شود تا کسی نتواند از خروجی تولید شده به رشته‌ی عددی اصلی دست پیدا کند. البته ما در این‌جا از این نکته که این روش تصادم دارد؛ به این معنا که چند ورودی مختلف ممکن است خروجی یکسانی تولید کنند، چشم‌پوشی می‌کنیم! لازم به ذکر است که رشته‌ی عددی فقط شامل ارقام ۰ تا ۹ است. الگوریتم به این صورت است که تعداد تکرار همه‌ی ارقام رشته را حساب می‌کند، ارقام تکراری را حذف می‌کند و تعداد تکرار هر رقم (با شرط این که حداقل ۲ بار تکرار شده باشد) را در رشته ورودی می‌نویسد و در نهایت رشته‌ی عددی را به صورت صعودی مرتب می‌کند. این کار روی خروجی به دست آمده مجدد تکرار می شود و آنقدر ادامه دارد تا خروجی نهایی با خروجی مرحله‌ی قبل تفاوتی نکند.

ورودی🔗

تنها عبارت ورودی رشته عددی مورد نظر است که می‌خواهیم آن را فشرده کنیم. طول این رشته حداقل یک و حداکثر $1\ 000$ رقم است.

خروجی🔗

تنها عبارت خروجی، عبارت فشرده شده نهایی است.

مثال🔗

ورودی نمونه 1

442254545

خروجی نمونه 1

22345

در این مثال رقم 4، 4 بار تکرار شده است و رقم‌های 2 و 5 هم به ترتیب 2 و 3 بار تکرار شده‌اند. رقم‌های تکراری حذف می‌شوند و فقط یکی از آن‌ها در رشته باقی می‌ماند، بنابراین رشته‌ی 425 باقی می‌ماند. سپس تعداد تکرار هر رقم در ادامه‌ی رشته نوشته می‌شود، بنابراین رشته‌ی 425423 ایجاد می‌شود و در نهایت ارقام به صورت صعودی مرتب می‌شوند که در این جا 223445 حاصل می شود. مجدداً عملیات فشرده‌سازی روی این رشته‌ی حاصل‌شده اعمال می‌شود و نتیجه‌ی آن 222345 می‌شود. یک بار دیگر عملیات فشرده‌سازی اعمال می‌شود و نتیجه‌ی آن 23345 می‌شود و با اعمال مجدد این الگوریتم خروجی 22345 حاصل می‌شود که دیگر قابل فشرده سازی نیست.

ورودی نمونه 2

2223

خروجی نمونه 2

223

ورودی نمونه 3

4321

خروجی نمونه 3

1234

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

من محمدرضا هستم و به تازگی در دیجی‌کال‍ا مشغول به کار شده‌ام. من تعداد خط کدی که هر روز می‌زنم را در یک دفترچه یادداشت می‌کنم --ل‍ابد چون حوصله‌ام سر رفته‌است. متاسفانه بی‌دقتی بدی کرده‌ام و تعداد خط کد روزهای مختلف را بدون هیچ جداکننده‌ای پشت سر هم نوشته‌ام و فقط یک رشته‌ی عددی حاصل شده است. به غیر از رشته‌ی عددی حاصل شده، تنها اطلاعاتی که دارم موارد زیر است:

• اگر روزی کد نزده باشم، چیزی در دفترچه یادداشت نکرده‌ام.
• می‌دانم تعداد خط کد هر روز ام (روز هایی که کد زده‌ام) از یک حدی اکیدا بزرگتر است.
• می‌دانم تعداد خط کد هر روز ام (روز هایی که کد زده‌ام) از یک حدی اکیدا کمتر است.
• تعداد روزهایی که کد زده‌ام مشخص نیست.

لطفا به من کمک کنید تا حداقل بفهمم رشته‌ی حاصل شده شامل چند حالت مختلف است. ممنون!

ورودی🔗

ورودی شامل سه خط است. خط اول همان رشته‌‌ی عددی حاصل شده است. خط دوم حد پایین تعداد خط کد هر روز است (تعداد خط کد هر روز باید اکیداً از این مقدار بیشتر باشد). خط سوم حد بالای تعداد خط کد هر روز است (تعداد خط کد هر روز باید اکیداً از این مقدار کمتر باشد). محدوده‌ی ورودی‌ها به صورت زیر است:

$0 < length(input) < 1\ 000$ $0 ≤ min < 100\ 000$ $0 < max < 100\ 000$

خروجی🔗

در تنها خط خروجی، باقیمانده‌ی تعداد حالت‌های مختلف بر عدد $10^9+7$ چاپ می‌شود.

مثال🔗

ورودی نمونه 1

‍1‍337
2
1500

خروجی نمونه 1

4

با اطلاعات داده‌شده فقط ۴ حالت زیر امکان‌پذیر است:

{13, 3, 7}
{13, 37}
{133, 7}
{1337}

ورودی نمونه 2

405
0
100

خروجی نمونه 2

1

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

افزون قصد دارد در قرعه‌کشی ویژه‌ی دیجی‌کلاب شرکت کند. تنها شرط ورود به این قرعه‌کشی، ثبت سفارش از $n$ کالای تعیین شده از دیجی‌کال‍ا است و محدودیت ثبت سفارش به تعداد سفارش‌های پیشین هر فرد، یعنی $k$ می‌باشد. با ثبت هر سفارش از این کالاها، امتیاز دیجی‌کلاب به اندازه‌ی موجودی انبار آن کالا در همان لحظه، افزایش پیدا می‌کند و در نهایت هر فرد به میزان امتیازهای دیجی‌کلاب خود شانس شرکت در قرعه‌کشی دارد. با داشتن موجودی کالاها در آغاز شروع قرعه‌کشی و تعداد سفارش‌های پیشین افزون، با فرض اینکه افزون تنها شرکت‌کننده‌ی این قرعه‌کشی است، ماکزیمم شانس او برای این قرعه‌کشی را حساب کنید.

ورودی🔗

ورودی شامل سه سطر است. در اولین سطر تعداد تنوع کالاها، در دومین سطر تعداد موجودی هر کالا با فاصله از هم داده می‌شود و در سومین سطر ورودی تعداد سفارش‌های پیشین افزون داده می‌شود. $1 ≤ n ≤ 100\ 000$ $1 ≤ list[n] ≤ 10^9$ $1 ≤ k ≤ 10^9$

خروجی🔗

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

مثال🔗

ورودی نمونه ۱

1
5
2

خروجی نمونه ۱

9

در این مثال، افزون تنها یک انتخاب دارد. اولین‌باری که کالا را برمی‌دارد ۵ امتیاز دریافت می‌کند و موجودی انبار کالا به ۴ کاهش پیدا می‌کند. دومین‌باری که کالا را انتخاب می‌کند ۴ امتیاز دریافت می‌کند و دیگر انتخابی نمی‌تواند داشته باشد. بنابر این مجموعا ۹ امتیاز دریافت می‌کند.

ورودی نمونه ۲

3
5 1 2
5

خروجی نمونه ۲

16

در این مثال، او هر ۳ بار اول از کالای اول لیست که ۵ موجودی دارد انتخاب می‌کند. بنابراین به ترتیب ۵ و ۴ و ۳ امتیاز دریافت می‌کند. حال موجودی انبار به شکل [2, 1, 2] می‌باشد. بنابراین دو انتخاب بعدی را از کالای اول و سوم برمی‌دارد و جمعا ۱۶ امتیاز دریافت می‌کند.

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

بهرام و اکبر که دوست و هم‌کار خوبی برای هم هستند، همیشه سعی می‌کنند یک‌دیگر را به چالش بکشند. بهرام که اخیرا یک مقاله درباره‌ی بازی‌های ریاضی ذهن خوانده است، تصمیم گرفته تا اکبر را به یک چالش دعوت کند. چالش از این قرار است که بهرام دو عدد طبیعی $n$ و $k$ انتخاب می‌کند و اکبر باید تمام اعداد $n$ رقمی، که رقم‌های پشت سر هم آن‌ها با هم دقیقا $k$ واحد اختلاف دارند را به صورت صعودی چاپ کند! (این از کرامات اکبر است)

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

ورودی🔗

در ورودی به ترتیب دو عدد $n$ و $k$، که با فاصله جدا شده‌اند، آمده است. $2 ≤ n ≤ 50$ $0 ≤ k ≤ 9$

خروجی🔗

اعداد $n$ رقمی که ارقام پشت سر همه‌ی آن‌ها $k$ واحد اختلاف دارند را به صورت صعودی و جدا شده توسط یک ویرگول، چاپ کنید. توجه داشته باشید که اعداد باید معتبر باشند. برای مثلا 070 نامعتبر است.

مثال🔗

ورودی نمونه:

3 7

خروجی نمونه:

181,292,707,818,929

در این مثال تمام ارقام عدد 181 با یک‌دیگر ۷ واحد اختلاف دارند. همین قاعده برای اعداد دیگر هم برقرار است و اعداد به صورت صعودی نوشته شده اند.

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

دیجی‌کال‍ا قصد دارد برای پیاده سازی پروداکت‌ جدید خود از بین $n$ مهندس نرم‌افزار متقاضی، حداکثر $k$ نفر را انتخاب کند، به طوری عدد «باحال بودن» تیم بیشینه شود. در فرایند مصاحبه، برای هر فرد یک معیار «بامرام بودن» و یک معیار «خوش‌مشرب بودن» محاسبه می‌شود. عدد «باحال بودن» تیم انتخاب شده برابر با حاصل‌ضرب مجموع مرام افراد تیم در کمینه‌ی خوش‌مشرب بودن افراد تیم می‌باشد. با داشتن لیست اعداد مرام و خوش‌مشربی مهندسان متقاضی، مشخص کنید امتیاز باحال‌ترین تیمی که می‌توان انتخاب کرد، چقدر است.

ورودی🔗

ورودی شامل سه سطر است. در سطر اول عدد $n$ یعنی تعداد کل می‌آید، در سطر دوم مرام افراد با فاصله از هم و در سطر سوم خوش‌مشرب بودن افراد با یک فاصله و در نهایت تعداد افراد مورد نیاز $k$ . $1 ≤ k ≤ n ≤ 100\ 00$ $1 ≤ Maram ≤ 100\ 000$ $1 ≤ KhoshMashrebi ≤ 10^8$

خروجی🔗

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

مثال🔗

نمونه ورودی ۱

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

نمونه خروجی ۱

68

در این مثال باحال‌ترین تیم، برای حالتی است که زیرمجموعه‌ی افرادی که مرام آن‌ها 2 و 10 و 5 است انتخاب شود که در این حالت امتیاز باحال بودن تیم برابر حاصل ضرب مجموع اعداد گفته شده (17) در کمینه‌ی خوش‌مشرب بودن نظیر آن‌ها (4) است. بنابراین امتیاز باحال بودن کل برابر 68 می‌شود.

نمونه ورودی ۲

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

نمونه خروجی ۲

72

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

نیکی در بخش Fraud Detection دیجی‌کال‍ا به دلیلی نامعلوم به دنبال کشف اسم‌های مشابه است. او به جای استفاده‌ از مدل‌های احتمالاتی سعی دارد با یک روش عجیب شباهت دو اسم با یکدیگر را بسنجد. نیکی در داخل هر دو رشته تعدادی از صفر تا بی‌نهایت خط تیره (-) قرار می‌دهد تا طول دو رشته با یکدیگر برابر شوند (طول نهایی دو رشته می‌تواند تا بی‌نهایت زیاد شود). این خط‌تیره‌ها در اول، آخر، بین حروف کلمات می‌توانند باشند و می‌توان چند خط تیره کنار هم قرار داد. سپس دو رشته‌ی به دست آمده را در کنار یکدیگر قرار می‌دهد و آن‌ها را حرف‌به‌حرف مقایسه می‌کند و شباهت دو اسم را برابر مجموع امتیاز قرار گرفتن حروف در کنار هم در نظر می‌گیرد. امتیاز قرار گرفتن حروف در کنار یکدیگر با قوانین زیر محاسبه می‌شوند:

• اگر دو خط تیره در کنار یک‌دیگر قرار بگیرند، امتیاز منفی ۵ به آن‌ها تعلق می‌گیرد
• اگر یک حرف در کنار یک خط‌تیره قرار بگیرد، امتیاز منفی ۵ به آن‌ها تعلق می‌گیرد
• اگر دو حرف در کنار یکدیگر قرار بگیرند، امتیاز آن‌ها از ماتریس مجاورت زیر محاسبه می‌گردد. هر عدد در این ماتریس نشان می‌دهد که مجاورت حرف مربوط به سطر و ستون آن عدد چه امتیازی دارد. این ماتریس شامل برخی حروف نمی‌شود، چرا که در اسم‌هایی که به دست نیکی می‌رسند این حروف وجود ندارند.

   A  C  D  E  F  G  H  I  K  L  M  N  P  Q  R  S  T  V  W  Y
A  4  0 -2 -1 -2  0 -2 -1 -1 -1 -1 -2 -1 -1 -1  1  0  0 -3 -2
C  0  9 -3 -4 -2 -3 -3 -1 -3 -1 -1 -3 -3 -3 -3 -1 -1 -1 -2 -2
D -2 -3  6  2 -3 -1 -1 -3 -1 -4 -3  1 -1  0 -2  0 -1 -3 -4 -3
E -1 -4  2  5 -3 -2  0 -3  1 -3 -2  0 -1  2  0  0 -1 -2 -3 -2
F -2 -2 -3 -3  6 -3 -1  0 -3  0  0 -3 -4 -3 -3 -2 -2 -1  1  3
G  0 -3 -1 -2 -3  6 -2 -4 -2 -4 -3  0 -2 -2 -2  0 -2 -3 -2 -3
H -2 -3 -1  0 -1 -2  8 -3 -1 -3 -2  1 -2  0  0 -1 -2 -3 -2  2
I -1 -1 -3 -3  0 -4 -3  4 -3  2  1 -3 -3 -3 -3 -2 -1  3 -3 -1
K -1 -3 -1  1 -3 -2 -1 -3  5 -2 -1  0 -1  1  2  0 -1 -2 -3 -2
L -1 -1 -4 -3  0 -4 -3  2 -2  4  2 -3 -3 -2 -2 -2 -1  1 -2 -1
M -1 -1 -3 -2  0 -3 -2  1 -1  2  5 -2 -2  0 -1 -1 -1  1 -1 -1
N -2 -3  1  0 -3  0  1 -3  0 -3 -2  6 -2  0  0  1  0 -3 -4 -2
P -1 -3 -1 -1 -4 -2 -2 -3 -1 -3 -2 -2  7 -1 -2 -1 -1 -2 -4 -3
Q -1 -3  0  2 -3 -2  0 -3  1 -2  0  0 -1  5  1  0 -1 -2 -2 -1
R -1 -3 -2  0 -3 -2  0 -3  2 -2 -1  0 -2  1  5 -1 -1 -3 -3 -2
S  1 -1  0  0 -2  0 -1 -2  0 -2 -1  1 -1  0 -1  4  1 -2 -3 -2
T  0 -1 -1 -1 -2 -2 -2 -1 -1 -1 -1  0 -1 -1 -1  1  5  0 -2 -2
V  0 -1 -3 -2 -1 -3 -3  3 -2  1  1 -3 -2 -2 -3 -2  0  4 -3 -1
W -3 -2 -4 -3  1 -2 -2 -3 -3 -2 -1 -4 -4 -2 -3 -3 -2 -3 11  2
Y -2 -2 -3 -2  3 -3  2 -1 -2 -1 -1 -2 -3 -1 -2 -2 -2 -1  2  7

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

ورودی🔗

ورودی شامل دو سطر است که در هر سطر یک رشته آمده است. حروف این رشته فقط از حروف داخل ماتریس و به صورت بزرگ هستند. برای مثال کاراکترهای B یا a در رشته‌ی ورودی وجود ندارند. $0 < length(str1), length(str2) < 1\ 000$

خروجی🔗

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

مثال🔗

ورودی نمونه ۱

A
AD

خروجی نمونه ۱

-1

در این مثال، بهینه‌ترین حالت برای وقتی است که یک خط تیره به انتهای رشته‌ی اول اضافه شود. بنابراین مجاورت حرف A از رشته‌ی اول و حرف A از رشته‌ی دوم 4 امتیاز، و مجاورت خط‌تیره از رشته‌ی اول و حرف D از رشته‌ی دوم 5- امتیاز دریافت می‌کند و بیشینه‌ی امتیاز شباهت این دو رشته برابر مجموع این اعداد، یعنی 1- است.

ورودی نمونه ۲

PLEASANTLY
MEANLY

خروجی نمونه ۲

8

در این مثال بیشترین امتیاز برای زمانی است که حروف به شکل زیر در کنار هم قرار بگیرند:

PLEASANTLY
-MEA--N-LY

در این مثال، حرف P از رشته‌ی اول در مقابل خط تیره از رشته‌ی دوم قرار دارد و امتیاز 5- می‌گیرد. سپس حرف L از رشته‌ی اول و حرف M از رشته‌ی دوم در کنار هم قرار می‌گیرند و امتیاز 2 دریافت می‌کنند. بنابراین امتیاز کل تا به اینجا برابر 3- است. به همین ترتیب ادامه می‌یابد.

پس از اینکه دوره‌ی آزمایشی شایان در دیجی‌کال‍ا تمام شد، حالا او باید تیمی که دوست دارد در آن کار کند را انتخاب کند. دپارتمان مهندسی دیجی‌کال‍ا از تعدادی تیم تشکیل شده است که هر کدام وظیفه‌ی توسعه‌ی محصول خاصی را برعهده دارند. از آن‌جایی که تنها مل‍اک انتخاب شایان، حقوق دریافتی‌ست، به او کمک کنید که با توجه به داده‌های موجود تیمش را انتخاب کند. برای این کار بخشی از پایگاه داده‌ی دیجی‌کال‍ا به شما داده شده‌است. این پایگاه داده در حال حاضر شامل ۲ جدول است، این جدول‌ها عبارتند از: employees وteams.

در جدول employees حقوق پایه‌ی افراد مانند جدول زیر ذخیره شده است. برای این کار بخشی از پایگاه داده‌ی دیجیکالا به شما داده شده است. این پایگاه داده در حال حاضر شامل ۲ جدول است. این جدول‌ها عبارتند از: employees وteams

در جدول employees حقوق پایه افراد مانند جدول زیر ذخیره شده است.

در جدول teams نیر اطلاعات هر تیم نوشته شده است.

بخش ۱🔗

شایان در ابتدا می‌خواهد بداند که بیشترین حقوقی که دیجی‌کال‍ا به کارمندانش می‌دهد چقدر است. در نتیجه کوئری ‌SQL بنویسید که بیش‌ترین حقوق را گزارش کند. خروجی کوئری شما برای مثال بالا باید جدول زیر باشد.

بخش ۲🔗

حال شایان می‌خواهد ببیند که بیشترین حقوقی که در هر تیم به افراد داده می‌شود چقدر است که بتواند بر اساس آن تیمش را انتخاب کند. حال با نوشتن یک کوئری SQL به شایان کمک کنید که بتواند افرادی که در هر تیم بیشترین حقوق را می‌گیرند شناسایی کند. خروجی کوئری شما برای مثال بالا باید جدول زیر باشد.

در نوشتن کوئری به نام ستون‌های جداول خروجی و ترتیب آن ها (اولین ستون team و آخرین ستون salary) دقت کنید. در جدول بالا اصغر و اکبر هر دو بیش‌ترین حقوق را در تیم Shopping-Operation می گیرند و در نتیجه اسم هر دو آمده است. همچنین دقت کنید تیمی که هیچ کارمندی برای آن ثبت نشده است در جدول خروجی نیامده است.

کد خود را در حتما در قالب زیر، در یک فایل با نام code.sql قرار دهید و پس از zip کردن، آن را ارسال کنید

-- Section1
   your first query here
-- Section2
   your second query here