المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی سوم:دوره‌ی ۱۹:سوال ۶

بارم بندی

این امتحان ۶ سوال دارد. آیدیدن (طراح امتحان) می‌خواهد طوری برای این ۶ سوال تعیین نمره (اصطلاحا «بارم بندی») کند که اولا نمره‌ی هر سوال یک عدد صحیح بین ۱۰ تا ۲۵ (شامل خود این دو عدد) باشد؛ ثانیا مجموع نمرات کل ۶ سوال دقیقا برابر با ۱۰۰ بشود.

فرض کنید که با توجه به سبک سوالات، نمره‌ی هر دانش‌پژوه از هر سوال به صورت «صفر و یک» (یا صفر، یا تمام نمره‌ی سوال) است. با این توصیف، نمره‌ی می‌خواهد طوری این سوالات را بارم‌بندی کند که تعداد نمرات متفاوتی که می‌شود از امتحان گرفت حداکثر بشود. برای مثال اگر آیدین برای چهار سوال نمره‌ی ۲۰ و برای دو سوال نمره‌ی ۱۰ را در نظر بگیرد، در این صورت تنها ۱۱ مقدار (مضارب ۱۰ بین صفر تا ۱۰۰) می‌تواند نمره‌ی یک دانش‌پژوه باشد در حالی که اگر نمرات شش سوال به ترتیب ۱۹،۱۲،۲۵،۲۴،۱۰ و ۱۰ باشد، در این صورت ۴۶ نمره‌ی متفاوت می‌تواند از این امتحان گرفته شود!

اگر حداکثر تعداد نمرات متفاوت در بهترین بارم‌بندی $J$ باشد، در این صورت باقی‌مانده‌ی تقسیم عدد $J^3$ (عدد $J$ به توان ۳) بر $\Delta$ چند است؟

پاسخ

‎
 
 
 
#include <iostream> 
#include <vector> 
using namespace std; 
 
#define FA(x) for (a[x] = (x?a[x-1]:10); a[x] <= 25; a[x]++) 
 
int main() { 
  int a[6]; 
  int m = 0; 
  FA(0) FA(1) FA(2) FA(3) FA(4) { 
    a[5] = 100; 
    for (int i=0; i<5; i++) 
      a[5] -= a[i]; 
    if (a[5] < 10 || a[5] > 25 || a[5] < a[4]) 
      continue; 
 
    vector<int> v; v.clear(); 
    for (int i=0; i < (1 << 6); i++) { 
      int g = 0; 
      for (int k=0; k<6; k++) 
        if ((i >> k) & 1) g += a[k]; 
      v.push_back(g);    
    } 
 
    int r = v.size(); 
    sort(v.begin(), v.end()); 
    for (int i=1; i<v.size(); i++) 
      if (v[i] == v[i-1]) r--; 
    m = max(r,m); 
  } 
 
  cout << m << endl; 
 
  return 0; 
}

ابزار صفحه