Готовимся к олимпиаде

 




Олимпиадные задания с решениями



  1. Условие задачи. Найдите наибольшее значение отношения трехзначного числа к сумме его цифр.


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


Запустим три  цикла два из которых вложенные:


Первый  будет начинаться с 1 (т.к. у трехзначного числа первая цифра не может быть нулем) и предназначен для перебора сотен.
Второй начнется с нуля - будет перебирать десятки.
Третий также с нуля  - будет перебирать единицы.
Текст программы на языке Паскаль.


var
 a,b,c: integer;
 res: real;
begin   
 res := 0;   
 for a := 1 to 9 do     
   for b := 0 to 9 do       
     for c := 0 to 9 do       
       if (a*100 + b*10 + c) / (a + b + c) > res then         
          res:= (a*100 + b*10 + c) / (a + b + c);    
 write('Result = ', res:0:2);
end.       
Три  цикла - это не самый лучший вариант, но давайте подумаем, что мы получим на первом шаге: a=1, b=0, c=0 (число 100), а сумма его цифр равна единице. Вот собственно и правильный ответ: наибольшее значение отношения трехзначного числа к сумме его цифр равно 100. Никакой цикл, по большому счету и не потребовался.
  1. Условие задачи. Дана строка, состоящая из символов, каждый из которых является знаком «+» или цифрой, начинающаяся и заканчивающаяся цифрой. Если в строке встречается сочетание «++», то выдать сообщение об ошибке, в противном случае вычислить получившуюся сумму.
Решение задачи на Паскале. Эта задача рассчитана больше на знание языка программирования, чем  на сообразительность. Для решения задачи можно использовать функцию "ORD", которая позволяет получить порядковый номер любого символа согласно таблице ASCII-кодов. Например, номер символа '0' - 48, а номер символа '1' - 49. Как вы понимаете, чтобы получить искомую цифру, необходимо отнять от номера символа 48.
Внимание!
  1. Во входной строке нет пробелов!
  2. Функция ORD будет работать в Turbo Pascal, но не будет работать в Pascal ABC.
  3. Pascal ABS поддерживает синтаксис Delphi, поэтому необходимо заменить строку "res:= res + (ord(s[i])-48);" на "res:= res + StrToInt(s[i]);"

const
 s = '2+6+8+9+1+5';
var
 i,res: integer;
begin
 res:=0;
 for i := 1 to length(s) - 1 do
   if (s[i] = '+') and (s[i+1]= '+' ) then
     begin
       write('Error');
       exit;
     end;
 for i := 1 to length(s) do
   if s[i] <> '+' then
     res := res + (ord(s[i])-48);
 write(res);
end.


  1. Условие задачи. Каждый элемент квадратной матрицы размеренности N x N равен нулю, либо единице. Найдите количество «островов», образованных единицами. Под «островом» понимается группа единиц (либо одна единица), со всех сторон окруженная нулями (или краями матрицы). Единицы относятся к одному «острову», если из одной из них можно перейти к другой «наступая» на единицы, расположенные в соседних клетках. Соседними являются клетки, граничащие по горизонтали или вертикали.
Я несколько изменил исходное условие задачи, уточнив, что одна единица тоже считается островом. Также я предлагаю считывать матрицу из файла, на дворе ведь уже 2010 год и решения олимпиадных задач проверяются, в основном, при помощи тестирующих систем.
Входные данные
В первой строке файла INPUT.TXT записано натуральное число N не больше 100 - размер квадратной матрицы. В следующих N строках задаются элементы матрицы через пробел.
Выходные данные
В файл OUTPUT.TXT выведите единственное число - количество островов.
Пример
INPUT.TXT
OUTPUT.TXT
5
1 0 1 1 1 
0 0 0 0 0
1 1 1 0 1 
0 1 0 0 1
0 0 0 1 1
4

Решение задачи
Итак, это классическая задача на поиск в глубину графа. Понятно, что надо обходить матрицу и каким-то образом вычислять количество островов. Вариант решения такой: после того, как мы попадаем на остров, надо это зафиксировать увеличив переменную-результат на единицу. Чтобы второй раз не посчитать один и тот же остров, сразу после посещения необходимо его уничтожить, т.е. присвоить всем клеткам острова значение ноль.
Поскольку тест задачи не слишком мал, стоит написать процедуру уничтожения островов, назовем ее"count". Чтобы во время выполнения процедуру не "выскочить" за пределы массива, сделаем его не размером N x N, а размеров N+2 x N+2, это даст  нам возможность окружить искомый массив размеромN x N  нулями.
const
 m = 102;
var
 a:array [1..m, 1..m] of integer;
 i,j,n,res: integer;
 input,output: text;
procedure count(i,j: integer);
 begin
   if a[i,j] <> 1 then
     exit;
   a[i,j] := 0;
   count(i + 1, j);
   count(i - 1, j);
   count(i, j + 1);
   count(i, j - 1);
 end;
begin
 res:= 0;
 assign(input,'input.txt');
 reset(input);
 assign(output,'output.txt');
 rewrite(output);
 read(input, n);
 {Заполняем массив нулями}
 for i:= 1 to n+2 do
   for j:=1 to n+2 do
     a[i,j]:=0;
 {Считываем матрицу из файла}
 for i:= 2 to n+1 do
   for j:=2 to n+1 do
     read(input,a[i,j]);
 {Обходим матрицу в поиске островов}
 for i := 2 to n+1 do
   for j := 2 to n+1 do
     if a[i,j] = 1 then
       begin
         inc(res);
         count(i,j);
       end;
 write(output,res);
 close(input);
 close(output);
end.


  1. Условие задачи. Клавиатура
Имя входного файла:
keyboard.in
Имя выходного файла:
keyboard.out
Максимальное время работы на одном тесте:
2 секунды
Максимальный объем используемой памяти:
64 мегабайта

Всем известно, что со временем клавиатура изнашивается, и клавиши на ней начинают залипать. Конечно, некоторое время такую клавиатуру еще можно использовать, но для нажатий клавиш приходиться использовать большую силу.
При изготовлении клавиатуры изначально для каждой клавиши задается количество нажатий, которое она должна выдерживать. Если знать эти величины для используемой клавиатуры, то для определенной последовательности нажатых клавиш можно определить, какие клавиши в процессе их использования сломаются, а какие – нет.
Требуется написать программу, определяющую, какие клавиши сломаются в процессе заданного варианта эксплуатации клавиатуры.
Формат входных данных
Первая строка входного файла содержит целое число n (1 ≤ n ≤ 100) – количество клавиш на клавиатуре. Вторая строка содержит n целых чисел – с1, с2, … , сn, где сi (1 ≤ сi ≤ 100000) – количество нажатий, выдерживаемых i-ой клавишей. Третья строка содержит целое число k (1 ≤ k ≤ 100000) – общее количество нажатий клавиш, и последняя строка содержит k целых чисел pj (1 ≤ pj ≤ n) – последовательность нажатых клавиш.
Формат выходных данных
В выходной файл необходимо вывести n строк, содержащих информацию об исправности клавиш. Если i-ая клавиша сломалась, то i-ая строка должна содержать слово “yes” (без кавычек), если же клавиша работоспособна – слово “no”.
Пример входных и выходных данных
keyboard.in
keyboard.out
5
1 50 3 4 3
161 2 3 4 5 1 3 3 4 5 5 5 5 5 4 5

yes
no
no
no
yes

Краткие методические рекомендации по решению задачи
Решение данной задачи не представляет особых сложностей и заключается в следующем. В первую очередь необходимо для каждой клавиши на клавиатуре посчитать количество нажатий на нее и проверить, больше ли оно некоторого числа. Количество нажатий клавиш можно хранить в массиве и, считывая очередное нажатие, увеличивать счетчик для данной клавиши. После считывания всех нажатий для всех клавиш следует последовательно проверить выполнение указанного в описании задачи условие.
Программная реализация решения этой задачи требует аккуратности при чтении входных данных и при выводе выходных данных. Кроме этого, требуется аккуратно организовать хранение информации о числе нажатий в одномерном массиве.
Таким образом, чтобы набрать полный балл, требуется реализовать простейшее линейное решение, в котором используются лишь базовые операции с массивами.
Возможные ошибки
Можно применить "лобовое" решение, т.е. создать два или  три массива, но на самом деле нужен только один размером 100 элементов. При лобовом решении необходим массив в 100000 элементов, а создать его в Turbo Pascal не удастся. Самое интересное, что лобовое решение проходит если использовать компилятор Free Pascal. При решении задачи надо обратить внимание, что в выходной файл данные надо выводит в нижнем регистре.
Текст программы на Паскале одного из участников олимпиады:
Var
 c : array [1..100] of longint;
 n, i, k, t : longint;
 f : text;
Begin
 Assign(f,'keyboard.in');
 Reset(f);
 ReadLn(f,n);
 For i:=1 to N do
   Read(f,c[i]);
 Readln(f,k);
 For i:=1 to k do
   begin  
     Read(f,t);
     Dec(c[t]);
   end;
 Close(f);
 Assign(f,'keyboard.out');
 Rewrite(f);
 For i:=1 to N do
   If c[i]>=0 Then
     Writeln(f,'no')
   Else Writeln(f,'yes');
 Close(f);
End.


  1. Газон
Имя входного файла:
lawn.in
Имя выходного файла:
lawn.out
Максимальное время работы на одном тесте:
2 секунды
Максимальный объем используемой памяти:
64 мегабайта

Фермер Иван с юности следит за своим газоном. Газон можно считать плоскостью, на которой в каждой точке с целыми координатами растет один пучок травы.
В одно из воскресений Иван воспользовался газонокосилкой и постриг некоторый прямоугольный участок газона. Стороны этого участка параллельны осям координат, а две противоположные вершины расположены в точках (x1, y1) и (x2, y2). Следует отметить, что пучки травы, находящиеся на границе этого прямоугольника, также были пострижены.
Довольный результатом Иван купил и установил на газоне дождевальную установку. Она была размещена в точке с координатами (x3, y3) и имела радиус действия струи r. Таким образом, установка начала поливать все пучки, расстояние от которых до точки (x3, y3) не превышало r.
Все было хорошо, но Ивана заинтересовал следующий вопрос: сколько пучков травы оказалось и пострижено, и полито в это воскресенье?
Требуется написать программу, которая позволит дать ответ на вопрос Ивана.
Формат входных данных
В первой строке входного файла содержатся четыре целых числа x1, y1, x2, y2 (−100 000 ≤ x1 < x2 ≤ 100 000; −100 000 ≤ y1 < y2 ≤ 100 000).
Во второй строке входного файла содержатся три целых числа x3, y3, r (−100 000 ≤ x3, y3 ≤ 100 000; 1 ≤ r ≤ 100 000)
Формат выходных данных
В выходной файл необходимо вывести одно целое число — число пучков травы, которые были и пострижены, и политы.
Пример входных и выходных данных
lawn.in
lawn.out
0 0 5 4
4 0 3
14
Иллюстрация к примеру
Олимпиадная задача Газон, пример
Краткие методические рекомендации по решению задачи
Одно из возможных решений данной задачи заключается в следующем. Для каждой прямой, содержащей все пучки травы с равной координатой по оси абсцисс (аналогично можно рассматривать и ось ординат), найдем ее точки пересечения с окружностью, отображающей область действия поливальной установки, если, конечно, такие точки существуют. Получив данные точки, не сложно за время O(1) посчитать количество пучков травы на данной прямой одновременно и политых, и постриженных. Это делается с помощью операции вычисления целой части числа. Далее, просуммировав найденные числа для всех прямых, можно найти ответ на поставленную задачу.
Не сложно показать, что время работы рассматриваемого решения будет O(r).
Возможные ошибки
Можно применить "лобовое" решение, т.е. создать два или  три массива, но на самом деле нужен только один размером 100 элементов. При лобовом решении необходим массив в 100000 элементов, а создать его в Turbo Pascal не удастся. Самое интересное, что лобовое решение проходит если использовать компилятор Free Pascal.
Текст программы на Паскале:
type
 abc=Int64;
var
 x1,y1,x2,y2,x3,y3,x: longint;
 k,r,y : abc;
 input,output: text;
function kol(x,z1,z2:longint):longint;
 var
   min,max,k: longint;
 begin
   if (x<x1)or(x>x2)or(z1>y2)or(z2<y1) then
     k:=0
   else
     begin
       min:=y1;
       if z1>y1 then
         min:=z1;
       max:=y2;
       if z2<y2 then
         max:=z2;
       k:=max-min+1
     end;
    kol:=k
 end;
begin
 assign(input, 'input.txt');
 reset(input);
 assign(output, 'output.txt');
 rewrite(output);
 readln(input,x1,y1,x2,y2);
 read(input,x3,y3,r);
 k:=kol(x3,y3-r,y3+r);
 y:=r;
 for x:=1 to r-1 do
   begin
     while sqr(x)+sqr(y)>sqr(r) do
       y:=y-1;
     k:=k+kol(x3+x,y3-y,y3+y)+kol(x3-x,y3-y,y3+y)
   end;
 k:=k+kol(x3+r,y3,y3)+kol(x3-r,y3,y3);
 write(output,k);
 close(input);
 close(output);
end.

Комментариев нет:

Отправить комментарий