МУНИЦИПАЛЬНЫЙ ЭТАП ВСЕРОССИЙСКОЙ ОЛИМПИАДЫ ШКОЛЬНИКОВ ПО ИНФОРМАТИКЕ В 2013-2014 УЧЕБНОМ ГОДУ ДЛЯ УЧАЩИХСЯ 9-11 КЛАССОВ

Максимальное время выполнения всех заданий: 240 минут

Ограничение по времени на каждый тест: 1 секунда

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

Задача 1. Участники Олимпийских игр

Максимальное количество баллов: 20  

За много лет проведения Олимпийских игр установлена необычная закономерность. Если в церемонии открытия игр принимают участие  N спортсменов, то сумму затрат на проведение олимпиады можно найти по следующему правилу: изменяется порядок цифр числа N на противоположный (например, число 123 превращается в 321, а число 120 – в 21) и к исходному прибавляется полученное число. Если результат не является палиндромом, то процедуру необходимо повторять, пока не получим палиндром. Если же исходное число N само является палиндромом, указанная процедура не потребуется, так как в этом случае сумма затрат численно будет равна количеству участников.

 Например, если количество участников равно 195, то получим 9339 после четвертого сложения:

 195  +  591  =  786,

 786  +  687  = 1473,

1473 + 3741 = 5214,

5214 + 4125 = 9339.

Специальной комиссии необходимо узнать требуемую сумму затрат на проведение Олимпийских игр по заданному количеству участников церемонии открытия.

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

В единственной строке указано одно целое число N - количество участников церемонии открытия Олимпийских игр. Известно, что минимальное число участников составляет 1, а максимальное равно 109.

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

Необходимо вывести строку, содержащую одно число – сумму затрат на проведение игр. Если указанная процедура не приведет к палиндрому за 1000 шагов, то вывести строку «No solution».

Пример

Задача 2. Праздничный торт

Максимальное количество баллов: 20  баллов

На Олимпийских играх готовятся к большому сладкому праздничному пиру. Для каждого участника выпекаются мини-торты круглой формы. Однако тарелки участников представляют собой правильные n-угольники. Если совместить центр тарелки и центр торта, то углы тарелок будут лежать на окружности торта, но часть торта «провиснет» и не достанется участнику.

Организаторы Олимпийских игр решили обрезать каждый мини-торт по форме соответствующей тарелки. Необходимо посчитать «убытки» кондитеров – площадь обрезков.

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

В первой строке располагаются два числа, разделенных пробелом: N – число сторон в многоугольнике (3 ≤ N ≤ 100), a – длина стороны многоугольника выраженная в миллиметрах (1 ≤ a ≤ 1000).

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

Выводится одно число – площадь в квадратных миллиметрах со всех обрезанных мини-тортов с точностью до 4 знаков после запятой.

Пример

Задача 3. Судейские оценки

Максимальное количество баллов: 30  

На Олимпийских играх собираются запустить новую систему автоматического сбора информации об оценках судей. Специальная камера, установленная в стадионе, делает фотографию в тот момент, когда судьи поднимают таблички с оценками. Сами оценки – это числа от 0 до 9 включительно.

Сделанная фотография пересылается в модуль распознавания, где на первом этапе выделяются пиксели, содержащие цифры, а на втором этапе происходит собственно распознавание цифр и предоставление отчета.

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

На вход программы подается матрица пикселей размерами , заполненная символами «.» (точка) и «*» (звездочка). Точки обозначают отфильтрованный шум, а звездочки – элементы цифр.

Сами цифры выглядят следующим образом.

Судьи сидят достаточно далеко друг от друга, поэтому соседние цифры не перекрываются, то есть между крайним правым столбцом матрицы, содержащим элементы одной цифры, и крайним левым столбцом, содержащим элементы другой цифры, находится по крайней мере один столбец, содержащий только символы «.» (точка). Однако судьи могут держать свои таблички на разной высоте.

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

В первой строке находятся два числа, разделенных пробелом: число строк N и число столбцов M матрицы пикселей, ,. Далее располагается матрица символов «.» или «*» размерами .

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

В первой строке необходимо поместить количество распознанных цифр K. В следующих K строках необходимо вывести распознанные цифры (по одной в каждой строке) в порядке их прочтения слева направо.

Пример

Задача 4. Футбольная команда

Максимальное количество баллов: 30

Главный тренер нашей футбольной команды должен отобрать несколько игроков для участия в Олимпийских играх. По мнению тренера для слаженной игры нашим футболистам может помочь лишь одно: необходимо выстроить их в шеренгу таким образом, чтобы их рост строго увеличивался, а вес строго уменьшался. Только такая команда сможет победить своих соперников!

Помогите главному тренеру найти максимальную длину последовательности игроков, удовлетворяющей этому свойству.

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

В первой строке указано общее количество футболистов N (1≤N≤1000). В каждой из N следующих строк располагается два целых числа, разделенных пробелом: рост футболиста в сантиметрах и его вес в килограммах (оба числа располагаются в пределах от 1 до 10000).

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

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

Пример

Пояснение к примеру

Максимальная последовательность содержит футболистов (в порядке увеличения роста) с номерами 1, 7, 6, 5. Эта последовательность не единственная.

Решения жюри

Задача 1

Длинная арифметика. Работа со строками.

#include <stdio.h>

#include <string.h>

void swap(char *&a, char *&b)

{

        char *t = a;

        a = b;

        b = t;

}

void summ(char *num, char *result)

{

        int

                len = strlen(num),

                s,

                t = 0;

        for(int i=0; i<len; ++i)

        {

                s = (num[i]-'0') + (num[len-1-i]-'0') + t;

                result[i] = s % 10 + '0';

                t = s / 10;

        }

        if(t==1)

                result[len] = '1';

        result[len+t] = 0;

}

bool isPalindrom(char *num)

{

        int

                len = strlen(num);

        bool

                f = true;

        for(int i=0; (i<len/2) && f; ++i)

                if(num[i]!=num[len-1-i])

                        f = false;

        return f;

}

int main()

{

        char

                *num = new char[2000],

                *res = new char[2000];

        FILE * f = fopen("input.txt", "r");

        fscanf(f, "%s", num);

        fclose(f);

        for(int k=0; (k<1000) && (!isPalindrom(num)); ++k)

        {

                summ(num, res);

                swap(num, res);

        }

        f = fopen("output.txt", "w");

        if( isPalindrom(num) )

                fprintf(f, "%s\n", num);

        else

                fprintf(f, "No solution\n");

        fclose(f);

        delete [] num;

        delete [] res;

        return 0;

}

Задача 2

Геометрическая задача. Работа с вещественными числами.

#include <math.h>

#include <iostream>

#include <stdio.h>

#define M_PI                3.14159265358979323846

using namespace std;

int main()

{

    long int i, k,n,a;

    long double r,s1,s2,s;

        cin>>n>>a;

        r=a/sin(M_PI/n)/2;

        s1=n*r*r*sin(2*M_PI/n)/2;

        s2=M_PI*r*r;

        s=(s2-s1);

    cout.flags(ios::fixed);

    cout.precision(4);

    cout<<s;

    return 0;

}

Задача 3

Обработка массива. Поиск в ширину (волновой алгоритм)

#include <stdio.h>

#include <vector>

using namespace std;

int main()

{

        FILE *f = fopen("input.txt", "r");

        int N, M;

        fscanf(f, "%d", &N);

        fscanf(f, "%d", &M);

        N+=2;

        M+=2;

        char **field = new char*[N];

        for(int i=0; i<N; ++i)

        {

                field[i] = new char [M];

                for(int j=0; j<M; ++j)

                        field[i][j] = '.';

        }

        char str[100];

        for(int i=1; i<N-1; ++i)

        {

                fscanf(f, "%s", str);

                for(int j=1; j<M-1; ++j)

                        field[i][j] = str[j-1];

        }

        vector<int> nums;

        for(int jpos=0; (jpos<M); ++jpos)

                for(int ipos=0; (ipos<N); ++ipos)

                {

                        if(field[ipos][jpos] == '*')

                        {

                                if( (field[ipos-1][jpos+1] == '*') && (field[ipos+1][jpos] == '*') && (field[ipos+2][jpos+2] == '.') )

                                        nums.push_back(0);

                                else if( (field[ipos-1][jpos+1] == '*') && (field[ipos-2][jpos+2] == '*') )

                                        nums.push_back(1);

                                else if( (field[ipos-1][jpos+1] == '*') && (field[ipos+4][jpos+3] == '.') )

                                        nums.push_back(2);

                                else if( (field[ipos-1][jpos+1] == '*') && (field[ipos+1][jpos] == '.') )

                                        nums.push_back(3);

                                else if( (field[ipos-1][jpos+1] == '.') && (field[ipos+6][jpos] == '.') )

                                        nums.push_back(4);

                                else if( (field[ipos-1][jpos+1] == '.') && (field[ipos+5][jpos] == '.') )

                                        nums.push_back(5);

                                else if( (field[ipos+2][jpos] == '*') )

                                        nums.push_back(6);

                                else if( (field[ipos-1][jpos+1] == '.') )

                                        nums.push_back(7);

                                else if( (field[ipos+2][jpos+3] == '.') )

                                        nums.push_back(8);

                                else

                                        nums.push_back(9);

                                jpos+=4;

                                break;

                        }

                }

        f = fopen("output.txt", "w");

        fprintf(f, "%d\n", nums.size());

        for(int i=0; i<nums.size(); ++i)

                fprintf(f, "%d\n", nums[i]);

        fclose(f);

        return 0;}

Задача 4

Динамическое программирование

#include <stdio.h>

#include <vector>

#include <utility>

#include <algorithm>

using namespace std;

int main()

{

        vector< pair<int,int> > foot;

        vector<int> max;

        int N;

        FILE *f = fopen("input.txt", "r");

        fscanf(f, "%d", &N);

        for(int i=0; i<N; ++i)

        {

                pair<int,int> a;

                fscanf(f, "%d", &a.first);

                fscanf(f, "%d", &a.second);

                foot.push_back(a);

        }

        fclose(f);

        sort( foot.begin(), foot.end() );

        for(int i=0; i<foot.size(); ++i)

        {

                max.push_back(1);

                for(int j=0; j<i; ++j)

                {

                        if( (foot[i].second<foot[j].second) && (max[j]+1>max[i]) )

                                max[i] = max[j]+1;

                }

        }

        f = fopen("output.txt", "w");

        fprintf( f, "%d\n", *max_element( max.begin(), max.end() ) );

        fclose(f);

        return 0;}

Решение на Паскале

var a,b:array [1..1000] of integer;

c:array [0..1001,0..1001]of integer;

i,n,max,j:integer;

finput:text;

begin

assign(finput,'input.txt');reset(finput);

readln(finput,n);

for i:=1 to n do

readln(finput,a[i],b[i]);

for j:=1 to n-1 do

for i:=1 to n-j do

if a[i]>a[i+1] then begin

max:=a[i];a[i]:=a[i+1];a[i+1]:=max;

max:=b[i];b[i]:=b[i+1];b[i+1]:=max;

end;

for i:=0 to n+1 do

for j:=0 to n+1 do

c[i,j]:=1;

for j:=1 to n do

begin

for i:=j+1 to n do

begin

if (b[i]<b[j]) and (a[i]<>a[j]) then begin

if c[j,j]+1>c[i,j-1]  then c[i,j]:=c[j,j]+1

else

  c[i,j]:=c[i,j-1];

end

else c[i,j]:=c[i,j-1];

c[j,i]:=c[i,j];

end;

c[j+1,j+1]:=c[j+1,j];

end;

max:=1;

for i:=1 to n do

begin

for j:=1 to n do

begin if c[i,j]>max then max:=c[i,j];

end;

end;

{

for i:=1 to n do

begin

writeln(a[i],' ',b[i]);

end;

 }

writeln(max);

readln;

end.