Задача 39 Лесенка-2

Вова стоит перед лесенкой из N ступеней. На каждой из ступеней написаны произвольные целые числа. Первым шагом Вова может перейти на первую ступень или, перепрыгнув через первую, сразу оказаться на второй. Также он поступает и дальше, пока не достигнет N-ой ступени. Посчитаем сумму всех чисел, написанных на ступенях через которые прошел Вова.

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

Входные данные

Входной файл INPUT.TXT содержит в первой строке натуральное число N – количество ступеней лестницы. Во второй строке через пробел заданы числа, написанные на ступенях лестницы, начиная с первой. Количество ступеней не превышает 1000, числа, написанные на ступенях, не превосходят по модулю 1000.

Выходные данные

Выходной файл OUTPUT.TXT должен содержать в первой строке наибольшее значение суммы. Во второй строке должны быть записаны через пробел номера ступеней по возрастанию, по которым должен шагать Вова.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	3 1 2 1	4 1 2 3
2	3 1 -1 1	2 1 3

program lesenka2;

{$APPTYPE CONSOLE}{$O-}

uses SysUtils;

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

i,n,p:integer;

procedure rec(m:integer); процедура вывода пути

begin каждой m-ой ступеньке соответствует

if m=0 then exit m-ый элемент массива b

else rec(b[m]); в m-ом элементе массива b храним номер

write(m,' '); ступеньки, с которой мы на нее попали

end;

begin

reset(input,'input.txt'); rewrite(output,'output.txt');

read(n);

b[1]:=0;

read(a[1]); считываем первое число

for i:=2 to n do

begin

read(p);

if a[i-1]>a[i-2] выбираем лучший вариант

then begin a[i]:=a[i-1]+p;b[i]:=i-1 end

else begin a[i]:=a[i-2]+p;b[i]:=i-2 end

end;

writeln(a[n],' ');

rec(n);

end.

динампрогрзадачи

К оглавлению

Системы счисления

Рассмотрим произвольные натуральные числа N и p.

Теорема: Существуют единственные числа с₀, с₁, ..., с_n такие, что с_npⁿ+…+c₁p+c₀ = N, причем 0 <= c_i < p (13). Здесь n = [log_pN].

Доказательство. Предположим, есть еще одно разложение d_npⁿ+…+d₁p+d₀ = N. Тогда, (d_n-c_n)pⁿ+…+(d₁-c₁)p+(d₀-c₀) = 0. Пусть, d_i-c_i – самый левый ненулевой коэффициент и пусть, для определенности, d_i-c_i < 0, тогда d_i-c_i <= -1. Тогда, (d_n-c_n)pⁿ+…+(d₁-c₁)p+(d₀-c₀) = (d_i-c_i)pⁱ+…+(d₁-c₁)p+(d₀-c₀) <= -pⁱ+(p-1)(p^i-1+…+p+1) = -pⁱ + (p-1) = -1 < 0. Противоречие.

Набор (с₀, с₁, ..., с_n) однозначно описывает число N. В таком случае говорят, что N представлено в системе счисления с основанием p и пишут N = (c_n…c₁c₀)_p.

Как по числу N определить числа с_i? Из (13) следует, что с₀ = N mod p и с_np^n-1+…+c₁ = N div p. Повторяя указанный процесс до тех пор, пока N <> 0, получим искомое разложение. Данную идею реализовывает алгоритм (14):

i:= 0;

While N<>0 do begin

c[i]:= N mod p;

N:= N div p;

i:= i+1;

end;

n:= i-1;

 

Обратная задача: по числам c₀, c₁, …, c_n найти N. Для ее решения воспользуемся формулой (13), переписанной в виде: N = p(…(p(pc_n+c_n-1)+c_n-2)+….)+c₀ (для чего?). Задачу решает алгоритм (15):

N:= 0;

For i:= n downto 0 do

N:= p*N+c[i];

Важным частным случаем является p = 10, при котором мы получаем алгоритмы разбиения числа на цифры и сворачивания массива цифр в число. Применение систем счисления часто упрощает решение различных задач.

1. Делимость на 15

2. Остаток от деления

3. Еще остаток от деления

4. Интересная функция

5. Необычная система счисления

6. Экономия чернил

7. Несложные вычисления

8. Несложные вычисления

9. Баллы для тестов

10. Двоичное число

11. Троичная сбалансированная система счисления

Задача 1 Делимость на 15

Число вводится своим двоичным представлением (длина числа непревышает 10000 двоичных разрядов). Необходимо определить делитсяли число на 15. Вспомним признак делимости на 9 в десятичной системе счисления: Если сумма цифр десятичного числа делится на 9, то и само число тожеделится на 9. Докажем это:

Пусть есть число

S = a[n]*10^n + a[n-1]*10^(n-1) + ... + a[1]*10 + a[0].

Прибавим и отнимем каждую цифру числа за исключением a[0]:

S = a[n]*10^n-a[n]+a[n] + a[n-1]*10^(n-1)-a[n-1]+a[n-1] + ... +

+a[1]*10-a[1]+a[1] + a[0]=

=a[n]*(10^n-1)+a[n]+a[n-1]*(10^(n-1)-1)+a[n-1]+...+a[1](10-1)+a[1]+a[0].

Найдем остаток от деления этого числа на 9:

S mod 9 = (a[n]*(10^n-1)+a[n] + a[n-1]*(10^(n-1)-1)+a[n-1] +

+ ... + a[1]*(10-1)+a[1] + a[0]) mod 9

А так как (10^k - 1) делится на 9 нацело, то получаем

S mod 9 = (a[n] + ... +a[1] +a[0]) mod 9,

число делится на 9, если сумма его цифр(десятичных) делится на 9.ч.т.д. Заметьте все вышеприведенные рассуждения справедливы только для десятичной системы счисления.

Если проделать это для системы счисления с основанием 16, то получим: Число делится на 15, если сумма его шестнадцатеричных цифр делится на 15. Итак, нам нужно перевести двоичное число в шестнадцатеричную систему счисления, разбиваем двоичное число справа налево на тетрады (четверки цифр),если количество двоичных цифр не кратно 4, то дополняем число нужным количество нулей справа Каждой четверке двоичных цифр соответствует одна шестнадцатеричная цифра (от 0 до 15).Находим сумму цифр и находим остаток от деления ее на 15, если остаток 0, то введенное число делится на 15, иначе - нет.

системысчислениязадачи

Задача 2 Остаток от деления

Дано число в K-ичной системе счисления (a[i] - это его i-я цифра) a[n]a[n-1]...a[0] (K<=36). Найти остаток от деления его на m. Числа K,1<=n,m<=100, как и a[i], представляются в десятичной системе счисления.

Входные данные: файл input.txt , в первой строчке через пробел три числа к, n, m именно в такой последовательности, в следующих n строчках по одному числу a[i].

Выходные данные: файл output.txt содержит одно число – искомый остаток.

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

В системе счисления с основанием K число представляется в виде

a[n]*Kⁿ + a[n-1]*K^(n-1) + ... +a[0].

Найдем остаток от деления его на m

S=(a[n]*Kⁿ + a[n-1]*K^(n-1) + ... +a[0]) mod m =

=( SUM a[i]*Kⁱ) mod m = ( SUM a[i]* (Kⁱ mod m))mod m (*)

i=0..n i=0..n

это вытекает из следующих соображений: пусть Kⁱ mod m=t,

тогда Kⁱ =p*m+t, и (a[i]*K^i) mod m = (a[i] * (p*m+t)) mod m =

= (a[i]* p*m) mod m + (a[i]*t) mod m =

первое слагаемое равно нулю = a[i] * (Kⁱ mod m)) mod m.

При этом для любых чисел b[i] выполняется

( SUM b[i] ) mod m =( SUM (b[i] mod m )) mod m. (**)

i=0..n i=0..n

Доказательство

Пусть b[i] mod m=t[i], тогда b[i]=p[i]*m+t[i]=>

(SUM(p[i]*m+t[i]))mod m=(SUM p[i]*m)mod m+(SUM t[i])mod m={поскольку

первое слагаемое равно нулю, т.к. оно делится на m, имеем}=

=(SUM t[i])mod m = (SUM(b[i] mod m))mod m

Отсюда S=(SUM ((a[i]*(K^i mod m))mod m))mod m; (***)

Отметим также очевидное равенство Kⁱ mod m =[(K^(i-1) mod m) * K] mod m,

т.к. если K^(i-1) = p*m+t, то K^(i-1) mod m = t, Kⁱ = p*m*K+t*K и

Kⁱ mod m = t*K mod m = [(K^(i-1) mod m)*K] mod m. (****)

Подсказка к составлению программы: вычисления в цикле производятся по формуле (***), Kⁱ mod m считается по формуле (****)

системысчислениязадачи

Задача 3 Еще остаток от деления

Любое натуральное число N можно единственным способом представить с помощью некоторых целых неотрицательных d[0], ... ,d[s] в виде

N=d[s]*(s+1)!+d[s-1]*s! +...+d[1]*2!+d[0] (*)

при условии, что 0<=d[i]<=i+1, i=0,..,s, где d[s]<>0.

Дано s+1 натуральное число d[0], ..., d[s], и натуральное K, s<200,d[i]<65535, K<65535. Найти остаток от деления числа N, определяемого в факториальной системе (*) числами d[0], ..., d[s], на число K.

Входные данные:

В первой строчке через пробел числа S, K. В следующих S строчках по одному числу d[i];

Выходные данные:

Одно число - остаток от деления.

Задача решается также, как и предыдущая:

s

N mod K =(SUM (d[j] mod K) * ((s+1)! mod K)) mod K,

j=0

где (s+1)! mod K = [ (s! mod k) * ((s+1) mod k)] mod k,

Алгоритм запишется следующим образом:

остаток:=0;

faktorial:=1;

for i:=1 to s+1 do

begin

остаток:=(остаток+d[i-1]*faktorial) mod k;

faktorial:=faktorial * (i+1) mod k;

end;

В переменной остаток после выхода из цикла будет искомое значение.

системысчислениязадачи

Задача 5 Интересная функция

Функция A(n) для целых неотрицательных n определена так:

A(0)=0, A(1)=1, A(2n)=A(n), A(2n+1)=A(n)+A(n+1).

Для данного n найти и напечатать A(n). Обязательное условие: n столь велико, что недопустимо заводить массив из n чисел (равно как и массив, длина которого растет с ростом числа n).

Входные данные: файл input.txt содержит одно число n;

Выходной файл: файл output.txt содержит одно число A(n);

Задача очень интересная, попробуйте решить сами. Начать лучше с подсчета значения функции вручную.

Задача 6 Необычная система счисления

Любое положительное целое число можно записать в необычной системе счисления с основанием К и цифрами от 1 до К (не используя цифру О). Например, число 60, заданное в обычной десятичной системе счисления, в необычной системе счисления с основанием 3 имеет значение 1313, так как 60 = 1 З³ + 3 З² + 1 3' + 3 3

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

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

В единственной строке входного файла input.txt содержатся два разделенных пробелом целых числа N и К (1 <=N< 2*10⁹, 2 <=К <=9), записанных в десятичной системе счисления.

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

Выходной файл output.txt должен содержать число М, записанное в необычной системе счисления с основанием К и цифрами от 1 до К.

Пример:

Input.txt	Output.txt
60 3	1313

Различные методы решения.

Метод первый: переводим число из десятичной системы счисления в обычную (в которой есть ноль)с основанием к. Далее, просматривая число справа налево, ищем в числе ноль. Заменяем его цифрой к. Двигаясь далее по числу заменяем все встречающиеся нули на цифру равную к-1,а первую ненулевую цифру уменьшаем на 1.

И так до тех пор пока не дойдем до последней цифры числа.

Например: 27₁₀=1000₃=223

20000₁₀=1000102202₃=222332132

program neobsys1;

const nmax=30;

var a:array[0..nmax] of byte; массив цифр полученного числа. В а[0] хранится i,j,n,m,k,p:longint; количество цифр полученного числа

procedure init;

begin

assign(input,'input.txt');

reset(input);

read(n,k);

close(input);

fillchar(a,sizeof(a),0); заполняем массив нулями

end;

procedure out;

begin

assign(output,'output.txt');

rewrite(output);

i:=1;

while a[i]=0 do inc(i); пропускаем первые нули

for j:=i to nmax do write(a[j]); выводим остальные цифры

close(output);

end;

procedure perevod(m:longint); переводим данное число в обычную систему

счисления

begin с основанием к делением лесенкой

i:=nmax;

while m>=k do

begin

a[i]:=m mod k;

m:=m div k;

dec(i);

inc(a[0]);

end;

a[i]:=m;

inc(a[0]);

end;

procedure solve;

begin

perevod(n);

i:=nmax; начинаем движение по числу справа налево

while i>nmax-a[0]+1 do пока цифры числа не кончились

begin

if a[i]=0 если цифра числа ноль

then

begin

a[i]:=k; заменяем ее цифрой к

j:=i-1; двигаясь дальше заменяем по пути все

встречающиеся

while (j>nmax-a[0])and(a[j]=0) нули цифрой равной к-1

do begin a[j]:=k-1;dec(j) end;

dec(a[j]);

i:=j;

end

else

dec(i); если цифра не ноль, то сдвигаемся на одну

позицию влево

end;

end;

begin init; solve; out;end.

Второй способ решения.

Сначала накапливаем статистику. Возьмем к=3.

10 3

1. 1

2. 2

3. 3

4. 11

5. 12

6. 13

7. 21

8. 22

9. 23

10. 31

11. 32

12. 33

13. 111

14. 112

15. 113

16. 121

17. 122

18. 123

19. 131

20. 132

21. 133

22. 211

23. 212

24. 213

25. 221

26. 222

27. 223

Получение следующего числа из предыдущего осуществляется прибавлением 1.Эту операцию оформим в виде процедуры Next. Если двигаясь к числу n начинать движение с 1, то по времени не успеем. Следовательно, движение надо начинать с числа близкого к n, запись которого в необычной системе известна. За такое число надо взять степень числа к, наиболее близкую к данному n. Замечаем, что 3^t записывается как 22…23, где t-1 двойка и последняя тройка.

Следовательно в системе с основанием к число k^t запишется так (к-1)(к-1)…(к-1)к. Для нахождения t найдем наибольшую степень к такую, что k^t<=n.

program neobsys2;

const nmax=10;

var p,i,j,h,k,t,n:longint;

a:array[1..nmax]of byte;

um:byte;

Procedure init;

begin

assign(input,'input.txt');

reset(input);

read(n,k);

h:=nmax;

p:=1; t:=0; ищем t

while p<n do

begin

p:=p*k;

inc(t);

end;

p:=p div k; в p находится k^t

dec(t); так как через n перескочили, возвращаемся на шаг обратно

a[h]:=k; в последний элемент массива записываем к

for i:=h-1 downto h-t+1 do в предыдущие t-1 элементов цифру к-1

a[i]:=k-1;

close(input);

end;

Procedure print;

var i:integer;

begin

assign(output,'output.txt');

rewrite(output);

i:=1;

while a[i]=0 do inc(i); пропускаем первые нули

for j:=i to h do выводим оставшиеся цифры

write(a[j]);

close(output);

end;

Procedure Next;

var i:integer;

begin

i:=h; um:=1;

while (i>0) and (um<>0) do пока не дошли до конца массива и в уме не ноль

begin

if a[i]+um>k then если при прибавлении 1 получается >k

begin

a[i]:=1; um:=1; заменяем цифру 1 и в уме 1

end

else

begin

a[i]:=a[i]+um; иначе просто прибавляем то, что в уме

um:=0; и в уме делаем 0

end;

dec(i); сдвигаемся на одну позицию влево

end;

end;

begin

init;

for i:=p+1 to n do начиная с k^t прибавляем 1 пока не дойдем до n

Next;

print; выводим результат

end.

системысчислениязадачи

Задача 7 Экономия чернил

Царь Горох издал указ об экономии чернил в тридевятом царстве. В частности, он запретил пользоваться написанием знаков «+» и «-­» для отображения положительности или отрицательности числа. В связи с этим придворным математикам пришлось изобретать новые системы представления чисел. Они вышли из положения, заменив положительные основания в старых системах на отрицательные. Действительно, представление числа по отрицательному основанию не требует знаков.

Например, число 7 по основанию -2 представляется в виде 11011 (1*16+1*(-8)+0*4+1*(-2)+1=7), число -7 по основанию -2 представляется в виде 1001 (1*(-8)+0*4+0*(-2)+1=-7), так как соответствующие степени основания равны 1, -2, 4, -8 и т.д.

Но придворные математики никак не могут разобрать общий алгоритм перевода чисел. Помогите им в этом.

Составьте программу, которая:

1. Вводит целые числа N (-2000000000N2000000000) и В (-10B(-2) из текстового файла NB.DAT

2. Переводит число N в систему счисления с отрицательным основанием В

3. Выводит результат в текстовый файл NB.SOL

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

Входной файл Input.txt содержит единственную строку с числами N и В, которые разделены пробелом

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

Выходной файл Output.txt должен содержать единственную строку с числом N, представленным в системе счисления по основанию В Пример

Input.txt	Output.txt
7 -2 11 -3	11011 102

системысчислениязадачи

Задача 8 Несложные вычисления

Дано натуральное число N. Перевести его в систему счисления с основанием K и найти разность произведения и суммы чифр получившегося числа.

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

program neslojvich;

var k,n,p,s,r:longint;

begin

assign(input,'simple.in');

assign(output,'simple.out');

reset(input);

rewrite(output);

read(n,k);

s:=0; в этой переменной будем хранить сумму цифр

p:=1; в этой переменной будем хранить произведение цифр

while n>0 do пока в числе есть цифры

begin

r:=n mod k; находим остаток от деления n на k. Это последняя цифра

будущего числа

inc(s,r); прибавляем ее в s

p:=p*r; умножаем ее на p

n:=n div k находим частное от деления n на k.

end;

write(p-s); выводим разность произведения и суммы цифр

close(input);

close(output);

end.

системысчислениязадачи

Задача 9 Баллы для тестов

Директор фабрики пиджаков решил внедрить новую технологию проверки качества – тестовую. По замыслу специально обученные люди будут примерять на себе пиджаки и тестировать их по разработанной системе – на запах, длину рукавов, отрываемость карманов и т.п. За каждый тест начисляются либо все баллы, назначенные за этот тест (если тест пройден), либо 0. При этом директор хочет так назначить баллы за каждый тест, чтобы для любой набранной суммы баллов можно было точно сказать, какие тесты пройдены, а какие нет. Но и это еще не все: из всех возможных способов такого назначения баллов хочется выбрать такой, чтобы сумма баллов за все тесты к пиджаку была минимальной. Решение этой заковыристой задачки директор передоверил воспитанникам местного дома культуры, посулив решившему три рубля и новенький фабричный пиджачок. У вас есть шанс обзавестись пиджаком-трансформером с отрывающимися карманами и пришиваемым воротничком. Дерзайте!

Вход ные данные:

Число N (1 ≤ N ≤ 30) - количество тестов для пиджака.

Выходные данные:

Минимальная сумма баллов

Input.txt	Output.txt
1	1

Отмечая пройденный тест 1, а непройденный 0 получим последовательность из n нулей и единиц. Каждой такой последовательности соответствует одно десятичное число, если последовательность рассматривать как двоичное число. В условии задачи есть две фразы которые позволяют переформулировать задачу и сделать ее более понятной. Это фраза: для любой набранной суммы баллов можно было точно сказать, какие тесты пройдены, а какие нет и фраза : из всех возможных способов такого назначения баллов хочется выбрать такой, чтобы сумма баллов за все тесты к пиджаку была минимальной. Максимальная сумма баллов будет когда все тесты пройдены и тогда в двоичном числе будет n единиц и для люьой суммы баллов меньше максимальной мы можем точно определить какие тесты пройдены, а какие нет, переведя эту сумму в двоичное число. В новой формулировке задача будет выглядеть так: дано двоичное число состоящее из n единиц. Перевести его в десятичную систему счисления. Это можно сделать, используя схему Горнера для вычисления значения многочлена при х=2. Все коэффициенты многочлена равны 1. Но можно получить нужное число проще. Рассмотрим пример. Пусть n=3. Тогда все возможные результаты тестирования:

2-я 10-я

000=0

001=1

010=2

011=3

100=4

101=5

110=6

111=7

Следующее число будет 1000₂=8₁₀=1*2³. Тогда 7=2³-1. В общем случае 2ⁿ-1. Таким образом достаточно посчитать значение этого выражения. Это число укладывается в тип longint.

Program test;

Var i,n,p:longint;

Begin

Assign(input,’input.txt’);

Reset(input);

Assign(output,’output.txt’);

Rewrite(output);

Read(n);

P:=1;

For i:=1 to n do

P:=p*2;

Dec(p);

Write(p);

Close(input);

Close(output);

End.

системысчислениязадачи

Задача 10 Двоичное число

Планета Шелезяка. . Полезных ископаемых на планете нет.

Воды тоже нет. Атмосферы нет. Ничего на планете нет. Если

что и было, роботы все истратили и живут в бедности

Кир Булычев Путешествие Алисы

Как известно, планета Шелезяка расположена в отдаленной части нашей Галактики, в стороне от космических трасс. Воду роботы (единственные обитатели планеты во второй половине 21-го века) ликвидировали специально, чтобы не ржаветь (они опасались ливней и наводнений). В связи с этим планета оказалась решительно никому кроме роботов не нужна. Однажды на пустынную планету прилетели пираты. То были настоящие матерые злодеи. Их сердцу была неведома жалость. Они захватили почти всех роботов и увезли их в далекую-далекую галактику и заставили работать на шахтах на планете Бендомир. Прошло немало времени, прежде чем про это стало известно на Земле. Ричард Темпест, бесстрашный сотрудник института Времени, отправился в прошлое с целью помешать дьявольским планам пиратов. Как оказалось, пользуясь гостеприимством роботов, пираты предлагали роботам решить задачку на скорость. Однако вычислительные возможности роботов были не велики, а оптимизировать алгоритмы их работы было некому. Поэтому все, что оставалось злодеям загрузить в трюм корабля бесчувственные тела роботов, поглощенных вычислениями. Ричарду удалось узнать, над чем безуспешно бились электронные мозги роботов. Пираты предлагали им целое неотрицательное число n. После этого они просили узнать, что произойдет с этим числом, если к нему n раз применить операцию: взять старший бит в двоичной записи числа и поставить его в конец. Например, если один раз применить эту операцию к числу 1410 = 11102 , получится 1310 = 11012 . После повторного применения получится 1110 = 10112 . Ричард присвистнул. Если ему удастся раздобыть программу, которая быстро решает эту задачу, он сможет отправиться во времена до прилета пиратов и загрузить в роботов эту программу, чтобы они смогли противостоять злобным пиратам.

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

Формат входного файла

В первой строке входного файла содержится целое число n (0 ≤ n ≤ 10¹⁸ ).

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

number.in	number.out
0	0
14	7

program z_F;

{$APPTYPE CONSOLE}

{$O-}

uses SysUtils, Math;

var p, n, res:int64;

i, t, m:integer;

begin

AssignFile(input, 'number.in'); reset(input);

AssignFile(output, 'number.out'); rewrite(output);

read(n);

res:=n;

t:=0;

if n=0 then частный случай n=0

begin

write(0);

halt(0);

end;

if n=1 then частный случай n=1

begin

write(1);

halt(0);

end;

if n=2 then частный случай n=2

begin

write(1);

halt(0);

end;

t:=trunc(log2(n)); меньшее на 1 количество цифр в

двоичной записи числа

if (1 shl t)<>n then inc(t); если 2^t <>n,

то увеличиваем на 1

количество цифр.

m:=0;

if n div t >0 then

begin

for i:=1 to t do

if (1 and(n shr i))=1 then inc(m); если n при делении на 2ⁱ дает остаток 1

res:=1;

res:=(res shl m)-1;

end ;

write(res);

сlose(input);Close(output);

halt(0);

end.

системысчислениязадачи