Олимпиадные задачи по информатике

[The Godfather]

2006-2007 уч. год, Школьная олимпиада, г. Н.Новгород

Задача 1.«Многоугольник». 15 баллов

Вектор ОА( 100, 0) поворачивается относительно начала координат на заданный угол а градусов (а - целое, 0 < а < 180) по часовой стрелке. Новый вектор также поворачивается и т.д. Концы вектора рассматриваются как вершины многоугольника. Сколько у полученного многоугольника вершин?

Пример 1: a = 30, ответ = 12
Пример 2: a = 27, ответ = 40

Решение на Паскале:

{Задача 1.«Многоугольник». 15 баллов. 2006-2007 уч. год, Школьная олимпиада, г. Н.Новгород
Вектор ОА( 100, 0) поворачивается относительно начала координат на заданный угол а градусов (а - целое, 0 < а < 180) по часовой стрелке. Новый вектор также поворачивается и т.д. Концы вектора рассматриваются как вершины многоугольника. Сколько у полученного многоугольника вершин?}
program abc;
uses crt;
label kon;
var a,s,x:integer;
begin
clrscr;
writeln ('Input a');
readln(a);
x:=0;
s:=a;
if (a=0)OR(a>180) then begin
writeln ('No solutions');
goto kon;
end;
while NOT (s mod 360 =0) do begin
x:=x+1;
s:=s+a;
end;
writeln ('Kolvo uglov ',x+1);
kon:readln;
end.

Задача 2. «Остаток». 20 баллов

На доске подряд выписаны натуральные числа от 1 до n (n < 1000000000). Сначала с доски стерли все нечетные числа. Из оставшихся чисел стирают все числа, оказавшиеся на четных местах. Затем снова стирают все числа, оказавшиеся на нечетных местах, и так далее, пока не останется одно число. Какое?

Пример 1: n = 6, ответ = 6
Пример 2: n = 100, ответ = 86

Решение на Паскале. Вариант 1:

{2006-2007 уч. год, Школьная олимпиада, г. Н.Новгород
Задача 2. «Остаток». 20 баллов
На доске подряд выписаны натуральные числа от 1 до n (n < 1000000000). Сначала с доски стерли все нечетные числа. Из оставшихся чисел стирают все числа, оказавшиеся на четных местах. Затем снова стирают все числа, оказавшиеся на нечетных местах, и так далее, пока не останется одно число. Какое?
Пример 1: n = 6, ответ = 6
Пример 2: n = 100, ответ = 86}
program abc;
uses crt;
label kon;
var i,n,n2,a,d:longint;
begin
clrscr;
writeln ('Input a');
readln (a);
n:=1;
d:=0;
n2:=2;
i:=1;
kon:d:=d+1;
if (d mod 2)=1 then begin
n:=n+i;
n2:=n2+4*i;
end;
i:=i*2;
if ((a>n)AND(a<n2))OR(a=n) then writeln ('Останется число ', n)
else if a=n2 then writeln ('Останется число ',n2)
else if a=1 then writeln ('Останется число 1')
else goto kon;
readln;
end.

Решение на Паскале. Вариант 2:

{2006-2007 уч. год, Школьная олимпиада, г. Н.Новгород
Задача 2. «Остаток». 20 баллов
На доске подряд выписаны натуральные числа от 1 до n (n < 1000000000). Сначала с доски стерли все нечетные числа. Из оставшихся чисел стирают все числа, оказавшиеся на четных местах. Затем снова стирают все числа, оказавшиеся на нечетных местах, и так далее, пока не останется одно число. Какое?
Пример 1: n = 6, ответ = 6
Пример 2: n = 100, ответ = 86}
program abc;
uses crt;
label kon,konec;
var i,i2,n,n2,a,b,d:longint;
begin
clrscr;
writeln ('Input a');
readln (a);
if a=1 then begin
writeln ('Bla 1');
goto konec;
end;
n:=1;
d:=0;
n2:=2;
i:=1;
kon:d:=d+1;
if (d mod 2)=1 then begin
n:=n+i;
n2:=n2+4*i;
end;
i:=i*2;
if ((a>n)AND(a<n2))OR(a=n) then writeln ('Bla ', n)
else if a=n2 then writeln ('Bla ',n2)
else goto kon;
konec:readln;
end.

Задача 3. «Дроби». 25 баллов

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

Пример 1: Числитель = 2, Знаменатель = 3, ответ 2/3 = 1/2 + 1/6
Пример 2: Числитель = 500 Знаменатель = 1001, ответ 500/1001 = 1/3 + 1/7 + 1/43 + 1/18447