سوال:
یک میله فلزی به طول L متر در اختیار داریم که برخی نقاط آن جهت برش از قبل مشخص شده اند.
مغازه ای که برش را انجام می دهد به ازای هر برشی که بر روی میله فلزی به طول p متر انجام شود، فارغ از نفطه ای که می خواهد برش دهد، p دلار هزینه می گیرد. مثلاً اگر میله ای به طول 2 متر در اختیار داشته باشیم و بخواهیم نقاط با فاصله نیم متری و 1 متری از ابتدای میله را برش دهیم دو انتخاب داریم:
ابتدا نقطه نیم متری را برش بزنیم (2 دلار) و سپس یک میله به طول نیم متر داریم و میله ی دیگری به طول 1/5 متر که باید یک نقطه از آن را برش دهیم (1/5 دلار) که در کل هزینه 3/5 دلار می شود.
یا
ابتدا نقطه 1 متری را برش می دهیم (2 دلار) و سپس یک میله به طول یک متر داریم که بایستی نقطه وسط آن بریده شود(1 دلار) و میله ی دیگری به طول 1 متر که دیگر نیازی به برش ندارد. (در کل 3 دلار)
حال می خواهیم با ترتیبی این میله را برش دهیم که کمترین هزینه را داشته باشد.
ورودی:
فایلی به نام input.txt که در خط اول آن طول میله (L)
در خط دوم تعداد نقاطی که می خواهیم برش دهیم (n)
و در n خط بعد فاصله نقاطی که می خواهیم برش دهیم از سمت چپ میله
خروجی:
فایل به نام output.txt که در خط اول آن کمترین هزینه ممکن برای برش
و در n خط بعدی به ترتیب نقاطی که باید از ابتدا به انتها برش یابند
مثال:
input.txt: 2 2 0.5 1
output.txt:
3
1
.5
نکات:
تحویل پروژه بصورت حضوری است.
به برنامه ای که توسط خود دانشجو نوشته نشده باشد و یا کپی شده باشد، نمره ای تعلق نمی گیرد.
input.txt
