62 lines
3.3 KiB
Markdown
62 lines
3.3 KiB
Markdown
|
---
|
|||
|
|
id: 5900f52a1000cf542c51003b
|
|||
|
|
title: 'Завдання 444: Лотерея за круглим столом'
|
|||
|
|
challengeType: 5
|
|||
|
|
forumTopicId: 302116
|
|||
|
|
dashedName: problem-444-the-roundtable-lottery
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
# --description--
|
|||
|
|
|
|||
|
|
Група людей $p$ вирішує сісти за круглим столом для гри з продажу лотерейних квитків. Кожна людина починає з невідкритого лотерейного квитка, що роздають у довільному порядку. Кожен квиток, при відкритті, виявляє однофунтовий приз від 1 до $p$ фунтів; двох однакових квитків немає. Мета гри для кожного з учасників полягає в тому, щоб максимально збільшити свій виграш до кінця гри.
|
|||
|
|
|
|||
|
|
В якості першого гравця обирається довільна людина. У свій хід кожен гравець має лише один з двох варіантів:
|
|||
|
|
|
|||
|
|
1. Гравець може відкрити свій квиток та показати його вартість всім за столом.
|
|||
|
|
2. Гравець може обміняти свій невідкритий квиток на відкритий квіток попереднього гравця, а потім залишити гру з цим квитком. Далі попередній гравець відкриває свій щойно отриманий квиток та показує його вартість всім за столом.
|
|||
|
|
|
|||
|
|
Гра закінчується коли всі квитки були відкриті. Всі гравці, що залишилися за столом, повинні закінчити гру з поточними квитками.
|
|||
|
|
|
|||
|
|
Припустимо, що кожен гравець використовує оптимальну стратегію для збільшення очікуваної вартості свого виграшу.
|
|||
|
|
|
|||
|
|
Нехай з з $p$ гравців, $E(p)$ буде очікуваною кількістю гравців, що залишаться в кінці гри (наприклад, $E(111) = 5.2912$ якщо округлити до 5-тизначних цифр).
|
|||
|
|
|
|||
|
|
Нехай $S_1(N) = \displaystyle\sum_{p = 1}^N E(p)$.
|
|||
|
|
|
|||
|
|
Нехай $S_k(N) = \displaystyle\sum_{p = 1}^N S_{k - 1}(p)$ для $k > 1$.
|
|||
|
|
|
|||
|
|
Знайдіть $S_{20}({10}^{14})$ та запишіть відповідь у вигляді рядка у науковому позначені з округленням до 10-тизначних цифр. Використовуйте нижній регістр `e` для відокремлення додатка та степеня. Наприклад, відповідь на $S_3(100)$ буде `5.983679014e5`.
|
|||
|
|
|
|||
|
|
# --hints--
|
|||
|
|
|
|||
|
|
`roundtableLottery()` повинен видати рядок.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert(typeof roundtableLottery() === 'string');
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
`roundtableLottery()` повинен видати рядок `1.200856722e263`.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert.strictEqual(roundtableLottery(), '1.200856722e263');
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --seed--
|
|||
|
|
|
|||
|
|
## --seed-contents--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
function roundtableLottery() {
|
|||
|
|
|
|||
|
|
return true;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
roundtableLottery();
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --solutions--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
// solution required
|
|||
|
|
```
|