Олимпиадная информатика - 2015

Задача « Красивое число»

Целое положительное число m мы назовём красивым, если в его записи между любыми двумя чётными цифрами есть хотя бы одна нечётная цифра, а между любыми двумя нечётными цифрами хотя бы одна чётная цифра.Вам нужно определить, будет ли данное m красивым числом.

Формат входного файла beauty.in Входной файл: В первой строке одно целое число n - количество цифр в записи числа m (1 <= n <= 10&sup6;). Во второй строке записаны без пробелов n цифр от 0 до 9. Первый символ в этой строке - ненулевая цифра.

Формат выходного файла beauty.out Выходной файл: Выведите "Yes", если данное число красивое, и "No" - в противном случае.

var 	q,w:char;
	n,i:longint;
 
assign(input,'beauty.in'); 
reset(input);
assign(output,'beauty.out'); 
rewrite(output);
begin
readln(n);
read(q);
for i:=1 to n-1 do
begin
	read(w);
	if(ord(w)+ord(q))div 2=0 then
begin
	write('No');
	halt;
end;
q:=w;
end;
write('Yes');
close(input);
close(output);
end.

close
 

Разбор задачи №1 "Красивое число"

Поскольку длина числа может достигать 1000000 цифр, будем рассматривать его как последовательность символов. Для выполнения условия задачи чётные и нечетные цифры должны чередоваться.

Будем последовательно рассматривать соседние пары символов. Для проверки совпадения или несовпадения чётности цифр используем, что сумма двух чисел одной чётности – чётная, а разной чётности - нечётная. Рассмотрев очередную пару символов, первому символу придадим значение второго и запросим значение следующего символа.

Если они (а значит и их коды) имеют одинаковую чётность, то число не является красивым – сообщаем об этом и досрочно прекращаем выполнение программы. Если же рассмотрены все пары соседних цифр и не найдено ни одной пары с одинаковой чётностью, то сообщаем, что число красивое.