المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی سوم:دوره‌ی ۲۰:سوال ۵

جام جهانی

در جام جهانی فوتبال ۳۲ تیم حضور دارند. اگر این ۳۲ تیم را بر اساس رتبه‌شان در فیفا مرتب کنیم تیم‌ها رتبه ۱ تا ۳۲ می‌گیرند. (رتبه ۱ قوی‌ترین تیم و رتبه ۳۲ ضعیف‌ترین تیم است).

کامران معتقد است که اگر دو تیم با رتبه‌ی $a$ و $b$ (هر دو بین ۱ تا ۳۲) با هم مسابقه بدهند با احتمال $D=50-|a-b|$ درصد با هم مساوی می‌کنند و با احتمال $\frac{b\times (100-D)}{a+b}$ تیم $a$ برنده می‌شود و با احتمال $\frac{a\times (100-D)}{a+b}$ تیم $b$ برنده می‌شود.

فرض کنیم تیم‌های با رتبه‌ی ۲۱،۱۳،۷ و ۳۰ در یک گروه در مرحله مقدماتی حضور داشته باشند. می‌دانیم هر دو تیم با هم یک بار بازی می‌کنند (جمعا ۶ بازی) و هر پیروزی ۳ امتیاز و هر مساوی یک امتیاز دارد. در پایان مرحله‌ی گروهی، نفر اول و دوم گروه بالا می‌آیند. ترتیب نهایی تیم‌ها در یک گروه بر اساس امتیاز است؛ تیمی که امتیاز بیش‌تری کسب کند، رتبه کم‌تری کسب می‌کند. در صورت تساوی امتیازها، تیم‌های با امتیاز مساوی بر اساس رتبه اولیه‌شان مرتب می‌شوند؛ به طوری که تیمی که رتبه‌ی اولیه‌ی کم‌تری داشته باشد، رتبه‌ی نهایی کم‌تری هم پیدا می‌کند. برای مثال اگر تمام ۶ بازی مساوی بشود، تیم‌های با رتبه‌ی اولیه ۷ و ۱۳ از این گروه صعود می‌کنند.

کامران می‌خواهد احتمال صعود تیم با رتبه ۲۱ از این گروه را پیدا کند. اگر این احتمال $P$ باشد، عدد $ \lfloor P\times \ Delta^2 \rfloor$ را به عنوان جواب بنویسید.

پاسخ

#include <iostream>
#define FR(i,n) for(int i=0; i<n; i++)
using namespace std;
 
typedef long long LL;
enum MatchResult { WIN = 0, DRAW, LOSE };
 
const int rank[] = {7, 13, 21, 30};
const int n = 4;
const int nm = n*(n-1)/2 // number of matches: 6
const int me = 2; // team #2 is our team
const int delta = 90907;
 
struct Match {
  int a, b;
  Match(int a, int b) : a(a), b(b) {}
  double p[3]; // based on team a
};
 
int main() {
  Match mat[] = {Match(0,1), Match(0,2), Match(0,3),
                Match(1,2), Match(1,3), Match(2,3)};
  FR(i,nm) {
    int ra = rank[mat[i].a], rb = rank[mat[i].b];
    mat[i].p[DRAW] = (50 - abs(ra - rb)) / double(100);
    mat[i].p[WIN] = rb * (1.0 - mat[i].p[DRAW]) / double(ra + rb);
    mat[i].p[LOSE] = ra * (1.0 - mat[i].p[DRAW]) / double(ra + rb);
  }
 
  double ans = 0;
  int res[nm];
#define SFR(i) for (res[i]=0; res[i]<=2; res[i]++)
  SFR(0) SFR(1) SFR(2) SFR(3) SFR(4) SFR(5) {
    double prob = 1;
    FR(i,nm) prob *= mat[i].p[res[i]];
 
    int score[n];
    FR(i,n) score[i] = 0;
    FR(i, nm) {
      if (res[i] == WIN ) { score[mat[i].a] += 3; score[mat[i].b] += 0; }
      if (res[i] == DRAW) { score[mat[i].a] += 1; score[mat[i].b] += 1; }
      if (res[i] == LOSE) { score[mat[i].a] += 0; score[mat[i].b] += 3; }
    }
    int btm = 0; // better than me!
    FR(i,n) if (i != me)
      if (score[i] > score[me] || (score[i] == score[me] && i < me))
        btm++;
    if (btm < 2) ans += prob;
  }
  LL final = (LL)((LL)delta*delta*ans);
  cout << final << endl;
  return 0;
}

ابزار صفحه