Лягушонок Билли сидел на камне и любовался на закат, когда понял, что проголодался. Он огляделся и с удивлением обнаружил, что в ручье около него копошатся мошки. Ручей представляет собой прямую, на которой расположен и камень, на котором сидит Билли. Лягушонок был очень голоден, и потому захотел съесть всех мошек. У Билли очень длинный язык, поэтому он может, не спрыгивая с камня, съесть любую мошку (но только одну за раз). Однако высовывать язык на большие расстояния не так-то просто, лягушонок на каждый сантиметр высунутого языка тратит одну единицу энергии. Каждый раз, когда Билли съедает мошку из какой-то точки происходит следующее: все мошки, сидящие слева от съеденной мошки, и все мошки, сидящие справа от нее в ужасе отпрыгивают от места событий на один сантиметр вдоль ручья. Мошки, которые сидят в той же точке, что и съеденная, настолько шокированы этим событием, что не двигаются.
Вы используете гостевой доступ (Вход) Эврика: Задачи турнира 2018 г. В начало Курсы Кружки и уроки Камчатский край Эврика Тема 35 Задачи турнира 2018 г. Задача №113668. Лягушонок Билли Лягушонок Билли сидел на камне и любовался на закат, когда понял, что проголодался. Он огляделся и с удивлением обнаружил, что в ручье около него копошатся мошки. Ручей представляет собой прямую, на которой расположен и камень, на котором сидит Билли. Лягушонок был очень голоден, и потому захотел съесть всех мошек. У Билли очень длинный язык, поэтому он может, не спрыгивая с камня, съесть любую мошку (но только одну за раз).
Однако высовывать язык на большие расстояния не так-то просто, лягушонок на каждый сантиметр высунутого языка тратит одну единицу энергии. Каждый раз, когда Билли съедает мошку из какой-то точки происходит следующее: все мошки, сидящие слева от съеденной мошки, и все мошки, сидящие справа от нее в ужасе отпрыгивают от места событий на один сантиметр вдоль ручья. Мошки, которые сидят в той же точке, что и съеденная, настолько шокированы этим событием, что не двигаются.
Если мошка в какой-то момент времени прыгает на камень, где сидит Билли, то Билли тут же съедает ее не тратя энергии. При этом другие мошки не перемещаются. Лягушонок Билли хочет понять — какое минимальное количество единиц энергии ему потребуется для того, чтобы съесть всех мошек ему это выяснить.
Входные данные В первой строке входного файла задано одно натуральное числа n (1≤n≤100000) — количество мошек. Во второй строке входного файла задано n натуральных чисел — расстояния каждой из мошек до камня. Известно, что все мошки находятся на одной прямой по одну сторону от камня. Расстояния даны в порядке неубывания. Расстояния не превышают 109 .
Выходные данные Выведите одно число — минимальное количество единиц энергии, которое потребуется Билли, чтобы съесть всех мошек.
Пояснение к примеру Сначала Билли съест одну мошку, сидящую в точке 4. Другая мошка, сидящая в этой точке не сдвинется, обе мошки из точки 2 сдвинутся в точку 1. После того, как он съест вторую мошку в точке 4, обе мошки из точки 1 отпрыгнут в точку 0, где и будут сразу съедены.
Ну вот как-то так, если что-то не ясно - спрашивай. Инициализации начальных элементов нет, так что без соответствующей правки она не заработает.
int main() { // Something int a[n][m]; // Init
// Находим максимум int im = 0, jm = 0, max = a[0][0]; for (int i = 0 ; i < n; ++i) for (int j = 0; j < m; ++j) if (a[i][j] > max) { max = a[i][j]; im = i; jm = j; }
// Двигаем максимум вниз swapCollumn(a, n, m, im, n-1); swapRow(a, n, m, jm, m-1);
}
//Премещаем 2 столбца местами void swapCollumn(int ** a, int n, int m, int c1, int c2) { if (c1 < 0 || c2 < 0 || c1 >= n || c2 >= n) return; for (int i = 0; i < m; ++i) swap(&a[c1][i], &a[c2][i]); }
//Перемещаем 2 строки местами void swapRow(int ** a, int n, int m, int r1, int r2) { if (r1 < 0 || r2 < 0 || r1 >= m || r2 >= m) return; for (int i = 0; i < n; ++i) swap(&a[i][r1], &a[i][r2]); }
void swap(int * el1, int el2) { int t = *el1; *el1 = *el2; *el2 = *el1; }
Program N94780249; const s: longint = 0; var x: longint; t: string; e: integer; begin writeln('Вводите целые числа (0 - окончание ввода) : '); repeat repeat write('> '); readln(t); val(t, x, e); if e <> 0 then writeln('Ошибка! Повторите ввод. ') until e = 0; s += x until x = 0; if s = 0 then writeln('Числа не вводились. ') else writeln('Сумма введённых чисел = ', s, #10); write('Для завершения работы нажмите Enter...'); readln end.
int main() {
// Something
int a[n][m];
// Init
// Находим максимум
int im = 0, jm = 0, max = a[0][0];
for (int i = 0 ; i < n; ++i)
for (int j = 0; j < m; ++j)
if (a[i][j] > max) {
max = a[i][j];
im = i;
jm = j;
}
// Двигаем максимум вниз
swapCollumn(a, n, m, im, n-1);
swapRow(a, n, m, jm, m-1);
}
//Премещаем 2 столбца местами
void swapCollumn(int ** a, int n, int m, int c1, int c2) {
if (c1 < 0 || c2 < 0 || c1 >= n || c2 >= n)
return;
for (int i = 0; i < m; ++i)
swap(&a[c1][i], &a[c2][i]);
}
//Перемещаем 2 строки местами
void swapRow(int ** a, int n, int m, int r1, int r2) {
if (r1 < 0 || r2 < 0 || r1 >= m || r2 >= m)
return;
for (int i = 0; i < n; ++i)
swap(&a[i][r1], &a[i][r2]);
}
void swap(int * el1, int el2) {
int t = *el1;
*el1 = *el2;
*el2 = *el1;
}
const
s: longint = 0;
var
x: longint;
t: string;
e: integer;
begin
writeln('Вводите целые числа (0 - окончание ввода) : ');
repeat
repeat
write('> ');
readln(t);
val(t, x, e);
if e <> 0 then
writeln('Ошибка! Повторите ввод. ')
until e = 0;
s += x
until x = 0;
if s = 0 then
writeln('Числа не вводились. ')
else
writeln('Сумма введённых чисел = ', s, #10);
write('Для завершения работы нажмите Enter...');
readln
end.