Городская олимпиада по программированию - 2016
Олимпиада этого года погружала участников в частную жизнь мальчика Васи. Мальчик Вася обладает кучей неприятных особенностей - ленив, туп, жаден... А нам про него задачи решать. Ну, ладно, поехали.
Задач было 4.
В каждом из классов встретилось 3 из них.
Поэтому я не буду разделять по классам, а просто объясню решение задач.
Задача 1. Тупость.
Папа у Васи силен в математике. А Вася не очень. Папа уехал в командировку, а Васе надо срочно для любого целого числа 0<N<10^9 найти количество пар неотрицательных целых чисел X и Y, таких, что:
X+Y+X*Y = N
Помогите Васе.
Решение.
Прежде, чем решать задачу, надо понять, что именно от вас требуется.
1. Надо искать не САМИ ЧИСЛА и количество пар, удовлетворяющих условию.
2. Для любого числа существует как минимум 2 пары: X=0, Y=N и X=N, Y=0 - точно удовлетворяющие этому условию.
3. X и Y никак ни могут быть больше N - потому, что пункт 2. Но могут быть какие-то числа между 0 и N.
Принцип решения:
Запускаем цикл от 0 до N по X
Внутри него запускаем цикл от 0 до N по Y
Если равенство X+Y+X*Y = N выполняется, изменяем счетчик пар на 1.
Выводим результат на экран.
Не забываем проверять условия для переменных. В случае некорректного ввода возвращаем программу к вводу чисел.
program rep;
label 1;
var
n,x,y:longint;
k:byte;
begin
1: writeln('Vvedi 0<n<1000000000: ');
Readln(n);
If ((n<0) or (n>1000000000)) then goto 1;
For x:=0 to n do
for y:=0 to n do
If (x+y+x*y=n) then k:=k+1;
writeln(' Vsego ',k,' par');
end.
Задача 2. Жадность.
Вася выбирает себе подарок на новый год. При этом он хочет 2 подарка из одного магазина. Стоимость подарка 0<А<10^9. Родители готовы дать ему X денег. При этом X - целое число, 0<X<10^9. В магазине не более 20 подарков в ассортименте. Вася выбирает по принципу: 2 самых дорогих подарка, которые в сумме не превышают выделенную родителями сумму денег. Посчитайте максимальную сумму, на которую Вася может выбрать подарки.
При запуске программы необходимо ввести:
1. Количество подарков в магазине (и проверить, не больше ли 20, если что - отправить на повторный ввод)
2. Число, показывающее, сколько можно потратить
3. Стоимость каждого из подарков, имеющихся в магазине.
Программа выводит на экран сумму двух самых ценных подарков, подходящих под условие.
Решение.
1. Мы вводим все необходимые по условию данные, проверяя их на соответствие условию.
2. Узнав количество подарков, в цикле запрашиваем стоимость для каждого. Для этого мы зададим массив А[1..20], чтоб можно было запомнить стоимость каждого из подарков, мы помним, что их максимум 20.
3. Получив стоимость подарков, мы сортируем массив в порядке убывания (или возрастания, это не важно. В принципе, можно и не сортировать, но с сортировкой красивее...
program pod;
label 1,2;
var
x,s, max,z:longint;
n,i,j:byte;
a:array[1..20] of longint;
begin
1:Write('Skolko podarkov v magazine? ');
Readln(n);
If ((n<=0) or (n>20)) then goto 1;
2:Write('Skolko deneg mogno potratit? ');
Readln(x);
If ((x<0) or (x>1000000000)) then goto 2;
For i:= 1 to n do begin
write ('Stoimost ',i,' podarka = ');
Readln(a[i]);
end;
For j:=1 to n do
For i:=1 to n-1 do
if a[i]<a[i+1] then
begin
z:=a[i];
a[i]:=a[i+1];
a[i+1]:=z;
end;
For i:=1 to n-1 do
For j:=i+1 to n do begin
if ((a[i]<x)and (a[j]<x) and (a[i]+a[j]>max) and (i<>j) and (a[i]+a[j]<=x)) then
max:=a[i]+a[j];
End;
writeln('Max summa = ',max);
end.
О двух других задачах я расскажу в следующем посте.
