Информатика в школе

Рассмотрим решение задач  школьного этапа Всероссийской олимпиады школьников по информатике на программирование. Скачать задания вы можете по ссылкам:

ВОШ по информатике школьный этап 9-11 классы (2014 г.)
ВОШ по информатике школьный этап 7-8 классы (2014 г.)

Рассмотрим следующие задачи:

• Шахматная доска
• Манхеттен
• Пятница, 13-е
• Автомобильные номера
• Числа-палиндромы

Задача №1. Шахматная доска.

 Шахматная доска состоит из n × m клеток, покрашенных в черный и белый цвет в «шахматном» порядке. При этом клетка в левом нижнем углу доски покрашена в черный
цвет. Определите, сколько всего на доске черных клеток. Программа получает на вход два числа n и m, записанных в отдельных строках. Все числа — натуральные, не превосходящие 30 000. Программа должна вывести одно целое число — количество черных клеток на доске.

Решение.

Рассмотрим частные случаи:

Видим закономерность:

1. если количество полей четное (4х4=16), то на каждом ряду одинаково количество черных и белых клеток, т.е. чтобы найти количество черных полей нужно общее количество клеток разделить на 2. Проверим: 16:2=8. Посчитаем. Действительно 8!! Можете поэкспериментировать с досками других размеров, но чтобы общее число клеток было четным.
2. если количество полей нечетное (5х5=25) то дело обстоит иначе. Количество черных клеток вычисляется по формуле: (n+1)/2, где n — общее число полей шахматной доски (25+1)/2=13 — верно!!!)

Если применим данную формулу для досок 3х3 или 5х3 — ответ будет верным.

Программа на Паскале будет выглядеть следующим образом:

var n, m, result: longint;
begin
readln(n);
readln(m);
if n*m mod 2 =0 then result:=n*m div 2 else
result := (n*m+1) div 2;
writeln(result);
end.

(Оператор div используется из-за того, что в данном шаблоне, в условии задачи, все переменные имеют целочисленный тип. Если div заменить на обычное деление, то переменную result нужно объявлять как real).

---

Задача №2. Манхеттен.

Кварталы Манхэттена состоят из авеню, направленных с юга на север и улиц, направленных с запада на восток. Все улицы и авеню пронумерованы числами, начиная с 1
подряд (первая улица, вторая улица, третья улица и т. д.). Передвигаться можно только по улицами или по авеню.

Миша впервые попал на Манхэттен. Сейчас он стоит на пересечении авеню номер x1 и улицы номер y1. Ему нужно попасть на перекресток авеню номер x2 и улицы номер y2.
Определите маршрут, который он должен пройти. Программа получает на вход 4 числа: x1, y1, x2, y2, записанных в отдельных строках. Все числа — натуральные, не превышают 103. Начальное и конечное расположение Миши не совпадают.
Программа должна вывести последовательность из латинских заглавных букв, описывающих маршрут, которому должен следовать Миша. Буква «N» обозначает перемещение на один квартал на север, «S» — на юг, «W» — на запад, «E» — на восток. Программа должна вывести самый короткий из всех возможных маршрутов, если же кратчайших маршрутов существует несколько, то программа должна вывести любой из них (но только один).
Программа может выводить последовательность ходов не в одну строку (как в примере), а каждый символ ответа — в отдельной строке (например, если каждый символ
ответа выводится при помощи отдельной команды вывода внутри цикла).

Решение.

Представим систему улиц и авеню в виде системы координат, где перекрестки — это точки с соответствующими координатами (пересечение второго авеню и первой улицы — точка с координатами (2;1); пересечение четвертого авеню и третей улицы — точка с координатами (4;3) и т.д.)

Чтобы добраться от перекрестка второй авеню и четвертой улицы (точка А) до перекрестка шестой авеню и первой улицы (точка В) нужно пройти вправо на x2 — x1 = dx (6-2 = 4) и вниз на y2 — y1 = dy (4 — 1 = 3). Если бы точка В была на месте точки А, а точка А на месте точки В, то пришлось бы двигаться влево на dx и вверх на dy. Т.е. от взаимного расположения этих точек (А и В) зависит направление движения.

Напишем программу на языке Паскаль:

var x1,y1,x2,y2,dx,dy,i:integer;
begin
readln(x1,y1,x2,y2);
dx:=abs(x1-x2); // расстояние по оси x
dy:=abs(y1-y2);  // расстояние по оси y

if x2>x1 then  // если точка В правее точки А, то ...
             for i:=1 to dx do write('E') else for i:=1 to dx do write('W');
if y1>y2 then  // если точка А выше точки В, то ...
             for i:=1 to dy do write('S') else for i:=1 to dy do write('N');
end.

Остальные задачи несколько сложнее. В ближайшее время будет разбор. Следите за обновлениями, подписывайтесь!