Разбор задач с олимпиад

Разбор задач с олимпиад 2018-2019 учебного года

Разбор задач с олимпиад 2017-2018 учебного года

Разбор задач с олимпиад 2016-2017 учебного года

Разбор задач с олимпиад 2015-2016 учебного года

Презентация
Задания со школьного этапа (1 тур)
Задания со школьного этапа (2 тур)
Задания с муниципального этапа

Разбор задач с городской олимпиады 2014-2015 года.



Разбор задач со школьной (лицейской) олимпиады 2014-2015 года.



Разбор задач с обласной олимпиады 2013-2014 года


Разбор задач с городской олимпиады 2013-2014 года


Разбор задач со школьной (лицейской) олимпиады от 07.10.2013


Задача А.

1. Задачу можно просто решить с массивами, но для этого лучше использовать динамическое создание и сравнивать поэлементно:
program taska;
var
   z,x,l,i,n,k,j:integer;
   a,b:array of byte;

begin
   readln(n,k);
   setlength(a,k+1);
   setlength(b,n+1);
   z:=0;
   for i:=1 to k do read(a[i]);
   for i:=1 to n do read(b[i]);

   for i:=1 to n do begin
      j:=1;l:=i;
      while (j<=k)and (l<=n)and (b[l]=a[j]) do  begin
      inc(l);
      inc(j);
   end;
      if j=k+1 then z:=z+1;
   end;
      write(z);
end.

2. Можно решить с использованием битов (но только если размер первого массива не превышает 64). Для этого биты 0 и 1 помещаем в память длиной 64 бита:
#include <iostream>
using namespace std;
int main()
{
struct Options{unsigned long long s:64;};//самое длинное целое в 64 бита
int a,n,i,j;
int k;

Options O,b,t;
O.s=0;
b.s=0;
t.s=1;
cin>>n>>k;
for (i=0;i<k;i++){t.s=(t.s<<1)+1;}/* заносим бит 0 или 1 в память с помощью битового сдвига << на 1 бит влево плюс 1, т.е. заполняем единицами k бит, чтобы при добавлении лишних битов длина была выравнена до длины первого массива */
for (i=0;i<k;i++)
{
    cin>>a;
    O.s=(O.s<<1)+a; /* заносим биты из первого массива в память */
}
int L=0;
for (i=0;i<n;i++)
{
    cin>>a;
    b.s=(b.s<<1)+a;  /* заносим биты из второго массива в память */
    b.s=b.s&t.s; /* пересечение битов (логическое умножение), чтобы выравнять биты по первому массиву */
    if ((b.s xor O.s)==0) L=L+1; /*проверка на совпадение всех битов с уже введенными. Операция xor обнуляет все одинаковые биты*/
}
cout<<L;
    return 0;
}
Например, для входных данных:
5 3
1 1 0
0 1 1 0 1
получим: n=5, k=3
t.s =         00000111
O.s =         00000110
для 4-х введенных чисел второго массива:
b.s =         00000110
b.s&t.s =     00000110
b.s xor O.s = 00000000 равно 0.
Совпадение есть. 
Если добавить последнее число 1:
b.s =         00001101
b.s&t.s =     00000101
b.s xor O.s = 00000011 не равно 0.
Т.е. делаем как бы маску (шаблон) для проверки совпадающих битов, каждый раз добавляя справа новый бит после операции сдвига влево ( b.s=(b.s<<1)+a;) и удаляя (b.s=b.s&t.s;) левый не нулевой бит, выравнивая длину битов по заданному набору битов в исходном числе O.s.
Как будто смотрим в "шаблон" из дырочек (0 и 1) и пропускаем через него, как через "сито", ленту, состоящую так же из 0 и 1. При совпадении этих "дырочек" увеличиваем количество совпадений на 1 и продолжаем двигать ленту влево, пока не закончатся все "биты". (Немного напоминает ленту машины Тьюринга)

3. Тот же подход можно реализовать с использованием строк в Паскале, так как количество чисел в первом массиве не превосходит 100, что меньше максимально возможной длины строки 255:
var a,b:string;
    c:char;
    n,k,i,j,z,t:integer;
begin
  readln(n,k);
  a:='';
  z:=0;
 for i:=1 to  k do
 begin
   read(t);
   if t=1 then a:=a+'1' else a:=a+'0'; //собираем в строку без пробелов все числа - биты 0 или 1
 end;
 z:=0;//количество совпадений
 b:='';
 for i:=1 to k-1 do
 begin
   read(t);
   if t=1 then b:=b+'1' else b:=b+'0'; //собираем в строку без пробелов первые k-1 "бит"
 end;
 for i:=k to n do
 begin
   read(t);
   if t=1 then b:=b+'1' else b:=b+'0'; //добавим еще один "бит" до длины k
   if a=b then z:=z+1; // и проверим на совпадение с первым массивом
     delete(b,1,1); // удаляем первый слева "бит" и начинаем цикл заново
 end;
 writeln(z);
 readln;
end.

.

Задача B.

Это простая задача на длинную арифметику с учетом системы счисления. Для этого переводить число в десятичное и обратно не обязательно. Нужно проводить вычисления в системе счисления, определенной по максимальной "цифре" числа. Пример программы на Паскале:
program taskb;
const alf='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
{занесем все возможные "цифры" числа - по этой строке определим систему счисления}
 var s,q:string;
   b,len,p,i,d,a:integer;

begin
   readln(s);
   len:=length(s);
   p:=2;
   i:=length(alf);{начинаем смотреть с последнего символа алфавита}
   while pos(alf[i],s)=0 do dec(i); { как только какой-то символ будет в данном числе запомним эту позицию в переменную i - это и будет найденная система счисления}
p:=i;//система счисления
b:=0;//следующее число в произведении
d:=0;//в следующий разряд
q:='';//строка результата
for i:=len downto 1 do begin {начинаем умножать с последней цифры}
     a:=(pos(s[i],alf)-1)*2;{определяем ее значение и умножаем на 2}
     b:=(a+d) mod p; {складываем полученное число с перенесенным разрядом от предыдущего умножения и определяем какое число останется, используя операцию mod p}
     d:=(a+d) div p;{определяем какое число перенесем в следующий разряд}
     q:=alf[b+1]+q;{собираем "цифру" в системе счисления р в строку q, добавляя к строке слева}
   end;
   repeat {если еще есть что-то в d, то переводим это число в систему счисления p}
   if d<>0 then q:=alf[d mod p + 1]+q;
   d:=d div p;
   until d=0;
   writeln(q); {вывод результата}
end.

Задача C.

Задача на правильный ввод строк (фамилия и имя), подсчет совпадений по каждой строке и сортировка по двум критериям: вначале по количеству совпадений по убыванию, затем, если количество совпадений совпадает, то по фамилии и имени по возрастанию. При выводе нужно учесть до какого числа совпадений делать вывод, если такого числа нет, то выводим "No truants".
Пример программы на С++ с использованием ввода-вывода в файл:
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
int main()
{ int f,i,j,n,k,m=0,maxa=0,a;
ifstream cin("input.txt"); //переопределяем стандартный ввод и вывод в файл
ofstream cout("output.txt");
    cin >> n >>k;
    string ss,s1,s2,s[n];
    int A[n];

    for (i=0;i<n;i++)
    {
        cin>>s1>>s2;
        ss=s1+" "+s2;
        f=0; for (j=0;j<m;j++) if (s[j]==ss){f=1;++A[j];break;}//проверка совпадений
//если нет, то добавляем строку в массив
        if (f==0)
       {
            A[m]=1;
            s[m]=ss;
            ++m;
       }
    }
//сортировка пузырьком
     f=1;
     for (i=0;i<m-1 && f; i++){
     f:=0; /* для быстроты сортировки добавим переменную f, если ни одна  проверка не прошла и ничего не поменяли, то массив отсортирован и в дальнейших шагах не нуждается */
     for (j=0;j<m-1-i;j++)
          if (A[j]<A[j+1]){f=1;ss=s[j];s[j]=s[j+1];s[j+1]=ss;a=A[j+1];A[j+1]=A[j];A[j]=a;}
                else
                if ((A[j]==A[j+1]) && (s[j]>s[j+1])){
                    f=1; ss=s[j];s[j]=s[j+1];s[j+1]=ss;a=A[j+1];A[j+1]=A[j];A[j]=a;}
    //вывод
     if (A[0]<k)
     {cout<<"No truants";return 0;}
     for (i=0;i<m;i++)
     if (A[i]>=k)
     cout<<s[i]<<" "<<A[i]<<endl;
    return 0;
}

Задача D.

Задача из ЕГЭ вариант С3 на динамическое программирование.

#include <iostream>
using namespace std;

void get_ans(int *table, int i)
// будем помечать каждое состояние игры числом
// четное число означает, что игрок, оказавшийся в этой позиции не может выиграть
// нечетное: игрок, оказавшийся в этой позиции имеет выигрышную стратегию
{
    if((table[i+2]%2 == 0)&&(table[i*2]%2 == 0)) //если любой шаг ведет к выигрышной позиции
    {
        table[i] = min(table[i+2], table[i*2]) + 1; //то выбираем скорешую победу
    }
    else if (table[i+2]%2 == 0) //если выигрышная команда +2
        {
            table[i] = table[i+2] + 1; //то выбираем ее
        }
        else if (table[i*2]%2 == 0) //если выигрышная команда *2
            {
                table[i] = table[i*2] + 1; //то выбираем ее
            }
            else //если все пути проигрышные
            {
                table[i] = max(table[i+2], table[i*2]) + 1; //то выбираем самый длинный
            }
}

int main()
{
    int s,n;
    cin >> s >> n;
    int *table = new int[(n+1)*2];
    for(int i=2*n; i>=n; i--)
    {
         table[i] = 0; //состояние от N и больше пометим числом 0 - это состояние победы
    }
    for(int i=n-1; i>0; i--) // заполняем таблицу состояний игры
    {
        get_ans(table, i);
    }

    if(table[s]%2 == 0)
    {
        cout << "Vasya" << endl << table[s]/2 << endl;
    }
    else
    {
        cout << "Petya" << endl << table[s]/2+1 << endl;
    }
    return 0;
}

Задача E.

Эту задачу можно решить с помощью волнового алгоритма поиска пути в лабиринте с учетом "стен" - когда король может быть бит пешкой. Сложность в правильном считывании данных и размещении стен на карте лабиринта. Пример программы на Паскале:
program taske;
var xn,yn,xk,yk:integer;
  map:array[0..9,0..9]of integer; //карта
  way:array[1..64,1..2]of integer;//путь
  i,j,k,st,dx,dy,kol,x,y:integer;
  a:char;
  procedure wave(xn,yn,xk,yk:integer);
  var k,x,y:integer;
  fl:boolean;
  begin
     map[xn,yn]:=1;
     k:=1;
     fl:=true;
     while fl do begin
     fl:=false;
     for x:=1 to 8 do
     for y:=1 to 8 do
      if map[x,y]=k then begin
         for dx:=-1 to 1 do
         for dy:=-1 to 1 do
          if map[x+dx,y+dy]=0 then begin
             map[x+dx,y+dy]:=k+1;
             fl:=true;
          end;
      end;
      if map[xk,yk]>0 then fl:=false else inc(k);
    end;
    end;
procedure track (xk,yk:integer);
var k,x,y:integer;
begin
  st:=1;
  way[1,1]:=xk;
  way[1,2]:=yk;
  k:=map[xk,yk]-1;
  x:=xk;
  y:=yk;
  while k>0 do begin
      for i:=-1 to 1 do
      for j:=-1 to 1 do
      if map[x+i,y+j]=k then begin
          x:=x+i;
          y:=y+j;
          inc(st);
          way[st,1]:=x;
          way[st,2]:=y;
          dec(k);
      end;
  end;
  end;

begin
   readln(a,yn);
   xn:=ord(a)-64;
   readln(a,yk);
   xk:=ord(a)-64;
   readln(kol);
   for i:=1 to kol do begin
      read(a,y);
      x:=ord(a)-64;
      map[x-1,y-1]:=-1;
      map[x+1,y-1]:=-1;
      read(a);
   end;
   for i:=0 to 9 do begin
      map[0,i]:=-1;
      map[9,i]:=-1;
      map[i,0]:=-1;
      map[i,9]:=-1;
   end;
   wave(xn,yn,xk,yk);
   if map[xk,yk]>0 then begin
      writeln(map[xk,yk]-1);
      track(xk,yk);
      for i:=st-1 downto 1 do
         write(chr(way[i,1]+64),way[i,2],' ');
   end else write('NO');
end.

Разбор задач с городской олимпиады от 05.12.2012

Задача А: Паркет

Ограничение по времени: 1 секунда
Ограничение по памяти: 16 Мб

В далекой заморской земле в самом большом здании города, представляющем собой прямоугольник размерами N´M, решено положить новый паркетный пол. После продолжительных обсуждений на всеобщем городском совете был, наконец, одобрен следующий проект: фигурками вида (только такие паркетные доски и производит местная паркетная фабрика):
 уложить вот такой рисунок (рисунок начинается с левого верхнего угла):

Ясно, что некоторые из приобретенных фигурок при укладке рисунка придется распилить. При этом возможно, некоторые части, на которые разделили фигурку, не будут участвовать в формировании рисунка. Вам необходимо определить минимальное количество фигурок требующих распила. Например, если размеры здания 3x4, то можно будет уложить 2 целых фигурки, а еще одну придется распилить. На рисунке ниже части, на которые распилили дополнительную фигурку, закрашены серым цветом.
Формат входного файла: В единственной строке входного файла содержатся два натуральных числа N и M, не превосходящие 109 – размеры прямоугольника, который необходимо замостить указанными фигурками.
Формат выходного файла: Необходимо вывести одно целое число – количество фигурок, которые придется распилить при укладке рисунка.
Пример:
parket.in
parket.out
3 4
1


Задача В: Словарь

Ограничение по времени: 1 секунда
Ограничение по памяти: 16 Мб

В языке одного из племен, затерянных на марсианских просторах, все слова одной и той же длины N, причем буквы в каждом слове попарно различны. В алфавите этого племени насчитывается N букв. Ученые-марсологи выяснили, что в словарь входят все возможные перестановки из N букв.
Переводчик в своем походном марсианско-русском словаре обозначает первую букву марсианского алфавита за «A», вторую за «B» и так далее (N не превосходит 20). Разумеется, слова в словаре упорядочены по алфавиту. И когда он встречает в какой-нибудь марсианской книге редко используемое слово, ему приходится долго листать словарь в поисках перевода. Помогите переводчику по марсианскому слову определить его порядковый номер в словаре.
Формат входного файла: В первой строке файла записано натуральное число N, не превосходящее 20, - длина слова. Следующая строка содержит марсианское слово для перевода. Слово состоит из заглавных латинских букв.
Формат выходного файла: Необходимо вывести одно целое число – порядковый номер этого слова в марсианско-русском словаре.
Примеры:
slovar.in
slovar.out
3
ABC
1
3
BCA
4


Задача C: Школа

Ограничение по времени: 1 секунда
Ограничение по памяти: 64 Мб

В школе некоторые из ребят хотели бы перейти из своего класса в другой, параллельный. Однако сделать это можно только в том случае, если кто-то из учеников этого класса также решит сменить класс – и освободит, таким образом, место. Скажем, ученик «10А» Антон сможет перейти в «10Г», если, например, Вера из «10Г» захочет перейти в «10Б», а Лена из «10Б» – в «10А».
Вам известны предпочтения ребят (ровно одно для каждого ученика). Необходимо определить длину максимальной цепи переходов учеников из класса в класс. Например, в разобранном выше случае длина цепи переходов составляет 3.
Формат входного файла: В первой строке входного файла задано количество N учеников, желающих перейти в другой класс. Каждая из следующих N строк состоит из имени ученика, буквы класса (отделенной от имени одним пробелом), в котором он учится, и отличной от нее буквы класса (также отделенной одним пробелом), куда хочет перейти. Используются только латинские буквы. Буквы класса – прописные. Длина имени ученика не превосходит 20.
Формат выходного файла: Одно целое число – длина максимальной цепи переходов.
Пример:
school.in
school.out
5
Anton A G
Petr G A
Roma B V
Vera G B
Lena B A
3

Примечание. В приведенном примере возможны две цепочки переходов:
1. Anton из A в GPetr из G в A – цепочка длины 2;
2. Anton из A в GVera из G в BLena из B в A – цепочка длины 3.

Задача D: Детали

Ограничение по времени: 1 секунда
Ограничение по памяти: 16 Мб

Имеется N кг металлического сплава. Из него изготавливают заготовки массой K кг каждая. После этого из каждой заготовки вытачиваются детали массой M кг каждая (из каждой заготовки вытачивают максимально возможное количество деталей). Если от заготовок после этого что-то остается, то этот материал возвращают к началу производственного цикла и сплавляют с тем, что осталось при изготовлении заготовок. Если того сплава, который получился, достаточно для изготовления хотя бы одной заготовки, то из него снова изготавливают заготовки, из них – детали и т.д.
Напишите программу, которая вычислит, какое количество деталей может быть получено по этой технологии из имеющихся исходно N кг сплава.
Формат входного файла: В файле через пробел записаны 3 целых числа: N, K, M. Все числа натуральные и не превосходят 108.
Формат выходного файла: Выведите одно число — количество деталей, которое может получиться по такой технологии.
Пример:
detali.in
detali.out
14 5 3
4



Приведу программы на Си для решения задач, рекомендованных для проверки и подготовленные Н. А. Гейдаровым:

Задача A: Паркет

#include <stdio.h>
int main()
{
freopen("parket.in", "r", stdin);
freopen("parket.out", "w", stdout);
int a, b;
scanf("%d", &a);
scanf("%d", &b);
long long N = a, M = b;


// Количество фигурок, укладывающихся в рисунок
/*
long long count = 0;
if((N<2)||(M<3))
{
printf("%d\n", count);
return 0;
}
if(M<=N)
{
long long diag = (N-M)/4 + 1;
//printf("%d\n", diag*(M-2));
count += diag*(M-2);
long long lim = (M-2)/4;
if( (M-2)%4 == 0 )
--lim;
//printf("%d\n", (M-2)*lim - 4*lim*(lim+1)/2);
count += (M-2)*lim - 4*lim*(lim+1)/2;
long long t = (M-1) - ( 4-(N-M)%4 );
if(t>0)
{
lim = t / 4;
if( t%4 == 0 )
--lim;
//printf("%d\n", t*(lim+1) - 4*lim*(lim+1)/2);
count += t*(lim+1) - 4*lim*(lim+1)/2;
}
}
else
{
long long diag = (M-N)/4 + 1;
//printf("%d\n", diag*(N-1) - ((M-N)%4==0?1:0));
count += diag*(N-1) - ((M-N)%4==0?1:0);
long long lim = (N-1)/4;
if( (N-1)%4 == 0 )
--lim;
//printf("%d\n", (N-1)*lim - 4*lim*(lim+1)/2);
count += (N-1)*lim - 4*lim*(lim+1)/2;
long long t = (N-2) - ( 4-(M-N)%4 );
if(t>0)
{
lim = t / 4;
if( t%4 == 0 )
--lim;
//printf("%d\n", t*(lim+1) - 4*lim*(lim+1)/2);
count += t*(lim+1) - 4*lim*(lim+1)/2;
}
}
printf("%d\n", count);
return 0;
*/
long long count = 0;
if(!((N<2)||(M<3)))
{
if(M<=N)
{
long long diag = (N-M)/4 + 1;
count += diag*(M-2);
long long lim = (M-2)/4;
if( (M-2)%4 == 0 )
--lim;
count += (M-2)*lim - 4*lim*(lim+1)/2;
long long t = (M-1) - ( 4-(N-M)%4 );
if(t>0)
{
lim = t / 4;
if( t%4 == 0 )
--lim;
count += t*(lim+1) - 4*lim*(lim+1)/2;
}
}
else
{
long long diag = (M-N)/4 + 1;
count += diag*(N-1) - ((M-N)%4==0?1:0);
long long lim = (N-1)/4;
if( (N-1)%4 == 0 )
--lim;
count += (N-1)*lim - 4*lim*(lim+1)/2;
long long t = (N-2) - ( 4-(M-N)%4 );
if(t>0)
{
lim = t / 4;
if( t%4 == 0 )
--lim;
count += t*(lim+1) - 4*lim*(lim+1)/2;
}
}
}
long long ans = (M*N)/4 - count;
if( (M*N)%4 )
++ans;
//printf("%lld\n", count);
printf("%lld\n", ans);
return 0;
}

Задача В: Словарь

#include <stdio.h>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

unsigned long long numP(int N, int *s)
{
set<int> letters;
vector<int> counts(N);

for(int i=0; i<N; ++i)
{
int t = 0;
for(int k=1; k<s[i]; ++k)
{
if( letters.find(k) == letters.end() )
++t;
}
letters.insert(s[i]);
counts[i] = t;
}

unsigned long long p = 1;
unsigned long long sum = 0;
for(int i=N-2; i>=0; --i)
{
sum += p*counts[i];
p *= N-i;
}
return sum+1;
}

int main()
{
freopen("slovar.in", "r", stdin);
freopen("slovar.out", "w", stdout);

int N;
scanf("%d\n", &N);
unsigned char c;
unsigned char t = 'A';
int *a = new int [N];
for(int i=0; i<N; ++i)
{
scanf("%c", &c);
a[i] = c-t+1;
}
printf("%lld\n", numP(N,a));

/*
for(int N = 1; N<24; ++N)
{
int *a = new int [N];
for(int i=0; i<N; ++i)
a[i] = N-i;
printf("%d: %lld\n", N, numP(N,a));
delete [] a;
}
*/
return 0;
}

Задача С: Школа

#include <stdio.h>
#include <vector>
#include <map>
using namespace std;

typedef vector<int> list;
list *klass;
int *color;
int *level;
int m;

void dfs(int v)
{
color[v] = 1;
for(size_t i=0; i<klass[v].size(); i++)
{
int u = klass[v][i];
if(color[u]==0)
{
level[u] = level[v] + 1;
dfs(u);
}
else if(color[u]==1)
{
if(level[v]-level[u]+1>m)
m = level[v]-level[u]+1;
}
}
color[v] = 2;
}

int main()
{
freopen("school.in", "r", stdin);
freopen("school.out", "w", stdout);

int N;
scanf("%d", &N);
m = 0;

klass = new list [N];
color = new int [N];
level = new int [N];
char s[25];
map<char,int> soot;
int count = 0;
for(int i=0; i<N; ++i)
{
scanf("%s", &s);

scanf("%s", &s);
char c1 = s[0];
if( soot.find(c1)==soot.end() )
soot[c1] = count++;

scanf("%s", &s);
char c2 = s[0];
if( soot.find(c2)==soot.end() )
soot[c2] = count++;

klass[soot[c1]].push_back(soot[c2]);
}

/*
for(int i=0; i<N; ++i)
{
for(size_t j=0; j<klass[i].size(); ++j)
printf("%d ", klass[i][j]);
printf("\n");
}
*/

for(int i=0; i<N; ++i)
{
for(int j=0; j<N; ++j)
{
color[j] = 0;
level[j] = 0;
}
dfs(i);
}
printf("%d\n", m);

delete [] klass;
delete [] color;
delete [] level;
return 0;
}

Задача D: Детали

#include <stdio.h>

int main()
{
freopen("detali.in", "r", stdin);
freopen("detali.out", "w", stdout);
int N, K, M;
scanf("%d", &N);
scanf("%d", &K);
scanf("%d", &M);

int ost = N;
int count = 0;
int zag, det, ost1, ost2;
while(zag = ost/K)
{
ost1 = ost%K;
det = K/M;
if(det==0)
break;
ost2 = K%M;
count += zag*det;
ost = ost1+ost2*zag;
}
printf("%d\n", count);
return 0;
}

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

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