گروه ACM دانشگاه آزاد پرند

وبلاگ رسمی گروه ACM دانشگاه آزاد اسلامی واحد پرند

گروه ACM دانشگاه آزاد پرند

وبلاگ رسمی گروه ACM دانشگاه آزاد اسلامی واحد پرند

گروه ACM دانشگاه آزاد پرند

به وبلاگ گروه ACM دانشگاه آزاد پرند خوش آمدید. در این وبلاگ می توانید از آخرین اخبار، رویدادها و اطلاعات مربوط به این گروه مطلع شوید.

بایگانی
آخرین مطالب
پیوندها
طبقه بندی موضوعی
کلمات کلیدی

کلاس

ACM

مسابقه

Contest

IAUP

کانتست

تمرین

پرند

LCPC

شریف

دانشگاه

آنلاین
پربیننده ترین مطالب
آخرین نظرات

شنبه, ۲۳ مرداد ۱۳۸۹، ۱۲:۱۹ ق.ظ

۲۳

سوالات تمرینی

شنبه, ۲۳ مرداد ۱۳۸۹، ۱۲:۱۹ ق.ظ

سلام آقای فاطمی پور چند تا سوال رو انتخاب کردند که باید تا جلسه بعدی کلاس ایشون که روز چهارشنبه است حل کنید سوالها از سایت uva هست.


Factors and Factorials_160

Divisors_294

Prime Cuts_406

Stern-Brocot_10077

Almost Prime Numbers_10539


در ضمن جلسه بعدی کلاس ایشون روز چهارشنبه ساعت 9 در کلاس 201 برگزار خواهد شدکه شامل مباحث زیر است.

Binary search (continue from last section)
Dynamic Programming (very important ^ 1000)

چند تا سوال هم من از سایت uva انتخاب کردم، سعی کنید حلشون کنید.

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




موافقین ۰ مخالفین ۰ ۸۹/۰۵/۲۳
انجمن ای سی ام دانشگاه آزاد پرند

نظرات  (۲۳)

۲۳ مرداد ۸۹ ، ۰۱:۲۴ writedown
سلام خیلی جالب بود.
۲۳ مرداد ۸۹ ، ۱۸:۱۴ mfs
جالبه که هیچ کس سوال یا مشکلی برای حل این تمرینات نداره
پس چند تا احتمال رو میشه مطرح کرد:
1-مسائل خیلی ساده بودن که خیلی راحت بچه ها همه رو حل کردند
2-به مشکلات زیادی برخورد کردند اما مطرح نکردند
3-اصلاً اقدام به حل تمرینات نکردند
4-...

اگه وقت یا حس و حال تمرین کردن رو ندارید، وقتتون رو بی‌خود سر کلاس تلف نکنید چون بدون تمرین کردن و حل مسائل مختلف و زیاد هرگز موفق نخواهید شد.
۲۴ مرداد ۸۹ ، ۰۹:۱۸ محمد
فکر کنم گزینه ی 4 درست تر به نظر بیاد
۲۴ مرداد ۸۹ ، ۲۳:۲۸ موسوی
سلام، خیلی ممنون از مطالب جالبتون.
من مال دانشگاه پرند نیستم اما خیلی علاقه دارم از اینجا همراه شما ادامه بدم. مسایلی رو که دادید من یه تعدادی رو حل کردم (10018 ، 10189، 10469، 160) یکی دوتا رو به مشکل بر خوردم و بقیه رو هنوز نرفتم سراغشون. تنها جایی که من گیر کردم داخلش، الگوریتم مناسبی بود برای اعداد اول بزرگ (مثلا تا 32 بیت) اگه راهنمایی کنید ممنون میشم.
۲۵ مرداد ۸۹ ، ۱۲:۳۳ mfs
به موسوی:
با داشتن لیستی از اعداد اول از 2 تا جذر n، می‌توان با تقسیم متوالی، تشخیص داد یک عدد در بازه‌ی 2 تا n، اول است یا نه. این لیست با روش‌های مختلفی مثل sieve of Eratosthenes قابل محاسبه است.

نکته : در هیچیک از سوالات نیاز به داشتن لیست تمام اعداد اول از 2 تا 32^2، وجود ندارد.
۲۶ مرداد ۸۹ ، ۰۲:۲۶ tajoreh
برای سوال اول :
باید فاکتوریل عدد را حتما بدست بیاریم؟
من برای زیر 10 نوشتم. اما بالای ده کامپیوتر شاخ در میاره!
نوع داده ای رو هم هر چی نوع long بود امتحان کردم.....

میشه لطفا یه راهنمایی کنید.(خیلی سختــــــــــــــــــــه!)
۲۶ مرداد ۸۹ ، ۰۲:۵۱ محمد
عدد n تا 100 میتونه باشه، چطوری می تونی فاکتوریل این عدد رو پیدا کنی؟ تو چه نوع داده ای می خوای ذخیره کنی؟! میتونست رنج این عدد رو ده ها برابر این هم بگیره!!!

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

...
(باعرض شرمندگی از اساتید محترم که جواب دادم)
۲۶ مرداد ۸۹ ، ۰۲:۵۶ محمد
صبر کن یه جور دیگه فکر کنیم ...
2 * 3 * 4 * 5 = !5

حالا در این میان به جز 4 بقیه ی اعداد اول هستند، اما 4 خودش از 2*2 که 2 عامل اوله تشکیل شده، پس جواب میشه
3 تا 2، 1 تا 3 و 1 تا 5
1 1 3
۲۶ مرداد ۸۹ ، ۱۳:۴۷ mfs
خواهش می‌کنم محمد جان، هدف همینه که همه به هم کمک کنیم تا با هم پیشرفت کنیم :)

اگه شما ACMer نبودید احتمالاً بله مجبور بودید !100 رو محاسبه کنید (با استفاده از BigNum) البته اینکه بعدش چه الگوریتمی ممکنه جواب بده من که چیزی به ذهنم نمی‌رسه

اما ما تو ACM یاد می‌گیرم که لزوماً راه ِ سرراست راه ِ صحیح نیست و چشم‌ها را باید شست، جور دیگر باید دید ... !

نکته‌ای که باعث میشه به راه‌حل برسید یه نکته‌ی ساده درباره‌ی فاکتوریل هاست:
100 * 99 * ... * 3 * 2 = !100
پس !100 عامل اول بزرگتر از 100 نمی‌تونه داشته باشه، چون اگه داشته باشه اون عدد لزوماً از ضرب حداقل دو تا از اعداد بالا بدست میاد که خودش اول بودن رو نقض می‌کنه.

حالا اینکه چطور میشه به لیست مورد نظر سوال رسید رو فکر کنم مثالی که محمد زده به اندازه‌ی کافی گویا هست.
۲۶ مرداد ۸۹ ، ۱۸:۵۳ tajoreh
مرسی سوال اول حل شد......(خیلی راحت بود!)
حالا سوال دوم:
divisors:
تقریبا از همون روش سوال اول استفاده کردم
برای 1 تا 10 و 1000 درست جواب میده
اما برای 999999924 یذره زیادی محاسبه میکنه:
الگوریتمم اینه که تعداد اعداد اول کوچکتر مساویه
ceil(sqrt(n))
که بر n بخش پذیر هستند را بدست بیاره؟
درسته؟
۲۶ مرداد ۸۹ ، ۲۱:۰۱ محمد
x = a^i * b^j *...*c^k
n = (i+1)(j+1)...(k+1)

a,b,c عامل های اول هستند و n تعداد حاصل ضرب ها
۲۷ مرداد ۸۹ ، ۰۱:۴۴ mfs
برای مسئله‌ی مقسوم علیه‌ها یک الگوریتم ِ Brute force هم مسئله را حل می‌کرد. که من انتظار داشتم چنین کدی بنویسید. یعنی برای هر عدد چک کنید که به چه تعداد عدد بخشپذیر است، تنها نکته این است که وقتی 80 بر 2 بخش پذیر است می‌توانیم بدون محاسبه‌ی مجدد نتیجه بگیریم که 80 بر x دیگری هم بخشپذیر است به طوریکه 80 = x*2 (حال ببینید با این نکته به چه صورت می‌توان فضای جستجو را کوچک کرد)

فرمولی که آقای خدابنده لطف کردند حاضر و آماده (کار خیلی بدیه) در اختیار شما قرار دادند هم درست است، به عنوان تمرین اثباتش کنید
۲۸ مرداد ۸۹ ، ۰۰:۲۸ محمد
معذرت خواهی
یکی باید به خودم کمک کنه که همش wrong میگیرم!!!!
۲۸ مرداد ۸۹ ، ۱۸:۲۵ tajoreh
میشه لطفا چند تا مورد ورودی برای divisors
پیشنهاد کنید:
تو کامپیوتر خودم درست میده؛ اما تو uva, wrong answer میگیرم.
ضمنن از بروت فرس استفاده کردم.
۲۸ مرداد ۸۹ ، ۱۸:۴۹ tajoreh
نه ببخشید از اون روش نیست.
همون روش اقای خدا بنده هست.
۲۸ مرداد ۸۹ ، ۲۰:۲۰ mfs
تعداد مقسوم علیه‌های 7560 -> 64
تعداد مقسوم علیه‌های 15120 -> 80
تعداد مقسوم علیه‌های 27720 -> 96
تعداد مقسوم علیه‌های 45360 -> 100
تعداد مقسوم علیه‌های 999999000 -> 1024

خب مطمئناً کامپیوترتون درست داده که سوال رو برای UVA فرستادید دیگه! اما راه‌حل شما باید به ورودی‌هایی که طراح سوال آماده کرده درست جواب بده تا accept بگیرید.

نکته : گاهی اوقات برای بدست آوردن چند تا تست کیس خوب، میشه یه راه‌حل brute force نوشت تا جواب چند تا تست کیس بزرگ رو بدست بیاریم و بعد با اونها راه‌حل اصلی مسئله رو تست کنیم(راه‌حل brute force مذکور به اندازه‌ی کافی سریع نیست که سوال را در زمان قابل قبول حل کند). بنابراین کافی بود برای پیدا کردن جواب 100% درست ِ چند تا تست کیس بزرگ این کد کوچولو را بنویسید :
int divCount = 0;
for(i = 1; i <= X; i++)
if(X % i == 0)
divCount++ ;
a این کد تعداد مقسوم‌علیه‌های 999999000 را در زمان حدوداً 26 ثانیه (در سیسنم من) پیدا می‌کند.

به فرمت خروجی دقت کنید حتی اگر یک کاراکتر کوچک را بزرگ یا بلعکس بنویسید، Wrong answer خواهید گرفت.

پیاده‌سازی راه‌حلی که من توضیح دادم به مراتب از پیاده‌سازی اون فرمول راحت تره.
۲۸ مرداد ۸۹ ، ۲۱:۰۵ tajoreh
تمام این تست کیسها را خیلی سریع جواب میده. ضمنن یه مورد دیگه هم که بهش اضافه کردم وقتی که a بزرگتر از b نباشه مثل خود uva . عدد 0 و تعداد -1 را چاپ کنه.
ضمنن من هم اول از همون روش استفاده کردم.
اما جوابش خیلی کند بود و Time limit گرفتم.
۲۸ مرداد ۸۹ ، ۲۲:۰۹ mfs
"وقتی که a بزرگتر از b نباشه مثل خود uva . عدد 0 و تعداد -1 را چاپ کنه." برای کدوم سوال؟ اگه منظورتون همین Divisors باشه که اصلاً نیازی به همچین کاری نداره.

روشی که تو نظر قبل گفتم که مطمئناً کند خواهد بود، فقط گفتم که با یه همچین کد ساده‌ای حداقل میتونی چند تا تست کیس خوب برای تست کردن الگوریتمی که طراحی می‌کنی بدست بیاری.

اما تو همون روش Brute force میشه فضای جستجو رو محدود کرد، یعنی لازم نیست که حلقه‌ی for تا X تکرار شه، که ایده‌ی اونو در نظر 12ام توضیح دادم. که در اونصورت در زمان قابل قبول مسئله رو حل میکنه (پیاده سازی من از همین الگوریتم، این مسئله رو تو زمان 0.16 حل کرد و پیاده سازیم از الگوریتم دوم(فورمول) در زمان 0.032 حل کرد).
۲۹ مرداد ۸۹ ، ۱۴:۳۳ tajoreh
سوال 10706
این لیستی که باید توش جستجو شه کجاست؟؟؟؟
۲۹ مرداد ۸۹ ، ۱۴:۵۶ mfs
این که دنباله چگونه ساخته میشه رو توضیح داده.
S1 = 1
S2 = 12
S3 = 123
S4 = 1234
S5 = 12345
S6 = 123456
...
S12 = 123456789101112
الی آخر.
حالا S ها رو به ترتیب کنار هم بذار به دنباله‌ی ارقام مورد نظر می‌رسی.

من پیشنهاد می‌کنم تمام سوالات باقیمانده را بخوانید و از آسانترین شروع کنید. (به نظر من این سوال سخت‌ترین سواله)
۲۹ مرداد ۸۹ ، ۱۷:۱۴ tajoreh
بلاخره بعد از 40 تای WA امروز یک AC گرفتم. 406
۲۹ مرداد ۸۹ ، ۱۷:۳۸ tajoreh
سوال 10077:
محدوده نداره! باید لیستش را تا اخرین عدد صحیح مثبت ایجاد کرد؟
۲۹ مرداد ۸۹ ، ۱۸:۲۷ محسن
نیازی نیست محدوده رو بدونی مثلا به مثال اولین تست کیسش توجه کن که 7 5 هست
1/0--------------- 1/1 ----------------- 0/1 1/1> 5/7 --> سمت چپ 'L'
'R' <---- 5/7>1/2 0/1--------------------1/2-----------------------1/1
'R' <---- 5/7>2/3 1/2--------------------2/3-----------------------1/1
'L' <---- 5/7<3/4 2/3--------------------3/4-----------------------1/1
goal <---- 5/7==5/7 2/3--------------------5/7-----------------------3/4

ارسال نظر

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