Алгоритм решения задания № 4 (скорая помощь) для отбора в летнюю школу стажировку от Яндекса

Задания № 4 школу стажировку от Яндекса

Один из алгоритмов для решения задания № 4 для отбора в летнюю школу стажировку от Яндекса. Условия задания можно просмотреть здесь.

Задача из списка олимпиадных. Ее условие и решение можно найти, например, в «Московские олимпиады по информатике» / Под ред. Е. В. Андреевой, В. М. Гуровица и В. .а. Матюхина. – М.: МЦНМО, 206. – 206 256 с.: ил. ISBN 5-94057-233-2

Алгоритм прост. Делается перебор всех возможных количеств квартиры на этаже, при этом для конкретного числа квартир вычисляется номер квартиры для заданного P2 и N2. Если не было совпадений с K2, то данные противоречивы. Если было одно совпадение вычисляем номер подъезда для первой квартиры. Если было больше одного совпадения, то определить однозначно нельзя.

A div b – остаток от деления A на b

A mod b – целая часть от деления A на b

Алгоритм можно записать так

Вход: K1, K2, M, P2, N2

Выход: P1, N1

Данные: X – количество квартир на этаже, A – .количество квартир на этаже переменная от 1 до 1000, P – вычисленный номер подъезда для конкурентного A, N – вычисленный номер этажа для конкретного А.

Алгоритм.

проверяем введенные данные на элементарную согласованность

Если M = 0, то данные противоречивы выводим -1 -1, выход из программы

Если N2 = 0, то данные противоречивы выводим -1 -1, выход из программы

Если K1 = 0, то данные противоречивы выводим -1 -1, выход из программы

Если K2 = 0, то данные противоречивы выводим -1 -1, выход из программы

Если P2 = 0, то данные противоречивы выводим -1 -1, выход из программы

Если M*P2 > K2, то данные противоречивы выводим -1 -1, выход из программы

Если N2 >M, то данные противоречивы выводим -1 -1, выход из программы

Начинаем вычислять количество квартир на этаже

A:= 1;

P1:= -1;

N1:= -1;

While A<= 1000 do

Begin

P := (K2 – 1) div (M*A) +1;

N := ((K2 – 1) mod (M*A) ) div A + 1;

If  P = P2 and N = N2 then

If  P1 <> -1 and N <> -1 then данные не позволяют однозначно решение выводим 0 0 и

выходим из программы;

    else begin

P1 := (K1 – 1) div (M*A) +1;

N1 := ((K1 – 1) mod (M*A) ) div A + 1;

    end;

A:= A+1;

End;

Выводи P1 и N1;

Share

Tags: , ,

Leave a Reply