ИНФОРМАТИКА КОД НА ПИТОН Слишком много платьев
Имя входного файла: стандартный ввод или stdin
Имя выходного файла: стандартный вывод или stdout
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 мегабайта
Сёстры Рита и Берта живут в одной комнате и делят один шкаф на двоих. Они очень любят
новые наряды, и поэтому у них скопился целый шкаф платьев. Их настолько много, что иногда
девочки путаются и берут не своё платье. В последнее время у девочек появилось много свободного
времени, поэтому они решили навести порядок в шкафу.
Сейчас платья висят вперемешку. Девочки хотят развесить их так, чтобы сначала висели все
платья одной из девочек, а потом все платья другой. За одной действие можно достать одно платье
и повесить его обратно в шкаф на любое место Рите и Берте узнать, за какое минимальное количество действий они справятся с
наведением порядка в шкафу?
Формат входных данных
В первой строке содержится целое число n (1 ⩽ n ⩽ 50 000) — количество платьев в шкафу.
Во второй строке — строчка длины n, состоящая только из символов «R» и «B», означающих
платья Риты и Берты соответственно.
Формат выходных данных
Выведите одно число — минимальное число действий необходимых для упорядочивания платьев.
Примеры
стандартный ввод или stdin стандартный вывод или stdout
4
RBRB
1
8
BBRRBRBR
2
cos(x) = 1 - x^2/2 + x^4/24 - x^6/720 + ...
1 - cos(2x) = 2 sin(x) sin(x)
sin(x) < 2 x / Pi
| 1 - cos(2x) | < 2 (2x/Pi)^2 = 8 x^2 / Pi^2
Если x^2 < Pi^2 eps / 8, то |1-cos(2x)|<eps
Предложение: делаем рекурсивный спуск по формуле cos(x)=2cos(x/2)^2 - 1, пока x > Pi sqrt(eps)/2, затем возвращаем 1-x^2/2. Оценка x < Pi sqrt(eps)/2 делалась для неравенства |1 - cos(x)| < eps, но возвращаем не просто 1, а 1-x^2/2 — до квадратичного члена, то есть с большей точностью. Кстати, Pi/2 < 2.
Код JavaScript
function cos1(x, eps)
{ if(Math.abs(x) < 2*Math.sqrt(eps)) return (1-x*x/2);
var c = cos1(x/2, eps);
return (2*c*c - 1);
} cos(0.5, 0.001);
Внимательно посмотрев на эту реализацию, можно увидеть хвостовую рекурсию, которую можно представить в виде цикла, что предпочтительнее, потому что не требует памяти под стек вызовов и потому является быстрее. Но это выходит за пределы рассматриваемой задачи.
P.S. Оценка рядом Маклорена-Тейлора при малых аргументах предпочтительнее: сходится быстрее.
другой вариант
Можно посчитать по ряду Тейлора, стандартно превратив итерацию в хвостовую рекурсию. Для этого используется вс функция, которой в качестве дополнительных (по сравнению с изначальной функцией) аргументов передаются все величины, которые хочется помнить (в данном случае номер члена i, очередной член a и вычисленную сумму s).
Код Haskell
cos' eps x = helper 1 1 0
where helper i a s
| abs a < eps = s
| otherwise = helper (i + 2) newa (s + a)
where newa = - a * x^2 / (i * (i + 1))
ряд Тейлора в данном случае удовлетворяет признаку Лейбница (ну, с оговорками), поэтому можно останавливаться, когда очередной член стал меньше эпсилона.
Код JavaScript
<script type="text/javascript"> function Cosine(x,eps)
{ function CosTaylor(x,n,an)
{ var an1 = (-1)*an*x*x/(2*n*(2*n-1));
if (Math.abs(an1) < eps) return an + an1;
else
{ return an + CosTaylor(x,n+1,an1); }
}
return CosTaylor(x,1,1); }
</script> <button onclick="alert( Cosine(0.75,0.001) )">Пример для x=0.75 и eps=0.001</button>
Здесь А - массив, N - количество чисел в массиве, sum - сумма элементов массива, count - количество искомых элементов, sum * 1.0 / N - это и есть среднее арифметическое, причем если здесь не умножать на 1.0, то результат будет округлен и программа будет уже работать неправильно, а если умножать, то все хорошо, потому что sum * 1.0 / N становится вещественным числом
Объяснение:
Здесь можно использовать динамику(чтобы не занимать место в памяти статическим массивом):
#include <iostream>
using namespace std;
int main()
{
int N, sum=0, count=0;
cin >> N;
int* A = new int[N];
for (int i = 0; i < N; i++) {
cin >> A[i];
sum += A[i];
}
for (int i = 0; i < N; i++) if (A[i] < (sum * 1.0 / N)) count++;
cout << count;
delete[] A;
}
Но если динамика еще не изучена, то:
#include <iostream>
using namespace std;
int main()
{
int N, sum=0, count=0, A[1000];
cin >> N;
for (int i = 0; i < N; i++) {
cin >> A[i];
sum += A[i];
}
for (int i = 0; i < N; i++) if (A[i] < (sum * 1.0 / N)) count++;
cout << count;
}