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

делится без остатка только на себя и единицу. Определить для заданного натурального N, является ли оно простым. Лимит времени 0.1 секунда.
Входные данные
Одно целое 0 < N ≤ 4000000000.
Выходные данные
Одно слово YES (без перевода строки), если N простое, либо слово NO, если N – составное.
Пример
Ввод Вывод
1223 YES
5000001 NO

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");
}

делители не в диапазоне до N-1, а до корня из N. В этом легко убедиться. Если у N есть делитель m>√N то N представимо в виде m×k, причем для k обязательно k<√N
Иначе получаем противоречие


#include
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");
}

>> 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");
}

Каждый уровень - это правильный N-угольник, угол которого совпадает с углом предыдущего. На сторонах первого уровня находится по две комнаты (в углах), на сторонах каждого следующего - на одну больше. Сколько в замке комнат?
Входные данные
Два целых числа N и K (3 ≤ N ≤ 106; 1 ≤ K ≤ 106).
Выходные данные
Выведите целое число - количество комнат в замке.
Пример
INPUT.TXT OUTPUT.TXT
6 3 28

от которой они начинают достраиваться. Сторона каждого следующего N-угольника содержит ровно на 1 комнату больше, чем сторона предыдущего. При этом каждый из N-угольников содержит такое же количество угловых вершин, что и предыдущий. Оно равно N-1.
Отсюда выводим формулу
#include
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 <}

std::cin >> n >> k;
std::cout << 1 + k*(n-1)+k*(k-1)*(n-2)/2;
}

888, образуют возрастающую последовательность
a1 = 192
…
a4 = 942
…
По номеру элемента последовательности найти его значение
Входные данные
Одно число N из диапазона 1< N ≤ 1000000.
Выходные данные
Одно число – значение aN элемента последовательности с номером N.

int n, i = 1;
cin >> n;
while (n){
i++;
if(i * i * i % 1000 == 888) n--;
}
cout << i;
return 0;
}

полезна при определении закономерности:
a1=192; a2=442; a3=692; a4=942; a5=1192…


#include
int main() {
int n;
std::cin >> n;
std::cout << 192 + 250*(n-1);
return 0;
}

тот, кто считает, что в одном килобайте 1000 байт, а хороший программист – это тот, кто полагает, что в одном километре 1024 метра.
Многим эта шутка понятна, так как все знают, что в процессах, связанных с информатикой и компьютерной техникой, фигурирует множество значений, выражаемых степенью двойки, то есть чисел вида 2K, где K – некоторое неотрицательное целое число. Назовем такие числа бинарными. Это такие числа как 2, 4, 8, 16, 32 и т.д.
Входные данные
N, не превосходящее 10000 по абсолютной величине.
Выходные данные
Выведите YES, если заданное число является бинарным, и NO в противном случае.
Примеры
№ Ввод Вывод
1 1024 YES
2 23 NO

main() {
int a;
double b;
cin >> a;
a = b = log2(a);
cout << (b == a ? "YES" : "NO");
}

превышающем 109.

#include
#include
int main(){
unsigned int x, cnt_digit;
std::cin >> x;
cnt_digit = log10(x) + 1;
std::cout << cnt_digit;
}

был вылить под каждое деревцо по ведру воды. Так как в день посадки шёл дождь, садовник начал поливку деревьев не в день посадки, а начиная с какого-то K-го дня.
Сколько дней садовник не поливал деревья, если в последний день он под каждое из деревьев вылил 1 / N часть воды из ведра, в предпоследний - 1 / (N - 1) часть, и т.д., а всего под каждое из деревьев вылил не более чем по половине ведра воды?
Входные данные
Количество деревьев N. 0 < N ≤ 1000000
Выходные данные
Искомое количество дней.
Пример
Ввод Вывод
3 2
1000000 606531

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;
}

нахождения их частичных сумм можно применить приближенную формулу Эйлера.

где n – количество членов ряда, а γ0,577 215 – постоянная Эйлера

#include
#include
int main() {
double n;
std::cin >> n;
std::cout << round(exp(log(n) +
0.41 / n - 0.5));
}

равенство:
N² = (N – 1)² + M²,
где М – целое число. Даны два целых числа А и В. Найти количество замечательных чисел из диапазона [A,B] включительно. Например, в диапазоне [1,10] таких чисел два, а именно числа 1 и 5.
Входные данные
Два целых числа А и В (1 ≤ A ≤ B ≤ 109), разделенных пробелом.
Выходные данные
Единственная строка - количество замечательных чисел из заданного диапазона.
Пример
Ввод Вывод
1 10 2

переборе возможных пар N и M для каждого числа диапазона [A;B]. Для больших значений B программа получит превышение лимита времени и не сможет пройти тесты. Попробуем оптимизировать перебор.
После несложных преобразований исходного равенства получим
2×N – 1= M²
В левой части этого равенства находится нечетное число, следовательно, М тоже нечетное и принадлежит отрезку от 1 до квадратного корня из числа 2×N–1. Так как максимальное значение N равно В, то правая граница отрезка, содержащего М, равна квадратному корню из числа 2*1000000000-1. Эта величина меньше 50000.

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;
}

чтобы вообще избавиться от перебора. Найдем наименьшее нечетное m1, такое что


и наибольшее нечетное m2, такое что


Очевидно, нечетных чисел от m1 до m2 всего

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;
}

известно, что все элементы в нем встречаются четное число раз. За исключением одного, который либо не повторяется, либо встречается нечетное число раз. Найдите этот элемент.
Входные данные
В первой строке одно целое неотрицательное число N≤105– общее количество элементов в наборе.
Во второй строке N целых чисел, по модулю не превосходящих 109.
Выходные данные
Единственное число x, повторяющееся нечетное количество раз.
Пример
Ввод Вывод
7
82 11 82 82 11 14 82 14

a, s = 0;
std::cin >> n;
while(n--) {
std::cin >> a;
s ^= a;
}
std::cout << s;
}

графств. Графства объединяются в конфедерации. Каждая конфедерация раз в год выбирает себе покровителя – одного из 200 жрецов. Конфедерации одновременно подают заявления (одно от конфедерации) в Совет Жрецов о том, кого они хотели бы видеть своим покровителем (если заявление не подано, то считают, что конфедерация хочет оставить себе того же покровителя). Все заявки удовлетворяются. Если несколько конфедераций выбирают одного и того же Жреца, то они навсегда объединяются в одну. Таким образом, каждый Жрец всегда является покровителем не более чем одной конфедерации. Требуется написать программу, позволяющую Совету Жрецов выяснить номер Жреца-покровителя каждого графства после Великих Перевыборов. В Совете все графства занумерованы (начиная с 1). Все Жрецы занумерованы числами от 1 до 200 (некоторые из них сейчас могут не быть ничьими покровителями).

графств в стране (1 ≤ N ≤ 5000) – и далее для каждого графства записан номер Жреца-покровителя конфедерации, в которую оно входит (графства считаются по порядку их номеров). Затем указаны заявления от конфедераций. Сначала записано число M – количество поданных заявлений, а затем M пар чисел (1 ≤ M ≤ 200): первое число – номер текущего Жреца-покровителя, второе – номер желаемого Жреца-покровителя.
Все числа во входных данных разделяются пробелами и (или) символами перевода строки.
Выходные данные
Вывести для каждого графства одно число – номер его Жреца-покровителя после Великих Перевыборов. Сначала – для первого графства, затем – для второго и т.д.
Пример
Ввод Вывод
7
1 1 5 3 1 5 1
2
5 1
1 3 3 3 1 3 3 1 3

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] << ' ';
}
}

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]) << ' ';
}

B. Записать их рядом, так чтобы получилось наибольшее число
Входные данные
Два числа, не превышающих 109, записаны через пробел.
Выходные данные
Одно число, составленное из первых двух, записанных рядом
Пример
Ввод Вывод
159 23 23159

b;
cin >> a >> b;
cout << max(a,b) << min(a,b);
}

2, 3, 5, 8, 13, 21...
Они определяются рекуррентным соотношением:
Fn = Fn-1 + Fn-2, F0 = F1 = 1.
Требуется найти последнюю цифру n-го числа Фибоначчи.
Входные данные
Одно целое число n (0 ≤ n ≤ 1018).
Выходные данные
Одно число - последнюю цифру числа Fn.
Примеры
№ Ввод Вывод
1 1 1
2 5 8

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);
}