+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- نیکی در بخش 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- است. به همین ترتیب ادامه می‌یابد.

کشف تقلب

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

نیکی در بخش 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

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

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

PLEASANTLY
-MEA--N-LY

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