На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 3 (разница в индексах элементов пары должна быть 3 или более, порядок элементов в паре неважен). Необходимо определить количество таких пар, для которых произведение элементов делится на 13.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (3 ≤ N ≤ 1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 3, в которых произведение элементов кратно 13.
Пример входных данных:
6
26
2
3
5
4
13
Пример выходных данных для приведённого выше примера входных данных:
5
Пояснение. Из шести заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: 26·5, 26·4, 26·13, 2·4, 2·13, 3·13. Из них на 13 делятся 5 произведений.
Требуется написать эффективную по времени и памяти программу для решения описанной задачи.
Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.
Объяснение
Так как число 13 – простое, значит нам достаточно хотя бы одного числа кратного 13, чтобы составить произведение кратное 13. В массиве будем смотреть на номер элемента, полученный путем вычисления остатка от порядка элемента и 3. Если этот элемент делится на 13, то в переменную count прибавляем единицу. При вводе очередного значения мы будем рассматривать его как потенциальную пару с элементом на 3 места ранее (с элементом который рассматриваем в массиве). Если очередное значение делится на 13, то прибавляем к ответу количество чисел без ближайших трех. Иначе прибавляем к ответу количество элементов делящихся на 13.
Решение на языке Паскаль
Показать решение|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
const k = 3; //требуемое расстояние между элементами const del = 13; //число на которое должно делиться произведение пары элементов var N: integer; mas: array[0..k - 1] of longint; //массив для хранения последних k элементов (элементы, кроме первого, которые сейчас не будут использоваться) a: integer; //очередное значение, подаваемое на вход программе count: integer; //количество делящихся на 29 элементов, без последних k элементов otv: uint64; //ответ c: integer; //переменная которая будет помогать нам при перестановке элементов в массиве begin count := 0; otv := 0; readln(N); for var i := 0 to k - 1 do readln(mas[i]); //считываем значения первых k элементов for var i := k to N - 1 do begin c := i mod k; readln(a); //считываем очередное значение if mas[c] mod del = 0 then count := count + 1; if a mod del = 0 then otv := otv + i - k + 1 else otv := otv + count; mas[c] := a; end; writeln(otv); end. |
Решение на языке Python
Показать решение|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
k = 3 #Требуемое расстояние между элементами otv = 0 #Ответ count = 0 #Количество чисел делящихся на 13, без последних k элементов N = int(input()) mas = [int(input()) for i in range(k)] #Массив хранения последних k значений for i in range(k + 1, N + 1): a = int(input()) if mas[0] % 13 == 0: count += 1 if a % 13 == 0: otv += i - k else: otv += count mas.pop(0) #Удаляем первый элемент и вставляем значение переменной a на последнее место mas.append(a) print(otv) |