118 - Digital Root

لینک سوال

مفهوم سوال :

سوال یه دنباله از اعداد به ما میده به عنوان A .

بعد حاصل جمع "دیجیتال روت"  مقادیر زیر رو می خواد :

A1

A1 * A2

A1 * A2 * A3

.

.

A1 * ... * An

منظور از دیجیتال روت : مقدار حاصل جمع تمام ارقام یه عدد هست ، اگه این مقدار بزرگتر از 10 باشه ، تا زمانی که حاصل از 10 کوچکتر نشده ، این کار باید انجام بشه ،

مثلا D( 123 ) = 6 یا D( 991 ) = 1 .

حل :

لازمه بدونید که :

D( a + b ) = d(a) + D(b) and

D( a * b ) = D( a ) * D( b )  for each a , b .

اثباتش سخت نیست ، چند تا مثال عددی بزنید تا ببینید چه اتفاقی می افته .

برای حل زمان گرفتن ورودی ها ، به جای هر عدد ، digit_root هر عدد رو ذخیره کنید .

بعد جواب رو حساب کنید .

من برای حل یه آرایه dynamic در نظر گرفتم که مثلا DPi برابر بود با حاصل ضرب i جمله اول دنباله A .

بعد از این کار ، دوباره مقدار های DP رو اپدیت می کنم به صورتی که DPi  برابر میشه با حاصل جمع i  جمله اول آرایه DP .

جواب مساله DPn هستش.

حواستون باشه ، همه جای راه حل بعد از هر بار شرب یا هر جمع ، حتما digital_root مقدار بدست اومده رو ذخیره کنید .

به اون 2 تا رابطه ای که بالا گفتیم ، می گن همریختی .

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