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
|
||
```
|