পোস্টটি পড়া হয়েছে 2,899 বার
UVa 10931 Parity Solution in Bengali

অনলাইন জাজ সিরিজ – ৯ (UVa 11854 – Egypt)

UVa online Judge এর একটা খুব easy problem হচ্ছে Egypt. আজ এই প্রবলেমটাই সলভ করব।

UVa 11854 – Egypt

 

উপরের দেয়া লিংকে গিয়ে প্রবলেমটি পড়ে ফেলো। একদম সোজা সাপ্টা ভাবে বলা হয়েছে যে অনেক দিন আগে মিশরীয়রা একটা ত্রিভুজ খুঁজে পেল যাতে একটি right angle বা সমকোণ রয়েছে। আর সেই ত্রিভুজের তিন বাহুর দৈর্ঘ্য যথাক্রমে ৩, ৪ ও ৫। তোমাকে বলা হয়েছে এই সমকোণী ত্রিভুজ হবার এই বৈশিষ্ট্যটা অন্য কোন ত্রিভুজের ক্ষেত্রে পাওয়া যায় কিনা সেটা বের করতে। এক্ষেত্রে তোমাকে ৩ টা পূর্ণ সংখ্যা ইনপুট দেয়া হবে। এই সংখ্যাগুলোকে হিসাব নিকাশ করে বের করতে হবে এই বাহুগুলোর সমন্বয়ে গঠিত ত্রিভুজটি (যদি আদৌ ত্রিভুজ গঠন করে) সমকোণী ত্রিভুজ কিনা।

Input constraints এ বলা আছে ত্রিভুজের বাহুর মানগুলো ৩০,০০০ এর চেয়ে বড় কোন সংখ্যা দেয়া হবে না। তাই নিশ্চিন্তে int ব্যবহার করতে পার। long বা long long int ব্যবহারের দরকার নাই। আর কখন প্রোগ্রামটা terminated হবে সেটাও বলা আছে। যখন ইনপুট দেয়া ৩ টি মানই শূণ্য হবে তখন প্রোগ্রামটা কাজ করা বন্ধ করবে।

এখন হিসাব নিকাশের পালা।

তিনটি বাহুর দৈর্ঘ্য দিয়ে আমরা কেমনে বুঝি কোন একটা ত্রিভুজ সমকোণী কিনা? মনে পড়েছে? সেই বাচ্চা কালে পড়েছিলাম। এত্তো বড় একটা উপপাদ্য। সেই রক্ত হিম করা “উপপাদ্য ২৩” বা পিথাগোরাসের উপপাদ্য! আমাদেরকে স্যার ক্লাসে বলেছিলেন এই উপপাদ্যের দাঁড়ি, কমা পর্যন্ত মুখস্ত করতে। দাঁড়ি-কমার প্লেসমেন্ট ভুল হলেও ডাবল জিরো! এখানে সেই ঐতিহাসিক উপপাদ্যের একটা প্রয়োগ করতে হবে।

পিথাগোরাস সাহেবের উপপাদ্য থেকে আমরা জানতে পারি সমকোণী ত্রিভুজের অতিভূজের বর্গ অপর দুই বাহুর বর্গের যোগফলের সমান। অর্থাৎ কোন একটা ত্রিভুজের অতিভুজ c আর অপর দুই বাহু যথাক্রমে a, b হলে সূত্রটি দাঁড়ায় a2 + b2 = c

Sample input এ দেয়া আছে 6, 8, 10. এখানে a = 6, b = 8 ও c = 10 হলে সূত্রানুযায়ী দেখতে পাই ৬ ও ৮ এর বর্গের যোগফল হয় ১০০ যা ১০ এর বর্গের সমান। অতএব এই ত্রিভুজটি পিথাগোরাসের উপপাদ্যকে satisfy করে। সুতরাং এটি একটি সমকোণী ত্রিভুজ।

লজিক তাহলে পেয়ে গেলাম কোডের। a আর b এর বর্গ করব। এরপর যোগ করে একটা ভ্যারিয়েবলে রাখব। এরপর c কে বর্গ করে আরেকটা ভ্যারিয়েবলে রাখব। এই দুইটা মান এরপর চেক করব যে সমান কিনা। যদি সমান হয় তাহলে রেজাল্ট হবে right, না হলে wrong. তো কোডটা করে ফেলিঃ

left_value = pow(a, 2) + pow(b, 2);
right_value = pow(c, 2);

if(left_value == right_value)
    printf("right\n");
else
    printf("wrong\n");

//একটু শর্টকাটে নিচের মত করেও করা যায়

if((a*a + b*b) == c*c))
    printf("right\n");
else
    printf("wrong\n");

তোমার কাছে যদি মনে হয় এই কোড পার্টটুকু ঠিক আছে তাহলে এটাকে Loop এর মধ্যে ফেলে দিয়ে প্রিন্ট কর। এবং নিশ্চিত ভাবে WA খাও! 😀

কেন ওয়া খাবা? স্যাম্পলের সাথে তো কোড মিলেছে! নিশ্চয়ই জাজে কোন সমস্যা আছে! তাই না?

নাহ! জাজ ঠিকই আছে। ইনপুটটা 6 8 10 না দিয়ে 10 8 6 দিলে কি তোমার কোড ঠিকঠাক রেজাল্ট দেয়? দেখ ত্রিভুজের ৩ টা বাহুর দৈর্ঘ্য ইনপুট দেয়ার ব্যাপারে বলা হয়েছে। কোথাও বলে নাই শেষের মানটাই অতিভুজ হবে। অর্থাৎ কোন একটা সমকোণী ত্রিভুজের বাহুগুলো তোমার প্রোগ্রামে যেভাবেই ইনপুট দেয়া হোক না কেন, তোমার রেজাল্ট আসতে হবে right! কারণ 6 8 10 বা 10 8 6 যেভাবেই লিখি না কেন একই ত্রিভুজকেই বুঝায়। তাহলে কোডটা কিভাবে ঠিকঠাক করা যায়?

উপরের কোডে শুধু c কে অতিভুজ কল্পনা করে চেক করেছি। এই চেকটা করতে হবে বাকি দুটি বাহুকেও অতিভুজ হিসেবে বিবেচনা করে। অর্থাৎ ত্রিভুজটি তখনই সমকোণী হবে যখন a2 + b2 = c অথবা b2 + c2 = a2  অথবা a2 + c2 = b2  এ ৩ টির যে কোন একটি সত্য হয়। উপরের কোডে a2 + b2 = c2 সত্য কিনা তা চেক করা হয়েছে। কিন্তু প্রকৃত পক্ষে এই তিনটি সমীকরণই চেক করতে হবে। যদি যে কোন একটা সত্য হয় তাহলে সেটি সমকোণী, অন্যথায় সমকোণী নয়। IF এর condition checking part এর ক্ষেত্রে Logical OR “||” ব্যবহার করে সহজেই এক লাইনে ৩টা চেক করা যেতে পারে।

কোথাও বুঝতে কোন সমস্যা হলে নির্দ্বিধায় কমেন্ট করো।

ধন্যবাদ। 🙂

6 thoughts on “অনলাইন জাজ সিরিজ – ৯ (UVa 11854 – Egypt)

  1. 0,0,0 দিলে প্রোগ্রামটা শেষ হবে এই লজিক কিভাবে লিখব?

    1. এভাবে করা যেতে পারেঃ (pseudo code)

      while(true) {
          input -> a, b, c;
      
          if(a, b, c all are zero) // if(a==0 && b==0 && c==0)
          break; // this line will break the loop
      
          // main calculation part
      
      }

Leave a Reply

Your email address will not be published. Required fields are marked *