Главная

Школьная олимпиада по информатике Люберецкого муниципального района Московской области 2010-2011 учебный год

8-11 классы

Время выполнения: 3 часа

Задача 1. Число

Оценка 10 баллов.

Задано натуральное число. Записать его в обратном порядке. Например, 12345 должно превратиться в 54321.

Решение

Var x:longint;
    i,err:integer;
    s,z:string;
Begin
  readln(x); {ввод числа}
  str(x,s); {преобразуем число в строку}
  z:='';
  for i:=length(s) downto 1 do
      z:=z+s[i]; {запись строки наоборот}
  val(z,x,err); {преобразуем строку в число}
  writeln(x); {вывод результата}
End.

Скачать эту программу
 

Задача 2. «Количество чисел, не делящихся на 2, 3 или 5» (20 баллов)

Оценка 10 баллов.

Задано натуральное число N. Требуется написать программу, которая находит количество натуральных чисел, не превышающих N и не делящихся ни на одно из чисел 2,3,5.

Формат входных данных

Вводится число N (1 < N <1000000000).

Формат выходных данных

Вывести найденное число.

Пример входных данных: 10

Пример выходных данных: 2

Решение

Решение по перебору всех вариантов от 2 до N, которое может быть равно 999999999, потребует больших временных затрат, т.е. писать

s:=0;
for i:=1 to n do
if (i mod 2<>0) and (i mod 3<>0) and (i mod 5<>0) then s:=s+1;

нельзя!

Число чисел от 1 до N, делящихся на 2 равно N div 2, подобным образом, число чисел, делящихся на 3 равно N div 3, и число чисел, делящихся на 5 равно N div 5.

Тогда, число чисел не делящихся на 2, 3, 5 с учетом того, что, например 6 делится и на 2, и на 3, a 10 делится на 2 и на 5, 45 делится на 3 и на 5, равно:
 

N-(N div 2+N div 3+N div 5-N div 6-N div 10-N div 15-N div 30).

Var n,s:longint;
Begin
  readln(n); {ввод числа n}
  s:=n-(n div 2+n div 3+n div 5-n div 6-n div 10-n       div 15-n div 30);
  writeln(s); {вывод результата}
End.


Задача 3. Шахматная доска

Оценка 15 баллов.

Из шахматной доски по границам клеток выпилили связную (очевидно, связанную) (не распадающуюся на части) фигуру без дыр. Требуется определить её периметр.

Формат выходных данных

Сначала вводится число N (1≤N≤64) — количество выпиленных клеток. В следующих N строках вводятся координаты выпиленных клеток, разделенные пробелом (номер строки и столбца — числа от 1 до 8). Каждая выпиленная клетка указывается один раз.

Формат выходных данных

Выведите одно число — периметр выпиленной фигуры (сторона клетки равна единице).

Примеры

Входные данные Выходные данные Комментарий
3
1 1
1 2
2 1		 8 Вырезан уголок из трех клеток. Сумма длин его сторон равна 8
1
8 8		 4 Вырезана одна клетка. Её периметр равен 4

Решение

Периметры ВСЕХ вырезанных клеток равны 4*N. Если из этого числа вычесть число общих границ клеток умноженное на 2, то мы получим искомый периметр.

Примем двумерный массив 8х8 за шахматную доску. Введенные клетки обозначим единицами. Общие границы клеток определим, просматривая клетки массива по вертикали и по горизонтали.

Const m=8;
Var x:array[1..m,1..m] of integer;
p,i,j,n,k:integer;
Begin
  readln(n); {ввод числа клеток}
    {ввод координат клеток}
  for k:=1 to n do begin
      write(k,' '); readln(i,j);
      x[i,j]:=1; {заполнение введенных ячеек
                    массива единицами}
     end;
  p:=4*n;
      {просмотр массива по горизонтали}
  for i:=1 to m do
    for j:=1 to m-1 do
      if (x[i,j]=1) and (x[i,j+1]=1) then p:=p-2;
      {просмотр массива по вертикали}
  for j:=1 to m do
    for i:=1 to m-1 do
      if (x[i,j]=1) and (x[i+1,j]=1) then p:=p-2;
  writeln(p); {вывод результата}
End.

Скачать эту программу
 

Задача 4. Римские числа

Оценка 15 баллов.

Имя входного файла b.in

Входной файл содержит одну строку, в которой записано римское число от единицы до десяти. Вывести его десятичный эквивалент. Римское число записывается с помощью символов латиницы I, V, X, между которыми нет разделителей.

Формат входных данных

Ввод производится из файла b.in. Во входном файле записана строка римского числа.

Формат выходных данных

Вывести на экран десятичный эквивалент римского числа.

Примеры

b.in Вывод
VI 6

Решение

Римские цифры — цифры, использовавшиеся древними римлянами в своей непозиционной системе счисления.

Натуральные числа записываются при помощи повторения этих цифр. При этом, если большая цифра стоит перед меньшей, то они складываются (принцип сложения), если же меньшая — перед большей, то меньшая вычитается из большей (принцип вычитания). Последнее правило применяется только во избежание четырёхкратного повторения одной и той же цифры.

Римские цифры появились около 500 лет до нашей эры у этрусков. Лишь в XV веке римские цифры были постепенно заменены арабскими (индийскими) цифрами.

Римские числа
I 1 XI 11 XXX 30 CD 400
II 2 XII 12 XL 40 D 500
III 3 XIII 13 L 50 DC 600
IV 4 XIV 14 LX 60 DCC 700
V 5 XV 15 LXX 70 DCCC 800
VI 6 XVI 16 LXXX 80 CM 900
VII 7 XVII 17 XC 90 M 1000
VIII 8 XVIII 18 C 100 MM 2000
IX 9 XIX 19 CC 200 MMM 3000
X 10 XX 20 CCC 300    

Мы рассматриваем более широкую задачу — написать программу переводящую римское число в десятичный (арабский) эквивалент.

Var s:string;
    i,n,m,k:integer;
Begin
  {Файловые операции. Открытие файла}
  Assign(input,'b.in'); Reset(input);
  {Ввод данных - римское число}
  readln(s);
  n:=0; m:=length(s);
  for i:=1 to m do begin
    case s[i] of
        'I': n:=n+1;
        'V': n:=n+5;
        'X': n:=n+10;
        'L': n:=n+50;
        'C': n:=n+100;
        'D': n:=n+500;
        'M': n:=n+1000;
    end;
{Если нарушен порядок следования римских символов}
  if ((s[i]='V') or (s[i]='X')) and (s[i-1]='I') then n:=n-2;
  if ((s[i]='L') or (s[i]='C')) and (s[i-1]='X') then n:=n-20;
  if ((s[i]='M') or (s[i]='D')) and (s[i-1]='C') then n:=n-200;
  end;
  {Вывод результата}
  writeln(n);
  repeat
  until KeyPressed;
End.

Скачать эту программу
 

Задача 5. Задача Иосифа Флавия

Оценка 20 баллов.

Существует легенда, что Иосиф Флавий — известный историк первого века — выжил и стал известным благодаря математической одаренности. В ходе иудейской войны он в составе отряда из 41 иудейского воина был загнан римлянами в пещеру. Предпочитая самоубийство плену, воины решили выстроится в круг и последовательно убивать каждого третьего из живых до тех пор, пока не останется ни одного человека. Однако Иосиф наряду с одним из своих единомышленников счел подобный конец бессмысленным — он быстро вычислил спасительные места в порочном круге, на которые поставил себя и своего товарища. И лишь поэтому мы знаем его историю.

В нашем варианте мы начнем с того, что выстроим в круг N человек, пронумерованных числами от 1 до N, и будем исключать каждого k-ого до тех пор, пока не уцелееет только один человек.

Например, если N=10, k=3, то сначала умрет 3-й, потом 6-й, затем 9-й, затем 2-й, затем 7-й, потом 1-й, потом 8, за ним — 5-й, и потом 10-й. Таким образом уцелеет 4-й.

Задача: определить номер уцелевшего.

Входные данные: числа N и k. Ограничения: 1≤N≤500, 1≤k≤100.

Выходные данные: программа должна выдавать номер уцелевшего человека на экран.

Формат входных данных

10 3

Формат выходных данных

4

Решение

Возьмем массив записей, в который введем номера людей от 1 до N и пометки "true". В цикле while, изменяя номера людей от m=k с шагом k до значения превышающего N (m<=N), помечаем "false" номера выводимых из круга. При этом по окончании цикла m>N, m-начало счета, будет равно m:=m-n

Перепишем элементы с меткой "true" во вспомогательный массив b, считая количество переписваемых элементов j. Если с начала j=1, то число переписанных элементов будет j-1. Массив b перепишем в массив a, при этом n=j-1.

Все повторяем до тех пор, пока n не станет равным 1. В первом (единственном) элементе масссива а — a[1].x будет номер оставшегося.

Type
  r_type=record
    x:integer;
    y:boolean
    end;
  a_type=array [1..500] of r_type;
Var a,b :a_type;
    i,j,k,n,m:integer;
Begin
  write('n='); readln(n);
  write('k='); readln(k);
  {Формирование массива}
  for i:=1 to n do begin
     a[i].x:=i;
     a[i].y:=true
    end;
  m:=k;
  repeat
    while k<=n do begin
    {Исключение элемента массива}
    a[k].y:=false;
    {Следующий элемент}
    m:=m+k;
   end;
   {В массив b неисключенные элементы}
  j:=1;
  for i:=1 to n do
     if (a[i].y) then begin
        b[j].x:=a[i].x;
        b[j].y:=true;
        inc(j);
     end;
  {Массив b переписывается в массив a}
  a:=b;
  {Значение m больше n после цикла while}
  m:=m-n;
  {Теперь n уменьшилось за счет исключенных элементов}
  n:=j-1;
  until n=1;
  {Вывод оставшегося элемента}
  write(a[1].x);
End.

Скачать эту программу
 

В статье Википедия. Задача Иосифа Флавия приведена более короткая программа:

Const nmax=500;
Var mass:array[1..nmax] of integer;
    i,j,m,n: integer;
Begin
  read(n,m);
  {Заполнение массива}
  for i:=1 to n do
     mass[i]:=i;
  i:=1;
  while n>1 do begin
    {Выводимый элемент i}
    i:=(i+m-1) mod n;
    if i=0 then i:=n;
    {Круг смыкается}
    for j:=i to n-1 do
         mass[j]:=mass[j+1];
    {Число элементов в круге уменьшается на 1}
    n:=n-1;
  end;
  writeln(mass[1]);
End.
Скачать эту программу