На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре неважен). Необходимо определить количество пар, для которых произведение элементов не кратно 14.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 1000.
В качестве результата программа должна вывести одно число: количество пар, в которых произведение элементов не кратно 14.
Пример входных данных:
4
2
6
5
42
Пример выходных данных для приведённого выше примера входных данных:
3
Пояснение. Из четырёх заданных чисел можно составить 6 попарных произведений: 2·6, 2·5, 2·42, 6·5, 6·42, 5·42. Из них на 14 не делятся 3 произведения (2·6, 2·5, 6·5).
Требуется написать эффективную по времени и памяти программу для решения описанной задачи.
Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.
Объяснение
14 = 2 * 7. Значит нам нужно найти количество пар, где оба из элементов не кратны 14 и их произведение не кратно 14 (то есть нам надо отсеивать пары, где один из элементов кратен 2, а другой кратен 7). Создадим 3 переменные, где будем хранить количество чисел кратных 2, но не кратных 14 (ch2), количество чисел кратных 7, но не кратных 14 (ch7) и другие числа не кратные 14 (ch). Далее суммируем количество сочетаний всех переменных и произведения ch на ch2 и ch на ch7. Теперь выводим ответ
Решение на языке Паскаль
Показать решение|
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 |
var N: integer; //Общее кол-во чисел ch2: integer;//Кол-во чисел делящихся на 2 но не делящихся на 14 ch7: integer;//Кол-во чисел делящихся на 7 но не делящихся на 14 ch: integer; //Кол-во оставшихся чисел не делящихся на 14 otv: integer; //Ответ a: integer;//Очередное число begin ch := 0; ch2 := 0; ch7 := 0; read(N); for var i := 1 to N do begin read(a); if a mod 14 <> 0 then begin if a mod 2 = 0 then ch2 := ch2 + 1 else if a mod 7 = 0 then ch7 := ch7 + 1 else ch := ch + 1; end; end; otv := ch * ch2 + ch * ch7 + ((ch - 1) * ch) div 2 + ((ch2 - 1) * ch2) div 2 + ((ch7 - 1) * ch7) div 2; write(otv); end. |
Решение на языке Python
Показать решение|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
ch2 = 0 #Кол-во чисел делящихся на 2 но не делящихся на 14 ch7 = 0 #Кол-во чисел делящихся на 7 но не делящихся на 14 ch = 0 #Кол-во оставшихся чисел не делящихся на 14 otv = 0 #Ответ N=int(input()) for i in range(N): a=int(input()) if a % 14 != 0: if a % 7 == 0: ch7 += 1 elif a % 2 == 0: ch2 += 1 else: ch+=1 otv = ch7 * ch + ch2 * ch + (ch-1) * ch / 2 + (ch2-1) * ch2 / 2 + (ch7-1) * ch7 / 2 print(int(otv)) |