Задача на Паскаль.ОЧЕНЬ НАДО!
Реверсивная игра
Тур I, задача 2
Недавно компания “Gold & Silver Software” анонсировала выход новой игры для мобильных телефонов под названием «Реверсивная игра». Игра является пошаговой и предназначена для одного игрока.
Игровое поле представляет собой горизонтальную полосу, разделенную на N клеток, пронумерованных целыми числами от 1 до N слева направо. Каждая клетка может быть черного либо белого цвета. Целью игры является приведение всей полосы к белому либо к черному цвету за минимальное количество ходов. За один ход игрок может выделить произвольное количество подряд идущих клеток и программа изменит цвет выделенных клеток на противоположный. То есть все выделенные клетки черного цвета станут белыми, а белые выделенные клетки станут черными.
Рисунок №1. Описание второго примера.
Выше приведен пример игры, при которой за два хода можно получить полосу черного цвета. Ваша задача - определить минимальное количество ходов, которое потребуется для того, чтобы из заданной полосы получить одноцветную.
Входные данные
Первая строка входного файла содержит ровно одно целое число N (1 ≤ N ≤ 1000).
Вторая строка содержит N целых чисел. Каждое i-е число соответствует цвету i-й клетки и равно 0 (для черного цвета) либо 1 (для белого цвета).
Выходные данные
Единственная строка выходного файла должна содержать одно целое число – минимальное количество ходов, необходимое для приведения полосы к одному цвету.
input.txtoutput.txt
5
1 1 1 1 1 0
6
0 1 1 0 0 1 2
7
1 0 1 0 1 0 0 3
input.txt output.txt
5
1 1 1 1 1 0
6
0 1 1 0 0 1 2
7
1 0 1 0 1 0 0 3
input.txt output.txt
5
1 1 1 1 1 (0)
6
0 1 1 0 0 1 (2)
7
1 0 1 0 1 0 0 (3)
В скобках аутпут
ReadLn(Fin, N);
Read(Fin, Z); B := (Z = 1); K0 := 0; K1 := 0; if B then Inc(K0) else Inc(K1);
for i := 2 to N do begin Read(Fin, Z); if B <> (Z = 1) then begin B := (Z = 1); if B then Inc(K0) else Inc(K1); end; end;
if K0 < K1 then WriteLn(Fout, K0) else WriteLn(Fout, K1);
Отличная олимпиадная задачка, по моему.
В вашем примере по моему сбилось форматирование. В конце каждой второй строки очевидно идет решение, поставьте переносы чтоле :)
По моему задача сводится к вычислению количества перемен знаков. Пока не вижу вариантов, чтобы быстрее можно было сменить цвет, чем за кол-во переходов в одну сторону.