المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی انتخاب تیم:دوره ی ۲۵:سوال ۸

Aseman

فساد شرکتی به تازگی افشا شده است! مردم برای اعتراض به عملکرد این شرکت، رو به روی ساختمان آن تجمع کرده‌اند. جمعی از اغتشاش‌گران هم در این میان قصد دارند سنگ به سمت ساختمان شرکت پرتاب کنند! ساختمان شرکت دارای $k$ پنجره است که $h$ تا از آن‌ها دو جداره (به پهنای دو شیشه) و بقیه یک جداره‌اند. صاحبان شرکت $m$ نفر استخدام کردند و به هر کدام یک شیشه دادند تا یکی از پنجره‌ها را مقاوم‌تر کنند. دقت کنید قدرت هر پنجره به هر مقدار می‌تواند افزایش یابد و شیشه‌ی آن $x$ جداره شود. هریک از این $m$ نفر، به طور تصادفی و بدون توجه به انتخاب دیگران یا تعداد شیشه‌های هر پنجره، یک پنجره را انتخاب کرده و آن را مقاوم‌تر می‌کند.

سپس هر یک از $n$ اغتشاش‌گر نیز، به طور تصادفی و بدون توجه به انتخاب دیگران یا تعداد شیشه‌های هر پنجره‌، یک پنجره را انتخاب کرده و سنگی به سمت آن پرتاب می‌کند. درنتیجه یکی از شیشه‌های آن پنجره را می‌شکند. اگر تمام شیشه‌های حداقل یک پنجره بشکند ساختمان ناامن می‌شود. برنامه‌ای بنویسید که احتمال امن ماندن ساختمان را محاسبه کند.

پیاده‌سازی

در این سوال شما باید توابع زیر را پیاده‌سازی کنید:

  • void initProgram()

این تابع دقیقا یک‌بار پیش از اجرای تمامی موارد آزمون صدا زده می‌شود. از آن برای انجام پیش‌پردازش‌ها(در صورت وجود) استفاده کنید.

  • این تابع، ورودی ندارد.
  • double getProbability(int k, int n, int m, int h)

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

  • $k, n, m, h$:چهار عدد متناظر با پارامترهای توضیح داده شده در متن سوال.

ارزیاب نمونه

ارزیاب نمونه ورودی را به صورت زیر می‌خواند:

در خط اول عدد $t$، تعداد موارد آزمون آمده است. سپس به ازای هر مورد آزمون یک خط آمده است که در آن به ترتیب چهار عدد $k$، $n$، $m$ و $h$ آمده است.

زیرمسئله‌ها

  • زیرمسئله‌ی اول (۳۰ نمره): $k \le 20; n, m \le 30; t \le 100$.
  • زیرمسئله‌ی دوم (۷۰ نمره): بدون محدودیت اضافی.

محدودیت‌ها

  • محدودیت زمان: ۳۰ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • $1 \le t \le 200$
  • $1 \le k \le 200$
  • $0 \le h \le k$
  • $1 \le n, m \le 100$

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
3
3 1 1 0
3 2 1 0
3 1 2 2
0.333333333
0.000000000
0.851851852

ابزار صفحه