سوال one two one two one two...

آمار پرسش:

پرسیده شده: 2015-09-02 17:17:15 -0600
مشاهده شده: 262 بار
بروز شده: 2015-09-04 12:16:48 -0600

پرسش‌های مشابه:

آیا گراف قویا همبند است؟

پیدا کردن مولفه های قویا همبند گراف جهت دار

یافتن کوتاه ترین دور در گراف ساده

کد برای بررسی یک ریختی 2 گراف

جزوه ی برنامه نویسی قسمت (گراف)

پيدا كردن دومين كوتاهترين مسير بين دو راس گراف با توجه به الگوريتم ديكسترا

شبکه $n\times n$ پایدار

پیدا کردن گراف دوبخشی کامل یکرنگ

حداکثر تعداد یال‌های گراف بدون مثلث

یافتن کوچکترین پیچ و مهره با مقایسه آنها

نکاتی در مورد نوشتن پاسخ:

در این قسمت می‌تونی به یک پرسش پاسخ بدی. اگه می‌خوای در مورد پرسش بحث و اظهار نظر کنی از قسمت «ثبت نظر» استفاده کن.
پاسخت رو دقیق و کامل بنویس، از عکس استفاده کن و اگه لازمه به منابع (کتاب یا سایت) ارجاع بده.
اگه پرسش یا پاسخ‌ها مفید هستند حتما بهشون رای بده تا پرسش‌ها و پاسخ‌های خوب مشخص بشن.

استفاده از ویرایشگر:

توی قسمت پیش‌نمایش می‌تونی ببینی متنی که نوشتی چجوری روی سایت دیده میشه.
خیلی مهم: برای اینکه به خط بعد بری باید دوتا Enter بزنی.
می‌تونی از تگ‌های معمولی و ساده‌ی html هم استفاده کنی.
با دکمه‌هایی که بالای ویرایش‌گر قرار دارند کلی کار می‌شه کرد. از عکس‌گذاشتن بگیر تا لیست شماره‌دار. حتما امتحان‌شون کن.

علائم ریاضی:

برای نوشتن علائم ریاضی می‌تونی از Mathjax استفاده کنی. راهنمای Mathjax رو از سایت math.stackexchange بخون.
برای نوشتن عبارت ریاضی وسط جمله، اون عبارت رو بین دوتا $ قرار بده.
برای نوشتن عبارت ریاضی تو یه خط جدید اون رو بین دوتا $$ قرار بده.

از ورودی یک عدد میگیریم به نام n ,حال باید کوچکترین عددی که از ارقام 1 و 2 تشکیل شده و بر n نیز بخشپذیر است را پیدا کنیم.n بین 1 تا 6^10 است.

ممکن است چنین عددی نتوان پیدا کرد در اینصورت تو خروجی"imposibble" رو چاپ کنید،

همچنین اگر عدد موردنظر بیش تر از 30 رقم شد "impossible" چاپ شود.نکته:time limit:1s

2015-09-02 17:17:15 -0600

حسن رستمی پور 98 ● 2 ● 3 ● 9

پاک‌کردن ویرایش سوال

نظرات

این سوال داینامیک نیست که .

2015-09-03 04:10:12 -0600 شجاعی فر

@شجاعی فر شاید با روش های دیگه هم حل بشه .ولی من با داینامیک حلش کردم.راه حلتو بگو....

2015-09-03 04:27:46 -0600 حسن رستمی پور

@توفیقی نوشت دیگه ... .

2015-09-03 05:31:47 -0600 شجاعی فر

Ahmaghe kheng javab hamishe yeke dige

2015-09-03 05:33:45 -0600 خرس بقال

@خرس اسکل الان برای n برابر با 9 ,1 به 9 بخشپذیر است؟؟!!!

2015-09-03 05:35:16 -0600 حسن رستمی پور

2 پاسخ

خوب با BFS حل میشه مسئله، بدین صورت که اینو به صورت یک گراف در نظر بگیر عددهایی که از ۱ و ۲ هستن رو راس‌ها و دوتا به هم یال دارن اگر از یکیشون یکان رو حذف کنیم تبدیل بشه به دومی (مثلا: ۱۲ و ۱ به هم یال دارن) حالا بیا از ۱ و ۲ شروع کن و BFS بزن :)

کد جواب: http://paste.white-crow.ir/view/351/2y10AjuZyHihqlT

نکته:‌ توی کد جواب یه سری optimize انجام شده که $O(n)$ بشه :)

سوال مشابه: http://www.spoj.com/problems/ONEZERO/

2015-09-03 04:48:42 -0600

توفیقی 1621 ● 17 ● 21 ● 42

پاک‌کردن ویرایش پاسخ

نظرات

خوب تعداد راس ها چقدر است؟؟برابر با تعداد اعداد ساخته شده از ارقام 1 و 2؟؟

2015-09-03 05:07:55 -0600 حسن رستمی پور

اهان منظورتو فهمیدم،خوب اینو می تونی بهتر کنی بدین صورت بجای اینکه رو یکان بحث کنی بیاییم روی سمت چپ ترین رقم بحث کنیم(کار راحت تر میشه!).اگه یکم دقت کنی میفهمی که این روش همون داینامیکه(منظورم اینه همین کارو میشه با داینامیک نوشت).در کل خوب بود ایول ؛)

2015-09-03 05:22:03 -0600 حسن رستمی پور

@حسن رستمی پور این روش دقیقا BFS هست xD میشه جواب داینامیکش رو بنویسی؟

2015-09-03 06:14:15 -0600 توفیقی

اوکی حتما؛)

2015-09-03 06:17:39 -0600 حسن رستمی پور

به درخواست دوستان راه حل داینامیک این سوال رو میزارم :) (ولی ازتون خواهش دارم اول خودتون رو سوال فکر کنید بعد راه حل رو ببینید)

یه ارایه دو بعدی به نام dp تعریف می کنیم .[Dp[i][j یه رشته هست که برابر با عددی i رقمی است که باقیمانده اش بر n برابر با j باشد(عدد را در رشته ذخیره می کنیم).

حال سطر به سطر ارایه ی dp را از روی سطر قبلی اپدیت می کنیم ... (توضیحات بیشتر رو داخل کد دادم)

اینم کدم : /http://paste.ubuntu.com/12274850

2015-09-03 06:28:57 -0600