Задача1
1. Дана последовательность натуральных чисел 7, 11, 13, 14, 19, 21, 22, 25, :.
Требуется написать программу, которая по заданному N находит N-ый член этой последовательности.
Ограничение времени: 1 секунда на тест.
Входные данные
Входной файл INPUT. TXT содержит число N (1000 ≤ N ≤ 2147483647).
Выходные данные
В выходной файл OUTPUT. TXT выведите N-ый член последовательности.
Примеры
№ | INPUT. TXT | OUTPUT. TXT |
1 | 1005 | 524672 |
2 | 2100 | 16781824 |
ОТВЕТ 1
Рассмотрев двоичные разложения представленных элементов последовательности, можно сделать вывод о том, что в последовательность входят только те натуральные числа, у которых три единицы в двоичном разложении. Таким образом, n-й член последовательности имеет вид 2k1+2k2+2k3. l+1-значных двоичных чисел с тремя единицами всего l*(l-1)/2. Это позволяет найти k1. Из аналогичных соображений находим k2 и k3. Для вычисления значения самого n-го члена воспользуемся схемой Горнера 2k1+2k2+2k3=((2k1-k2+1)*2k2-k3+1)*2k3. Для вычисления последнего выражения надо использовать в длинной арифметике две операции: умножение на два и добавление единицы.
var
n, l : longint;
k1,k2,k3,k, i,j, p : integer;
a : array [1..1000] of integer;
begin
assign(input, 'input. txt'); reset(input);
assign(output, 'output. txt'); rewrite(output);
read(n);
l:=2; while n-l*(l-1) div 2 > 0 do begin
n:=n-l*(l-1) div 2; l:=l+1 end; k1:=l;
l:=1; while n-l>0 do begin
n:=n-l; l:=l+1; end; k2:=l; k3:=n-1;
a[1]:=1; k:=1;
for i:=1 to k1-k2 do begin
p:=0; for j:=1 to k do begin
p:=p+a[j]*2; a[j]:=p mod 10; p:=p div 10 end;
if p>0 then begin k:=k+1; a[k]:=p end end;
a[1]:=a[1]+1;
for i:=1 to k2-k3 do begin
p:=0; for j:=1 to k do begin
p:=p+a[j]*2; a[j]:=p mod 10; p:=p div 10 end;
if p>0 then begin k:=k+1; a[k]:=p end end;
a[1]:=a[1]+1;
for i:=1 to k3 do begin
p:=0; for j:=1 to k do begin
p:=p+a[j]*2; a[j]:=p mod 10; p:=p div 10 end;
if p>0 then begin k:=k+1; a[k]:=p end end;
for i:=k downto 1 do write(a[i]);
close(output)
end.
Задача 2
Для содержания двух воинственных инопланетян Aки и Bуки используется клетка с многослойной перегородкой, которая изготавливается из имеющихся N сеток. Для каждой сетки i (i = 1, :, N) известно время ее разрушения инопланетянином Aки - ai и инопланетянином Bуки - bi. Разрушение сетки каждым из инопланетян происходит последовательно слой за слоем, с постоянной скоростью по толщине сетки.
Требуется написать программу проектирования такой перегородки, время разрушения которой было бы максимальным.
Ограничение времени: 1 секунда на тест.
Входные данные
В первой строке входного файла INPUT. TXT записано число N (1 ≤ N ≤ 256). В каждой из последующих N строк содержатся два положительных вещественных числа ai и bi, разделенные пробелом.
Выходные данные
В первую строку выходного файла OUTPUT. TXT записать время разрушения перегородки с точностью, не меньшей 10-3. В следующую строку файла записать номера сеток в порядке их расположения от инопланетянина Aки к инопланетянину Bуки, разделяя числа пробелами.
Пример
№ | INPUT. TXT | OUTPUT. TXT |
1 | 4 | 6.000 |
ОТВЕТ 2
Необходимо отсортировать перегородки по отношению времён их разрушения инопланетянами. После этого подсчитываем время их разрушения.
var i, n:integer;
a, b,c:array[1..300] of real;
d:array[1..300] of integer;
procedure Sort;
var i, j,y:integer;x:real;
begin
for i:=1 to n do
for j:=i+1 to n do begin
if c[j]>c[i] then begin
x:=c[i];y:=d[i];
c[i]:=c[j];d[i]:=d[j];
c[j]:=x;d[j]:=y;
end;end;
end;
function Time:real;
var uk1,uk2:integer;
t11,t22,t, t1,t2:real;
begin
uk1:=1;uk2:=n;
t1:=0;t2:=0;
while uk1<>uk2 do begin
t11:=t1+A[d[uk1]];
t22:=t2+b[d[uk2]];
if t11<t22 then begin
inc(uk1);t1:=t11;end
else begin dec(uk2);t2:=t22;end;
end;
if t1>t2 then begin
t:=(t1-t2)/b[d[uk1]];
t2:=t1;
end else begin
t:=(t2-t1)/a[d[uk1]];
t1:=t2;
end;
t:=t1+(1-t)/(1/a[d[uk1]]+1/b[d[uk1]]);
Time:=t;
end;
BEGIN
Assign(input,'input. txt');
Reset(input);
Assign(output,'output. txt');
Rewrite(output);
Read(n);
for i:=1 to n do begin
read(a[i],b[i]);
c[i]:=a[i]/b[i];
d[i]:=i;
end;
Sort;
Writeln(Time:0:3);
for i:=1 to n do write(d[i],' ');
END.
Задача 3
Вокруг планеты Зин-зик-буль движется два спутника с постоянными угловыми скоростями. Их положение в двумерном пространстве определяется h часами m минутами.
Требуется написать программу, которая найдет число полных минут до ближайшего момента полного затмения, (положение спутников на одной прямой с планетой).
Технические требования:
Входной файл: INPUT. TXT.
Выходной файл: OUTPUT. TXT.
Ограничение времени: 1 секунда на тест.
Формат входных данных:
Файл INPUT. TXT состоит из одной строки, в которой через пробел записаны два числа h (0 ≤ h ≤ 11) и m (0 ≤ m ≤ 59).
Формат выходных данных:
В выходной файл OUTPUT. TXT вывести единственное целое число - найденное число полных минут.
Пример файлов входных и выходных данных:
INPUT. TXT | OUTPUT. TXT |
0 0 | 0 |
1 1 | 4 |
ОТВЕТ 3
Легко заметить, что в течении одного полного оборота спутников моментов нахождения на одной прямой всего одиннадцать: 0 часов, 0 минут; 1 час, 5 минут и несколько секунд; 2 часа, 10 минут и несколько секунд и т. д. Эти моменты можно получить из простого уравнения 11t=720k, где t– время совпадения в минутах, а k равно последовательно 0, 1, 2, :, 10. По заданному времени (часы, минуты) находим это время в минутах, а после этого ближайшее после него время нахождения на одной прямой. Чтобы избежать дробных чисел будем измерять время не в минутах, а в одну одиннадцатую минуты.
var
h, m, t : integer;
begin
assign(input,'input. txt'); reset(input);
assign(output,'output. txt'); rewrite(output);
read(h, m);
t:=11*(60*h+m) mod 720;
if t<>0 then t:=720-t;
write(t div 11)
end.
