مسابقات ACM

[warmaster]

سلام
یک سوال ACM هست ذهنم رو مشغول کرده نتونستم براش جواب پیدا کنم اگه هر کسی جوابی به ذهنش میرسه کمک کنه ممنون میشم
در ضمن کد نمی خوام کسی بده فقط یک راه حل بگه
لینک سوال

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

من فکر میکنم این مساله یک راه حل بازشگشتی میشه براش پیدا کرد حالا پیاده سازیش میتونه به صورت پویا هم باشه

قضیه اینه که ما یک عدد از ورودی دریافت میکنیم مثلا 5 حالا باید یک دنباله بنویسیم که از 1 شروع میشه و به 5 ختم میشه

به طوری که هر عدد رو از دنباله انتخاب کنیم بشه با مجموع دو عدد از همون دنباله(دنباله صعودیه) ساخت

مثلا

1 2 4 5
4 = 2 + 2
یا 5 = 4 + 1
البته جواب یکتا نیست و دنباله های دیگه ی هم میشه نوشت که ما باید دنباله ی که کمترین طول رو داره به خروجی بدیم
باز همون کمترین طول ها هم میتونه چند حالت باشه که هر کودومش رو به خروجی بدیم قابل قبوله
مثلا برای 5 با همون طول قبلی این دنباله هم هست

1 2 3 5

من یک راه حل به ذهنم رسیده که برای عداد زوج جواب میده فقط
مثلا اگه 12 رو در ورودی داشته باشیم دنباله ی اون به این صورته که
میگیم 12 با نصف خودش ساخته میشه یعنی اگه 6 توی دنباله باشه حله!چون
12 = 6 + 6 همین راه حل رو بصورت بازگشتی ادامه میدیم برای 6 تا به 3 یا 4 برسیم!
دنباله اینطوری میشه
1 2 3 6 12
این راه حل برای عداد فرد جواب نمیده! HELP HELP HELP

[Ar@m]

شما فقط كافيه اگه عدد زوج بود همونطور كه خودت گفتي تقسيمش كني به 2
اگه عدد فرد بود و بر سه بخش پذير بود بر 3 تقسيم كني و دو عدد بعد يكي نسبت يك سوم و يكي دو سوم عدد ميشن يعني 15 ميشه 10 و 5
اگه هم فرد بود و به سه بخش پذير نبود يكي ازش كم كني

مثلا عدد 235
فرده ولي به 3 بخش پذير نيست پس يكي ازش كم ميكنيم:
234
حالا زوجه تقسيم به 2 ميكنيم:
117
فرده و بر 3 بخش پذيره پس اعداد بعديش ميشن:
78 و 39

39 هم فرده هم به 3 بخش پذير . اعداد بعدي:
26 و 13

13 فرده به 3 بخش پذير نيست يكي ازش كم ميكنيم:
12

12 زوجه
6

6 رسيده به دنباله ي كار درست كن 1 و 2 و 4
خب ديگه آسون شد!

پس عدد 235 ميشه دنباله ي:
1 2 4 6 12 13 26 39 78 117 234 235

[warmaster]

شما فقط كافيه اگه عدد زوج بود همونطور كه خودت گفتي تقسيمش كني به 2
اگه عدد فرد بود و بر سه بخش پذير بود بر 3 تقسيم كني و دو عدد بعد يكي نسبت يك سوم و يكي دو سوم عدد ميشن يعني 15 ميشه 10 و 5
اگه هم فرد بود و به سه بخش پذير نبود يكي ازش كم كني

مثلا عدد 235
فرده ولي به 3 بخش پذير نيست پس يكي ازش كم ميكنيم:
234
حالا زوجه تقسيم به 2 ميكنيم:
117
فرده و بر 3 بخش پذيره پس اعداد بعديش ميشن:
78 و 39

39 هم فرده هم به 3 بخش پذير . اعداد بعدي:
26 و 13

13 فرده به 3 بخش پذير نيست يكي ازش كم ميكنيم:
12

12 زوجه
6

6 رسيده به دنباله ي كار درست كن 1 و 2 و 4
خب ديگه آسون شد!

پس عدد 235 ميشه دنباله ي:
1 2 4 6 12 13 26 39 78 117 234 235

دمت گرم نکته ی جالبی بود خیلی جالب
من چند روز پیش با درخت حلش کردم 16ms طول کشید AC گرفتم دیدم بعضیا زمانش کمتر شده گفتم باید یه راه حل دیگه هم باشه
این راه حل خودم همه ی حالت ها رو محاسبه کردم اوله برنامه

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

[warmaster]

شما فقط كافيه اگه عدد زوج بود همونطور كه خودت گفتي تقسيمش كني به 2
اگه عدد فرد بود و بر سه بخش پذير بود بر 3 تقسيم كني و دو عدد بعد يكي نسبت يك سوم و يكي دو سوم عدد ميشن يعني 15 ميشه 10 و 5
اگه هم فرد بود و به سه بخش پذير نبود يكي ازش كم كني

مثلا عدد 235
فرده ولي به 3 بخش پذير نيست پس يكي ازش كم ميكنيم:
234
حالا زوجه تقسيم به 2 ميكنيم:
117
فرده و بر 3 بخش پذيره پس اعداد بعديش ميشن:
78 و 39

39 هم فرده هم به 3 بخش پذير . اعداد بعدي:
26 و 13

13 فرده به 3 بخش پذير نيست يكي ازش كم ميكنيم:
12

12 زوجه
6

6 رسيده به دنباله ي كار درست كن 1 و 2 و 4
خب ديگه آسون شد!

پس عدد 235 ميشه دنباله ي:
1 2 4 6 12 13 26 39 78 117 234 235

دوست عزیز راه حلتون جواب نمیده متاسفانه تو صورت سوال گفته جواب های مختلفی داریم ولی اون جوابهای قبوله که طولشون مینمم باشه
مثلا برای 77 اینطوری عمل میکنه الگوریتمتون
77 نه به سه بخشپذیره نه 2 پس
76 به 2 تقسیم میشه
38 نه 2 تقسیم میشه
19 نه به 2 بخشپذیره نه به 3
18 به 2 تقسیم
9 به 3 تقسیم و به نسبت 1/3 و 2/3 میشکونیم
6
3
2
1
طول دنباله ی شما شد 10 در صورتی که طول 9 هم میشه
1 2 4 8 9 17 34 68 77

[Ar@m]

تو صورت سوال گفته جواب های مختلفی داریم ولی اون جوابهای قبوله که طولشون مینمم باشه

به اين قسمت سوال دقت نكردم
حتما يه راهي داره. فكر ميكنم بهش

[sin2x=2sinxcosx]

سلام خدمت دوستان .
خیلی وقته تاپیک گم شده تو انجمن .
اون عزیزانی که به این مسابقات علاقه دارن :
یه کتابی هست به اسم Programming Challenges .
تو این کتاب سرفصل مطالبی که برای یه ACM باز تو مسابقه لازمه بدونه تا بتونه مسئله ها رو بهتر حل کنه اورده + توضیحات کوتاهی در مورد هر مطلب + چندین مثال در رابطه با اون مطلب . خیلی کتاب خوبیه برای شروع .
این سرفصل هست :

Data Structures
Strings
Sorting
Arithmetic & Algebra
Combinatorics
Number Theory
Backtracking
Graph Traversal
Graph Algorithms
Dynamic Programming
Grids
Geometry
Computational Geometry

این لینک دانلود این کتاب :

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

و این هم Judger برای Submit کردن سوالای این کتاب :

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

موفق باشید ...................

[sin2x=2sinxcosx]

با سلام ...
خدمت دوستان علاقه مند به مسابقات ACM عرض کنم که یک مسابقه ACM در راه هست . مسابقات ACM انفرادی دانشگاه مشهد .
یکی از مسابقات ACM معتبر در کشور که هفتمین دوره اش قراره امسال برگذار بشه .

از این قسمت می تونین در مسابقات ثبت نام کنین که پس از تایید اطلاعاتتون پسورد به ایملیتون ارسال میشه . تا 15 تیر فرصت دارین .

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

دو تا مسابقه اینترنتی برگذار میشه . یکی در 18 تیر و یکی در 20 تیر . 20 نفر از مسابقه اول و 20 نفر از مسابقه دوم و 10 نفر از مجموع دو مسابقه به مسابقه نهایی در مشهد اعزام می شوند .

جهت کسب اطلاعات بیشتر به این سایت مراجعه نمایید :

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

[ati_1991]

سلام.
مسابقات acm جهانی چند وقت یکبار انجام میشه؟ از ایران شرکت کننده زیاد داره؟

[sin2x=2sinxcosx]

سلام.
مسابقات acm جهانی چند وقت یکبار انجام میشه؟ از ایران شرکت کننده زیاد داره؟

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

[hadi_hhh]

سلام کسی کد سوال 101 از سایت [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ] رو می دونه یا اینکه می تونه راهنمایی کنه؟