Выходные данные
Файл Output.txt должен содержать число T – количество дней, через которое знаки вернутся в начальное положение. Гарантируется, что ответ не превышает 1012.
Пример:
-
Input.txt
Output.txt
10
10 9 8 7 6 5 4 3 2 1
2
Очевидно, что решение 'в лоб', заключающееся в построении очереди обмена символов и проверки совпадения с первоначальным их расположением, при данных ограничениях задачи будет не эффективным.
Заметим следующее: если взять некоторую позицию то символ на ней будет появляться периодически через некоторое количество дней, которое не больше, чем общее количество символов. Если же взять наименьшее общее кратное от всех периодов появления символов на каждой позиции то мы и получим ответ, который требуется в задаче. Ещё одной трудностью является то, что ответ может превышать maxlongint, поэтому нужно модернизировать стандартный алгоритм нахождения NOD следующим образом:
Function NOD(a,b:extended):extended;
Begin a:=a-(round(a/b)-1)*b;
While (a>0)and(b>0) do begin
if a>b then a:=a-trunc(a/b)*b else b:=b-trunc(b/a)*a;
end;
Nod:=A+B
End;
задачи
Задача 40 Период дроби нет решения
Найти длину периода и сам период бесконечной степенной дроби в системе счисления по основанию Р, представляющей рациональное число N/M (для конечных дробей считать, что длина периода равна 1, а сам период равен 0).
Входные данные:
входной файл Input.txt содержит в единственной строчке через пробел M,N,P -целые десятичные числа, 0<N<M<=100, 1<P<10.
Выходные данные:
выходной файл Output.txt содержит период дроби .
Введем переменную N1=N. Пусть N1 и M заданы в десятичной системе счисления. Переведем дробь N1/M в систему счисления с основанием p: Пусть в системе с основанием p искомая дробь 0.a(1)a(2)... Получаем: a(1)*p^(-1)+a(2)*p^(-2)+ ... =N1/M. Умножим правую и левую части
равенства на p: a(1)+a(2)*p^(-1)+ ... = N1*p/M. Выделяя целую часть выражений слева и справа от знака равенства, получаем a(1) = целая часть (N1*p/M). Обозначим N2 = N1*p mod M; очевидным образом получаем a(2)*p^(-1)+ ... = N2/M. Домножая на p и находя целую часть, опять же имеем a(2)=целая часть (N2*p/M); продолжая аналогично, определяем коэффициенты a(3), a(4) и т.д. В ходе выделения цифр ai мы можем получить различных значений Ni не более чем M (по алгоритму выше у нас всегда Ni<M). Если вдруг какие-то два остатка совпадают: Ni=Nj, i<>j, то совпадают и цифры разложения: a(i+1)=a(j+1), a(i+2)=a(j+2), ... , т.е. цифры (a(i+1), ... ,a(j)) образуют один из кратных периодов. Нам надо найти минимальную длину такой периодически повторяющейся последовательности, которая равна количеству цифр между двумя ближайшими повторяющимися остатками, и сами цифры.
Поступаем следующим образом: выделяем M цифр p-ичной дроби (исходя из вышесказанного, к этому моменту период уже обязан начаться). Запоминаем Nm, и ищем первый такой остаток Nk, k>m, что Nm=Nk. Величина k-m как раз и есть искомая длина периода, а цифры ak..am период.
задачи
Задача 41 Нахождение цифры
Определите, какая из цифр в десятичной записи всех простых чисел из заданного отрезка [a,b] встречается чаще всего. Если таких цифр несколько, найдите наименьшую из них. Известно, что в этом отрезке есть хотя бы одно простое число.
Входные данные:
В первой строке файла Input.txt находятся целые числа a и b (1<a<b<10000), разделенные пробелами.
Выходные данные:
В файле Output.txt должна быть записана искомая цифра.
Пример:
-
Input.txt
Output.txt
2 4
2
Переберем последовательно все числа от a до b. Если число простое, то справа налево перебираем его цифры и считаем их в массиве n. Потом пробегаем по массиву n и находим макимальное число. Оно и будет ответом.
Program findcifri;
var
a,b,i,max,maxn:integer;
n:array [1..10] of integer;
procedure add(m:longint);
var
begin
while m>0 do
begin]
inc(n[m mod 10]);
m:= m div 10;
end;
end;
function simple(p:longint):boolean;
var i:longint;
begin
simple:=false;
if p=2 then begin simple:=true;exit; end; если число =2 то оно простое,
выходим из функции
if (p=1)or(p mod 2=0) then exit; если число =1 или делится на 2
то оно не простое
i:=3; начинаем проверку с 3
while i<=SQRT(p) do проверяем все нечетные числа от 3 до
кв.корня из числа
if p mod i=0 если p делится на i, то оно не простое
then exit выходим из функции
else inc(i,2); иначе берем следующее нечетное
simple:=true если ни на какое число p не разделилось,
то число p простое
end;
begin
assign(input,'input.txt');
reset(input);
read(a,b);
close(input);
for i:=a to b do if simple(i) then add(i);
max:=0;
for i:=0 to 9 do
begin
if n[i]>= max then
begin
max:=n[i];
maxn:=i;
end;
end;
assign(output,'output.txt');
rewrite(output);
write(maxn);
close(output);
end.
задачи
Задача 42 Сумма
Рассмотрим сумму:
где n! обозначает произведение 1*2*3*...*n. Требуется написать программу, которая по заданным n и k определяет k-ю цифру десятичного разложения дробной части числа Sn.
Формат входных данных:
Входной файл Input.txt содержит две строки. В первой записано число n (2<n<=1000000000), во второй k (1<=k<=50000).
Формат выходных данных:
Выходной файл Output.txt должен содержать найденную цифру.
Input.txt |
Output.txt |
3 100 |
3 |
Преобразуем сумму следующим образом:
Таким образом, задача свелась к вычислению десятичного разложения 1/n!. Для получения k-ой десятичной цифры воспользуемся длинной арифметикой. При этом учтем, что первые цифры в десятичной записи дроби 1/n! при увеличении n становятся нулями. Эти соображения и реализованы в программе:
Program summa;
var
n, k, i, m, p, z : longint;
a : array [1..50000] of byte;
begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
readln(n,k);
z:=0; m:=2;
a[1]:=5; for i:=2 to k do a[i]:=0;
while (z<k) and (m<n) do
begin
m:=m+1;
p:=0;
for i:=z+1 to k do
begin
p:=p*10+a[i];
a[i]:=p div m;
p:=p mod m
end;
while (z<k) and (a[z+1]=0) do z:=z+1
end;
write(g,9-a[k]);
close(output)
end.
задачи
Задача 43 Роботландия Сообщество роботов живет по следующим законам:
- один раз в начале года они объединяются в группы по три или пять роботов;
- за год группа из 3 роботов собирает 5 новых, а группа из 5 роботов собирает 9 новых;
- роботы собираются так, чтобы собрать за год наибольшее количество;
- каждый робот живет три года после сборки.
Известно начальное количество роботов К и все они только что собраны. Сколько роботов будет через N лет?
Идея решения. Если роботов много, им выгоднее собираться по 5, потому что 3 пятерки соберут 27 роботов, а 5 троек только 25. Рассмотрим все случаи, когда количество роботов не делится на 5.
- Количество роботов при делении на 5 дает остаток 3.
Роботы собираются пятерками, а три “лишних” робота составляют одну тройку.
- Количество роботов при делении на 5 дает остаток 1.
Все роботы, кроме 6, собираются пятерками, а 6 “лишних” образуют 2 тройки ( 2 тройки соберут 10 роботов, а одна пятерка- 9).
- Количество роботов при делении на 5 дает остаток 4.
Все роботы, кроме 9, собираются пятерками, а 9 “лишних” образуют 3 тройки (3 тройки соберут 15 роботов, а одна пятерка- 9).
- Количество роботов при делении на 5 дает остаток 2.
Все роботы, кроме 12, собираются пятерками, а 12 лишних образуют 4 тройки (4 тройки соберут 20 роботов, а 2 пятерки -18).
Роботы собираются в группы так, чтобы максимальное их число было задействовано в процессе изготовления новых роботов.
Program robot;
var
i,k,n,s,s0,s1,s2,s3,x:integer;
begin
write('Начальное количество роботов...');
readln(k);
write('Количество лет...');
readln(n);
s0:=k; количество роботов, которым 0 лет
s1:=0; количество роботов, которым 1 год
s2:=0; количество роботов, которым 2 года
s3:=0; количество роботов, которым 3 года
for i:=0 to n do процесс идет n лет
begin
s:=s0+s1+s2+s3; сколько всего роботов
case s mod 5 of выделяем случаи
0: x:=(s div 5)*9;
1: if s=1 then x:=0
else x:=(((s-5) div 5)*9)+10;
2: if s=2 then x:=0
else if s=7 then x:=10
else x:=(((s-10) div 5)*9)+20;
3 : x:=((s div 5)*9)+5;
4 : if s=4 then x:=5
else x:=(((s-5) div 5)*9)+15;
end;
s3:=s2; роботы “постарели” на год
s2:=s1;
s1:=s0;
s0:=x; построили за последний год
end;
writeln('Через ',n, ' лет будет ',s,' роботов');
end.
задачи
Задача 44 Простые гири
Имеются гири с массами: 1 г, 2 г, ..., N г (N<500000). Требуется написать программу, распределяющую эти гири на максимально возможное количество пар так, чтобы суммарный вес гирь в каждой паре выражался простым числом.
Формат входных данных:
Входной файл Input.txt содержит число N.
Формат выходных данных:
В выходной файл Output.txt выводится список найденных пар. Все числа в выходном файле разделяются пробелами и символами перевода строки. В каждой строке записывается одна найденная пара.
-
Input.txt
Output.txt
7
1 6
7 4
5 2
Для решения задачи найдем наименьшее простое число p, большее чем n. Тогда пары чисел (p-n, n), (p-n+1, n-1), ... будут удовлетворять условию задачи. А также легко заметить, что этими парами выбираются все числа интервала от p-n до n. Теперь повторяем эту процедуру для нового n равного p-n-1 до тех пор пока n>1. В результате получим максимальное количество пар
( , где [] - целая часть числа), удовлетворяющих условию задачи.
Изложенное выше и использовано в программе.
Program giri;
var
n, p, l, i : longint;
function prost(n:longint) : boolean;
var b : boolean;
x : longint;
begin
b:=true;
for x:=2 to round(sqrt(n)) do
b:=b and (n mod x <> 0);
prost:=b
end;
begin
assign(input,'input.txt'); reset(input); read(n);
assign(output,'output.txt'); rewrite(output);
while n>1 do
begin
p:=n+1;
while not prost(p) do p:=p+1;
l:=p-n;
for i:=0 to (n-l) div 2 do
write(l+i,' ',n-i);
n:=l-1
end;
close(g)
end.
задачи
Задача 45 Xитрое жюри
Дана последовательность целых чисел. Известно, что все числа в ней встречаются четное количество раз, кроме одного, которое встречается нечетное число раз. Требуется написать программу, которая определяет это число.
Формат входных данных:
Входной файл Input.txt содержит заданную последовательность. Каждое из чисел последовательности больше -2147483649 и меньше 2147483648. В каждой строке файла записано по одному числу. Общее количество чисел в файле не превышает 500001.
Формат выходных данных:
Выходной файл Output.txt должен содержать найденное число.
Примеры входных и выходных файлов:
Input.txt |
Output.txt |
-1 2 -1 |
2
|
Рассмотрим следующую операцию сложения по модулю 2: 0+0=0, 1+0=1, 0+1=1 и 1+1=0. Многозначные числа будем складывать поразрядно после двоичного разложения каждого из слагаемых. Так определенная операция сложения обладает следующими свойствами: a+0=a, a+a=0, a+b=b+a, (a+b)+c=a+(b+c). Этих свойств достаточно, чтобы показать, что такая сумма чисел, удовлетворяющих условиям задачи, как раз и будет искомым числом. Действительно, числа, которые встречаются четное количество раз, дают в результате сложения 0 (после перегруппировки слагаемых), а, так как только одно из них встречается нечетное число раз, то оно и останется после всех сложений.
В математике и программировании описанное сложение еще называют исключающим “или”, а в Турбо Паскале это сложение реализована как операция “XOR” над целыми числами. Подсказка была заложена в названии задачи.
задачи
Задача 46 Число в последовательности нет решения
Последовательность 011212201220200112 строится следующим образом: сначала пишется 0, затем повторяется следующее действие: уже написанную часть приписывают справа с заменой 0 на 1, 1 на 2, 2 на 0, и т.д. Требуется написать программу, которая по заданному натуральному числу n
определяет, какая цифра стоит на n-ом месте.
Формат входных данных:
Входной текстовый файл Input.txt содержит число N (1<=N<=2147483647).
Формат выходных данных:
Выходной файл Output.txt должен содержать одно искомое число.
Примеры входного и выходного файлов:
Input.txt |
Output.txt |
10
|
2
|
задачи
Задача 47 Зачеркнутая цифра нет решения
Дано произвольное натуральное число, не все цифры которого одинаковы. Затем в этом числе произвольным образом переставляются цифры так, чтобы получилось число отличное от записанного. Затем меньшее из двух чисел вычитают из большего. В полученной разности вычеркивают одну ненулевую цифру.
Входной файл Input.txt содержит:
в первой строке одно натуральное число, содержащее N цифр (1<N100000) – разность большего и меньшего чисел без вычеркнутой цифры.
Выходной файл Output.txt должен содержать одно натуральное число - зачеркнутую цифру.
Пример входного и выходного файлов:
-
Input.txt
Output.txt
180186
3
задачи
Задача 48 Постройка пирамиды
Досталась сыну фараона от отца в наследство куча камней кубической формы, приготовленных для постройки пирамиды. И решил он увековечить свое имя, построив такую пирамиду, какую до него никто не строил. Издал указ следующего содержания:
Получит награду тот, кто составит проект постройки пирамиды удовлетворяющей следующим условиям:
В каждом следующем ряду камней должно быть не больше чем в предыдущем и количество камней в двух соседних рядах не должно отличаться больше чем на один камень..
Каждый следующий ряд должен быть по весу не больше предыдущего.
Сумма максимальных по весу камней, взятых по одному из каждого ряда должна быть максимальна.
И стал ждать. Время шло, но никто не приходил за наградой. Задача оказалась непростой.
Возможно, среди вас найдется тот, кто способен решить эту задачу.
Формат входного файла
Первая строка входного файла содержит натуральное число N – количество камней (1 ≤ N ≤ 20000), за которым следуют N натуральных чисел – весов камней x1, …, xn (0 < xi ≤ 10000). Все числа разделены пробелами.
Формат выходного файла
В выходной файл запишите план постройки пирамиды.
Примеры входного и выходного файлов:
Input.txt |
Output.txt |
3 1 2 2 |
2 2 1 |
4 3 5 2 3 |
3 3 2 5 |
7 1 2 4 3 2 2 6 |
3 4 2 2 6 2 |
Решение этой задачи достаточно простое. Обратим внимание на третье условие: Сумма максимальных по весу камней, взятых по одному из каждого ряда, должна быть максимальна. Упорядочим веса камней по невозрастанию и будем укладывать камни начиная с первого столбца снизу вверх.
Для 3-го тестового примера 3
4 2
6 2 2
Один камень оказался лишним. В первом примере лишних камней нет.
program Xeops;
const nmax=100;mmax=100;
var k,st,t,n,sc,kol,i,j :longint;
a :array [1..5000] of integer;
b :array [1..nmax,1..mmax] of integer;
procedure init;
var i,kol,sum,max :integer;
begin
assign(input,'input.txt');
reset(input);
read(n);
for i:=1 to n do read(a[i]);
close(input);
end;
procedure solve;
var max,q :integer;
begin
for i:=1 to n-1 do сортируем камни по невозрастанию весов
for j:=i+1 to n do
if a[i]<a[j] then
begin
q:=a[i];a[i]:=a[j];a[j]:=q;
end;
k:=1; посчитаем сколько рядов
st:=((k+1)*k)div 2; и камней будет в пирамиде
while st<=n do
begin
inc(k);
st:=((k+1)*k)div 2;
end;
dec(k);st:=((k+1)*k)div 2;
if st<n
then n:=st;
kol:=k; запоминаем количество рядов в пирамиде
t:=0;
for j:=1 to kol do выкладываем камни, начиная с первого столбца
begin снизу вверх
if t>n then break;
for i:= kol downto j do
begin
inc(t);b[i,j]:=a[t];
if t>n then break;
end;
end;
end;
procedure out;
begin
assign(output,'output.txt');
rewrite(output);
for i:=1 to kol do выводим полученную пирамиду
begin
for j:= 1 to kol do
if b[i,j]>0 then write(b[i,j],' ');
writeln;
end;
close(output);
end;
begin init; solve; out; end.
задачи
Задача 49 Три автомата
В некотором царстве в некотором государстве жил да был Федот-стрелец удалой молодец. Вызвал его как-то царь к себе и говорит: "Соизволь-ка мне добыть, то чего на белом свете вообще не может быть." Пригорюнился Федот, но делать нечего, простился с женой и пошел. Шел долго ли коротко ли, но набрел на старика удивительного, и сказал ему старик: "Помогу я тебе, но ты должен за это решить задачу".
А задача была такой: "Три автомата печатают на карточках пары неотрицательных целых чисел. Каждый автомат, прочитав некоторую карточку, выдает новую карточку; прочитав карточку с парой (m,n), первый автомат выдает карточку (m-n,n), второй - карточку (m+n,n), третий карточку (n,m). Пусть первоначально дана карточка (p,q). Можно ли, используя автоматы в любом порядке, получить из нее карточку (r,t)? Если - да, то необходимо подсчитать общее минимальное число срабатываний всех автоматов.
Помогите Федоту дать ответ на эти вопросы.
Входной файл Input.txt состоит из одной строки, содержащей две пары неотрицательных целых чисел, записанных через пробел.
Выходной файл Output.txt содержит одно натуральное число - минимальное количество срабатываний всех автоматов, если карточку получить можно или NO, если нельзя.
Примеры входного и выходного файлов:
Input.txt |
Output.txt |
4 2 4 6 |
3 |
Для решения задачи используем свойства наибольшего общего делителя двух натуральных чисел
1) НОД(m-n,n)=НОД(m,n) при условии, что m>=n
2) НОД(n,m)=НОД(m,n)
3) НОД(m+n,n)=НОД(m,n)
Если данные пары чисел имеют разные НОД, то карточку получить нельзя и надо выводить NO. Если же НОД данных пар чисел равны, то применяя первый и третий автоматы получаем две цепочки из пар чисел иллюстрирующих нахождение НОД двух натуральных чисел. В последних парах второе число обязательно будет ноль.
Например: дана карточка 14 6, надо получить карточку 6 4. Получаем две цепочки.
П
ервая
: (14 6) (8 6 ) (2 6) (6 2) (4 2)
(2 2) (0 2) (2 0)
В торая: (6 4) (2 4 ) (4 2) (2 2) (0 2) (2 0).
Двигаясь слева направо по обеим цепочкам, находим общую пару (4 2) и дальнейшее понятно. Искомое количество срабатываний автоматов находится из цепочки
(14 6) (8 6 ) (2 6) (6 2) (4 2) (2 4) (6 4) .
задачи
Задача 50 Гадкие парни
В круг поставили 2*N человек. Первые из них N славных и далее N гадких парней. Найти такое натуральное M, что если двигаться по кругу, начиная с первого, и наказывать каждого M-го, то первыми будут наказаны все гадкие парни.
Формат входного файла
Файл содержит одно натуральное число N (1N12)
Формат выходного файла
Файл содержит одно натуральное число – искомое M.
Примеры
Input.txt |
Output.txt |
3 |
5 |
Если мы начнем наказывать с последнего 2N-го гадкого парня, затем накажем предпоследнего и так далее до первого, то можно положить M равному наименьшему общему кратному чисел 2N,2N-1,…N+2,N+1 или просто общему кратному этих чисел.
Первое решение M=(2N)(2N-1)…(N+2)(N+1). Это число достаточно большое. Уже при N=7 в нем более 11 цифр и надо использовать длинную арифметику или тип int64 языка программирования Дельфи
При N=12 M=620448401733239439360000.
Второе решение M=НОК((2N),(2N-1),…(N+2),(N+1)). Напоминаем , что НОК(a,b)=(a*b)/НОД(a,b). и НОД(a,b,c)= НОД(НОД(a,b),c); НОК(a,b,c)= НОК(НОК(a,b),c); В этом случае число M входит в тип longint;
program slav_gad;
const nmax=10;
var a:array[1..nmax] of longint;
r,i,nok,d,n:longint;
procedure init;
begin
assign(input,'input.txt');
reset(input);
read(n);
close(input);
end;
function nod(a,b:longint):longint;
var p,q,r:longint;
begin
if a<b then begin q:=a;a:=b;b:=q;end;
repeat
r:=a mod b;
a:=b;b:=r
until r=0;
nod:=a;
end;
procedure solve;
begin
d:=1;nok:=1;
for i:=2*n downto n+1 do
begin
d:=nod(nok,i);
nok:=(nok div d)*i;
end;
end;
procedure out;
begin
assign(output,'output.txt');
rewrite(output);
write(nok);
close(output);
end;
begin init; solve; out; end.
задачи
Задача 51 Банкноты
После того, как была отпечатана партия из N банкнот достоинством в миллиард тугриков, выяснилось, что одна банкнота не напечаталась. Каждая из банкнот имеет уникальный номер от 1 до N. По заданному списку номеров отпечатавшихся банкнот необходимо выяснить номер недостающей.
Входные данные
На первой строке входного файла записано число N (1 <= N <= 1000000). Далее записано N-1 число в диапазоне [1..N]. Числа разделены произвольными количествами пробелов и/или переводов строк.
Выходные данные
В выходной файл нужно записать единственное число – номер пропущенной банкноты.
Примеры
Input.txt |
Output.txt |
7 1 6 5 7 3 4 |
2 |
9 1 2 4 5 6 7 8 9 |
3 |