আমাদের কথা খুঁজে নিন

   

চলুন solve করে ফেলি ACM এর ১০০৭৯ সমস্যা

1st way : Obviously, if you have zero cuts in the pizza, you'll have 1 slice. If you have one slice you'll have two pieces. It's given that you'll have 7 pieces with 3 slices, and you should also know that two slices would equate to four pieces. (0,1) (1,2) (2,4) (3,7) Code: Select all 1 - 2 - 4 - 7 D1: 1 2 3 D2: 1 1 Therefore: Quadratic. Using y = ax^2+bx+c (and knowing that 1 is your c value, as (0,1)) 2 = a(1)^2 + b(1) + 1 1 = a + b 4 = a(2)^2+b(2) + 1 3 = 4a + 2b Then eliminate: 2*2 = (a + b)*2 - 3 = 4a + 2b 1 = 2a a = 1/2 1 = a + b 1 = 1/2 + b 1/2 = b Thusly: y = ax^2+bx+c y = (x^2)/2+(x/2)+1 Or y = ((x^2+x)/2)+1 2nd way : For each cut, you are guaranteed to be able to intersect all the previous cuts. If you sketch out the first few cuts, you'll see that: p(n) = p(n-1) + (n-1) + 1 that is, for any given pizza with n cuts, the maximum number of Solution Description: slices is equal to a pizza with n-1 cuts, plus one slice for every cut that is intersected by the nth cut ( we know that to be n-1 ), plus 1. From this, you get a recurrence that can be solved to give a constant time function: p(n) = p(n-1) + n If we solve this we will get the following : p(n) = (n*(n+1))/2 + 1

অনলাইনে ছড়িয়ে ছিটিয়ে থাকা কথা গুলোকেই সহজে জানবার সুবিধার জন্য একত্রিত করে আমাদের কথা । এখানে সংগৃহিত কথা গুলোর সত্ব (copyright) সম্পূর্ণভাবে সোর্স সাইটের লেখকের এবং আমাদের কথাতে প্রতিটা কথাতেই সোর্স সাইটের রেফারেন্স লিংক উধৃত আছে ।