Задания и решения1-го тура Netoi-2009 icon

Задания и решения1-го тура Netoi-2009




Скачати 312.04 Kb.
НазваЗадания и решения1-го тура Netoi-2009
Дата конвертації29.11.2012
Розмір312.04 Kb.
ТипЗадача
1. /Семинар_16_11_2010/Винница2009/Solution_1.docx
2. /Семинар_16_11_2010/Сайты подготовки.docx
3. /Семинар_16_11_2010/Ярославль2009/Теоретическая часть.doc
4. /Семинар_16_11_2010/Ярославль2009/Условие.doc
Задания и решения1-го тура Netoi-2009
Олимпиады по программированию, г. Москва Олимпиады в области точных наук, г. Санкт-Петербург Олимпиады по информатике, г. Санкт-Петербург
2. Обмануть обманщика
2009 г. Теоретическая часть

Задания и решения1-го тура NetOI-2009

Решения можно присылать на проверку до 0 часов 28 ноября 2009 года. Работает проверка задач на авторских тестах в  режиме on-line.

Задача Newillusion

Герой задачи 1 тура NetOI-2000 Illusion, цирковой фокусник, выходит на арену с новым номером. Он просит зрителей назвать двузначное число n, а далее просит их же указать количество К преобразований этого числа, поясняя зрителям, что преобразованием двузначного числа n он называет  двузначное число, образованное из первых двух цифр числа n2.(Например, преобразованием числа 30 будет 90, а 7556). При этом он мгновенно называет число, которое получается из n после К преобразований.  Напишите программу, делающую то же самое.


Технические условия. Программа читает с клавиатуры числа n (10<=n<=99) и К (1<=K<=1000000000), разделенные пробелом. Программа выводит на экран полученное число.
Пример
Ввод
21 5
Вывод
14



Задача Tangent

Как известно, касательной к окружности является прямая, которая имеет ровно одну общую точку с этой окружностью. Возможна ситуация, когда одна и та же прямая является касательной сразу к двум окружностям. Тогда она называется общей касательной. Напишите программу, которая будет находить количество разных общих касательных для заданных двух окружностей. При выводе учтите древнюю традицию приписывать числу 7 значение «много». То есть, когда количество общих касательных будет строго большим 6, независимо от истинного количества выводите 7.


Технические условия. Программа читает с клавиатуры шесть целых чисел (каждое не больше по модулю миллиона) через пробел X1,Y1,R1,X2,Y2,R2 - соответственно координаты центра и радиусы 1-го и 2-го круга. Программа выводит на экран искомое число (с учетом упомянутой древней традиции).
Пример
Ввод 20 0 4 50 0 10
Вывод 4



Задача Lazer

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


Технические условия.
Программа читает с клавиатуры количество шариков n (1<=n<=1000), затем два целых числа dx, dy, не равных одновременно нулю (-1000<=dx,dy<=1000) – координаты точки, через которую пройдет луч лазера. Далее программа читает n троек целых чисел, не превосходящих 1000 по модулю. Каждая тройка – координаты центра и радиус очередного шарика (всегда положительное число). Вася находится в начале координат. Никакие два  шарика не имеют общих точек, а Вася не находится внутри шарика. Программа выводит на экран количество пробитых лучом лазера шариков. Если луч касается шарика, такой шарик не считается пробитым.

Пример

Ввод
4 4 3 -4 -4 2 2 1 1 1 7 5 12 9 3
Вывод
2
 



Задача Radars

Есть n городов, расположенных на прямой. Телекомпания хочет разместить 3 радара в трех городах для вещания. Однако компания хочет получить максимальную мощность такой системы. Если радары расположены в городах с координатами x1, то мощность будет равна (x3-x2)*(x2-x1), т.е.  произведению расстояний. Необходимо найти наибольшую возможную мощность вещания.


Технические условия.Программа читает с клавиатуры число n (3<=n<=100000) - количество городов, затем n чисел,не превосходящих 1000000 по абсолютной величине – координаты города. Программа выводит на экран искомое число.
Пример
Ввод
5 3 1 5 2 4
Вывод
4

(Замечание. Не следует особо задумываться над физической терминологией - у телевизионщиков свое видение мира...)


Задача Lotto

Компания Megasoft организовала телевикторину. На табло появляется натуральное число. Участник должен дописать к нему справа несколько цифр (обязательно хотя бы одну) так,чтобы получилось простое число и прислать SMS с полученным числом в студию. Участник, приславший свое число первым, эту сумму и выигрывает. Владелец компании Megasoft Гилл Бейтс известен своей жадностью и не хочет платить лишние деньги. Поэтому он решил негласно изменить правила. Теперь выигрыш получит тот участник викторины, который первым пришлет наименьшее возможное  число. Помогите Г.Бейтсу определить сумму выигрыша согласно новым правилам.

Технические условия.
Программа читает с клавиатуры натуральное число, не большее 1000000. Программа выводит на экран минимальное число, которое можно получить по новим правилам викторины,то есть сумму, с которой Г.Бейтс вынужден распрощаться.
Примеры
Ввод
12
Вывод
127
Ввод
41
Вывод
419


Задача Newillusion

Самое первое решение, которое напрашивается (без анализа данных) – поставить цикл от 1 до К, в цикле выполнять преобразования фокусника: возводить n в квадрат и оставлять только две первые цифры числа. После цикла получаем искомое число.

For i:=1 to n do

Begin

n:=n*n;

case n of

100..961: n:= n div 10;

1024..9801: n:= n div 100;

end;

write(n,' ');

Такое решение было бы возможно только при малых К. При больших К решение получается с большой задержкой и не является удачным.

Сделаем анализ возможных преобразований:

10 : 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 (получение 10 в преобразовании далее дает только 10)

11 : 12 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36 (подчеркнутый интервал повторяется)

12 : 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36 12 (появление любого числа из подчеркнутого интервала вызывает повтор интервала )

13 : 16 25 62 38 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36 12 (с началом в этот числе)

14 : 19 36 12 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36 12 14

15 : 22 48 23 52 27 72 51 26 67 44 19 36 12 14 19 36 12 14 19 36

16 : 25 62 38 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36 12 14

17 : 28 78 60 36 12 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36

18 : 32 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10

19 : 36 12 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36 12 14 19

20 : 40 16 25 62 38 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36

21 : 44 19 36 12 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36 12

22 : 48 23 52 27 72 51 26 67 44 19 36 12 14 19 36 12 14 19 36 12

23 : 52 27 72 51 26 67 44 19 36 12 14 19 36 12 14 19 36 12 14 19

24 : 57 32 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10

25 : 62 38 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36 12 14 19

26 : 67 44 19 36 12 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36

27 : 72 51 26 67 44 19 36 12 14 19 36 12 14 19 36 12 14 19 36 12

28 : 78 60 36 12 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36 12

29 : 84 70 49 24 57 32 10 10 10 10 10 10 10 10 10 10 10 10 10 10

30 : 90 81 65 42 17 28 78 60 36 12 14 19 36 12 14 19 36 12 14 19

31 : 96 92 84 70 49 24 57 32 10 10 10 10 10 10 10 10 10 10 10 10

32 : 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10

33 : 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10

34 : 11 12 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36 12 14 19

35 : 12 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36

36 : 12 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36

37 : 13 16 25 62 38 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36

38 : 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36 12

39 : 15 22 48 23 52 27 72 51 26 67 44 19 36 12 14 19 36 12 14 19

40 : 16 25 62 38 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36 12

41 : 16 25 62 38 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36 12

42 : 17 28 78 60 36 12 14 19 36 12 14 19 36 12 14 19 36 12 14 19

43 : 18 32 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10

44 : 19 36 12 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36 12 14

45 : 20 40 16 25 62 38 14 19 36 12 14 19 36 12 14 19 36 12 14 19

46 : 21 44 19 36 12 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36

47 : 22 48 23 52 27 72 51 26 67 44 19 36 12 14 19 36 12 14 19 36

48 : 23 52 27 72 51 26 67 44 19 36 12 14 19 36 12 14 19 36 12 14

49 : 24 57 32 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10

50 : 25 62 38 14 19 36 12 14 19 36 12 14 19 36 12 14 19 36 12 14

При этом появление первой 10 или любого числа из 14, 19, 36, 12 встречается в первом или втором десятке преобразований, или на первом преобразовании. Достаточно выполнить преобразования фокусника до получения одного из пяти вышеперечисленных чисел. Далее, если встретилась 10, то это и будет ответ, если встретилось число из интервала 14, 19, 36, 12, то отбросить из количества преобразований полное количество (т.е. по 4) вхождения интервалов, оставшееся количество преобразований посчитать по интервалу с учетом первого встретившегося числа в преобразованиях. Интервал можно считать зацикленным, т.е. если первое, встреченное при преобразованиях число 19, то интервал будет иметь вид: 19, 36, 12, 14.

const num=[14,19,36,12]; {Множество, хранящее интервал для сравнения полученных чисел}

Anum:array[0..3] of integer=(14,19,36,12);{массив, хранящий интервал повторяющихся чисел}

var n:integer; {исходное двузначное число}

k:longint; {количество преобразований}

i:longint; {индекс для подсета количества преобразований}

begin

readln(n,k); {ввод исходных данных}

i:=0; {начальное значение количества полученных преобразований}

repeat {в цикле выполняются начальные преобразования фокусника до получения одного из чисел: 10, 14, 19, 36,12}

i:=i+1; {номер нового преобразования}

n:=n*n; {возведение в квадрат текущего изменяемого числа}

case n of {оставляются первые две цифры из полученного квадрата}

100..961: n:= n div 10; {если полученный квадрат – 3-значное число, то отбрасываем одну цифру}

1024..9801: n:= n div 100; {если полученный квадрат – 4значное число, то отбрасываем две цифры}

end;

until (i=k)or(n=10)or(n in num);{выходим из цикла: если выполнены все преобразования, если появилась 10, если появилось число из множества}

if (i{если выполненное количество преобразований не достигло К и последнее число входит в множество}


begin

i:=(k-i) mod 4; {результатом будет число из множества: вычисляем номер числа из неполного вхождение интервала, на котором остановимся на К-ом преобразовании}

case n of {корректируем номер в связи с тем, какое число встретилось первым, т.е. с какого числа повторяющийся интервал должен начинаться}

19: i:=i+1;

36: i:=i+2;

12: i:=i+3;

end;

if i>3 then i:=i-4; {если полученный номер превысил максимальный индекс массива, то корректируем его}

writeln(Anum[i]); {выводим соответствующий элемент массива, последнее преобразование}

end

else writeln(n); {если из цикла мы вышли по первым двум условиям, то сразу имеем ответ}

end.


Задача Tangent

Для решения задачи необходимо рассмотреть возможные взаимные расположения окружностей и получающиеся в каждом случае секущие:


взаимное расположение окружностей copy.jpg


d – расстояние между центрами.

Вариант а) касательные отсутствуют;

Вариант б) при совпадении центров и радиусов количество касательных бесконечно, т.е равно 7;

Вариант в) касательные отсутствуют;

Вариант г) единственная касательная;

Вариант д) две касательных;

Вариант е) три касательных;

Вариант ж) четыре касательных.

Остается проверить величины d, R, r, на соответствующие условия, с учетом того, что действительные числа не сравниваются на равенство одно другому. Необходимо ввести константу точности вычисления: е=0.001. При необходимости сравнить два действительных числа на равенство, нужно модуль их разности сравнить с константой е. Если число меньше е, то считается, что числа при разности дали 0, т.е. равны.

Const e=0.001;

var x1,y1,r1,x2,y2,r2:longint; {Координаты и радиус первой и второй окруджности}

kol:integer; {Количество секущих}

v:longint; {вспомогательная переменная}

d:real; {расстояние между центрами радиусов}

begin

read(x1,y1,r1,x2,y2,r2); {считываем координаты центра и радиус первой и второй окружностей}

if r1>r2 then {Для облегчения вычисления необходимо, чтобы радиус первой окружности был меньшим. Если это не так, то}

begin v:=x1; x1:=x2; x2:=v; {меняем координаты центров и радиусов наоборот}

v:=y1; y1:=y2; y2:=v;

v:=r1; r1:=r2; r2:=v;

end;

if (x1=x2)and(y1=y2) then {Если центры окружностей совпадают, то}

begin

if r1<>r2 then kol:=0 {если радиусы не совпадают, то секущих нет (рис. а)}

else kol:=7; { если радиусы совпадают, то секущих бесконечное множество (рис. б)}

end

else {если радиусы не совпадают, то}

begin

d:=sqrt(sqr(x1-x2)+sqr(y1-y2)); {вычисляем расстояние между центрами окружностей}

if d{если расстояние меньше разницы радиусов, то секущих нет (рис. в)}

if abs(d-(r2-r1))<=e then kol:=1 {если расстояние равно разнице радиусов, то секущая одна (рис. г)}

if (d>r2-r1)and(d{рис. д) - две секущих}

if abs(d-(r2+r1))<=e then kol:=3; {сли расстояние равно сумме радиусов, то секущих три (рис. е)}

if d>r2+r1 then kol:=4; {сли расстояние больше суммы радиусов, то секущих четыре (рис. ж)}

end;

write(kol); {вывод количества секущих}

end.


Задача Lazer

В начале формируем прямую, проходящую через центр координатной плоскости и точку (dx, dy). Удобнее использовать уравнение прямой с угловым коэффициентом: . Уравнение окружности используем стандартное: , где (x0, y0) – координаты центра окружности и R0 – радиус окружности. Необходимо значение величины y из первого уравнения подставить во второе уравнение и раскрыть скобки. Сгруппировать данные относительно х2 и х, получив квадратное уравнение с коэффициентами; ; ; . Так как b – четное, то вычисляем b/2. Тогда дискриминант будет вычисляться: . Если D>0, то прямая пересекает окружность, а не касается ее. Этот вариант нам и нужен. Корни уравнения вычисляются: , значения y1;2 находятся по формуле уравнения прямой. К такому расчету относится и уравнение прямой, когда dy=0. (ось абсцисс – исходная прямая).

Если уравнение прямой совпадает с осью ординат (dx=0), то поворачиваем всю картинку на 900 и зеркально отображаем: меняем значения dx и dy, а, в дальнейшем, все x0 и y0. После этого можно применять для данных выше описанный алгоритм.

Так как пистолет стреляет в одну сторону, то для полного решения нам необходимо выбрать пересечения окружностей и луча в направлении выстрела. Для этого после нахождения окружности, пересеченной прямой выстрела (D>0), находим одну из точек пересечения (одной достаточно) и проверяем синус угла, образованного лучом ( (0,0) – (x1,y1) ) и осью абсцисс и синус угла, образованного лучом ( (0,0) – (dx,dy) ) и осью абсцисс на совпадение знака (их произведение должно быть больше 0). Если точки лежат на оси Х, то синусы равны 0 (любой из них) проверяем, чтобы координата dx и х1 лежали в одной полуплоскости.

Проверить пересечение луча и окружности можно еще таким способом: лежат ли точка (dx, dy) и (x1, y1) в одной четверти координатной плоскости: .

В приведенной программе реализован первый способ проверки пересечения окружности и луча.

var n:integer; {количество шаров}

dx,dy:integer; {координаты точки, через которую проходит выстрел}

x,y,r:integer; {координаты проверяемого шара}

kol:integer; {количество сбитых шаров}

i, {индекс для перебора всех шаров}

vs:integer; {вспомогательная переменная}

a,b,c, {коэффициенты квадратного уравнения}

d, {дискриминант квадратного уравнения}

xp,yp, {корень квадратного уравнения}

vd:real; {синус угла прямой, определяющей направление луча лазера}

f:boolean; {признак того, что dx=0 и необходимо поворачивать все объекты}

begin

read(n,dx,dy); {ввод количества шаров и координаты точки, через которую проходит луч лазера}

kol:=0; {начальное количество сбитых шаров}

f:=false; {поворота делать не надо}

if dx=0 then {если выстрел вертикальный, то}

begin vs:=dx; dx:=dy; dy:=vs; f:=true; end; {поворачиваем угол стрельбы на 900 и включаем признак поворота для шаров}

vd:= dy/sqrt(dx*dx+dy*dy)); {вычисляем синус угла прямой, определяющей направление луча лазера}

for i:=1 to n do {начинаем цикл ввода данных о шарах и проверке: сбиты ли они?}

begin

read(x,y,r); {ввод координат центра и радиуса текущего шара}

if f then begin vs:=x; x:=y; y:=vs; end; {если включен признак поворота, то меняем координаты местами}

a:=1+sqr(dy/dx); {вычисляем коэффициент а квадратного уравнения}

b:=-(x+dy*y/dx); { вычисляем коэффициент b квадратного уравнения }

c:=x*x+y*y-r*r; { вычисляем коэффициент c квадратного уравнения }

d:=(b*b-a*c); { вычисляем дискриминант квадратного уравнения }

if (d>0) then {если прямая пересекает шар, то}

begin

xp:=(-b-sqrt(d))/a; {находим одну точку пересечения, координата х}

yp:=dy*xp/dx; {координата у}

d:=(vd*(yp/sqrt(xp*xp+yp*yp)); {произведение синусов луча лазера и через полученную точку}

if (d>0)or((d=0)and(x*dx>=0)) then kol:=kol+1; {если знак совпадает или равен нулю, но абсциссы лежат }

end;

end;

write(kol); {вывод количества сбитых шаров}

end.


Задача Radars

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

xr:=0;

for x3:=n downto 3 do

for x2:=x3-1 downto 2 do

for x1:=x2-1 downto 1 do

begin

v:=(x3-x2)*(x2-x1);

if v>xr then xr:=v

end;

Для более быстрого решения необходимо отсортировать массив входных данных. Первый радар поставить в первый город, чтобы меньшее число вычиталось из х2 при расчете мощности. Третий радар поставить в последний город, чтобы из большего числа вычиталось х2 при расчете мощности. Для нахождения второго города необходимо перебирать все города с предпоследнего ко второму и проверять получившиеся мощности. Сперва такие мощности будут увеличиваться, затем могут оказаться одинаковые, а потом будут уменьшаться. При нахождении первой мощности, меньшей предыдущей, необходимо остановиться и принять за второй радар номер предыдущего, проверенного города.

var n:longint; {количество городов}

t:array[1..100000] of longint; {координаты городов}

x1,x2,x3, {х1, х3 – координаты первого и третьего городов, в которых расположены радар, х2 – номер второго города}

xr, {максимальная мощность телесистемы}

v:longint; {вспомогательная переменная}

procedure QSort(a,b:longint); {процедура быстрой рекурсивной сортировки, a, b – интервал массива для текущей сортировки}

var x,tt,k,m,vs:longint; {локальные переменные}

begin

tt:=(a+b) div 2; {вычисляем номер элемента, относительно которого выполняется сортировка}

x:=t[tt]; {запоминаем элемент, относительно которого выполняется сортировка }

k:=a-1; {начальное значение индекса для элементов, меньших х}

m:=b+1; { начальное значение индекса для элементов, больших х }

tt:=a; {индекс, бегущий по массиву в интервале от а до b, по нему выбираются элементы массива для сравнения с х}

while tt{цикл движения по массиву в интервале от а до b}

begin

if t[tt]>x then {если найденное число больше х}

begin

m:=m-1; {изменяем индекс, отвечающий за элементы, большие х}

vs:=t[tt]; t[tt]:=t[m]; t[m]:=vs; {меняем числа, стоящие по индексам tt и m}

end

else if t[tt]{ если найденное число меньше х }

begin k:=k+1; { изменяем индекс, отвечающий за элементы, меньшие х }

vs:=t[tt]; t[tt]:=t[k]; t[k]:=vs; {меняем числа, стоящие по индексам tt и k}

tt:=tt+1 {изменяем индекс движения по массиву}

end

else tt:=tt+1; { изменяем индекс движения по массиву }

end;

if k>a then QSort(a,k); {если нашлись элементы, меньшие х, то выполняем дальнейшую перестановку данных в этом интервале}

if m{ если нашлись элементы, большие х, то выполняем дальнейшую перестановку данных в этом интервале }

end; {конец процедуры сортировки}

begin {начало главной программы}

read(n); {ввод количества городов}

for x1:=1 to n do {организовываем цикл для ввода координат городов}

read(t[x1]); {ввод координат городов}

QSort(1,n); {вызов сортировки массива координат городов}

xr:=0; {начальное значение максимальной мощности системы}

x1:=t[1]; x3:=t[n]; {формируем координаты первого и третьего города, в которых будут расположены радары}

x2:=n; {начальное значение индекса координаты второго города}

repeat {открываем цикл поиска максимальной мощности системы}

x2:=x2-1; {изменяем индекс для координаты второго города}

v:=(x3-t[x2])*(t[x2]-x1); {расчет текущей мощности системы}

if v>xr then xr:=v; {текущая мощность больше максимальной на данный момент, то запоминаем ее}

until (v{выходим из цикла, если текущая мощность стала меньше максимальной или индекс второго города равен 2}

write(xr); {вывод найденной максимальной мощности телесистемы}

end.


Задача Lotto

Так как цифру к числу добавлять нужно обязательно, то проверять исходное число на простоту нет необходимости.

Какие цифры нельзя добавлять к числу: 0, 2, 4, 5, 6, 8. Так как они являются признаками деления числа на 2, 5, 10, что исключает изначально получение простого числа. Поэтому для добавления к исходному числу остаются цифры 1, 3, 7, 9.

* Большинство результатов можно получить добавлением одной цифры к числу. Для этого достаточно доклеивать последовательно каждую цифру, начиная с 1, и полученное число проверять на простоту. Если простое число получилось при добавлении одной из цифр, то далее проверять подстановки цифр нет необходимости. Начиная подстановки с 1, мы обеспечиваем себе поиск заранее минимального простого числа.

** Если после добавления одной цифры (последовательно 1, 3, 7, 9) полученное число не стало простым, необходимо к исходному числу добавлять сперва 0 (промежуточные цифры могут быть любые) и повторять алгоритм со *. Если не получили простое число, то заменяем 0 на 1 (и т.д. до 9), и повторяем алгоритм со *.

Если опять не получили простого числа, то к исходному числу доклеиваем 0 и выполняем алгоритм с **. Если результат не достигнут, то вместо нуля подставляем 1 (и т. д. до 9), и повторяем алгоритм с **.

Промежуточных цифр может быть несколько. Для формирования промежуточных цифр удобно ввести вспомогательный одномерный массив. Если промежуточная цифра одна, то реальный размер массива равен 1. Элементами массива будут последовательно цифры от 0 до 9, они будут добавляться к исходному числу, а к полученному числу будет выполняться алгоритм со *.

Если промежуточных цифр две, то реальный размер массива будет равен 2 (три – три и т.д.).

*** Формирование промежуточного двузначного числа будет начинаться с 00. Далее увеличивается только последняя цифра: 01, 02, …, 09. Когда цифра не может увеличиваться, сбрасываем ее в 0, сдвигаем указатель по массиву влево на единицу и, если указанное число не достигло 9, то увеличиваем его на единицу: 10, 20, …, 90. Если указанная цифра уже равна 9, то обнуляем ее и сдвигаем указатель еще влево, и повторяем действия. К полученному числу применяем алгоритм *.

Если перебраны все варианты промежуточных чисел на выбранном варианте: от 00 до 99, а простое число не получилось, то увеличиваем размерность массива на одну цифру и повторяем алгоритм ***, только для большего количества цифр.

var v:longint; {исходное число}

n:longint; {полученное минимальное простое число}

l, {промежуточная переменная для формирования минимального простого числа}

d, {реальный размер массива промежуточных цифр (а)}

i, {индекс массива промежуточных цифр}

g,j:longint; {вспомогательные переменные}

a:array[1..5] of integer; {массив для промежуточных цифр}

function Prost(k:longint):boolean; {функция проверяет число k на простоту: true – простое, false – не простое}

var i:longint; {индекс по возможным делителям}

f:boolean; {признак простоты}

begin

i:=2; {начальный делитель}

f:=true; {предполагаем, что число k - простое}

while (i<=sqrt(k))and(f) do {цикл перебора возможных делителей числа k}

begin

if k mod i=0 then f:=false; {если делитель найден, то устанавливаем признак в false}

i:=i+1; {выбор следующего делителя}

end;

Prost:=f; {имени функции присваиваем полученное значение признака}

end;

procedure Podbor(num:longint;var numr:longint); {процедура получает исходное число num, добавляет к нему последовательно одну из четырех возможных цифр и запускает функцию проверки простоты Prost. Если число оказалось простым, то numr присваивается результат. Если простое число не получается ни с одной из цифр, то numr получает значение 0}

begin

num:=num*10; {умножая число на 10 сдвигаем все цифры на разряд влево, повышая разряд и делая разряд единиц пустым для добавления цифры}

if Prost(num+1) then numr:=num+1 {в разряд единиц добавляем 1 и проверяем число на простоту, если оно простое, то формируем numr}

else begin if Prost(num+3) then numr:=num+3 {аналогичная проверка с цифрой 3 в разряде единиц}

else begin if Prost(num+7) then numr:=num+7 { аналогичная проверка с цифрой 7 в разряде единиц }

else begin if Prost(num+9) then numr:=num+9 { аналогичная проверка с цифрой 9 в разряде единиц }

else numr:=0; {если предыдущие проверки не дали простое число, numr возвращает 0}

end;

end;

end;

end;

begin {начало главной программы}

read(v); {ввод исходного числа}

l:=v; {дублирование исходного числа}

Podbor(l,n); {вызов процедуры подстановки к числу последней цифры и проверки полученного числа на простоту}

if n=0 then begin {если число не было найдено, то}

d:=1; {размер массива промежуточных цифр увеличиваем до одного числа}

repeat {цикл позволяет перебирать все промежуточные цифры, увеличивать их количество , формировать новое число и запускать процедуру Podbor}

i:=d; {формируем индекс по массиву а, начиная с последней цифры (разряд единиц), так как она изменяется в первую очередь}

j:=0; {индекс перебирает все возможные цифры для подстановки промежуточными цифрами}

while(j<=9)and(n=0) do {цикл формирует цифры массива а, позволяя сформировать новое искомое число}

begin

a[i]:=j; {формируем новую цифру массива а}

j:=j+1; {увеличиваем индекс по возможным промежуточным цифрам}

g:=1; {начальное значение индекса по массиву а для сборки искомого числа}

l:=v; { дублирование исходного числа }

while g<=d do begin l:=l*10+a[g]; g:=g+1; end; {в переменной l собирается новое число: исходное + все промежуточные}

Podbor(l,n); {вызов процедуры Podbor для полученного числа}

end;

if j>9 then begin {если все цифры массива а (разряд единиц) от 0 до 9 перебраны, а простое число не получено, то}

while (i>=1)and(a[i]=9) do {по массиву а все стоящие подряд промежуточные цифры, равные 9, обнуляем}

begin

a[i]:=0; { сбрасываем значение текущей цифры в 0}

i:=i-1; {выбираем предыдущую цифру из массива а}

end;

if i=0 then d:=d+1 {если обнулены все цифры, то перебраны все варианты (от 0 до 9, от 00 до 99), увеличиваем количество промежуточных цифр}

else a[i]:=a[i]+1; {если перебраны не все цифры, то берем следующую}

end

until (n>0); {цикл заканчивается, когда найдено простое число}

end;

write(n); {вывод полученного числа}

end.



Схожі:

Задания и решения1-го тура Netoi-2009 iconДокументи
1. /Задания в Worde/~$Миксер.doc
2. /Задания...

Задания и решения1-го тура Netoi-2009 iconДокументи
1. /материалы по подготовке к олимпиадам (задания )/олимпиада по англ. языку/8-11 класс English...
Задания и решения1-го тура Netoi-2009 iconОтветы на задания теоретического тура 3 этапа Всеукраинской олимпиады по астрономии 2012/2013 учебного года
Один любитель астрономии утверждал, что однажды, наблюдая в полночь парад планет в телескоп с большим полем зрения, он видел все...
Задания и решения1-го тура Netoi-2009 iconЗнаете ли вы пунктуацию? Задания с ключами
Они разные по степени сложности. Первые три задания – занимательного характера, это своеобразная «пунктуационная разминка». Остальные...
Задания и решения1-го тура Netoi-2009 iconЗадания ІІ тура Всеукраинской олимпиады по русскому языку и литературе
«Проси, что дать тебе?- сказал ему этот голос. Ты должен решить свою судьбу. Хочешь ли прославиться на земле вое ыми подвигами? Хочешь...
Задания и решения1-го тура Netoi-2009 iconИнформация о международных астрономических олимпиадах. Задания международных астрономических олимпиад 2007-2010гг
Астрономическая олимпиада «Космическая Одиссея». Задания, подготовленные участников проекта
Задания и решения1-го тура Netoi-2009 iconКонспект по плану. Работа с терминами и понятиями, приведенными в параграфе
Задания для дистанционного обучения в 9 классе по Всемирной истории (задания подобраны с учетом программы по Всемирной истории)
Задания и решения1-го тура Netoi-2009 iconНаказ №228 Про проведення районних змагань з шахів серед школярів «Біла тура»
На виконання наказу відділу у справах сім’ї, молоді та спорту Хмельницької райдержадміністрації від 19. 03. 2012 №16 «Про районні...
Задания и решения1-го тура Netoi-2009 iconРусская народная сказка. Лутонюшка 5 Вопросы и задания
Настоящее пособие содержит художественные тексты, а также вопросы и задания к ним, которые позволят проверить умения учащихся 5-9...
Задания и решения1-го тура Netoi-2009 iconМетодические указания по выполнению расчётно-графического задания
В методических указаниях приведены варианты расчетно-графического задания для студентов дневной формы обучения, указания по их оформлению,...
Задания и решения1-го тура Netoi-2009 iconМетодические рекомендации по организации домашнего задания Грамотный подход к объёму, дозировке домашних заданий может в какой-то степени сохранить здоровье учащихся
Задание должно быть понятно каждому ученику, т е все учащиеся должны точно знать, что делать и как делать (ясность задания)
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©te.zavantag.com 2000-2017
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи