دکتر زینگ

الگوریـــتـم

۲ مطلب با کلمه‌ی کلیدی «Topcoder» ثبت شده است

TC SRM #518 Third level

فرض کنید که ۲۰ سکه روی میزی قرار دارد به این صورت که روی سکه ها به سمت بالاستابتدا ۲ تا از این سکه ها رو به صورت شانسی بر عکس می کنیمبدیهیست که ۱۸ تا سکه رو و ۲ سکه پشت داریمحالا ۵ سکه را از بین این ۲۰ سکه به صورت شانسی انتخاب می کنیمتعداد سکه هایی که رو و پشت هستند تغییر می کندتعداد سکه های مورد انتظار بعد از تعدادی پشت و رو کردن به صورت شانسی را به چه صورت می توان بدست آورد.

در این سوال  تابع دو ورودی دارد۱تعداد سکه  ۲آرایه ای از تعداد سکه هایی که در هر مرحله باید به صورت شانسی انتخاب شوند و برعکس شوندتعداد سکه ها بین ۱ و ۱۰۰۰ و سایز آرایه حداکثر ۵۰ می باشد.

می خواهیم ۵ تا سکه از این ۲۰ سکه انتخاب کنیم۱۸/۲۰ احتمال دارد که از سکه های رو و ۲/۲۰ احتمال می رود که از سکه های پشت انتخاب کنیم و آنها را برعکس کنیمسکه های رویی که انتخاب می کنیم چون به صورت پشت قرار میگیرند از تعداد سکه های رو کم می شود و تعداد سکه هایی که از سکه های پشت انتخاب می کنیم به سکه های رو اضافه می شود به عبارت دیگر:

HEAD = HEAD - HEAD * ( a[i] / N) + (N- HEAD ) * ( a[i] / N ) ;


نکاتی که توی این فرمول باید دقت کنید CAST به دابل می باشد.

کد کامل :


double expectedHeads(int N, vector <int> a) {

double k = N ni = N;;

double

for( int i = 0 ; i < a.size() ; i++ ) {

k = k - (k )* (a[i]/ni) + ((ni-k)) * (a[i]/ni) ;

}

return k;

}

۰ نظر موافقین ۰ مخالفین ۰
امیرحسین رجبی

TC SRM #500 Third level

   این سوال از برنامه نویس می خواهد تا برنامه ای بنویسد که تعداد جواب های متمایز دو معادله را بدست آوردصورت سوال بسیار ساده و قابل فهم می باشد اما نکته ای که باعث میشود این سوال برنامه نویس را به چالش بکشد این است که جواب های معادله ممکن است از مرز حافظه های قابل استفاده در زبان برنامه نویسی عبور کند و عددی با۱۰۰۰۰۰ رقم تولید کند.


   برای حل این سوال می بایست جواب های معادله را به وسیله ی تکنیکی به دو بخش تقسیم کنیماین دوبخش حاصل باقیمانده ی جواب به دو عدد متفاوت است. ( انتخاب دو عدد متوالی ترجیح داده می شود برای مثال دو عدد ۱۰۰۰۰۰۰۰۰۱ و ۱۰۰۰۰۰۰۰۰۲ اینجا دیده میشود که عدد ۱ به صورت ۱ و ۱ بدست می آید و عدد ۱۰۰۰۰۰۰۰۰۳ به صورت ۱ و ۲ به دست می آید این روش تا عددی با تعداد ۱۰ به توان ۱۰ رقم را میتواند پشتیبانی کند !!!!


   ما ابتدا یک set از نوع pair می سازیم و شروع به بدست آوردن جواب ها به صورت موازی در دو متغیر می کنیم و باقیمانده دو متغیر را به عدد باقیمانده ی مربوط به متغیر بدست می آوریم و جایگزین متغیر می کنیم و آنها را در داخل ست وارد می کنیم.


این کد فقط برای یکی از معادلات هست :


st.insert( point(b1 , b1 ) );


long long a = b1 , b = b1;


for( int i = 0 ; i < n1-1 ; i++ ) {


a *= q1 ;


b *= q1 ;


a %= m1;


b %= m2;


st.insert( point( a , b) );


}



معادله ی دیگر نیز به همین شکل بدست می آوریم و داخل ست می کنیمسایز ست جواب سوال می باشد.


۰ نظر موافقین ۰ مخالفین ۰
امیرحسین رجبی