1420. Zipper |

1421. Bullet Hole |

1422. Oblique Cuboid |

1423. Quodigious |

1424. Tumble Down |

1425. Fish Catch |

1427. Huffman Code |

1428. Infinite Game |

14/11/2024 09:43:43

Реализация заданного алгоритма

Олимпиадные задачи на английском языке

Олимпиадные задачи на английском языке

24/06/2010 | Лето 2010 дорешивание ( 5G) |

02/07/2010 | Лето 2010 - 5 (G) |

*Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод*

Послать решение Blockly Посылки Темы Где Обсудить (0)

Bowling is a game requiring many talents-the ability to lift and throw a sixteen-pound ball, a
keen fashion eye for gaudy clothes, and the advanced mathematical skills necessary to keep score.
Computers aren't much help in lifting or dressing, but they are fine tools for keeping score. In this
problem, we define a new way of scoring known as "Fibonacci" scoring and write a program to
keep score.

In bowling, the basic idea is to roll the ball toward standing wooden pins, trying to knock down as
many as possible. A game consists of ten *frames*. Each frame begins with ten pins standing, and
the bowler is given a first roll to knock down as many pins as possible, and a second roll (if any
pins are left standing after the first roll) to knock down as many of the remaining pins as possible.
If all ten pins are knocked down after the first roll, it is called a *strike*. If all ten pins are knocked
down after the second roll, it is called a *spare*. If some pins remain standing after the second roll,
it is called an *open frame*.

Let `p_i` be the number of pins knocked down and `r_i` be the number of rolls taken in frame `i`, for
`i\ =\ 1,\ 2,\ 3,\ …,\ 10`. Note that a strike has `p_i\ =\ 10` and `r_i\ =\ 1`, a spare has `p_i\ =\ 10` and `r_i\ =\ 2`,
and an open frame has `0\ ≤\ p_i\ <\ 10`. A score si is defined for each frame `i\ =\ 1,\ 2,\ 3,\ …,\ 10` using
"Fibonacci" scoring, in which a strike usually earns `p_i\ +\ s_{i-1}\ +\ s_{i-2}` points, a spare usually earns
`p_i\ +\ s_{i-1}` points, and an open frame earns `p_i` points. Formally, the score `s_i` for frame `i` is defined
recursively by

`p_i\ +\ s_{i-1}\ +\ s_{i-2}` if `p_i` = 10 and `r_i` = 1 and `i\ ≥\ 3`,

`p_i\ +\ s_{i-1}` if `p_i\ =\ 10` and ((`r_i\ =\ 2` and `i\ ≥\ 2`) or (`r_i\ =\ 1` and `i\ =\ 2`)),

`p_i` otherwise,

and the total score is `sum_{i=1}^{10}\ s_i`.

Input Format

Each line of the input represents a game and contains a list of numbers recording how many
pins were knocked down by each roll of the ball.

Output Format

Each line shows the scores `s_i` for frames `i\ =\ 1,\ 2,\ 3,\ …\ ,\ 10` of the corresponding game in
the input. The last number in each line is the total score. Right-justify each number output in a
5-column field, with '` = `' preceding the total.

Sample Input

6 4 10 10 6 3 9 1 8 1 10 10 8 2 8 2 10 5 5 10 9 1 8 0 6 3 10 10 10 10

Sample Output

10 20 40 9 19 9 38 57 67 77 = 346 10 20 40 50 8 9 27 46 83 139 = 432