Задача1. Многочлен
Заданий
многочлен вигляду:
Завдання Напишіть програму POLYNOM, яка за степенем многочлена N обчислить суму його коефіцієнтів за модулем 9973 після
розкриття дужок та зведення подібних членів.
Вхідні дані Єдиний рядок вхідного файлу POLYNOM.DAT містить одне ціле
число N (1≤N≤100) – степінь многочлена.
Вихідні дані Єдиний рядок
вихідного файлу POLYNOM.SOL має
містити єдине ціле число, що дорівнює сумі коефіцієнтів многочлена за модулем 9973
після розкриття дужок та зведення подібних (тобто остачу від ділення суми
коефіцієнтів на 9973).
Оцінювання Не менш ніж у 15% тестів число N не буде перевищувати 4. Не менш ніж у 50% тестів
число N не буде перевищувати 50.
Приклад вхідних та вихідних даних
POLYNOM.DAT
|
POLYNOM.SOL
|
2
|
100
|
Розв′язання.
const m = 9973;
var n,i,res,t,j
: longint;
f1,f2 : text;
begin
assign(f1,'POLYNOM.DAT'); reset(f1);
assign(f2,'POLYNOM.SOL'); rewrite(f2);
readln(f1,n);
res := 0;
for i := 1 to
(n*n) do
res := (res+i) mod m;
for i := 2 to n
do begin
t := 0;
for j := 1 to (n*n) do
t := (t+res*j) mod m;
res := t;
end;
writeln(f2,res);
close(f1); close(f2);
end.
Задача2. Відстань між числами
Нехай
числа a і b записані
у десятковій системі числення. Визначимо відстань між ними як:
(a1-b1)2+(a2-b2)2+(a3-b3)2+…, де ai позначає i-ту цифру числа a, а bi позначає i-ту цифру числа b. Нумерація цифр починається із молодшого розряду числа, якому відповідає номер 1. Якщо значення i більше, ніж довжина числа, то вважається, що i-та цифра рівна нулеві.
(a1-b1)2+(a2-b2)2+(a3-b3)2+…, де ai позначає i-ту цифру числа a, а bi позначає i-ту цифру числа b. Нумерація цифр починається із молодшого розряду числа, якому відповідає номер 1. Якщо значення i більше, ніж довжина числа, то вважається, що i-та цифра рівна нулеві.
Завдання Напишіть
програму NUMBERS, яка за
трьома цілими невід’ємними числами A, B та C знайде такі числа X і Y, для яких
виконуються умови:
1. A≤X≤B і A≤Y≤B
2. X є мінімальним
серед таких чисел, від яких відстань до C найменша
можлива.
3. Y є максимальним
серед таких чисел, від яких відстань до C найбільша
можлива.
Вхідні дані Перші три
рядки вхідного файлу NUMBERS.DAT містять
відповідно цілі числа A, B та C (0≤A≤B≤1018, 0≤C≤1018).
Вихідні дані Вихідний
файл NUMBERS.SOL має
містити два рядки, які містять відповідно цілі числа X та Y.
Оцінювання Щонайменше
у 50% тестів журі числа A, B та C не будуть
перевищувати 100 000.
Приклад вхідних та вихідних даних
NUMBERS.DAT
|
NUMBERS.SOL
|
11
25
130
|
20
19
|
Відстань
від числа 20 до числа 130: (1-0)2+(2-3)2+(0-0)2=1+1+0=2
Відстань
від числа 19 до числа 130: (1-0)2+(1-3)2+(9-0)2=1+22+92=1+4+81=86
Розв′язання.
varmax,maxa,min,mina:array[0..1000]of longint;
ttmp,a,b,c:string;
j,q1,q2,t,smin,smax,gmax,gmin,nn,i:longint;
procedure run(x,p:longint);
var i,q1,q2,q3:longint;
begin
if x>nn then
begin
if smin<gmin then
begin
gmin:=smin;
min:=mina;
end;
exit;
end;
q1:=ord(a[x])-48;
q2:=ord(b[x])-48;
q3:=ord(c[x])-48;
if p = 1 then
begin
mina[x+t]:=q3;
run(x+1,1);
end
else
begin
if p = 0 then
begin
mina[t+x]:=q1;
smin:=smin+(q3-q1)*(q3-q1);
run(x+1,2);
smin:=smin-(q3-q1)*(q3-q1);
for i:=q1+1 to q2-1 do
begin
mina[x+t]:=i;
smin:=smin+(q3-i)*(q3-i);
run(x+1,1);
smin:=smin-(q3-i)*(q3-i);
end;
mina[t+x]:=q2;
smin:=smin+(q3-q2)*(q3-q2);
run(x+1,3);
smin:=smin-(q3-q2)*(q3-q2);
end
else
if p = 2 then
begin
mina[x+t]:=q1;
smin:=smin+(q3-q1)*(q3-q1);
run(x+1,2);
smin:=smin-(q3-q1)*(q3-q1);
for i:=q1+1 to 9 do
begin
mina[x+t]:=i;
smin:=smin+(q3-i)*(q3-i);
run(x+1,1);
smin:=smin-(q3-i)*(q3-i);
end;
end
else
begin
for i:=0 to q2-1 do
begin
mina[x+t]:=i;
smin:=smin+(q3-i)*(q3-i);
run(x+1,1);
smin:=smin-(q3-i)*(q3-i);
end;
mina[t+x]:=q2;
smin:=smin+(q3-q2)*(q3-q2);
run(x+1,3);
smin:=smin-(q3-q2)*(q3-q2);
end;
end;
end;
procedure gen(x,p:longint);
var i,q1,q2,q3:longint;
begin
if x>nn then
begin
if smax>gmax then
begin
gmax:=smax;
max:=maxa;
end;
exit;
end;
q1:=ord(a[x])-48;
q2:=ord(b[x])-48;
q3:=ord(c[x])-48;
if p = 1 then
begin
if q3<5 then
begin
maxa[x+t]:=9;
smax:=smax+(9-q3)*(9-q3);
gen(x+1,1);
smax:=smax-(9-q3)*(9-q3);
end
else
begin
maxa[x+t]:=0;
smax:=smax+(0-q3)*(0-q3);
gen(x+1,1);
smax:=smax-(0-q3)*(0-q3);
end;
end
else
begin
if p = 0 then
begin
maxa[t+x]:=q2;
smax:=smax+(q3-q2)*(q3-q2);
gen(x+1,3);
smax:=smax-(q3-q2)*(q3-q2);
for i:=q2-1 downto q1+1 do
begin
maxa[x+t]:=i;
smax:=smax+(q3-i)*(q3-i);
gen(x+1,1);
smax:=smax-(q3-i)*(q3-i);
end;
maxa[t+x]:=q1;
smax:=smax+(q3-q1)*(q3-q1);
gen(x+1,2);
smax:=smax-(q3-q1)*(q3-q1);
end
else
if p = 2 then
begin
for i:=9 downto q1+1 do
begin
maxa[x+t]:=i;
smax:=smax+(q3-i)*(q3-i);
gen(x+1,1);
smax:=smax-(q3-i)*(q3-i);
end;
maxa[x+t]:=q1;
smax:=smax+(q3-q1)*(q3-q1);
gen(x+1,2);
smax:=smax-(q3-q1)*(q3-q1);
end
else
begin
maxa[t+x]:=q2;
smax:=smax+(q3-q2)*(q3-q2);
gen(x+1,3);
smax:=smax-(q3-q2)*(q3-q2);
for i:=q2-1 downto 0 do
begin
maxa[x+t]:=i;
smax:=smax+(q3-i)*(q3-i);
gen(x+1,1);
smax:=smax-(q3-i)*(q3-i);
end;
end;
end;
end;
begin
assign(input,'numbers.dat');reset(input);
assign(output,'numbers.sol');rewrite(output);
readln(a);
readln(b);
readln(c);
ttmp:=c;
nn:=length(a);
if length(b)>nn then nn:=length(b);
if length(c)>nn then nn:=length(c);
while length(a)<nn do a:='0'+a;
while length(b)<nn do b:='0'+b;
while length(c)<nn do c:='0'+c;
smin:=0;
smax:=0;
t:=0;
while (length(a)>0) do
begin
if a[1]=b[1] then
begin
inc(t);
q1:=ord(a[1])-48;
q2:=ord(c[1])-48;
mina[t]:=q1;
maxa[t]:=q1;
smin:=smin+(q1-q2)*(q1-q2);
smax:=smax+(q1-q2)*(q1-q2);
delete(a,1,1);
delete(b,1,1);
delete(c,1,1);
end
else break;
end;
nn:=length(a);
gmin:=10000000;
gmax:=0;
run(1,0);
j:=1;
while (j<nn+t)and(min[j]=0) do inc(j);
for i:=j to nn+t do write(min[i]);
writeln;
gen(1,0);
j:=1;
while (j<nn+t)and(max[j]=0) do inc(j);
if gmax=0 then
begin
writeln(ttmp);
end
else
begin
for i:=j to nn+t do write(max[i]);
writeln;
end;
close(input);close(output);
end.
Немає коментарів:
Дописати коментар