ІНФОРМАТИКА для 9 класу


99 49 25477612258980856902730428600

Ідеї розв’язання задачі “Табори”

Шукана кількість дорівнює кількості способів вибору n різних натураль — них чисел із множини {1, 2, …, s–1} – кількості n-елементних підмножин (s–1)-елементної множини:

image

Можна обрати один із таких алгоритмів.

Скоротити на більший із факторіалів-добутків у знаменнику і, вико — риставши алгоритм Евкліда, скоротити на найбільші спільні дільники множники чисельника і знаменника, щоб подати знаменник добутком одиниць. У цьому випадку не гарантується дотримання обмежень на час.

Попередньо обчисливши всі прості числа від 1 до s (решето Ератос — фена), знайти степінь простого числа p у канонічному розкладі m! на прості множники: [m/p]+[m/p2]+[m/p3] + … і використати отриману інформацію для знаходження добутку. Саме такий підхід реалізовано в авторському розв’язанні цієї задачі.

На останньому етапі – множенні чисел базового типу – для повного розв’язання потрібно використати подання числа масивом його цифр – “довгу арифметику”. Інакше останніх три тести пройти неможливо.

Реалізація програми в середовищі Free Pascal.

Const m=200000; {Верхня межа n} mc=5000;

Base=1000000000; {Основа системи числення}

Varj, k,l, {Лічильники} h, n, {Вхідні дані} hn, {=h-n-i} nc, {Кількість цифр відповіді} np, {Кількість знайдених простих чисел} z: longint; y, r: qword; o: text;

S: array[i..m] of boolean; {Число просте?} c: array[i..mc] of qword; {Цифри відповіді} p: array[i..m] of longint; {Прості числа}

Читать  Формалізація та алгоритмізація обчислювальних процесів

Pp: array[i..m] of longint; {Степені простих чисел у розкладі відповіді на прості множники}

BEGIN

Assign(o,’camps. in’);

Reset(o); read(o, h,n); close(o);

Assign(o,’camps. out’); rewrite(o); dec(h); hn:=h-n;

//Пошук простих чисел for j:=i to h do s[j]:=true; for l:=2 to h div 2 do

If s[l] then

For k:=2 to h div l do s[k*l]:=false; np:=0;

For j:=2 to h do if s[j] then

Begin inc(np); p[np]:=j; pp[np]:=0 end;

//Пошук степенів простих чисел for j:=i to np do

Begin y:=i; repeat

Y:=y*p[j]; z:=h div y; inc(pp[j],z);

Until z=0; y:=i; repeat

Y:=y*p[j]; z:=n div y; dec(pp[j],z);

Until z=0; y:=1;

Repeat y:=y*p[j]; z:=hn div y; dec(pp[j],z);

Until z=0 end;

//Пошук цифр відповіді nc:=1; c[1]:=1;

For j:=1 to np do

For k:=1 to pp[j] do begin

R:=0;

For l:=1 to nc do begin

R:=r+p[j]*c[l]; c[l]:=r mod base; r:=r div base

End;

While r>0 do begin

Inc(nc);

C[nc]:=r mod base; r:=r div base

End end;

//Запис відповіді write(o, c[nc]);

[Всего голосов: 6    Средний: 3.5/5]