Презентация на тему: РАЙОННАЯ ОЛИМПИАДА ПО ПРОГРАММИРОВАНИЮ

Реклама. Продолжение ниже
РАЙОННАЯ ОЛИМПИАДА ПО ПРОГРАММИРОВАНИЮ
Задача 1. «Речные гонки»
Задача 1. «Речные гонки»
Задача 1. «Речные гонки»
Задача 1. «Речные гонки»
Задача 1. «Речные гонки»
Задача 2. « Сеть »
Задача 2. « Сеть »
Задача 2. « Сеть »
Задача 1. «Сеть»
Задача 2. « Сеть »
Задача 2. « Сеть »
Задача 2. « Сеть »
Задача 2. « Сеть »
Задача 3. « Большое число »
Задача 3. « Большое число »
Задача 3. « Большое число »
Задача 3. « Большое число »
Задача 3. « Большое число »
Задача 3. « Большое число »
Задача 3. « Большое число »
Задача 3. « Большое число »
Задача 3. « Большое число »
Задача 4. « Ох, уж эти скобки »
Задача 4. « Ох, уж эти скобки »
Задача 4. « Ох, уж эти скобки »
Задача 4. « Ох, уж эти скобки »
Задача 4. « Ох, уж эти скобки »
Задача 4. « Ох, уж эти скобки »
Задача 4. « Ох, уж эти скобки »
Задача 4. « Ох, уж эти скобки »
Задача 4. « Ох, уж эти скобки »
Задача 4. « Ох, уж эти скобки »
Задача 4. « Ох, уж эти скобки »
Задача 4. « Ох, уж эти скобки »
Задача 4. « Ох, уж эти скобки »
Задача 4. « Ох, уж эти скобки »
Задача 4. « Ох, уж эти скобки »
Задача 4. « Ох, уж эти скобки »
Задача 4. « Ох, уж эти скобки »
Задача 5. « Разбиение числа »
Задача 5. «Разбиение числа»
Задача 5. «Разбиение числа»
Задача 5. «Разбиение числа»
Задача 5. «Разбиение числа»
Задача 5. «Разбиение числа»
Задача 6. « НОК »
Задача 6. « НОК »
Задача 6. «НОК»
Задача 6. «НОК»
Задача 6. «НОК»
Задача 6. «НОК»
Задача 6. «НОК»
Задача 6. «НОК»
Задача 6. «НОК»
Задача 6. «НОК»
Задача 6. «НОК»
Задача 6. «НОК»
Задача 6. «НОК»
1/59
Средняя оценка: 4.9/5 (всего оценок: 75)
Код скопирован в буфер обмена
Скачать (129 Кб)
Реклама. Продолжение ниже
1

Первый слайд презентации: РАЙОННАЯ ОЛИМПИАДА ПО ПРОГРАММИРОВАНИЮ

8 декабря 20 1 6 года

Изображение слайда
1/1
2

Слайд 2: Задача 1. «Речные гонки»

Егор и Петр участвуют в речной гонке на лодках: участники одновременно стартуют в пункте A и должны проплыть против течения реки в пункт B. Тот, кто приплывет первым, объявляется победителем. В результате жеребьевки Егору и Петру выпало участвовать в одном заплыве. Нам известны скорости движения лодок ребят и скорость течения реки. Ваша задача – определить, кто же из них победит.

Изображение слайда
1/1
3

Слайд 3: Задача 1. «Речные гонки»

Входной файл river.in : В первой строке ввода содержатся три целых числа: V1 – скорость лодки Егора, V2 – скорость лодки Петра и V3 – скорость течения реки (0 ≤ V1, V2, V3 ≤ 10 6 ). Выходной файл river.out : Выводится одна строка, содержащая следующий текст: " EGOR ", если первым приплывет Егор; " PETR ", если первым приплывет Петр; "R IVER ", если победителя определить не удалось.

Изображение слайда
1/1
4

Слайд 4: Задача 1. «Речные гонки»

Примеры: river.in river.out 10 5 1 EGOR 4 5 2 PETR 6 6 2 RIVER

Изображение слайда
1/1
5

Слайд 5: Задача 1. «Речные гонки»

Победитель будет выявлен в том случае, если скорость одного из мальчиков будет больше скорости другого и больше скорости реки. Если же скорости мальчиков одинаковы или скорости обоих мальчиков меньше скорости реки, то победителя нет.

Изображение слайда
1/1
6

Слайд 6: Задача 1. «Речные гонки»

var v1, v2, v3 : longint; f_in, f_out : text; begin assign(f_in,'river10.in'); reset(f_in); readln(f_in,v1,v2,v3); close(f_in); assign(f_out,'river.out'); rewrite(f_out); if (v1>v2) and (v1>v3) then write(f_out,'EGOR'); if (v2>v1) and (v2>v3) then write(f_out,'PETR'); if (v1=v2) or ((v1<=v3) and (v2<=v3)) then write(f_out,'RIVER'); close(f_out); end.

Изображение слайда
1/1
7

Слайд 7: Задача 2. « Сеть »

Для проведения олимпиады организаторы планируют объединить компьютеры участников в сеть. Из сетевого оборудования в наличии есть N коммутаторов и неограниченное количество сетевых кабелей. Коммутатор с номером i ( 1 ≤ i ≤ n ) характеризуется числом a i — количеством портов в этом коммутаторе. Организаторы могут соединить кабелем либо два коммутатора, либо два компьютера, либо коммутатор и компьютер. Каждый коммутатор может быть соединен кабелями не более чем с a i устройствами (коммутаторами или компьютерами), каждый компьютер — не более чем с одним.

Изображение слайда
1/1
Реклама. Продолжение ниже
8

Слайд 8: Задача 2. « Сеть »

Два компьютера могут обмениваться данными, если от одного из них до другого можно добраться по кабелям, возможно, пройдя при этом по цепочке из коммутаторов. Организаторы хотят построить сеть таким образом, чтобы каждые два компьютера могли обмениваться данными. Какое максимальное количество компьютеров организаторы могут объединить в сеть, используя имеющиеся коммутаторы?

Изображение слайда
1/1
9

Слайд 9: Задача 2. « Сеть »

Входной файл network.in : В первой строке входного файла находится одно число N — количество коммутаторов, имеющихся у организаторов ( 0 ≤  N  ≤ 10 5 ). Во второй строке файла находится N чисел a i — количество портов в коммутаторе с номером i ( 1 ≤  a i  ≤ 10 9, 1 ≤  i  ≤  N ). Выходной файл network.out : Выводится единственное число — максимальное количество компьютеров, которое удастся объединить в сеть, используя имеющиеся коммутаторы.

Изображение слайда
1/1
10

Слайд 10: Задача 1. «Сеть»

Примеры: network.in network.out 3 10 4 5 15 2 1 10 10 2 3 10 11

Изображение слайда
1/1
11

Слайд 11: Задача 2. « Сеть »

Обратим внимание на то, что коммутатор с одним портом бесполезен и, более того, вреден – он занимает порт у другого коммутатора, к которому мог быть подключен компьютер. Точно также бесполезен (хотя и не вредит!) коммутатор с двумя портами. Таким образом все коммутаторы, у которых один или два порта, необходимо исключить из рассмотрения. Найдем количество коммутаторов m, у которых портов больше 2, а также общее количество портов у всех таких коммутаторов sp.

Изображение слайда
1/1
12

Слайд 12: Задача 2. « Сеть »

По окончании цикла проверим m. Если m= 0, т.е. не задействован ни один коммутатор, то соединить можно только два компьютера. В противном случае, для объединения в сеть m коммутаторов необходимо m-1 соединение, т.е. 2( m -1) порт. Таким образом, искомое количество компьютеров равно sp - 2( m -1).

Изображение слайда
1/1
13

Слайд 13: Задача 2. « Сеть »

var n, i, p, m : longint; k, sp : int64; f_in, f_out : text; begin assign(f_in,'network.in'); reset(f_in); readln(f_in,n); sp:=0; m:=0; for i:=1 to n do begin

Изображение слайда
1/1
14

Слайд 14: Задача 2. « Сеть »

read(f_in, p); if p>2 then begin sp:=sp+p; inc(m); end; end; close(f_in); if m=0 then k:=2 else k:=sp-2*(m-1); assign(f_out,'network.out'); rewrite(f_out); write(f_out,k); close(f_out); end.

Изображение слайда
1/1
Реклама. Продолжение ниже
15

Слайд 15: Задача 3. « Большое число »

Дано целое число N, состоящее из четного количества десятичных цифр. Над ним последовательно производятся следующие действия: 1. цифры числа разделяются на две равные половины; 2. левая и правая половины разворачиваются, то есть порядок следования цифр меняется на противоположный; 3. аналогичные действия выполняются для частей числа без первой и последней цифры, и так далее.

Изображение слайда
1/1
16

Слайд 16: Задача 3. « Большое число »

Когда останется последняя цифра первой половины числа и первая — второй, процесс останавливается, так как разворачивать их не имеет смысла. Рассмотрим пример. Пусть N = 1234567890. Тогда в процессе выполнения указанных действий будет получена следующая цепочка: 5432109876, 5123478906, 5143298706, 5142389706. Ваша задача — узнать результат последовательности указанных преобразований.

Изображение слайда
1/1
17

Слайд 17: Задача 3. « Большое число »

Входной файл bignum.in : Входной файл содержит единственное число N ( не более 10000 цифр ). Допускаются нули в начале записи числа. Выходной файл bignum.out : Выходной файл должен содержать единственное число — результат применения всех действий.

Изображение слайда
1/1
18

Слайд 18: Задача 3. « Большое число »

Примеры: bignum.in bignum.out 1234567890 5142389706 000123 000231 012039 201390

Изображение слайда
1/1
19

Слайд 19: Задача 3. « Большое число »

Т.к. исходное число может содержать в начале нули, то хранить его нужно в строковом виде. А т.к. в нем может быть до 10000 цифр, то будем использовать тип AnsiString. Пусть n – количество цифр в числе; np – количество цифр в половине числа; k – номер цифры в 1-й половине числа, с которой должна начаться перестановка цифр. Тогда np-k+1 - количество переставляемых цифр в одной половине; ( np-k+1) div 2 - количество перестановок.

Изображение слайда
1/1
20

Слайд 20: Задача 3. « Большое число »

Пусть i – номер перестановки ( 1≤ i ≤ ( np-k+1) div 2 ), тогда в 1-й половине переставляются цифры на позициях k+i-1 и np-i+1, а во 2-й половине – на позициях np+i и n-k-i+2. В начале k=1, затем, после выполнения всех перестановок для этого значения k, оно увеличивается на 1. Данный цикл перестановок продолжается до тех пор, пока k не сравняется с np.

Изображение слайда
1/1
21

Слайд 21: Задача 3. « Большое число »

var n, i, k, np : longint; d : AnsiString; s : char; f_in, f_out : text; begin assign(f_in, 'bignum.in'); reset(f_in); readln(f_in,d); close(f_in); n:=length(d); np:=n div 2;

Изображение слайда
1/1
22

Слайд 22: Задача 3. « Большое число »

k:=1; while k<>np do begin for i:=1 to (np-k+1) div 2 do begin s:=d[k+i-1]; d[k+i-1]:=d[np-i+1]; d[np-i+1]:=s; s:=d[np+i]; d[np+i]:=d[n-k-i+2]; d[n-k-i+2]:=s; end; inc(k); end;

Изображение слайда
1/1
23

Слайд 23: Задача 3. « Большое число »

assign(f_out,'bignum.out'); rewrite(f_out); write(f_out,d); close(f_out); end.

Изображение слайда
1/1
24

Слайд 24: Задача 4. « Ох, уж эти скобки »

Математическое выражение записано в виде произведения: ( ± a 2 x 2 ± a 1 x ± a 0 )∙( ±b 2 x 2 ±b 1 x ±b 0 )∙( ±c 2 x 2 ±c 1 x ±c 0 )∙ … Внутри каждой из N скобок произведения находится выражение вида: ± a 2 x 2 ± a 1 x ± a 0, где хотя бы один из коэффициентов a i не равен нулю ( b i, c i и т.д., аналогично).

Изображение слайда
1/1
25

Слайд 25: Задача 4. « Ох, уж эти скобки »

Требуется составить программу, которая перемножает выражения в скобках и выводит полученную функцию в виде многочлена с приведенными по степеням x слагаемыми, то есть в виде: ±q 2N x 2N ±q 2N-1 x 2N-1 ± …±q 3 x 3 ±q 2 x 2 ±q 1 x ±q 0.

Изображение слайда
1/1
26

Слайд 26: Задача 4. « Ох, уж эти скобки »

Входной файл brackets.in : В первой строке входного файла находится число N ( 1 ≤ N ≤ 6 ). Во второй строке находится выражение из N пар скобок. Внутри каждой пары скобок находится выражение в виде « ±a 2 x^2±a 1 x±a 0 », где « ±» — это или знак « + », или знак « − ». Значение каждого из коэффициентов a i, b i, c i и т.д. не превышает 10.

Изображение слайда
1/1
27

Слайд 27: Задача 4. « Ох, уж эти скобки »

Выражение составлено по следующим правилам: Всё выражение записывается, начиная со старшей степени переменной по убыванию степеней. Если какой-то коэффициент равен нулю, то этот коэффициент и соответствующий ему x опускаются в записи вместе с арифметическим знаком. Исключением является случай, когда все коэффициенты равны нулю. В этом случае вместо всего выражения указывается единственный коэффициент 0. Если a i =±1 и i >0, то единица перед соответствующим ему x не ставится. Если первый отличный от нуля коэффициент положителен, то знак « + » перед ним опускается. В выражении отсутствуют пробельные символы (пробел, табуляция) и знаки умножения.

Изображение слайда
1/1
28

Слайд 28: Задача 4. « Ох, уж эти скобки »

Выходной файл brackets.in : В первой строке выходного файла выводится результат раскрытия скобок в исходном выражении в следующем формате: ±q 2N x^(2N)±q 2N-1 x^(2N-1)±…±q 1 x±q 0. Формат выражения должен полностью соответствовать описанию для входного файла. Скобки вокруг степеней ставить не нужно, они приведены здесь только для читабельности.

Изображение слайда
1/1
29

Слайд 29: Задача 4. « Ох, уж эти скобки »

Примеры : brackets.in brackets.out 1 ( 3xˆ2+2x-1) 3xˆ2+2x-1 2 (4xˆ2+3x+5)(2xˆ2+4x+1) 8xˆ4+22xˆ3+26xˆ2+23x+5 3 (-x+7)(x)(xˆ2+x+1) -xˆ4+6xˆ3+6xˆ2+7x 6 (1)(2)(3)(4)(5)(6) 720

Изображение слайда
1/1
30

Слайд 30: Задача 4. « Ох, уж эти скобки »

В массиве r[1..3,1..13] будем записывать коэффициенты трех многочленов ( в 1-й строке – 1-й множитель, во 2-й строке – 2-й множитель, в 3-й строке – произведение. Процедура Skobka записывает коэффициенты трехчлена одной скобки либо в 1-ю либо во 2-ю строки массива. Процедура Sol перемножает многочлен 1-й строки массива на трехчлен 2-й строки массива, при этом результат сначала получается в 3-й строке, а затем переносится в 1-ю строку. Процедура Output выводит полученный результат.

Изображение слайда
1/1
31

Слайд 31: Задача 4. « Ох, уж эти скобки »

В процедуре Skobka сначала в строке s ищется позиция p символов x^. Если p>0, то s[1].. s[p-1] образуют коэффициент при x 2. При этом нужно учесть случаи, когда p=1 (x^2), p=2 и s[1]=‘-’ (-x^2). Символы с 1 по p +2 в строке s удаляются. Затем в строке s ищется позиция p символа x. Если p>0, то s[1].. s[p-1] образуют коэффициент при x. При этом нужно учесть случаи, когда p=1 (x), p=2 и s[1]=‘-’ (-x), p=2 и s[1]=‘ + ’ ( + x). Символы с 1 по p в строке s удаляются. Оставшиеся символы в строке s образуют свободный член трехчлена.

Изображение слайда
1/1
32

Слайд 32: Задача 4. « Ох, уж эти скобки »

Рассмотрим принцип работы процедуры Sol на примере нахождения коэффициента c 8 : c 8 x 8 = a 8 x 8 ∙b 0 +a 7 x 7 ∙b 1 x+a 6 x 6 ∙b 2 x 2 =(a 8 b 0 +a 7 b 1 +a 6 b 2 )∙x 8 C 8 = a 8 b 0 +a 7 b 1 +a 6 b 2 Остальные коэффициенты находятся аналогично. x x 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 x 0 i 1 2 3 4 5 6 7 8 9 10 11 12 13 a a 10 a 9 a 8 a 7 a 6 a 5 a 4 a 3 a 2 a 1 a 0 b b 2 b 1 b 0 c c 12 c 11 c 10 c 9 c 8 c 7 c 6 c 5 c 4 c 3 c 2 c 1 c 0

Изображение слайда
1/1
33

Слайд 33: Задача 4. « Ох, уж эти скобки »

При выводе результата необходимо учитывать следующие моменты; Перед каждым положительным коэффициентом, кроме первого слагаемого, должен стоять знак +. Коэффициент 1 не выводится. У коэффициента -1 выводится только знак -. Пункты 2 и 3 не распространяются на вывод свободного члена. Если все коэффициенты результата равны 0, то необходимо вывести 0.

Изображение слайда
1/1
34

Слайд 34: Задача 4. « Ох, уж эти скобки »

var n, i, p : longint; r : array[1..3,1..13] of longint; s : String; f_in, f_out : text; procedure skobka(s:string;k:integer); var p, i, t : integer; begin for i:=1 to 13 do r[k,i]:=0;

Изображение слайда
1/1
35

Слайд 35: Задача 4. « Ох, уж эти скобки »

p:=pos('x^',s); if p>0 then begin if p=1 then r[k,11]:=1 else if (p=2) and (s[1]='-') then r[k,11]:=-1 else val(copy(s,1,p-1),r[k,11],t); delete(s,1,p+2); end; p:=pos('x',s);

Изображение слайда
1/1
36

Слайд 36: Задача 4. « Ох, уж эти скобки »

if p>0 then begin if p=1 then r[k,12]:=1 else if (p=2) and (s[1]='+') then r[k,12]:=1 else if (p=2) and (s[1]='-') then r[k,12]:=-1 else val(copy(s,1,p-1),r[k,12],t); delete(s,1,p); end; val(s,r[k,13],t); end;

Изображение слайда
1/1
37

Слайд 37: Задача 4. « Ох, уж эти скобки »

procedure sol; var i,j:integer; begin for i:=1 to 13 do r[3,i]:=0; for i:=2 downto 0 do for j:=10 downto 0 do r[3,13-i-j]:=r[3,13-i-j]+r[1,13-j]*r[2,13-i]; for i:=1 to 13 do r[1,i]:=r[3,i]; end;

Изображение слайда
1/1
38

Слайд 38: Задача 4. « Ох, уж эти скобки »

procedure output; var f:integer; begin f:=0; for i:=1 to 13 do if r[1,i]<>0 then begin if (f=1) and (r[1,i]>0) then write(f_out,'+'); if r[1,i]=-1 then if i=13 then write(f_out,'-1‘) else write(f_out,'-‘) else if (r[1,i]<>1) or (i=13) then write(f_out,r[1,i]); if i<13 then write(f_out,'x'); if i<12 then write(f_out,'^',13-i); f:=1; end if f=0 then write(f_out,0); end;

Изображение слайда
1/1
39

Слайд 39: Задача 4. « Ох, уж эти скобки »

begin assign(f_in,'brackets1.in'); reset(f_in); readln(f_in,n); readln(f_in,s); close(f_in); if n=1 then skobka(copy(s,2,length(s)-2),1) else begin p:=pos(')',s); skobka(copy(s,2,p-2),1); delete(s,1,p); for i:=2 to n do begin p:=pos(')',s); skobka(copy(s,2,p-2),2); delete(s,1,p); sol; end; end;

Изображение слайда
1/1
40

Слайд 40: Задача 4. « Ох, уж эти скобки »

assign(f_out,'brackets.out'); rewrite(f_out); output; close(f_out); end.

Изображение слайда
1/1
41

Слайд 41: Задача 5. « Разбиение числа »

Факториалом числа n называется произведение n!=1·2·...·n при n>0 и n!=1 при n=0. Количество сочетаний из n элементов по k определяется следующим образом: C n k =n!/(k!(n-k)!), если 0≤k≤n, и C n k = 0, если k>n. В математике такие числа называются также биномиальными коэффициентами. Требуется представить заданное число P в виде суммы трех биномиальных коэффициентов: P=C a 1 +C b 2 +C c 3, 0≤a<b<c

Изображение слайда
1/1
42

Слайд 42: Задача 5. «Разбиение числа»

Входной файл decomp.in : Входной файл содержит единственное число P ( 1 ≤ P ≤ 10 18 ). Формат выходного файла decomp.out : В выходной файл выводится искомые числа a, b, c ( 0 ≤ a < b < c ), разделённые пробелами. Если задача не имеет решения, выведите три нуля. Примеры : decomp.in decomp.out 42 1 4 7 31 1 5 6

Изображение слайда
1/1
43

Слайд 43: Задача 5. «Разбиение числа»

Сначала определим, как вычислять значения C a 1, C b 2 и C c 3 : C a 1 = a!/(1! (a-1)!)=a, C b 2 =b!/(2!(b-2)!)=b(b-1)/2, C c 3 =c!/(3!(c-3)!)=c(c-1)(c-2)/6. Найдем наибольшее значение c, для которого значение C c 3 меньше введенного числа p. Для этого используем функцию fc, реализующую бинарный поиск в диапазоне от 2 до 2000000. Аналогично в диапазоне от 1 до 2000000 ищем наибольшее значение b, для которого C b 2 ≤ p - C c 3 (функция fb ). Находим a = p - C c 3 – C b 2.

Изображение слайда
1/1
44

Слайд 44: Задача 5. «Разбиение числа»

var p, s, n, i, a, b, c : int64; f_in, f_out : text; function fc(x:int64):int64; var min, max, s : int64; begin min:=2; max:=2000000; while max-min>1 do begin s:=(max+min) div 2; if s*(s-1)*(s-2) div 6>x then max:=s else min:=s end; fc:=min; end;

Изображение слайда
1/1
45

Слайд 45: Задача 5. «Разбиение числа»

function fb(x:int64):int64; var min, max, s : int64; begin min:=1; max:=2000000; while max-min>1 do begin s:=(max+min) div 2; if s*(s-1) div 2>x then max:=s else min:=s end; fb:=min; end;

Изображение слайда
1/1
46

Слайд 46: Задача 5. «Разбиение числа»

begin assign(f_in,'decomp.in'); reset(f_in); readln(f_in,p); close(f_in); c:=fc(p); p:=p-c*(c-1)*(c-2) div 6; b:=fb(p); a:=p-b*(b-1) div 2; assign(f_out,'decomp.out'); rewrite(f_out); write(f_out,a,' ',b,' ',c);; close(f_out); end.

Изображение слайда
1/1
47

Слайд 47: Задача 6. « НОК »

Наименьшим общим кратным (НОК) нескольких чисел называется наименьшее натуральное число, которое делится на каждое из этих чисел. Заданы два числа N и K. Требуется найти набор из N различных натуральных чисел, наименьшее общее кратное которых равняется K. Среди всех этих чисел не должно быть единицы и самого числа K.

Изображение слайда
1/1
48

Слайд 48: Задача 6. « НОК »

Входной файл lcm.in : В первой строке входного файла записаны через пробел два числа N и K ( 1 ≤ N ≤ 1000, 1 ≤ K ≤ 10 9 ). Выходной файл lcm.out : В выходной файл в первой строке выводится искомый набор из N чисел, разделённых пробелами. Если Вы смогли найти несколько наборов, то выведите любой из них. Если требуемого набора не существует, тогда выведите -1.

Изображение слайда
1/1
49

Слайд 49: Задача 6. «НОК»

Примеры : lcm.in lcm.out 2 14 2 7 12 20736 3 9 27 81 256 128 64 32 16 8 4 2 17 42 -1 7 123456 2 3 4 6 30864 41152 61728

Изображение слайда
1/1
50

Слайд 50: Задача 6. «НОК»

На 1-м этапе исходное число K разложим на простые множители: K=p 1 α 1 ∙p 2 α 2 ∙ … ∙p t α t. При этом простые делители p 1, p 2, …, p t будем хранить в массиве P, а количество таких делителей α 1, α 2, …, α t – в массиве KP. Определим общее количество делителей: r=( α 1 +1)( α 2 +1)…( α t +1)-2 Если окажется, что r<n ( или t<2 или n=1 ), то выводим -1. В противном случае переходим ко 2-му этапу.

Изображение слайда
1/1
51

Слайд 51: Задача 6. «НОК»

Вычислим и выведем два числа: d 1 =p t α t ( произведение всех наибольших простых делителей) и d 2 =K div p 1. В вспомогательный массив a запишем все степени первого простого делителя p 1. При этом запомним позицию в массиве, где закончились эти числа. Все степени второго простого делителя p 2 также запишем в массив a. Кроме того, туда же запишем все произведения этих степеней на все числа, ранее записанные в массив. При этом снова запомним конечную позицию в массиве. Эти же действия повторим для всех остальных простых делителей.

Изображение слайда
1/1
52

Слайд 52: Задача 6. «НОК»

Во время выполнения действий 2-го этапа нужно выполнять следующее: Все получаемые числа, если они не совпадают с d 1 и d 2, выводим в файл. Ведем подсчет количества выведенных чисел, как только это количество совпадет с N, работу программы завершаем.

Изображение слайда
1/1
53

Слайд 53: Задача 6. «НОК»

const maxp=1000000; var n, i, k, m, x, t, j, r, q, d, qq, l, d1, d2, kd : longint; p, kp : array[1..maxp] of longint; a : array[1..1000] of int64; f_in,f_out:text; begin assign(f_in,'lcm2.in'); reset(f_in); read ln(f_in,n,k); close(f_in); for i:=1 to maxp do kp[i]:=0;

Изображение слайда
1/1
54

Слайд 54: Задача 6. «НОК»

x:=k; while x mod 2=0 do begin inc(kp[1]); x:=x div 2; end; if kp[1]>0 then begin p[1]:=2; t:=2; end else t:=1;

Изображение слайда
1/1
55

Слайд 55: Задача 6. «НОК»

m:=3; repeat while x mod m=0 do begin inc(kp[t]); x:=x div m; end; if kp[t]>0 then begin p[t]:=m; inc(t); end; inc(m,2); until x=1; dec(t);

Изображение слайда
1/1
56

Слайд 56: Задача 6. «НОК»

r:=1; for i:=1 to t do r:=r*(kp[i]+1); r:=r-2; assign(f_out,'lcm.out'); rewrite(f_out); if (t<2) or (r<n) or (n=1) then write(f_out,-1) else begin d1:=1; for j:=1 to kp[t] do d1:=d1*p[i]; d2:=k div d1; write(f_out,d1,' ',d2,' '); kd:=2; if kd=n then begin close(f_out); halt end;

Изображение слайда
1/1
57

Слайд 57: Задача 6. «НОК»

q:=0; for i:=1 to t do begin d:=1; for j:=1 to kp[i] do begin d:=d*p[i]; inc(q); a[q]:=d; if (d<>d1) and (d<>d2) then begin write(f_out,d,' '); inc(kd); if kd=n then begin close(f_out); halt end; end end;

Изображение слайда
1/1
58

Слайд 58: Задача 6. «НОК»

if i>1 then begin for l:=1 to qq do begin d:=a[l]; for j:=1 to kp[i] do begin d:=d*p[i]; inc(q); a[q]:=d; if (d<>d1) and (d<>d2) then begin write(f_out,d,' '); inc(kd);

Изображение слайда
1/1
59

Последний слайд презентации: РАЙОННАЯ ОЛИМПИАДА ПО ПРОГРАММИРОВАНИЮ: Задача 6. «НОК»

if kd=n then begin close(f_out); halt end; end end; end; end; qq:=q; end; end; close(f_out); end.

Изображение слайда
1/1
Реклама. Продолжение ниже