ای سی ام کار تازه وارد

در این وبلاگ مطالبی در مورد برخی الگوریتم ها و راهنمایی برای حل سوالات ارائه می گردد

ای سی ام کار تازه وارد

در این وبلاگ مطالبی در مورد برخی الگوریتم ها و راهنمایی برای حل سوالات ارائه می گردد

108 - Self-numbers 2

دوشنبه, ۱۱ فروردين ۱۳۹۳، ۱۲:۱۰ ق.ظ

لینک سوال


مفهوم سوال

سوال میگه (d(n رو n + مجموع ارقام عدد n تعریف می کنیم .

عدد n رو یک سازنده عدد (d(n میگیم .

عددهایی که هیچ سازنده ای ندارند رو Self Number میگیم .

سوال به ما لیستی شامل k اندیس رو میده و self number متناظر با اندیس هارو از ما می خواد .

N < 107 و k < 5000


حل

کافیه همه self number هارو غربال کنیم .

از 1 شروع می کنیم و اگر عددی سازنده نداشت ( مارک نشده بود ) ، به لیست اضافه می کنیم .

همچنین برای هر عدد (d(n رو مارک می کنیم .

برای اینکه سرعت محاسبه رو بالا ببریم و همچنین حافطه مصرفی رو کاهش بدیم از DP استفاده می کنیم .

طبق گفته سوال بزرگترین self number ای که مورد سوال قرار می گیره از 10کمتره .


ما احتیاج داریم حاصل جمع هر عددی از 1 تا 107 رو می خوایم .

برای اینکار از یه تکنیک ساده استفاده می کنیم .

برای همه عددهای کوچکتر از 10پیش محاسبه می کنیم .

برای محاسبه عددی مثل x کافیه 4 رقم اول اون رو جدا کنیم . حالا هر عددی تبدیل شده به دو قسمت که کوچکتر از 104 هستند ، (d(n رو می تونیم تو (O(1 حساب کنیم .


حافطه این سوال خیلی پایینه برای همین نمی تونیم 107 حافظه بگیریم .

برای حل این مشکل 2 راه ارائه میدیم .

راه اول

به اندازه n / 8 حافظه بگیریم و از هر بیت حافظه استفاده کنیم .


راه دوم

عدد ماکزیمم 7 رقمیه پس (d(n حداکثر 7 * 9 = 63 تا بیشتر از n میشه .

پس می تونیم یه لیست مثلا 1000 تایی بگیریم و به صورت دوری عددهارو روش مارک کنیم .


موافقین ۲ مخالفین ۱ ۹۳/۰۱/۱۱
رضا حسینی آشتیانی 108 acm.sgu.ru self numbers 2

نظرات  (۲)

۱۰ شهریور ۹۳ ، ۱۸:۱۶ سپیده آقاملائی
چرا دیگه به روز نکردی وبلاگ رو؟
پاسخ:
سلام
فشار درسی، خستگی :D
دوباره شروع می کنم، حداقل SGU رو تا 200 می رسونم.
۰۲ دی ۹۳ ، ۰۰:۰۵ مجتبی خوریانی
سلام
ممنونم از کار قشنگتون

مسابقات کدفورس
رو اگر در وبلاگ بیشتر تحلیل کنید، خیلی خوب میشه
پاسخ:
اگه وقت خالی پیدا کردم یه کانتست دیگه رو می زارم
فعلا می خوام SGU هارو تکمیل کنم

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی