Информатика (7-9 класс)

Информатика (7-9 класс)

1. Зарплата (10 баллов)

В отделе работают N сотрудников, которые получают заработную плату в рублях. Требуется определить: на сколько рублей зарплата самого высокооплачиваемого сотрудника отличается от самого низкооплачиваемого.

Входные данные В первой строке входного файла input. txt указано N - число сотрудников, в следующих строках записаны размеры зарплат всех сотрудников. Каждая заработная плата – это натуральное число.

Выходные данные В выходной файл output. txt необходимо вывести одно целое число — разницу между максимальной и минимальной зарплатой.

ТЕСТЫ

№	input. txt	output. txt
1	3 1000 5000 10000	9000
2	6 12500 5000 4500 12000 4000 6500	8500

Указания к решению

В этой задаче необходимо найти наибольше и наименьшее значения и вывести их разность.

Для этого можно упорядочить входной массив А (зарплаты сотрудников) по возрастанию, например, методом «пузырька» и вычислить разность аN – а1. Но это не самое оптимальное решение.

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

Разбалловка:

При N =2 ® 2 балла

При N =3 (тест 1) ® 4 балла

При N =6 (тест 2) ® 7 баллов

При больших N (N>50) - 10 баллов

2. В автобусе (10 баллов)

Цена проезда в автобусах нашего города — 16 рублей. Однако каждый взрослый пассажир имеет право провезти бесплатно не более одного ребенка, а для остальных детей необходимо купить билет на каждого. Отметим, что дети не могут проезжать в автобусе без сопровождения взрослых.

Помогите посчитать минимальную и максимальную стоимость проезда в рублях, которую могли заплатить пассажиры автобуса.

Входные данные В единственной строке входного файла input. txt записаны два целых числа n и m (0 ≤ n, m ≤ 100) — количество взрослых и количество детей в автобусе, соответственно.

Выходные данные В единственную строку выходного файла output. txt нужно вывести:

- если в автобусе могли ехать n взрослых и m детей, то через пробел два числа — минимальную и максимальную возможную стоимость проезда этих людей, соответственно;

- в противном случае выведите «Невозможно» (без кавычек).

ТЕСТЫ

№	input. txt	output. txt
1	1 2	2 2
2	2 2	2 3
3	0 5	Невозможно
4	5 6	6 10

Указания к решению

Необходимо рассмотреть все возможные случаи.

a)  если никто не ехал в автобусе, то соответствующие значения равны нулю.

b)  невозможен проезд детей без взрослых.

c)  если детей в автобусе нет, каждый взрослый оплачивает проезд.

d)  в остальных случаях максимальная стоимость будет тогда, когда всех детей везет один взрослый. Минимальная стоимость определяется по разному в двух случаях: если детей не больше взрослых, то за них платить не надо (каждый взрослый везет не более одного ребенка); в противном случае (детей больше взрослых) придется платить за n взрослых и m-n детей, т. е. всего за n+(m-n) = m билетов.

Разбалловка:

Тест 1 ® 3 балла.

Тест 1+2 ® 5 баллов

Тест 1+2+3 ® 8 баллов.

Тест 1+2+3+4 ® 10 баллов

3. Ферзь, ладья и конь (10 баллов)

На шахматной доске 8х8 расположены три фигуры: ферзь, ладья и конь. Требуется определить количество пустых полей доски, которые находятся под боем. Для простоты будем полагать, что фигуры могут «бить» через другие фигуры. Например, в рассмотренной на рисунке ситуации будем считать, что ферзь бьет клетки D4, D5, D6, D7 и D8 через ладью.

Входные данные

В единственной строке входного файла input. txt записаны через пробел координаты расположения трех фигур: ферзя, ладьи и коня соответственно. Каждая координата состоит из одного латинского символа и одной цифры.

Выходные данные

В выходной файл output. txt нужно вывести количество пустых полей, которые бьют указанные фигуры.

Пример

№	input. txt	output. txt
1	D1 D3 E5	29
2	H8 A2 D5	37
3	A1 A2 B2	27
4	D3 D3 E5	Невозможно

Указания к решению

Для решения данной задачи необходимо определить бьет ли данная фигура, находящаяся в клетке (х1,у1) клетку (х2,у2)? Отметим, что нас интересуют только пустые клетки. Задача упрощается тем условием, что фигуры могут «бить» через другие фигуры, т. е. мы пренебрегаем другими фигурами.

Для ладьи это условие проще всего: х1=х2 или у1=у2 (клетки либо по вертикали, либо по горизонтали).

Для ферзя к этому условию добавляется условие перемещения по диагонали, т. е. ½х1-х2½= ½у1-у2½.

Для коня это условие более сложно. Конечно, можно проверить все восемь возможных варианта хода, но такая запись слишком громоздка. Проще, если догадаться, проверить условие ½(х1-х2)*(у1-у2)½= 2.

Наиболее простой вариант решения задачи заключается в переборе всех клеток шахматной доски и проверке их достижимости одной из имеющихся фигур. Это позволит избежать повторения тех клеток, которые бьются сразу несколькими фигурами.

Разбалловка:

Считаются клетки для ладьи ® 2 балла.

Считаются клетки для ладьи и ферзя® 5 баллов

Считаются клетки для всех возможных вариантов ® 8 баллов.

Считаются клетки для всех возможных вариантов + учет невозможной позиции® 10 баллов

4. Зайчик (100 баллов)

Зайчику в клетке поставили лесенку. Лестница имеет определенное количество ступенек N. Заяц может одним прыжком преодолеть не более К ступенек. Для разнообразия зайчик пытается каждый раз найти новый путь к вершине лестницы. Сколько различных способов есть у зайца добраться до вершины лестницы при заданных значениях K и N.

Например, если N=4 и K=3, то существуют следующие маршруты: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1. Т. е. при данных значениях у зайца всего 7 различных вариантов добраться до вершины

Входные данные

В единственной строке входного файла input. txt записаны два натуральных числа N и K (1 ≤ K ≤ N ≤ 300), где N – общее число ступенек лестницы, К - максимальное количество ступенек, которое может преодолеть заяц одним прыжком.

Выходные данные

В единственную строку выходного файла output. txt нужно вывести количество возможных вариантов различных маршрутов зайца на верхнюю ступеньку лестницы.

ТЕСТЫ

№	input. txt	output. txt
1	3 1	1
2	7 2	21
3	10 3	274

Указания к решению

Обозначим f(x) - количество способов запрыгнуть на ступеньку.

Тогда при K=3 и N=4 имеем:

f(1) = 1 - прыгнул на ступеньку

f(2) = 1 + f(1) = 2 - прыгнул или сразу, или с первой.

f(3) = 1 + f(1) + f(2) = 4 - прыгнул или сразу, или с первой, или со второй.

f(4) = f(1) + f(2) + f(3) = 7 - сразу нельзя, прыгнул или с первой, или со второй, или с третьей......

…..

f(n) = f(n - k) + ... + f(n - 1).

Разбалловка:

Тест 1 ® 2 балла.

Тест 1 + 2 ® 4 балла.

Тест 1 + 2 + 3® 10 баллов.