ТОПЧЕТА
시간 제한1초메모리 제한1024 MB
배열의 각 값을 전체 합에서 자기 값을 뺀 값으로 바꾸는 변환을 K번 반복한 뒤 최댓값과 최솟값의 차이를 구한다.
문제
Митко играе следната игра. Той разполага с купчина от червени и сини топчета. В N кутии, номерирани с числата от 1 до N са поставени определен брой топчета с различни цветове (във всяка кутия има топчета от само един цвят – червени или сини). Митко си записва броя на топчетата във всяка кутия така: ако топчетата в кутията са сини, пред броя им слага знак „минус“, т.е. броят става отрицателно число. В началото на играта се пресмята сумата от числата, които е записал. След това Митко поставя в кутия с номер 1 толкова на брой топчета, колкото е разликата на общия брой и броя, който е в кутията. Ако се получи отрицателно число, в съответната кутия Митко поставя само сини топчета, а ако се получи положително - поставя червени топчета. Същото действие извършва с всички останали кутии. На втората стъпка се събира полученият нов брой на топчета във всички кутии и Митко трябва отново да започне да поставя в кутиите този брой минус броя, който се съдържа в съответната кутия. И така, тези действия се повтарят K пъти. Накрая Митко трябва да отговори на въпроса: Колко е разликата между максималния и минималния брой на топчета в кутиите след K на брой стъпки? Напишете програма balls, която пресмята тази разлика при зададени N, K и първоначален брой топчета във всяка кутия.
입력
От първия ред на стандартния вход се въвеждат две цели числа N и K. От следващия ред се въвеждат N цели числа – брой на топките в кутиите. Ако топките са сини, числото е отрицателно, ако са червени – положително. Числата са разделени с по един интервал.
출력
На един ред на стандартния изход програмата трябва да изведе едно цяло число – търсената разлика.
제한
- 2 ≤ N ≤ 1000000
- 1 ≤ K ≤ 1000
- Числата в редицата имат стойности в интервал от -2000 000 000 до 2000 000 000
힌트
- В първата кутия има 7 сини топчета, във втората 1 червено, а в третата 3 сини.
- На първата стъпка (K=1) Митко ще получи сбор -9.
- В първата кутия ще остави 2 броя сини топчета: -9-(-7) = -2
- Във втората кутия ще постави 10 броя сини топчета, а ще махне червеното: -9-1= -10
- В третата кутия ще постави още 3 броя сини топчета, за да станат 6: -9-(-3) = -6
- На втората стъпка (K=2) Митко ще получи сбор -18.
- В първата кутия ще станат 16 броя сини топчета: -18-(-2) = -16
- Във втората кутия ще станат 8 броя сини топчета: -18+10= -8
- В третата кутия ще станат 12 броя сини топчета: -18+6 = -12
Най-големият брой топчета е в първата кутия – 16, най-малкият е 8 – във втората кутия. Разликата е 8.