Олимпиада по информатике 9-11 классы

Школьная олимпиада 2019 год 9-11 классы

Задача 1

Шарики

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

Напишите и вы программу, которая определяет, сколько шариков будет удалено и какие шарики останутся.

Формат входного файла

В первой строке вводится количество шариков в цепочке (не более 1000).

Во второй строке цвета шариков (от 0 до 9, каждому цвету соответствует свое целое число).

Формат выходного файла

В первой строке требуется вывести количество шариков, которое будет удалено.

Во второй строке цвета оставшихся шариков или ничего, если все шарики были удалены.

Пример:

{Задача 1. Шарики 7-11 кл.}

var N:integer;      {длина цепочки шариков}

    r:array[1..1000] of byte;   {оставшиеся неудаленными шарики}

    i:integer;      {количество цифр в числе N}

    k:longint;      {счетчик цикла}

    a,b:byte;       {для ввода цвета шариков: a - левый, b - правый}

    inf,outf:text;

begin

  assign(inf,'input.txt');

  assign(outf,'output.txt');

  reset(inf);

  rewrite(outf);

  read(inf,N);     {ввод количества шариков}

  read(inf,a);     {ввод левого шарика}

  i:=0;            {столько шариков остается}

  k:=1;       {количество подряд идущих одного цвета шариков}

  while not(eof(inf)) do

    begin

      read(inf,b);    {ввод правого шарика}

      if a=b then

        begin

          inc(k);     {увеличиваем счет одинаковых шариков}

          continue;   {продолжение ввода}

        end

      else

        begin

          if k=1 then

            begin inc(i); r[i]:=a; end  {одиночного цвета шарик}

          else

            if k=2 then    {два шарика одинакового цвета}

              begin inc(i); r[i]:=a; inc(i); r[i]:=a; end;

          a:=b;      {правый шарик делаем левым}

          k:=1;      {начинаем счет сначала для нового цвета}

        end;

    end;

  {обработка последнего из шариков}

  if k=1 then begin inc(i); r[i]:=a; end

  else if k=2 then begin inc(i); r[i]:=a; inc(i); r[i]:=a; end;

  writeln(outf,N-i);    {вывод количества удаленных шариков}

  for k:=1 to i do write(outf,r[k],' '); {вывод оставшихся цветов}

  close(inf);

  close(outf);

end.

Задача 2  Отношение

Даны два натуральных числа a и b. Найдите наибольшее значение отношения трехзначного числа из отрезка [a,b] к сумме его цифр.

Формат входного файла

Первая строка содержит два натуральных числа a и b (99<a<b<1000).

Формат выходного файла

Файл должен содержать одно вещественное число- максимальное отношение с тремя цифрами после десятичной точки.

Пример:

{Задача 2. Отношение 7-11 кл.}

var i:integer;         {счетчик цикла}

    a,b:integer; {левый и правый концы данного отрезка}

    s:byte;            {сумма цифр числа i}

    x:integer;         {для дублирования числа i}

    y:real;            {отношение числа к сумме цифр}

    max:real;         {наибольшее значение отношения}

    inf,outf:text;

begin

  assign(inf,'input.txt');

  assign(outf,'output.txt');

  reset(inf);

  rewrite(outf);

  read(inf,a,b);      {ввод концов отрезка}

  max:=-1;            {инициализация max}

  for i:=a to b do {цикл перебора целых чисел на отрезке}

    begin

      x:=i;           {вычисление суммы цифр числа i}

      s:=0;

      while x>0 do

        begin

          s:=s+(x mod 10);

          x:=x div 10;

        end;

      y:=i/s;         {вычисление отношения}

      if max<y then max:=y;    {проверка на максимум}

    end;

  writeln(outf,max:0:3);   {вывод результата}

  close(inf);

  close(outf);

end.

Задача 3

Система счисления

Ученики выполняют контрольную работу по информатике по теме «Системы счисления». Дается N примеров вида основание А: число1=основание В:число2. Число 1 записанное в системе счисления по основанию А переводится в число 2, записанное в системе счисления по основанию В. (2<=A,B<=10). Все числа в десятичной системе не превышают 2*10⁹.Составить программу, формирующую строку из N знаков «+», «-».«+», если перевод сделан правильно и «-», если неправильно.

Формат входного файла

Первая строка содержит натуральное число N (1<=N<=10).

В следующих N строках примеры по переводу.

Формат выходного файла

Файл должен содержать строку из N символов «+» «-»

Пример:

{Задача 3. Система счисления 9-11 кл.}

{На входе основание всегда указывается в десятичной системе счисления!}

var N:integer;         {количество примеров}

    c:char;            {символ}

    oleft,oright:integer;      {основание слева, основание справа}

    nleft,nright:integer;      {число слева, число справа}

    i:integer;         {счетчик цикла}

    inf,outf:text;

begin

  assign(inf,'input.txt');

  assign(outf,'output.txt');

  reset(inf);

  rewrite(outf);

  readln(inf,N);      {ввод количества примеров}

  for i:=1 to N do    {цикл просмотра всех примеров}

    begin

      read(inf,c);      {ввод основания слева}

      oleft:=ord(c)-ord('0');

      repeat

        read(inf,c);

        if c<>':' then oleft:=oleft*10+ord(c)-ord('0');

      until c=':'; {считано основание слева}

      read(inf,c);      {ввод числа слева}

      nleft:=ord(c)-ord('0');

      repeat

        read(inf,c);

        if c<>'=' then nleft:=nleft*oleft+ord(c)-ord('0');

      until c='='; {считано число слева и переведено в 10-ую систему счисления}

      read(inf,c);      {ввод основания справа}

      oright:=ord(c)-ord('0');

      repeat

        read(inf,c);

        if c<>':' then oright:=oright*10+ord(c)-ord('0');

      until c=':'; {считано основание справа}

      read(inf,c);      {ввод числа справа}

      nright:=ord(c)-ord('0');

      repeat

        read(inf,c);

        if c in ['0' .. '9'] then nright:=nright*oright+ord(c)-ord('0')

                             else break;

      until c='#13';{считано число справа и переведено в 10-ую систему счисления}

      if nleft=nright then write(outf,'+')   {вывод результата}

                      else write(outf,'-');

      readln(inf); {переводим курсор на новую строку (следующий пример)}

  end;

  close(inf);

  close(outf);

end.

Задача 4

Волшебный Мост

               Крестьянин, возвращаясь с ярмарки, увидел на мосту странную картину. Какой-то человек сначала считал деньги в кошельке, затем бросал в реку несколько монеток, бежал на другой конец моста, снова считал деньги в кошельке, и опять бросал несколько монеток и шёл на другой конец моста. Наконец, пересчитав свои деньги, он явно обрадовался и отправился в дальнейший путь.

- Что ты делал? Зачем ты бросал деньги в воду? – спросил крестьянин, догнав странного человека.

Видя, что свой секрет скрыть не удастся, человек рассказал, что мост волшебный. Если бросить с моста ровно 29 копеек, то, как только пройдёшь мост, количество рублей в оставшейся сумме денег превращаются в новой сумме в количество копеек, а копейки – в рубли. Перейдя мост несколько раз, можно получить сумму, намного больше первоначальной.

- Самое важное – вовремя остановиться, - сказал человек и ушёл.

Крестьянин задумался, достал кошелёк и пересчитал свои деньги. У него было 46 рублей 47 копеек. «29 копеек – не деньги, дай-ка попробую». После первого прохода у него получилось 18 рублей 46 копеек, после второго прохода – 17 рублей 18 копеек, а после третьего – 89 рублей 16 копеек. «Ух-ты! А ещё больше можно получить?» - обрадовался крестьянин. После четвёртого прохода у него стало 87 рублей 88 копеек, после пятого – 59 рублей 87 копеек, после шестого – 58 рублей 59 копеек, после седьмого – 30 рублей 58 копеек, после восьмого – 29 рублей 30 копеек, после девятого – 1 рубль 29 копеек, а после десятого осталась 1 копейка.

«Эх, надо было после третьего раза остановиться!» - расстроился крестьянин.

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

Формат входного файла

В первой строке содержится целое число М – количество копеек, которые нужно бросать с моста (1 <= М <= 50). Во второй строке содержатся два целых числа R и К через пробел – начальная сумма денег у крестьянина, выраженная в рублях и копейках (0 <= R <= 99, 0 <= К <= 99).

Формат выходного файла

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

Пример:

29

46 47

3

{Задача 4. Волшебный Мост 9-11 кл.}

var M:integer; {размер презента реке за один проход, копеек 0<=M<=99}

    R,K:integer;       {рублей, копеек}

    pr:integer;        {счетчик проходов}

    x:integer;         {для обмена рублей и копеек значениями}

    rmax,kmax:integer; {максимальная сумма в руках}

    prmax:integer;     {номер прохода, когда сумма максимальная}

    inf,outf:text;

begin

  assign(inf,'input.txt');

  assign(outf,'output.txt');

  reset(inf);

  rewrite(outf);

  readln(inf,M);    {ввод размера презента}

  readln(inf,R,K);  {ввод рублей, копеек}

  pr:=0;            {инициализация переменных}

  Rmax:=R;

  Kmax:=K;

  prmax:=pr;

  while (R>0) or (K>0) do {пока денежки имеются, посматриваем все варианты}

    begin

      dec(K,M);      {вычли копейки}

      if K < 0 then       {ушли в минус}

        begin

          inc(K,100);     {нашли 100 копеек}

          dec(R);         {потеряли рубль}

          if R < 0 then break;{если оказывается терять нечего, выходим из цикла}

        end;

      x:=R;      {рубли и копейки меняем значениями}

      R:=K;

      K:=x;

      inc(pr);   {считаем проходы}

      if R*100+K > Rmax*100+Kmax then   {если получили бо-o-oльшую сумму,}

        begin

          Rmax:=R;          {запоминаем как максимальную на текущий проход}

          Kmax:=K;

          prmax:=pr;

        end;

    end;

  writeln(outf,prmax);   {вывод результата}

  close(inf);

  close(outf);

end.

Задача 5

Привал

             Путник двигался t1 часов со скоростью v1, t2 часов со скоростью v2, ..., tn часов со скоростью vn. За какое время он одолел первую половину пути (после чего запланировал привал)?

Формат входного файла

Первая строка содержит единственное число N - количество участков пути. Следующие N строк содержат по два числа ti и vi, разделенных пробелом. Все числа в файле натуральные и не превышают 100.

Формат выходного файла

Файл должен содержать одно действительное число с тремя знаками после десятичной точки - время преодоления первой половины пути.

Пример:

3

3 5

4 4

6 2

4.625

{Задача 5. Привал 9-11 кл.}

var N:integer;         {количество интервалов пути}

    i:integer;         {счетчик цикла}

    tv:array[1..100,1..2] of byte;   {массив времен и скоростей}

    s:longint;         {длина всего пути}

    x:real;            {половина пути}

    y:real;            {осталось до половины пути}

    t:real;            {время прохождения половины пути}

    inf,outf:text;

begin

  assign(inf,'input.txt');

  assign(outf,'output.txt');

  reset(inf);

  rewrite(outf);

  read(inf,N);      {ввод количества интервалов пути}

  s:=0;             {инициализация длины пути}

  for i:=1 to N do {цикл ввода времен и скоростей и вычисления длины пути}

    begin

      read(inf,tv[i,1],tv[i,2]);   {ввод времен и скоростей}

      s:=s+tv[i,1]*tv[i,2];        {вычисление длины пути}

    end;

  x:=0;

  t:=0;

  for i:=1 to N do  {цикл вычисления точки середины пути}

    begin

      y:=tv[i,1]*tv[i,2];   {вычисление длины интервала}

      if x+y<s/2 then      {ищем середину пути}

        begin

          x:=x+y;          {суммирование длин интервалов}

          t:=t+tv[i,1];  {суммирование времен прохождения интервалов}

        end

      else

        begin

          y:=s/2-x;      {длина до середины пути}

          t:=t+y/tv[i,2];   {время прохождения длины y}

          break;         {выход из цикла по i}

        end;

    end;

  writeln(outf,t:0:3);   {вывод результата}

  close(inf);

  close(outf);

end.

Задача 6

Наименьшее количество

Найти количество натуральных чисел из отрезка [a,b], имеющих наименьшее количество делителей.

Формат входного файла

Первая строка содержит два натуральных числа a и b. (1<=a<b<=1000)

Формат выходного файла

Файл должен содержать два натуральных числа: количество таких чисел и минимальное количество делителей.

Пример:

{Задача 6. Наименьшее количество 9-11 кл.}

var a,b:integer;    {левый и правый концы данного отрезка}

    d:integer;      {очередной делитель}

    i:integer;      {счетчик цикла}

    k:integer; {количество чисел отрезка с наименьшим количеством делителей}

    kmin:integer; {наименьшее количество делителей}

    ki:integer; {количество делителей числа i}

    inf,outf:text;

begin

  assign(inf,'input.txt');

  assign(outf,'output.txt');

  reset(inf);

  rewrite(outf);

  read(inf,a,b);      {ввод концов отрезка}

  kmin:=1001;         {инициализация kmin}

  k:=0;               {инициализация k}

  for i:=a to b do    {цикл перебора целых чисел на отрезке}

    begin

      ki:=0;      {количество делителей числа i}

      d:=1;       {первый делитель числа i}

      while d*d<=i do   {делители d не превосходят корня из числа i}

        begin

          if i mod d =0 then

            if d*d=i then inc(ki)  {один делитель, 5*5=25}

                     else inc(ki,2); {два делителя, 2*12=24}

          inc(d);

        end;

      if ki<kmin then begin kmin:=ki; k:=1; end {счет k сначала}

                 else if ki=kmin then inc(k); {продолжение счета k}

    end;

  writeln(outf,k,' ',kmin);    {вывод результатов}

  close(inf);

  close(outf);

end.

Задача 7

Из одних пятерок

Дано натуральное число N (0<N<=2*10⁹). Найти наименьшее натуральное число больше данного, составленного из одних 5.

Формат входного файла

Первая строка содержит единственное натуральное число N

Формат выходного файла

Файл должен содержать одно натуральное число

Пример:

{Задача 7. Из одних пятерок 9-11 кл.}

var N:longint;      {данное число 0<N<=2 000 000 000}

    x:longint;         {для дублирования числа N}

    b:byte;            {старшая цифра числа x}

    inf,outf:text;

begin

  assign(inf,'input.txt');

  assign(outf,'output.txt');

  reset(inf);

  rewrite(outf);

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

  x:=N;             {дублирование числа N}

  while x>0 do

    begin

      b:=x mod 10;  {отсекаемая правая цифра числа x}

      x:=x div 10;   {отсечение правой цифры числа x}

      write(outf,5);     {вывод очередной пятерки}

    end;

  if 5<b then write(outf,5); {приписывание еще одной пятерки}

  close(inf);

  close(outf);

end.

Задача 8

След

След квадратной матрицы - это число, равное сумме элементов главной и побочной  диагоналей. Вычислите след заданной квадратной матрицы A[N,N]. и найдите количество элементов матрицы равных следу. Все элементы матрицы целые числа, не превышающие по модулю 500.

Формат входного файла

Первая строка содержит одно натуральное число N. (1<=N<=30)

Формат выходного файла

Файл должен содержать одно натуральное число: количество элементов матрицы, равных следу.

Пример:

{Задача 8. След 9-11 кл.}

var N:integer;   {размер квадратной матрицы 1<=N<=30}

    A:array[1..30,1..30] of integer; {квадратная матрица}

    s:integer; {след - сумма элементов главной и побочной диагоналей}

    i,j:integer;    {индексы массива A}

    k:integer;   {количество элементов, равных следу}

    inf,outf:text;

begin

  assign(inf,'input.txt');

  assign(outf,'output.txt');

  reset(inf);

  rewrite(outf);

  read(inf,N);      {ввод размера квадратной матрицы}

  s:=0;             {обнуление следа}

  for i:=1 to N do {ввод значений элементов квадратной матрицы}

    for j:=1 to N do

      begin

        read(inf,A[i,j]);

        if (i=j) or (j=N-i+1) then

                s:=s+A[i,j]; {суммирование элементов диагоналей}

      end;

  k:=0;            {инициализация k}

  for i:=1 to N do {ввод значений элементов квадратной матрицы}

    for j:=1 to N do

      begin

        if A[i,j]=s then inc(k); {счет элементов, равных следу}

      end;

  writeln(outf,k);

  close(inf);

  close(outf);

end.