رتبه بندی 
عکس نویسنده 
· محدودیت زمان: ۱ ثانیه
· محدودیت حافظه: ۲۵۶ مگابایت
جمشید کاظمی (که با نام مستعار کامران پوریایی شناخته می‌شود)، به تازگی آدم شده و از زندان آزاد شده است. او که به مدت طولانی در زندان بوده، از فضای برنامه نویسی و کامپیوتر دور شده و می‌خواهد با شرکت در مسابقات برنامه نویسی دوباره به این فضا بازگردد. برای همین به سایت کوئرا آمد و بین مسابقات برگزار شده گشت و گذار کرد. در این بین مسابقه‌ی Snapp Challenge توجهش را جلب کرد. نحوه رتبه بندی این مسابقه (مانند همین مسابقه ای که اکنون در حال شرکت کردن در آن هستید!) به این شکل بود: شرکت کننده ها به ترتیب تعداد سوال‌هایی که آن‌ها را کامل حل می‌کنند مرتب می‌شوند. افرادی که به تعداد برابر سوال حل می‌کنند، به ترتیب جریمه شان مرتب می‌شوند؛ یعنی هر کسی جریمه‌اش کمتر باشد رتبه‌ی بهتری می‌گیرد. مقدار جریمه به این صورت محاسبه می‌شود:
فرض کنید که مجموع زمان ارسال نهایی شرکت کننده برای سوال‌هایی که حل کرده aaa ثانیه باشد، و برای آن سوال‌ها در مجموع bbb بار ارسال غلط (قبل از ارسال نهایی) فرستاده است. (مثلاً ارسالی که پاسخ غلط می دهد، یا ارسالی که زمان اجرایش مناسب نیست.) در این صورت جریمه شرکت کننده برابر a+1200×ba + 1200 times ba+1200×b خواهد بود. یعنی هر ارسال غلط مانند ۱۲۰۰ ثانیه (برابر ۲۰ دقیقه) دیرتر فرستادن پاسخ نهایی است.
در نهایت افرادی که هم تعداد سوال برابری حل کرده اند و هم جریمه‌شان برابر است، رتبه برابری می‌گیرند. مثلاُ اگر ۲ نفر رتبه ۵ بیاورند، نفر بعدی رتبه ۷ خواهد بود و مسابقه رتبه ۶ نخواهد داشت. و اگر ۴ نفر رتبه ۳ بگیرند، نفر بعدی رتبه ۷ خواهد گرفت و مسابقه رتبه‌های ۴ و ۵ و ۶ نخواهد داشت.
این نحوه رتبه بندی و مخصوصاً ۲۰ دقیقه جریمه برای هر ارسال غلط، جمشید را به فکر فرو برد که آیا این بهترین روش برای رتبه‌بندی است؟ برای همین به این فکر کرد که این زمان ۲۰ دقیقه‌ای را تغییر دهد. مشخص است که مقدار منطقی این عدد ممکن است هر مقدار اعشاری باشد؛ پس برای انتخاب مقدار درست باید بطور خاصی تحلیل انجام داد. او این تحلیل را چنین انجام می‌دهد: فرض کنید رتبه‌ی یک شرکت کننده در رتبه بندی با فرض ۲۰ دقیقه جریمه، rrr است. حال فرض کنید که مقدار جریمه به ازای هر ارسال غلط تغییر کند و در رتبه بندی که با فرض مقدار جدید صورت می‌گیرد، رتبه این شرکت کننده برابر r′r'r′ بشود. اگر رتبه‌ی شرکت‌کننده در این حالت بهتر بود (یا r>r′r > r'r>r′)، شرکت کننده به مقدار (r−r′)2(r - r')^2(r−r′)2 خوش‌حال می‌شود و اگر رتبه بدتر شده بود، به مقدار (r′−r)2(r' - r)^2(r′−r)2 ناراحت می‌شود که مانند این است که −(r′−r)2-(r' - r)^2−(r′−r)2 خوش‌حال شده است. حال مجموع میزان خوش‌حال شدن تمامی شرکت کننده ها در این رتبه بندی را میزان خوب بودن مقدار r′r'r′ برای جریمه رتبه بندی در نظر می‌گیریم.
جمشید که اکنون آدم خوب و خوش‌قلبی شده است، می‌خواهد از روی این معیار که از روی خوش‌حالی افراد تعیین شده رتبه بندی ها را بسنجد. برای همین به دنبال بیشترین میزان خوب بودن به‌ازای تمامی مقادیر جریمه‌ی ممکن است. (تمام مقادیر صحیح یا اعشاری مثبت یا منفی می‌توانند برای جریمه انتخاب شوند!) با دریافت مقادیر aaa و bbb و تعداد سوال‌های حل شده برای هریک از شرکت کننده های یک مسابقه، بیشترین میزان خوب بودن ممکن برای رتبه‌بندی این مسابقه را محاسبه کنید.
در واقعیت، چنین تحلیلی در رابطه با رتبه‌بندی بهینه در کوئرا انجام شد تا در صورت نیاز مقدار جریمه تغییر بکند!
ورودی
در خط اول ورودی یک عدد nnn آمده است که تعداد شرکت‌کنندگان در مسابقه را نشان می‌دهد. سپس در هریک از nnn خط بعدی سه عدد می‌آید که برای یک شرکت‌کننده به ترتیب تعداد سوال حل شده، مقدار aaa (مجموع زمان ارسال‌های نهایی برای سوال‌های حل شده به ثانیه) و مقدار bbb (تعداد ارسال‌های غلط برای سوال‌های حل شده) می‌باشند.
تعداد سوال حل شده توسط هر نفر عددی طبیعی و حداکثر ۷ است. 1≤n≤1001 le n le 1001≤n≤100 0≤a≤86 4000 le a le 86 4000≤a≤86 400 0≤b≤700 le b le 700≤b≤70
خروجی
در تنها خط خروجی یک عدد چاپ کنید که برابر بیشترین میزان خوب بودن بین تمام مقادیر مختلف برای جریمه است.
مثال
ورودی نمونه ۱
4
10 100 1
30 100 1
50 100 1
70 100 1
خروجی نمونه ۱
14
ورودی نمونه ۲
4
2 30 1
1 60 1
1 70 2
3 90 2
خروجی نمونه ۲
1
مرکز یادگیری سایت تبیان
فرض کنید که مجموع زمان ارسال نهایی شرکت کننده برای سوال هایی که حل کرده aaa ثانیه باشد، و برای آن سوال ها در مجموع bbb بار ارسال غلط (قبل از ارسال نهایی) فرستاده است.
عکس نویسنده نویسنده : الناز فطیرخورانی
بازدید :
زمان تقریبی مطالعه :
تاریخ : چهارشنبه 1397/10/19 ساعت 09:51
· محدودیت حافظه: ۲۵۶ مگابایت
جمشید کاظمی (که با نام مستعار کامران پوریایی شناخته می‌شود)، به تازگی آدم شده و از زندان آزاد شده است. او که به مدت طولانی در زندان بوده، از فضای برنامه نویسی و کامپیوتر دور شده و می‌خواهد با شرکت در مسابقات برنامه نویسی دوباره به این فضا بازگردد. برای همین به سایت کوئرا آمد و بین مسابقات برگزار شده گشت و گذار کرد. در این بین مسابقه‌ی Snapp Challenge توجهش را جلب کرد. نحوه رتبه بندی این مسابقه (مانند همین مسابقه ای که اکنون در حال شرکت کردن در آن هستید!) به این شکل بود: شرکت کننده ها به ترتیب تعداد سوال‌هایی که آن‌ها را کامل حل می‌کنند مرتب می‌شوند. افرادی که به تعداد برابر سوال حل می‌کنند، به ترتیب جریمه شان مرتب می‌شوند؛ یعنی هر کسی جریمه‌اش کمتر باشد رتبه‌ی بهتری می‌گیرد. مقدار جریمه به این صورت محاسبه می‌شود:
فرض کنید که مجموع زمان ارسال نهایی شرکت کننده برای سوال‌هایی که حل کرده aaa ثانیه باشد، و برای آن سوال‌ها در مجموع bbb بار ارسال غلط (قبل از ارسال نهایی) فرستاده است. (مثلاً ارسالی که پاسخ غلط می دهد، یا ارسالی که زمان اجرایش مناسب نیست.) در این صورت جریمه شرکت کننده برابر a+1200×ba + 1200 times ba+1200×b خواهد بود. یعنی هر ارسال غلط مانند ۱۲۰۰ ثانیه (برابر ۲۰ دقیقه) دیرتر فرستادن پاسخ نهایی است.
در نهایت افرادی که هم تعداد سوال برابری حل کرده اند و هم جریمه‌شان برابر است، رتبه برابری می‌گیرند. مثلاُ اگر ۲ نفر رتبه ۵ بیاورند، نفر بعدی رتبه ۷ خواهد بود و مسابقه رتبه ۶ نخواهد داشت. و اگر ۴ نفر رتبه ۳ بگیرند، نفر بعدی رتبه ۷ خواهد گرفت و مسابقه رتبه‌های ۴ و ۵ و ۶ نخواهد داشت.
این نحوه رتبه بندی و مخصوصاً ۲۰ دقیقه جریمه برای هر ارسال غلط، جمشید را به فکر فرو برد که آیا این بهترین روش برای رتبه‌بندی است؟ برای همین به این فکر کرد که این زمان ۲۰ دقیقه‌ای را تغییر دهد. مشخص است که مقدار منطقی این عدد ممکن است هر مقدار اعشاری باشد؛ پس برای انتخاب مقدار درست باید بطور خاصی تحلیل انجام داد. او این تحلیل را چنین انجام می‌دهد: فرض کنید رتبه‌ی یک شرکت کننده در رتبه بندی با فرض ۲۰ دقیقه جریمه، rrr است. حال فرض کنید که مقدار جریمه به ازای هر ارسال غلط تغییر کند و در رتبه بندی که با فرض مقدار جدید صورت می‌گیرد، رتبه این شرکت کننده برابر r′r'r′ بشود. اگر رتبه‌ی شرکت‌کننده در این حالت بهتر بود (یا r>r′r > r'r>r′)، شرکت کننده به مقدار (r−r′)2(r - r')^2(r−r′)2 خوش‌حال می‌شود و اگر رتبه بدتر شده بود، به مقدار (r′−r)2(r' - r)^2(r′−r)2 ناراحت می‌شود که مانند این است که −(r′−r)2-(r' - r)^2−(r′−r)2 خوش‌حال شده است. حال مجموع میزان خوش‌حال شدن تمامی شرکت کننده ها در این رتبه بندی را میزان خوب بودن مقدار r′r'r′ برای جریمه رتبه بندی در نظر می‌گیریم.
جمشید که اکنون آدم خوب و خوش‌قلبی شده است، می‌خواهد از روی این معیار که از روی خوش‌حالی افراد تعیین شده رتبه بندی ها را بسنجد. برای همین به دنبال بیشترین میزان خوب بودن به‌ازای تمامی مقادیر جریمه‌ی ممکن است. (تمام مقادیر صحیح یا اعشاری مثبت یا منفی می‌توانند برای جریمه انتخاب شوند!) با دریافت مقادیر aaa و bbb و تعداد سوال‌های حل شده برای هریک از شرکت کننده های یک مسابقه، بیشترین میزان خوب بودن ممکن برای رتبه‌بندی این مسابقه را محاسبه کنید.
در واقعیت، چنین تحلیلی در رابطه با رتبه‌بندی بهینه در کوئرا انجام شد تا در صورت نیاز مقدار جریمه تغییر بکند!
ورودی
در خط اول ورودی یک عدد nnn آمده است که تعداد شرکت‌کنندگان در مسابقه را نشان می‌دهد. سپس در هریک از nnn خط بعدی سه عدد می‌آید که برای یک شرکت‌کننده به ترتیب تعداد سوال حل شده، مقدار aaa (مجموع زمان ارسال‌های نهایی برای سوال‌های حل شده به ثانیه) و مقدار bbb (تعداد ارسال‌های غلط برای سوال‌های حل شده) می‌باشند.
تعداد سوال حل شده توسط هر نفر عددی طبیعی و حداکثر ۷ است. 1≤n≤1001 le n le 1001≤n≤100 0≤a≤86 4000 le a le 86 4000≤a≤86 400 0≤b≤700 le b le 700≤b≤70
خروجی
در تنها خط خروجی یک عدد چاپ کنید که برابر بیشترین میزان خوب بودن بین تمام مقادیر مختلف برای جریمه است.
مثال
ورودی نمونه ۱
4
10 100 1
30 100 1
50 100 1
70 100 1
خروجی نمونه ۱
14
ورودی نمونه ۲
4
2 30 1
1 60 1
1 70 2
3 90 2
خروجی نمونه ۲
1
مرکز یادگیری سایت تبیان
