Оказывается, вы — большой знаток группы AC/PE. Петя, узнав об этом, устроил следующую игру: он включает первую из списка n песен этой группы, а вы, в свою очередь, должны ее угадать. После того, как вы угадываете одну песню, Петя включает следующую по порядку песню, и так далее.
i-ая песня группы AC/PE имеет свою узнаваемость pi. Это означает, что, если песня до сих пор не была угадана, то, послушав ее еще ровно одну секунду, вы угадаете ее с вероятностью pi процентов. В противном случае вы продолжаете слушать её дальше. Имейте в виду, что вы можете делать догадки только в моменты времени, задающимися целым количеством секунд, прошедших с начала воспроизведения песни.
Во всех песнях AC/PE припев совпадает с названием, поэтому, услышав первые ti секунд i-ой песни, вы сразу точно угадываете ее название.
Так, например, в песне Highway To Red припев звучит довольно поздно, но она имеет высокую узнаваемость. В песне Back In Blue, напротив, слова названия звучат еще на первых секундах, однако до этого угадать ее тяжело. Обе эти песни вы сможете угадать еще по нескольким первым секундам.
Посчитайте матожидание количества песен, которые вы угадаете, если игра будет длиться ровно T секунд времени (т. е. последнюю догадку вы можете сделать в момент времени T, после чего игра прекращается).
Если все угаданы быстрее, чем за T секунд, игра заканчивается после угадывания последней песни.