[tutorial] SPOJ AE00 - Rectangles

Problem Description:

n সংখ্যক বর্গ আছে, যার প্রতিটা বাহুর দৈর্ঘ্য ১ ।

বলতে হবে এই বর্গ গুলো দিয়ে কতগুলো ভিন্ন ভিন্ন আয়ত বানানো সম্ভব ।

শর্ত হলো, কোন বর্গকে আরেকটার উপরে রাখা যাবে না, বা একাধিক বর্গ নিয়ে এর দৈর্ঘ্যকে পরিবর্তন করা যাবে না ।

যদি একটি আয়তের দৈর্ঘ্য a, প্রস্থ b হয়  এবং অন্য একটি আয়তের দৈর্ঘ্য b, প্রস্থ a হয় তবে তাদেরকে একই আয়ত হিসেবে গন্য করতে হবে ।

Prblem link

Solution:

যদি দৈর্ঘ্য 1 হয় তবে প্রস্থ হতে পারে, 1, 2, 3, ...... সর্বোচ্চ n = মোট n টা আয়ত

যদি দৈর্ঘ্য 2 হয় তবে প্রস্থ হতে পারে, 1, 2, 3, ...... সর্বোচ্চ n/2 = মোট n/2 টা আয়ত

যদি দৈর্ঘ্য 3 হয় তবে প্রস্থ হতে পারে, 1, 2, 3, ...... সর্বোচ্চ n/3 = মোট n/3 টা আয়ত

................

................

এভাবে, যদি দৈর্ঘ্য n হয় তবে প্রস্থ হতে পারে সর্বোচ্চ 1, কারণ n/n = 1, মোট 1 টা আয়ত ।

এখানে খেয়াল কর, দৈর্ঘ্য 1 এর জন্য আয়তের (দৈর্ঘ্য, প্রস্থ) = (1, 1), (1, 2), (1, 3), ....., (1, n)

আবার, দৈর্ঘ্য 2 এর জন্য আয়তের (দৈর্ঘ্য, প্রস্থ) = (2, 1), (2, 2), (2, 3), ....., (2, n/2)

দৈর্ঘ্য 3 এর জন্য আয়তের (দৈর্ঘ্য, প্রস্থ) = (3, 1), (3, 2), (3, 3), ....., (3, n/3)

খেয়াল কর, ১ এর জন্য (১, ২) আছে, আবার ২ এর জন্য আছে (২, ১), অর্থাৎ রিপিট হচ্ছে ।

আবার, ১ এর জন্য (১, ৩) আছে, ২ এর জন্য আছে (২, ৩), আবার ৩ এর জন্যও আছে (৩, ১), (৩, ২), অর্থাৎ, আবারো রিপিট ।

এভাবে, যে কোন দৈর্ঘ্য i এর জন্য i-1 পর্যন্ত আসলে আগেই তৈরি করা হয়েছে ।

তাই i দৈর্ঘ্য বিশিষ্ট মোট n/i - (i-1) টা নতুন আয়ত বানানো সম্ভব ।

তাহলে আউটপুট হবে, i = 1 থেকে শুরু করে i<=n পর্যন্ত  প্রতি দৈর্ঘ্যের জন্য যতগুলো করে আয়ত বানানো যাবে তাদের যোগফল ।

Code: