Интеллектуальный марафон. Информатика. Задачи личного тура

                                                                  Автор задач - Езовских В.Е.  

Разбор - Котелина Н.О.

1.  Арифметическая прогрессия

Старуха Шапокляк предложила Чебурашке N (3 <= N <= 100) натуральных чисел A_i (i = 1..N, A_i < 2014, все A_i различны). Помогите ему найти длину самой длинной арифметической прогрессии, которую можно сформировать, используя некоторые из чисел A_i.

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

Целое число N и N строк, в которых записаны N чисел A_i.

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

Целое число, равное длине самой длинной арифметической прогрессии.

Пример

input	output
5 10 4 5 15 2	3

 

РАЗБОР

Отсортируем последовательность чисел A[1],…, A[n] по возрастанию. Всем натуральным числам от 1 до A[n] сопоставим логические значения: b[i]=true, если число i входит в исходный набор и b[i]=false иначе.  Вычислим максимальную длину прогрессии Max.  Переберем всевозможные разности q (от 1 до A[n]-A[1]) арифметических прогрессий, которые можно сформировать из исходного набора.  Для каждой разности перебираем все A[i] в качестве потенциальных первых членов арифметической прогрессии. Для данного A[i] считаем длину L арифметической прогрессии с разностью q, с первым членом A[i]: в нее должны входить числа A[i]+q, A[i]+2q и т.д., поэтому перебираем элементы массива b с индексами A[i]+j*q, начиная с j=1: пока (A[i]+j*q<=A[n]) и  (b[A[i]+j*q]=true), L увеличиваем на 1, j увеличиваем на 1. Ответом будет максимум из всевозможных L. 

РЕШЕНИЕ

const

        MN=100;

        MA=2014;

var

        i, j, k, n, aa, q, l, lm:integer;

        a:array[1..MN] of integer;

        b:array[1..MA] of boolean;

begin

        readln(n);

        for i:=1 to n do begin readln(a[i]) end;

        for i:=1 to n-1 do for j:=i+1 to n do if (a[i]>a[j]) then begin

                k:=a[i]; a[i]:=a[j]; a[j]:=k

        end;

        aa:=a[n];

        lm:=2; for i:=1 to aa do b[i]:=FALSE; 

               for i:=1 to n do b[a[i]]:=TRUE;

        for q:=1 to aa-a[1] do  for i:=1 to n-1 do begin

                k:=a[i]; l:=1;

                while (((k+q)<=aa) and b[k+q]) do begin

                        inc(l); inc(k,q)

                end;

        if (l>lm) then lm:=l end; writeln(lm);

end.

 

2. Прореживание

Крокодил Гена решил перейти на растительную диету и посадил морковку. Однако всходы оказали слишком густыми, и возникла необходимость их проредить. Гена загадал натуральное число N (2 <= N <= 9) и придумал оптимальный с его точки зрения алгоритм выдергивания. Суть алгоритма состоит в следующем:

            1. Задаем M, равное 2.

            2. Нумеруем все ростки натуральными числами, начиная с единицы.

            3. Выдергиваем все ростки, номер которых делится на M.

            4. Увеличиваем M на единицу.

            5. Если M не превосходит N, переход на шаг 2, иначе – конец процесса.

После прореживания на грядке осталось S (1 <= S <= 1000) ростков моркови. Найдите точный диапазон, в котором может находиться число ростков моркови перед началом процедуры прореживания.

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

Две строки. В первой записано число N, во второй – число S.

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

Интервал, в котором находилось число ростков до прореживания.

Пример

input	output
4 5	[15,18]

РАЗБОР

Пусть [si,sa] –  диапазон значений числа ростков после i-го прореживания (при котором выдергиваются все i-е ростки), тогда после последнего прореживания si=sa=s. Будем последовательно производить «откаты», пока не узнаем, чему равнялись si, sa перед первым прореживанием. Как i-е прореживание изменяет нижнюю границу диапазона si? Пусть до прореживания было si_old, а после стало si_new, тогда si_new=si_old - si_old div i. Значит,

si_old=si_new+ si_old div i.  Понятно, что si_new=(i-1) (si_old div i)+ (si_old mod i).

Тогда  si_old div i=( si_new- si_old mod i) div (i-1). Получаем соотношение

si_old= si_new+(si_new- si_old mod i) div (i-1). Теперь, чтобы минимизировать si_old, надо  выбрать

максимально возможное si_old mod i. Это будет  (i-1), если si_new делится на i-1, и это будет

si_new mod (i-1), иначе. Тогда получаем следующее рекуррентное соотношение при i=n,n-1,…,2:

si_old=si_new+si_new div (i-1)-1, si_new делится на i-1,

si_old=si_new+(si_new-si_new mod (i-1)) div (i-1), si_new не делится на i-1.

Можно эти формулы объединить в одну:

si_old=si_new+(si_new-1) div (i-1).

Аналогично находится sa.

РЕШЕНИЕ

var

        i, n, s, si, sa:integer;

begin

       

        readln(n); readln(s);

        si:=s; sa:=s;

        for i:=n downto 2 do begin

                inc(si,(si-1) div (i-1));

                inc(sa,(sa-1) div (i-1));

                if (((sa+1) mod i)=0) then inc(sa)

        end;

        writeln('[',si,',',sa,']');

end.

 

3. По грибы

Крокодил Гена, разнообразя морковное меню, пошел по грибы. Поиск производится на координатной плоскости под названием Белый Бор, причём точкой старта является начало координат. Свой первый и последний подосиновик Крокодил Гена нашёл после N (1 <= N <= 1000000000) шагов. Первый шаг был в точку с координатами (1,0), каждый последующий шаг был на единицу длиннее и осуществлялся в направлении 90 градусов против часовой стрелки по отношению к направлению предыдущего шага. А именно, последовательные координаты Крокодила Гены таковы:

(0, 0), (1, 0), (1, 2), (-2, 2), (-2, -2), (3, -2) …

Вам нужно выяснить координаты подосиновика для заданного N.

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

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

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

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

Пример

input	output
5	3 -2

РАЗБОР

Найдем x. Если считать, что i-ый шаг определяется вектором (x_i,y_i), то

последовательность шагов выглядит так:

(1,0), (0,2),(-3,0), (0,-4),(5,0),(0,6),(-7,0),(0,-8),…

Тогда частичные суммы  x_i, y_i первых n членов этой последовательности равны:

 S_xn=1+0-3+0+5+0-7+…+x_n=(-1)^(n-1)div2*(n+1) div 2,

S_yn=0+2+0-4+0+6+0-8+…+y_n=2*(0+1+0-2+0+3+0-4+…+y_n/2)=(-1)^(n-2)div2 *2*(1+(n-2) div 4).  

РЕШЕНИЕ

var

        n, x, y:longint;

begin

        readln(n);

        x:=(n+1) div 2;

        if (odd((n-1) div 2)) then x:=-x;

        if (n=1) then y:=0 else begin

                y:=2*(1+(n-2) div 4);

                if (odd((n-2) div 2)) then y:=-y

        end;

        writeln(x,' ',y);

end.

4. Есть ли квадрат числа?

Чебурашка учится извлекать квадратные корни из натуральных чисел. У него есть N (2 <= N <= 8) карточек, на которых написаны цифры, отличные от нуля. Он перекладывает карточки, получая различные N-значные числа. Например, при N = 3 и цифрах на карточках 7, 2 и 9 Чебурашка может составить числа 729, 792, 279, 297, 927 и 972. Сможет ли он получить квадрат целого числа?

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

Строка, в которой записаны цифры на карточках.

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

Строка ‘YES’ или ‘NO’ в зависимости от того, смог ли Чебурашка получить квадрат целого числа.

Пример

input	output
31212	YES
818	NO

РАЗБОР

Найдем минимальное ni и максимальное na из всевозможных чисел, которые можно получить с помощью карточек. Для этого применим сортировку подсчетом: массив A заполним так: A[i], i=1..9, -- количество карточек c номером i, тогда ni=1..1..9..9, na=9..9..1..1, где 1 встречается A[1] раз, 2 встречается A[2] раза и т.д.. Тогда, если на одной из карточек записан квадрат числа b, то b больше либо равен квадратного корня j из ni , и не превосходит квадратного корня ja из na.   Переберем  целые числа из диапазона [j,ja], проверяя, можно ли квадрат числа, равный n, составить с помощью карточек (применяя сортировку подсчетом, вычисляем b[i]— количество цифр в числе n, равных i, сравниваем b[i] и A[i] для всех i).

РЕШЕНИЕ 

type

        arr=array[0..9] of integer;

var

        i, j, ja, n, ni, na, t:longint;

        a, b:arr;

        z:boolean;

begin

        readln(n);

        for i:=1 to 9 do a[i]:=0;

        while (n<>0) do begin inc(a[n mod 10]); n:=n div 10 end;

        ni:=0; na:=0;

        for i:=1 to 9 do for j:=1 to a[i] do ni:=10*ni+i;

        for i:=9 downto 1 do for j:=1 to a[i] do na:=10*na+i;

        j:=trunc(sqrt(ni));

        ja:=trunc(sqrt(na));

        z:=TRUE;

        while (z and (j<=ja)) do begin

                for i:=1 to 9 do b[i]:=0; n:=sqr(j);

                while (n<>0) do begin 

                  inc(b[n mod 10]); 

                  n:=n div 10 

                end;

                t:=0;

                for i:=1 to 9 do inc(t,abs(a[i]-b[i]));

                z:=(t<>0);

                inc(j)

        end;

        if (z) then writeln('NO') else writeln('YES');

end.

5. Путешествие Чебурашки.

Чебурашка решил отправиться в путешествие по городам Африки. Как вы знаете, названия городов на карте Африки весьма забавные и странные. Всего на карте имеется N (2 <= N <= 16) городов и название каждого записано прописными буквами ‘A’..’Z’, например – INTERNET. Старуха Шапокляк на правах спонсора установила жесткие правила путешествия: в каждом городе можно побывать лишь один раз и из одного города можно проехать в другой только в том случае, если в их названиях есть одинаковые буквы. Путешествие начинается из города, записанного первым в списке. Сможет ли Чебурашка разработать маршрут с посещением всех городов?

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

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

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

Строка ‘YES’, если Чебурашка смог составить маршрут путешествия и строка ‘NO’ в противном случае.

Пример

input	output
4 ASSA TRUST FATRAT UGUUGU	YES

6.  Интересное расстояние

Как известно, основными элементами головы Чебурашки являются три круга – лицо, правое и левое ухо. Как установил Крокодил Гена, все эти три круга имеют одинаковый радиус R, равный одному метру, и центры кругов расположены на одной прямой. Гену заинтересовал вопрос о том, каково расстояние между центрами ушей Чебурашки. Несмотря на уговоры, Чебурашка упорно сопротивлялся прямым измерениям. Тогда Крокодил Гена измерил отношение площади головы Чебурашки в квадратных метрах к числу pi=3.1415926.. и получил значение, равное S (ясно, что значение S лежит в интервале [1,3]). Вам нужно по S восстановить расстояние между центрами ушей Чебурашки.

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

Число S, полученное Крокодилом Геной.

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

Расстояние между центрами ушей Чебурашки в метрах, вычисленное с точностью до одного миллиметра.

Пример

input	output
2.16	1.896

РАЗБОР

Площадь головы Чебурашки  равна Q=3pR²-2x, где x— площадь фигуры F, полученной в результате пересечения уха и лица. Тогда на входе имеем соотношение S=3R²-2x/p=3-2x/p. Значит,  x=p(3-s)/2. Можно рассматривать только половину F, лежащую над прямой, соединяющей центры лица и ушей. Площадь этой фигуры равна b:=x/2=p(3-s)/4. Площадь b=2(S(сектора ABC)-S(треугольника ABD)) =2(a/2-cos(a)sin(a)/2)= a-sin(2a)/2.

Ответом на задачу будет выражение  4Rcos(A) (см. рис.), где  угол A можно найти в результате двоичного поиска. Начальный диапазон, в котором находится A, равен [0,p/2] (если A=0, то уши касаются лица, если A=p/2, то уши совпадают с лицом). В процессе поиска, если диапазон, в котором находится A, равен [ai, aa], то рассматриваем середину диапазона am, сравниваем с нулем выражение b-am+sin(2am)/2, в зависимости от знака берем либо левую половину диапазона [al,am], либо правую [am,ar]). Поиск продолжается до тех пор, пока длина aa-ai>eps.

const

        R=1.0;

        ERROR=1E-10;

var

        s, a, ai, aa, b, f, x:real;

begin

        readln(s);

        b:=Pi*(3-s)/4;

        ai:=0.0;

        aa:=Pi/2;

        while ((aa-ai)>=ERROR) do begin

                a:=(ai+aa)/2;

                f:=b-a+sin(2*a)/2;

                if (f>0) then ai:=a else aa:=a

        end;

        x:=4*R*cos(a);

        writeln(x:5:3);

end.