Ликбез для подготовки учащихся к работе с системами проверки олимпиадных задач (Язык C++). Занятие №2. Уменьшение сложности алгоритмов.


#2. ОптимизацияЧайка К.В.Разбор задач на C++ 1. Убрать лишние итерацииТест простотыНатуральное число N называется простым, если оно делится без остатка только на себя и единицу. Определить для заданного натурального N, является ли оно простым. Лимит времени 0.1 секунда.Входные данныеОдно целое 0 < N ≤ 4000000000.Выходные данныеОдно слово YES (без перевода строки), если N простое, либо слово NO, если N – составное.ПримерВвод Вывод1223 YES5000001 NO 2. Тест простоты – решение #1#include <iostream>int main() { unsigned int n; bool isprime = true; std::cin >> n; for(unsigned int i = 2; i < n; i++) if(n % i == 0) isprime = false; // число составное std::cout << (isprime ? "YES" : "NO");} 3. Тест простоты – решение #1Улучшить решение задачи можно, если искать делители не в диапазоне до N-1, а до корня из N. В этом легко убедиться. Если у N есть делитель m>√N то N представимо в виде m×k, причем для k обязательно k<√NИначе получаем противоречие#include <iostream>int main() { unsigned int n; bool isprime = true; std::cin >> n; for(int i = 2; i * i <= n; i++) if(n % i ==0 ) isprime = false; std::cout << (isprime ? "YES" : "NO");} 4. Тест простоты – решение #3#include <iostream>int main(){ unsigned int n; std::cin >> n; bool isprime = n%2 && n>2; //простое нечетно for(int i=3; isprime && i*i<=n; i+=2) isprime=n % i; std::cout << (isprime ? "YES" : "NO");} 5. Убрать лишние циклы - прогрессииЗамок (acmp.ru)Замок состоит из K уровней. Каждый уровень - это правильный N-угольник, угол которого совпадает с углом предыдущего. На сторонах первого уровня находится по две комнаты (в углах), на сторонах каждого следующего - на одну больше. Сколько в замке комнат?Входные данныеДва целых числа N и K (3 ≤ N ≤ 106; 1 ≤ K ≤ 106). Выходные данныеВыведите целое число - количество комнат в замке. ПримерINPUT.TXT OUTPUT.TXT6 3 28 6. Замок – решение #1Рассмотрим «уровни» N-угольников. Начальным уровнем является комната, от которой они начинают достраиваться. Сторона каждого следующего N-угольника содержит ровно на 1 комнату больше, чем сторона предыдущего. При этом каждый из N-угольников содержит такое же количество угловых вершин, что и предыдущий. Оно равно N-1. Отсюда выводим формулу#include <iostream>unsigned long long n, k, r = 0, s, i;int main(){ std::cin >> n >> k; for(i = 0; i < k; i++) r += i; s = 1 + (n-1)*k + (n-2)*r; std::cout <<s;} 7. Замок – решение #2#include <iostream>unsigned long long n, k;int main(){ std::cin >> n >> k; std::cout << 1 + k*(n-1)+k*(k-1)*(n-2)/2;} 8. Кубы 888 - условиеВсе натуральные числа, кубы которых, заканчиваются на 888, образуют возрастающую последовательность a1 = 192 … a4 = 942 …По номеру элемента последовательности найти его значениеВходные данныеОдно число N из диапазона 1< N ≤ 1000000.Выходные данныеОдно число – значение aN элемента последовательности с номером N. 9. Кубы 888 – решение #1#include <iostream>using namespace std; int main(){ int n, i = 1; cin >> n; while (n){ i++; if(i * i * i % 1000 == 888) n--; } cout << i; return 0;} 10. Кубы 888 – решение #2Однако эта программа является вспомогательной и полезна при определении закономерности: a1=192; a2=442; a3=692; a4=942; a5=1192… #include <iostream>int main() { int n; std::cin >> n; std::cout << 192 + 250*(n-1); return 0;} 11. Матфункции вместо цикловБинарные числа (acmp.ru)Говорят, что плохой программист – это тот, кто считает, что в одном килобайте 1000 байт, а хороший программист – это тот, кто полагает, что в одном километре 1024 метра. Многим эта шутка понятна, так как все знают, что в процессах, связанных с информатикой и компьютерной техникой, фигурирует множество значений, выражаемых степенью двойки, то есть чисел вида 2K, где K – некоторое неотрицательное целое число. Назовем такие числа бинарными. Это такие числа как 2, 4, 8, 16, 32 и т.д. Входные данныеN, не превосходящее 10000 по абсолютной величине. Выходные данныеВыведите YES, если заданное число является бинарным, и NO в противном случае. Примеры№ Ввод Вывод1 1024 YES2 23 NO 12. Бинарные числа - решение#include <iostream>#include <cmath> //функция log2using namespace std; int main() { int a; double b; cin >> a; a = b = log2(a); cout << (b == a ? "YES" : "NO");} 13. Подсчет количества цифрОпределить количество цифр в натуральном числе x, не превышающем 109.#include<iostream>#include <cmath>int main(){ unsigned int x, cnt_digit; std::cin >> x; cnt_digit = log10(x) + 1; std::cout << cnt_digit;} 14. Суммы рядовСадовник (e-olymp)Садовник посадил за день N деревьев и должен был вылить под каждое деревцо по ведру воды. Так как в день посадки шёл дождь, садовник начал поливку деревьев не в день посадки, а начиная с какого-то K-го дня.Сколько дней садовник не поливал деревья, если в последний день он под каждое из деревьев вылил 1 / N часть воды из ведра, в предпоследний - 1 / (N - 1) часть, и т.д., а всего под каждое из деревьев вылил не более чем по половине ведра воды? Входные данныеКоличество деревьев N. 0 < N ≤ 1000000Выходные данныеИскомое количество дней.ПримерВвод Вывод3 21000000 606531 15. Садовник – решение #1 с циклами#include <iostream>int main() { int n, k, days = 0; double waterPerTree = 0; std::cin >> n; while(waterPerTree <= 0.5) waterPerTree += (double) 1 / (n - days++); k = n - days +1; std::cout << k;} 16. Садовник – решение #2Воспользуемся для этого свойствами гармонических рядов. Для нахождения их частичных сумм можно применить приближенную формулу Эйлера. где n – количество членов ряда, а γ0,577 215 – постоянная Эйлера#include <iostream>#include <cmath>int main() { double n; std::cin >> n; std::cout << round(exp(log(n) + 0.41 / n - 0.5));} 17. Замечательные числаНазовем целое число N замечательным, если для него справедливо равенство: N² = (N – 1)² + M², где М – целое число. Даны два целых числа А и В. Найти количество замечательных чисел из диапазона [A,B] включительно. Например, в диапазоне [1,10] таких чисел два, а именно числа 1 и 5.Входные данныеДва целых числа А и В (1 ≤ A ≤ B ≤ 109), разделенных пробелом.Выходные данныеЕдинственная строка - количество замечательных чисел из заданного диапазона.ПримерВвод Вывод1 10 2 18. Замечательные числа – решение #1Первое интуитивное решение задачи состоит в переборе возможных пар N и M для каждого числа диапазона [A;B]. Для больших значений B программа получит превышение лимита времени и не сможет пройти тесты. Попробуем оптимизировать перебор.После несложных преобразований исходного равенства получим 2×N – 1= M² В левой части этого равенства находится нечетное число, следовательно, М тоже нечетное и принадлежит отрезку от 1 до квадратного корня из числа 2×N–1. Так как максимальное значение N равно В, то правая граница отрезка, содержащего М, равна квадратному корню из числа 2*1000000000-1. Эта величина меньше 50000. 29. Замечательные числа – решение #1#include <iostream>using namespace std;int main() { int a, b, cnt = 0, n; cin >> a >> b; for(int m = 1; m*m <= 2e9; m += 2){ n = (m*m + 1)/2; if (a<=n && n<=b) cnt++; } cout << cnt;} 20. Замечательные числа – решение #2Второй лучший способ состоит в том, чтобы вообще избавиться от перебора. Найдем наименьшее нечетное m1, такое чтои наибольшее нечетное m2, такое чтоОчевидно, нечетных чисел от m1 до m2 всего 21. Замечательные числа – решение #2#include <iostream>using namespace std;int main() { int a, b, cnt = 0, n; cin >> a >> b; for(int m = 1; m*m <= 2e9; m += 2){ n = (m*m + 1)/2; if (a<=n && n<=b) cnt++; } cout << cnt;} 22. Оптимизация с помощью битовых операцийНечётно повторяемыйЗадан набор чисел, о которых известно, что все элементы в нем встречаются четное число раз. За исключением одного, который либо не повторяется, либо встречается нечетное число раз. Найдите этот элемент.Входные данныеВ первой строке одно целое неотрицательное число N≤105– общее количество элементов в наборе.Во второй строке N целых чисел, по модулю не превосходящих 109.Выходные данныеЕдинственное число x, повторяющееся нечетное количество раз.ПримерВвод Вывод782 11 82 82 11 14 82 14 23. Нечетно повторяемый – решение#include <iostream>int main(){ int n, a, s = 0; std::cin >> n; while(n--) { std::cin >> a; s ^= a; } std::cout << s;} 24. Оптимизация с помощью структур данныхВыборы жрецовНечётно повторяемыйСтрана состоит из маленьких графств. Графства объединяются в конфедерации. Каждая конфедерация раз в год выбирает себе покровителя – одного из 200 жрецов. Конфедерации одновременно подают заявления (одно от конфедерации) в Совет Жрецов о том, кого они хотели бы видеть своим покровителем (если заявление не подано, то считают, что конфедерация хочет оставить себе того же покровителя). Все заявки удовлетворяются. Если несколько конфедераций выбирают одного и того же Жреца, то они навсегда объединяются в одну. Таким образом, каждый Жрец всегда является покровителем не более чем одной конфедерации. Требуется написать программу, позволяющую Совету Жрецов выяснить номер Жреца-покровителя каждого графства после Великих Перевыборов. В Совете все графства занумерованы (начиная с 1). Все Жрецы занумерованы числами от 1 до 200 (некоторые из них сейчас могут не быть ничьими покровителями). 25. Выборы жрецовВходные данныеВ первой строке записано число N – количество графств в стране (1 ≤ N ≤ 5000) – и далее для каждого графства записан номер Жреца-покровителя конфедерации, в которую оно входит (графства считаются по порядку их номеров). Затем указаны заявления от конфедераций. Сначала записано число M – количество поданных заявлений, а затем M пар чисел (1 ≤ M ≤ 200): первое число – номер текущего Жреца-покровителя, второе – номер желаемого Жреца-покровителя. Все числа во входных данных разделяются пробелами и (или) символами перевода строки. Выходные данныеВывести для каждого графства одно число – номер его Жреца-покровителя после Великих Перевыборов. Сначала – для первого графства, затем – для второго и т.д. ПримерВвод Вывод71 1 5 3 1 5 125 11 3 3 3 1 3 3 1 3 26. Выборы жрецов – «лобовое» решение#include <iostream>using namespace std;int n, a[5000], m, b1[200], b2[200], i, j;int main(){ cin >> n; for(i = 0; i < n; i++) cin >> a[i]; cin >> m; for (i = 0; i < m; i++) cin >> b1[i] >> b2[i]; for (i = 0; i < n; i++){ for(j = 0; j < m; j++) if (b1[j]==a[i]) {a[i] = b2[j]; break;} cout << a[i] << ' '; }} 27. Выборы жрецов – ассоциативный массив#include <iostream>using namespace std;int n, m, a[5000], b[201] = {0,}, i;int main() { cin >> n; for(i = 0; i < n; i++) cin >> a[i]; cin >> m; while(m--) { cin >> i; cin >> b[i]; } for (i = 0; i < n; i++) cout << (b[a[i]] ? b[a[i]] : a[i]) << ' ';} 29. Лексикографический порядокСоставить число из двухИмеется два натуральных числа A и B. Записать их рядом, так чтобы получилось наибольшее числоВходные данныеДва числа, не превышающих 109, записаны через пробел.Выходные данныеОдно число, составленное из первых двух, записанных рядомПримерВвод Вывод159 23 23159 29. Составить из двух - решение#include <iostream>using namespace std;int main(){ string a, b; cin >> a >> b; cout << max(a,b) << min(a,b);} 30. Проверка периодичностиСнова Фибоначчи (acmp.ru)Вам наверняка знакомы числа Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21... Они определяются рекуррентным соотношением: Fn = Fn-1 + Fn-2, F0 = F1 = 1. Требуется найти последнюю цифру n-го числа Фибоначчи. Входные данныеОдно целое число n (0 ≤ n ≤ 1018). Выходные данныеОдно число - последнюю цифру числа Fn. Примеры№ Ввод Вывод1 1 12 5 8 31. Снова Фибоначчи- решение#include <cstdio>int main() { unsigned long long n; int n, a , b, c; a = b = c = 1; scanf("%d", &n); (n %= 60)--; if (n < 0) n = 59; while(n--){ c = a + b; if (c > 9) c -= 10; a = b; b = c; } printf("%d", c);}