سکه

[farzaneh2008]

سلام من یک سوال از مسابقات acm رو برای پروژم انتخاب کردم ولی راستش چون امتحان دارم فرصت ندارم روش کار کنم اگه کسی می تونه به من کمک کنه
این هم سوالم
فزض کنید سکه های 5،10،25،50 تومانی داریم شخصی می خواهد تمام حالت های ممکن برای تولید N تومان را داشته باشد به عنوان مثال برای تولید مبلغ 45 تومان می توان حالت های زیر را متصور شد:
10+10+25
5+5+10+25
5+5+5+5+25
5+10+10+10+10
5+5+5+10+10+10
10+10+5+5+5+5+5
5+5+5+5+5+5+5+10
5+5+5+5+5+5+5+5+5
کاری را که شما باید انجام دهید این است که مبلغ کل را دریافت نموده و تمامی حالت های ممکن را برای آن با استفاده از سکه های موجود نمایش دهید ورودی برنامه شما مبلغ n خواهد بود.
ممنون می شم اگه کمکم کنید.

 

[Sharif_]

من سعی می کنم الگوریتمش رو بنویسم و بذارم
اون طوری که فکر میکنم باید اسون باشه

 

[Sharif_]

فقط من یه موضوع رو نفهمیدم
n نیمتونه باشه
n های ضریب 5 میتونن باشن

 

[Sharif_]

برای اینکه عدد فرد رو هم شامل بشه 2 رو هم اضافه کردم

اگه خواستی میتونی خودت حذف کنی

 

[dunhill]

mishe bishtar tozih bedin?

 

[Omid Jackson]

برای اینکه عدد فرد رو هم شامل بشه 2 رو هم اضافه کردم

اگه خواستی میتونی خودت حذف کنی

من این سوال رو حل کردم ولی الگوریتمش بهینه نیست!
اونی که حل کردم برای ACM بود و سنت هم داشت. 300$ رو میزد که تو 3 ثانیه حل کنه ولی خیلی طول میکشه با این الگوریتم. دوستام میگن با DP حل میشه که هنوز یاد نگرفتم. بنویسم کد رو میذارم برای دوستان

 

[Omid Jackson]

این هم برنامه ای که نوشتم ولی اصلا فایده نداره! یعنی اگر 10$ بزنیم خیلی طول میکشه