Всякий, кто хочет побеждать на олимпиадах по программированию, должен знать изложенный здесь материал. И если вы все это усвоили, ваши шансы очень сильно возрастут. Так что учитесь и побеждайте :).
Книга алгоритмов (665 kb) - очень хорошая книга, в которой описывается огромное количество приемов программирования и алгоритмов. Рекомендую: очень нужный материал.
Лекции (250 kb) - лекции для участников олимпиад, также излагаются приемы решения задач и алгоритмы.
Задачи (191 kb) - задачи с разбором.
Задачи (161 kb) - олимпиадные задачи с разбором. В кодировке DOS.
Минимум (9,07 kb) - статья о том, что необходимо знать участнику олимпиад.
Оценка решений (15,6 kb) - статья о том, как оцениваются решения задач на олимпиадах.
|
неділю, 25 грудня 2016 р.
Переможцю олімпіад по програмуванню.
Різні види алгоритмів сортування
Математика
-- Длинные числа
-- Эффективное вычисление ДПФ и ДПХ
-- Теория чисел
-- Геометрия
-- Графы и маршруты
-- Комбинаторика и перебор
-- Приближение функций
-- Быстрые вычисления
-- Псевдослучайные последовательности
-- Линейная алгебра
-- Математическая статистика
-- Корни функций и нелинейных систем
-- Разное
Сортировка
-- Поразрядная
-- Быстрая
-- Пирамидальная
-- Слиянием
-- Пузырьком + модификации
-- Вставками
-- Шелла
-- Выбором
-- FAQ
-- Топологическая
-- Быстрая с составными ключами
Структуры данных
-- Введение в абстрактные структуры
-- АВЛ-деревья
-- Красно-черные деревья
-- Деревья со случайным поиском
-- Слоёные списки (скип-списки)
-- Хеш-таблицы
-- Б, Б+ и Б++ деревья
-- Обходы бинарных деревьев
-- Hashed Array Trees[Перевод]
-- StringBTree
-- Triangle Mesh
Поиск. Строки и последовательности
-- Точный подстроки в строке
-- Нечеткий поиск
-- Проверка на подпоследовательность
-- Общие подпоследовательности. Дистанция
-- Поиск hcs, lis, his
-- Максимальная повторяющаяся подстрока
-- Общие элементы двух массивов
-- Бинарный поиск
-- Интерполяционный поиск
-- Бинарный поиск с определением ближайших узлов
-- Частный случай lis
Графика
-- Удаление скрытых линий и поверхностей
-- Эффекты
-- Поиск ближайшего цвета
-- Рисование
-- Заливка области/многоугольника
-- Перевод цветов из режима RGB в HSV
-- Квантизация
-- Фильтры и спецэффекты. Яркость и контраст
-- Отсечение отрезка
-- Отсечение многоугольника
-- 2D Бампмэппинг
-- Вpащение pастpовой каpтинки
-- Demodesign FAQ
-- Фракталы
-- Лист папоротника
-- Множество Мандельброт
-- Длинные числа
-- Эффективное вычисление ДПФ и ДПХ
-- Теория чисел
-- Геометрия
-- Графы и маршруты
-- Комбинаторика и перебор
-- Приближение функций
-- Быстрые вычисления
-- Псевдослучайные последовательности
-- Линейная алгебра
-- Математическая статистика
-- Корни функций и нелинейных систем
-- Разное
Сортировка
-- Поразрядная
-- Быстрая
-- Пирамидальная
-- Слиянием
-- Пузырьком + модификации
-- Вставками
-- Шелла
-- Выбором
-- FAQ
-- Топологическая
-- Быстрая с составными ключами
Структуры данных
-- Введение в абстрактные структуры
-- АВЛ-деревья
-- Красно-черные деревья
-- Деревья со случайным поиском
-- Слоёные списки (скип-списки)
-- Хеш-таблицы
-- Б, Б+ и Б++ деревья
-- Обходы бинарных деревьев
-- Hashed Array Trees[Перевод]
-- StringBTree
-- Triangle Mesh
Поиск. Строки и последовательности
-- Точный подстроки в строке
-- Нечеткий поиск
-- Проверка на подпоследовательность
-- Общие подпоследовательности. Дистанция
-- Поиск hcs, lis, his
-- Максимальная повторяющаяся подстрока
-- Общие элементы двух массивов
-- Бинарный поиск
-- Интерполяционный поиск
-- Бинарный поиск с определением ближайших узлов
-- Частный случай lis
Графика
-- Удаление скрытых линий и поверхностей
-- Эффекты
-- Поиск ближайшего цвета
-- Рисование
-- Заливка области/многоугольника
-- Перевод цветов из режима RGB в HSV
-- Квантизация
-- Фильтры и спецэффекты. Яркость и контраст
-- Отсечение отрезка
-- Отсечение многоугольника
-- 2D Бампмэппинг
-- Вpащение pастpовой каpтинки
-- Demodesign FAQ
-- Фракталы
-- Лист папоротника
-- Множество Мандельброт
Декілька способів для алгоритмів Евклида
| http://amberv.ru/skachat-olimpiadnye-zadachi-algoritmy-lektsii.php
НОД, решение ax+by=1, нахождение обратного
элемента по модулю
| |||||
 | |||||
|
| ||||
Алгоритм Евклида. | |||||
| |||||
|
1. Вычислим r - остаток от деления числа
a на b, a = bq+r, 0 <= r < b.
2. Если r = 0, то b есть искомое число.
3. Если r =/= 0, то заменим пару чисел (a,b) парой (b,r)
и перейдем к шагу 1. int NOD(int a,int b)
{
while(a!=0 && b!=0)
{
if(a>=b) a=a%b;
else b=b%a;
}
return a+b; // Одно - ноль
}
| ||||
Бинарный алгоритм Евклида. | |||||
| |||||
|
Этот алгоритм использует соотношения для НОД:
НОД(2*a, 2*b) = 2*НОД(a,b) НОД(2*a, b) = НОД(a,b) при нечетном b, Он иллюстрируется следующей программой: m:= a; n:=b; d:=1;
{НОД(a,b) = d * НОД(m,n)}
while not ((m=0) or (n=0)) do begin
if (m mod 2 = 0) and (n mod 2 = 0) then begin
d:= d*2; m:= m div 2; n:= n div 2;
end else if (m mod 2 = 0) and (n mod 2 = 1) then begin
m:= m div 2;
end else if (m mod 2 = 1) and (n mod 2 = 0) then begin
n:= n div 2;
end else if (m mod 2=1) and (n mod 2=1) and (m>=n)then begin
m:= m-n;
end else if (m mod 2=1) and (n mod 2=1) and (m<=n)then begin
n:= n-m;
end;
end;
{m=0 => ответ=d*n; n=0 => ответ=d*m}
| ||||
Алгоритм решения уравнения ax+by = 1. | |||||
| |||||
|
1.Определим матрицу E:
2. Вычислим r - остаток от деления числа a на b, a=bq+r, 0 <= r < b.
3. Если r=0, то второй столбец матрицы E даёт вектор ( x, y ) решений уравнения.
4. Если r =/= 0, то заменим матрицу E матрицей
| ||||
Расширенный алгоритм Евклида. | |||||
| |||||
|
Алгоритм Евклида можно расширить так, что он не только даст НОД(a,b)=d, но и найдет целые числа x и y, такие что ax + by = d.
Псевдокод.НА ВХОДЕ: два неотрицательных числа a и b: a>=b
НА ВЫХОДЕ: d=НОД(a,b) и целые x,y: ax + by = d.
1. Если b=0 положить d:=a, x:=1, y:=0 и возвратить (d,x,y)
2. Положить x2:=1, x1:=0, y2:=0, y1:=1
3. Пока b>0
3.1 q:=[a/b], r:=a-qb, x:=x2-qx1, y:=y2-qy1
3.2 a:=b, b:=r, x2:=x1, x1:=x, y2:=y1, y1:=y
4. Положить d:=a, x:=x2, y:=y2 и возвратить (d,x,y)
Исходник на Си./* Author: Pate Williams (c) 1997 */ #include <stdio.h> #define DEBUG void extended_euclid(long a, long b, long *x, long *y, long *d) /* calculates a * *x + b * *y = gcd(a, b) = *d */ { long q, r, x1, x2, y1, y2; if (b == 0) { *d = a, *x = 1, *y = 0; return; } x2 = 1, x1 = 0, y2 = 0, y1 = 1; #ifdef DEBUG printf("------------------------------"); printf("-------------------\n"); printf("q r x y a b "); printf("x2 x1 y2 y1\n"); printf("------------------------------"); printf("-------------------\n"); #endif while (b > 0) { q = a / b, r = a - q * b; *x = x2 - q * x1, *y = y2 - q * y1; a = b, b = r; x2 = x1, x1 = *x, y2 = y1, y1 = *y; #ifdef DEBUG printf("%4ld %4ld %4ld %4ld ", q, r, *x, *y); printf("%4ld %4ld %4ld %4ld ", a, b, x2, x1); printf("%4ld %4ld\n", y2, y1); #endif } *d = a, *x = x2, *y = y2; #ifdef DEBUG printf("------------------------------"); printf("-------------------\n"); #endif } int main(void) { long a = 4864, b = 3458, d, x, y; extended_euclid(a, b, &x, &y, &d); printf("x = %ld y = %ld d = %ld\n", x, y, d); return 0; }
Алгоритм работает за O(log2n) операций.
| ||||
Нахождение обратного элемента по модулю | |||||
| |||||
|
Для начала заметим, что элемент a кольца Zn обратим тогда и только тогда, когда НОД(a,n)=1. То есть ответ есть не всегда. Из определения обратного элемента прямо следует алгоритм.
Псевдокод.НА ВХОДЕ: а из Zn.
НА ВЫХОДЕ: обратный к а в кольце, если он существует.
1. Использовать расширенный алгоритм Евклида для нахождения
x и y, таких что ax + ny = d, где d=НОД(a,n).
2. Если d > 1, то обратного элемента не существует.
Иначе возвращаем x.
Исходник на Си./* Author: Pate Williams (c) 1997 */ #include <stdio.h> void extended_euclid(long a, long b, long *x, long *y, long *d) /* calculates a * *x + b * *y = gcd(a, b) = *d */ { long q, r, x1, x2, y1, y2; if (b == 0) { *d = a, *x = 1, *y = 0; return; } x2 = 1, x1 = 0, y2 = 0, y1 = 1; while (b > 0) { q = a / b, r = a - q * b; *x = x2 - q * x1, *y = y2 - q * y1; a = b, b = r; x2 = x1, x1 = *x, y2 = y1, y1 = *y; } *d = a, *x = x2, *y = y2; } long inverse(long a, long n) /* computes the inverse of a modulo n */ { long d, x, y; extended_euclid(a, n, &x, &y, &d); if (d == 1) return x; return 0; } int main(void) { long a = 5, n = 7; printf("the inverse of %ld modulo %2ld is %ld\n", a, n, inverse(a, n)); a = 2, n = 12; printf("the inverse of %ld modulo %2ld is %ld\n", a, n, inverse(a, n)); return 0; } | ||||
НОК. | |||||
| |||||
|
НОК( a , b) = a*b / НОД(a, b)
| ||||
середу, 14 грудня 2016 р.
Літня школа з програмування та математики 2016
https://itolymp.com/school.php
З метою підвищення загального освітнього рівня учнів з математики та інформатики під час літніх канікул 2016 року з 10 по 20 липня буде проведено «Літню школу з програмування та математики 2016» для учнів 7—11 класів.
Проведення літньої школи планується на базі Національного еколого-натуралістичного центру учнівської молоді (НЕНЦ) за адресою: м. Київ, вул. Вишгородська, 19. Наявність на території НЕНЦ спального корпусу та їдальні дозволяє взяти участь у школі учням з усіх регіонів України та забезпечити їх комфортними умовами проживання і харчування.
Заїзд відбуватиметься 10 липня, початок занять 10 липня о 12.00. 19 липня планується проведення олімпіади з програмування за результатами літньої школи. 20 липня підведення підсумків проведення школи, закриття школи та роз’їзд учасників.
Заняття в школі проводитимуться незалежно від класу навчання учнів по лігах:
- Юніорська ліга – учні, які взагалі не знайомі з програмуванням або їх знання на початковому рівні.
- Середня ліга – учні, що мають базовий рівень програмування, переможці ІІ етапу та учасники ІІІ етапу Всеукраїнських олімпіад з програмування.
- Вища ліга – учні з високим рівнем програмування, переможці ІІІ та IV етапів Всеукраїнських олімпіад з програмування.
До проведення занять у літній школі будуть запрошуватися провідні фахівці по підготовці учнів до олімпіад з програмування різних рівнів та студенти Київського національного університету імені Тараса Шевченка, які в шкільні роки приймали участь у Всеукраїнських олімпіадах з інформатики. Зокрема свою згоду на проведення занять у літній школі надали:
- Скляр Ірина Вільївна — Заслужений вчитель України, вчитель інформатики Київського природничо-наукового ліцею №145, підготувала багатьох переможців ІІІ та IV етапів Всеукраїнської учнівської олімпіади з інформатики, дев’ятьох переможців Міжнародної олімпіади з інформатики, автор посібників:
- Скляр І. В., Ставровський А. Б. Базовий курс програмування для фізико-математичних шкіл: навчальний посібник. — Київ: Україна, 2015.
- Скляр І. В. Теорія графів у школі. Задачі: посібник. — ВД «Перше вересня», 2015.
- Федорів Любомир Атанасійович — Заслужений вчитель України, вчитель інформатики Київського природничо- наукового ліцею №145, підготував багатьох переможців ІІІ та IV етапів Всеукраїнської учнівської олімпіади з інформатики, двох переможців Міжнародної олімпіади з інформатики (Київський природничо-науковий ліцей №145);
- Жуковський Сергій Станіславович — доцент кафедри прикладної математики та інформатики Житомирського університету імені Івана Франка, вчитель інформатики ліцею № 25 імені Н.А. Щорса; адміністратор інтернет-ресурсу для підготовки до олімпіад з програмування різного рівня e-olymp, має понад 100 переможців ІІІ етапу та близько 12 переможців IV етапу Всеукраїнської олімпіади з інформатики, є членом журі ІІІ та IV етапів Всеукраїнських олімпіад з інформатики.
- Порубльов Ілля Миколайович — старший викладач кафедри програмного забезпечення АС Черкаського національного університету імені Богдана Хмельницького, вчитель інформатики Черкаського фізико-математичного ліцею, вже багато років є одним з авторів задач Всеукраїнської інтернет олімпіади з інформатики та Всеукраїнської комплексної олімпіади з математики, фізики та інформатики «Турнір чемпіонів».
Формат літньої школи дозволяє краще засвоїти достатньо складний матеріал завдяки вільній, невимушеній, особливій атмосфері між учнями та викладачами під час навчального процесу, а також завдяки поєднанню навчальних занять з відпочинком на природі.
Необхідні умови для участі
Для участі у школі необхідно зареєструватися за посиланням. Реєстрація відкрита до 20 червня 2016 року.
Участь у Літній школі не є безкоштовною. Орієнтовна вартість участі в літній школі:
- для учнів, що потребують проживання та харчування на базі НЕНЦ - 2850 грн,
- для київських учнів – 1450 грн.
Загальна кількість учасників літньої школи обмежена. Організатори школи залишають за собою право самостійно обрати учасників школи з числа зареєстрованих учнів у випадку, коли кількість зареєстрованих буде занадто великою.
Обов’язковою умовою участі у літні школі є наявність власного ноутбука.
На ноутбуці повинні бути встановлені середовища програмування для мов С++ та Pascal.
Інструкції зі встановлення програмного забезпечення
Компілятор Free Pascal можна завантажити з сайту FreePascal.ru. При встановленні можна залишати установки за промовчанням.
Для встановлення компілятора С++ необхідно:
- Завантажити інсталятор середовища з офіційного сайту:
- Windows: завантажити
- Інші ОС: вибрати відповідно для своєї ОС
- Запустити інсталятор і встановити середовище (погоджуючись з параметрами за замовчуванням)
- Після того, натискаємо «Finish».
- Обираєм GNU GCC Compiler і тиснемо на «Ок». У випадку, якщо опція «GNU GCC Compiler» відсутня, слід особисто підключити компілятор як показано за посиланням: завантажити
Контакти
По всіх питаннях проведення «Літньої школи з програмування та математики 2016» звертатися до вчителя інформатики Скляр Ірини Вільївни за тел. 0953465850, 0638544852 або електронною поштою: irinasklyar@gmail.com.
неділю, 11 грудня 2016 р.
Вінницька олімпіада з інформатики 11.12.2016 року
Завдання для учнів 8-9 класів (юніори)
Задача Eclipse.
Юний астроном Петрик сфотографував сонячне затемнення і хоче визначити, яке
було затемнення – повне, часткове чи відсутнє взагалі. Він роздрукував знімок,
провів координатну пряму через центри Сонця і Місяця, визначив координати
центрів зображень небесних тіл та радіуси цих зображень. Допоможіть
Петрику. Сонце і Місяць на світлині Петрика мають форму круга.
Технічні умови.
Програма Eclipse читає з пристрою стандартного введення через
пропуск 4 числа – координату центра та радіус Сонця, потім координату
центра та радіус Місяця (всі числа натуральні, не більші 1000). Програма
виводить на пристрій стандартного виведення єдине число: 0, якщо затемнення не
було, 1, якщо затемнення часткове, 2,якщо повне.
Приклади Введення
3 5 3 5 Виведення 2
Введення 3 8 3 5
Виведення 1
Коментар: Повне
затемнення – це коли зображення диска Сонця повністю перекрите зображенням
диска Місяця, часткове – це коли зображення мають більше однієї спільної точки,
але перекриваються не повністю, затемнення немає, коли зображення не
перекриваються зовсім, але, можливо, мають одну спільну точку.
Приклад кодування на Паскалі
var x1,x2,r1,r2:int64;
begin
read(x1,r1,x2,r2);
if (((r2-r1)>=abs(x2-x1)) and (r2>=r1))
then write(2)
else if (((x1<x2) and ( x2-x1>=r1+r2)) or (( x1>x2) and (x1-x2>=r1+r2)))
then write(0)
else write(1);
end.
Приклад кодування на Паскалі
var x1,x2,r1,r2:int64;
begin
read(x1,r1,x2,r2);
if (((r2-r1)>=abs(x2-x1)) and (r2>=r1))
then write(2)
else if (((x1<x2) and ( x2-x1>=r1+r2)) or (( x1>x2) and (x1-x2>=r1+r2)))
then write(0)
else write(1);
end.
Задача laying.
Бізнесмен Петро Петрович збирає речі у відпустку. З собою в літак він може
взяти ручну поклажу і багаж. Для ручної поклажі у нього є рюкзак, а для багажу
– здоровенна валіза. За правилами перевезення маса ручної поклажі не
повинна перевищувати S кг, а багаж може бути будь-якої маси (за
наднормативний багаж Петро Петрович готовий доплатити). Зрозуміло,
найбільш цінні речі - ноутбук, фотоапарат, документи і т. д. – Петро Петрович
хоче покласти в ручну поклажу. Петро Петрович розклав усі свої речі
в порядку зменшення їх цінності і починає складати найбільш цінні речі в
рюкзак. Він діє в такий спосіб - бере найцінніший предмет, і якщо його маса не
перевищує S, то кладе його в рюкзак, інакше кладе його до валізи. Потім
він бере наступний за цінністю предмет, якщо його можна покласти в рюкзак,
тобто якщо його маса разом з масою вже покладених в рюкзак речей не
перевищує S, то кладе його в рюкзак, інакше до валізи, і таким же чином
процес триває для всіх предметів в порядку спадання їх цінності. Визначте вагу
рюкзака і валізи після того, як Петро Петрович складе всі речі.
Технічні умови.
Програма laying читає з пристрою стандартного введення число S
(1 ≤ S ≤ 2 × 109) – максимально дозволенa вага рюкзака та число N (1
≤ N ≤ 105) - кількість предметів. У наступному рядку дано N чисел
через пропуски - маси предметів, самі предмети перераховані в порядку
спадання цінності (спочатку вказана маса найціннішого предмета, потім маса
другого по цінності предмета і т. д.). Всі числа натуральні, сума ваг всіх
предметів не перевищує 2 × 109. Програма виводить на пристрій стандартного
виведення два числа - вагу рюкзака і вагу валізи (вага порожнього рюкзака і
валізи не враховується).
Приклад
Введення
Виведення
10 4
6 3 2 1
10 2
Приклад кодування на Паскалі
var s,sr,sv,n,i,r:int64;
begin
sr:=0; sv:=0;
readln(s,n);
for i:=1 to n do
begin
read(r);
if sr+r<=s then sr:=sr+r else sv:=sv+r;
end;
write(sr,' ',sv);
end.
Приклад кодування на Паскалі
var s,sr,sv,n,i,r:int64;
begin
sr:=0; sv:=0;
readln(s,n);
for i:=1 to n do
begin
read(r);
if sr+r<=s then sr:=sr+r else sv:=sv+r;
end;
write(sr,' ',sv);
end.
Задача Bear. Маленьке
ведмежа йде по дорозi, вздовж якої на вiдстанi М одне вiд одного ростуть
дерева. Зупиняючись пiд кожним деревом, ведмежа забуває, звiдки прийшло, i,
рушаючи через деякий час в подальші мандри, випадково вибирає той чи iнший
напрямок руху. На якiй вiдстанi вiд "стартового" дерева може бути
ведмежа пiсля К етапiв?
Технічні умови. Програма Bear зчитує з клавiатури
числа M та К через пропуск (1<=М,К<=10000). Програма
виводить на екран в один рядок через пропуски вiдстанi, на яких може
знаходитись ведмедик (вiд меншої до бiльшої).
Приклад
Введення 2 6 Виведення 0 4 8 12
Приклад кодування на мові Паскаль Задача Bear.
var i,m,k:int64;
begin
read(m,k);
if (k mod 2)=0 then begin
i:=-2;
repeat
i:=i+2;
write(i*m,' ');
until i>=k;
end
else begin
i:=-1;
repeat
i:=i+2;
write(i*m,' ');
until i>=k;
end;
end.
Приклад кодування на мові Паскаль Задача Bear.
var i,m,k:int64;
begin
read(m,k);
if (k mod 2)=0 then begin
i:=-2;
repeat
i:=i+2;
write(i*m,' ');
until i>=k;
end
else begin
i:=-1;
repeat
i:=i+2;
write(i*m,' ');
until i>=k;
end;
end.
Задача Chocolates.
Петрик святкував день народження 3 листопада і вирішив пригостити
однокласників шоколадками. Шоколадка коштувала N грн. З першого
листопада вартість шоколадки збільшилась рівно на Р відсотків.
Визначте скільки шоколадок зможе купити Петрик на S грн після
подорожчання.
Технічні умови.
Програма Chocolates читає з пристрою стандартного введення
(клавіатури) 3 цілих числа: N (1 ≤ N ≤ 107) - вартість шоколадки до
подорожчання, Р (0 ≤ Р ≤ 100) - величина подорожчання шоколадки у
відсотках, S (1 ≤ S ≤ 107) - сума грошей, яка є у
Петрика. Програма виводить одне число - кількість шоколадок, які може
купити Петрик.
Приклад
Введення
Виведення
25 5 100
3
Приклад кодування на мові Паскаль Задача Chocolates
var n,p,s,k:longint;
begin
read(n,p,s);
n:=n*100+n*p;
k:=((s*100) div n);
write(k);
end.
var n,p,s,k:longint;
begin
read(n,p,s);
n:=n*100+n*p;
k:=((s*100) div n);
write(k);
end.
Завдання для учнів 10-11 класів
Задача Mountain. Для
поповнення бюджету країни, що відома своїми гірськими
маршрутами, ввели новий податок для альпіністів. Величина податку
пропорційна довжині маршруту, але, оскільки маршрут проходить по горах і
пройдену відстань, яка залежить від висоти спуску і підйому, підрахувати
складно, податок утримується без урахування висоти, тобто величина податку
пропорційна горизонтальному переміщенню туристичної групи. Крім того, в силу
старовинного звичаю усі туристичні групи повинні переміщатися по горах
строго із заходу на схід. Експедиція хоче заощадити на податку, тому вона
розробляє гірський маршрут з мінімальною величиною податку. При цьому, оскільки
маршрут є гірським, він повинен містити підйом в гору і спуск з гори, тобто на
маршруті має бути точка, яка знаходиться строго вище початку і кінця маршруту.
Альпіністи склали карту, що містить
інформацію про висоту гір при пересуванні із заходу на схід. Висоти гір
виміряні в точках через рівні відстані. Знайдіть на цій карті туристичний
маршрут, за який податок буде мінімальний, а підйом та спуск, як і личить
альпіністам, буде на маршруті.
Технічні умови. Програма Mountain читає
з пристрою стандартного введення число N - кількість точок на
карті гір. У наступному рядку N чисел через пропуск містять
інформацію про висоту гір в даних N точках при русі із заходу на
схід. Всі числа натуральні, не перевищують 105. Програма виводить два
числа - номер точки початку маршруту і номер точки закінчення маршруту. Точки
нумеруються від 1 до N. Якщо маршруту, що задовольняє умовам, не
існує, програма повинна вивести одне число 0. Якщо знайдеться декілька
маршрутів, то вивести той що починається ближче до точки старту експедиції.
Приклади
Введення Виведення
7
18 10 15 20 20 10 3 3 6
3
9 8 5 0
Приклад кодування на С++ задачі Mountain.
#include<iostream>
#include<stdio.h>
using namespace std;
const int inf = 1000000000;
int n, h1, h2, st ,f , ansst, ansf, minn=inf;
int main()
{
scanf("%d",&n);
if (n<3)
{
int tmp;
for (int i=0;i<n;i++)
{
cin >> tmp;
}
cout << "0";
return 0;
}
scanf("%d%d",&h1,&h2);
int i=1;
while (i<=n)
{
int e=0;
while (i<n && h2>=h1)
{
if (h2>h1)
{
st=i;
e=1;
}
if (i+1<n)
{
h1=h2;
scanf("%d",&h2);
}
i++;
}
if (e==0)
{
if (i+1<n)
{
h1=h2;
scanf("%d",&h2);
}
i++;
continue;
}
if (i==n)
{
break;
}
if (h2<h1)
{
f=i+1;
if ((f-st)<minn)
{
minn=f-st;
ansst=st;
ansf=f;
}
}
f=0;
st=0;
}
if (minn==inf)
{
cout << "0";
return 0;
}
cout << ansst << " " << ansf;
return 0;
}
Задача Lattice. Є
прямокутник розміром M*N, що складається з клітинок 1*1. Знайдіть кількість
квадратів, всі вершини яких є вершинами клітинок. Сторони квадратів НЕ
обов’язково паралельні до сторін прямокутника.
Технічні умови. Програма Lattice читає
з пристрою стандартного введення два цілих числа - розміри прямокутника M та N(1≤M,N≤10000) і
виводить на пристрій стандартного виведення шукану кількість квадратів.
Приклад
Введення 2 3
Виведення 10
Приклад кодування на С++
#include<iostream>
#include<stdio.h>
using namespace std;
long long n,m,sum=0;
int main()
{
cin >> n >> m;
if (m>n) swap(m,n);
for (int i=0;i<m;i++)
{
sum+=(i+1)*(m-i)*(n-i);
}
cout << sum;
return 0;
}
Приклад кодування на С++
#include<iostream>
#include<stdio.h>
using namespace std;
long long n,m,sum=0;
int main()
{
cin >> n >> m;
if (m>n) swap(m,n);
for (int i=0;i<m;i++)
{
sum+=(i+1)*(m-i)*(n-i);
}
cout << sum;
return 0;
}
Задача Raft. Петрик
влітку відпочиває у бабусі в селі. Особливо йому подобається купатись на
сільському озері. Посередині озера плаває пліт, який має форму прямокутника.
Сторони плота спрямовані уздовж паралелей і меридіанів. Введемо систему
координат, в якій вісь ОХ направлена на схід, а вісь ОY - на північ. Нехай
південно-західний кут плоту має координати (x1, y1), північно-східний кут
- координати (x2, y2). Петрик знаходиться в точці з координатами (x,
y). Визначте, до якої сторони плоту (північної, південної, західної чи східної)
або до будь-якого кута плоту (північно-західному, північно-східному,
південно-західному, південно-східному) Петрику потрібно плисти, щоб якомога
швидше дістатися до плоту.
Технічні умови.
Програма Raft читає з пристрою стандартного введення шість чисел в
наступному порядку: x1, y1 (координати південно-західного кута
плоту), x2, y2 (координати північно-східного кута плоту), x, y (координати
Петрика). Всі числа цілі і по модулю не перевершують 100. Гарантується,
що x1 < x2, y1 < y2, x ≠ x1, x ≠ x2, y ≠ y1, y ≠ y2,
координати Петрика знаходяться поза плотом. Якщо Петрику слід пливти до
північної сторони плоту, програма повинна вивести на пристрій стандартного
виведення символ «N», до південної - символ «S», до західної - символ «W», до
східної - символ «E». Якщо Петрику слід пливти до кута плоту, потрібно вивести
один з наступних рядків: «NW», «NE», «SW», «SE».
Приклад
Введення Виведення
-1 -2 5 3 -4 6 NW
Приклад кодування на Паскалі
var x1,x2,x,y1,y2,y:integer;
begin
read(x1,y1,x2,y2,x,y);
if ( (y>y2) and (x>x1) and (x<x2)) then write('N')
else if ( (y<y1) and (x>x1) and (x<x2)) then write('S')
else if ((x<x1) and (y>y1) and (y<y2)) then write('W')
else if ((x>x2) and (y>y1) and (y<y2)) then write('E')
else if ((x<x1) and (y>y2)) then write('NW')
else if ((x<x1) and (y<y1)) then write('SW')
else if ((x>x2) and (y>y2)) then write('NE')
else write('SE');
end.
Приклад Raft
кодування на С++
Приклад кодування на Паскалі
var x1,x2,x,y1,y2,y:integer;
begin
read(x1,y1,x2,y2,x,y);
if ( (y>y2) and (x>x1) and (x<x2)) then write('N')
else if ( (y<y1) and (x>x1) and (x<x2)) then write('S')
else if ((x<x1) and (y>y1) and (y<y2)) then write('W')
else if ((x>x2) and (y>y1) and (y<y2)) then write('E')
else if ((x<x1) and (y>y2)) then write('NW')
else if ((x<x1) and (y<y1)) then write('SW')
else if ((x>x2) and (y>y2)) then write('NE')
else write('SE');
end.
Приклад Raft
кодування на С++
#include<iostream>
#include<stdio.h>
using namespace std;
int x,y,x1,x2,y1,y2;
int main()
{
cin
>> x1 >> y1 >> x2 >> y2 >> x >> y;
if (x>=x1 && x<=x2)
{
if (y>=y2)
{
cout << "N";
}
else{
cout << "S";
}
return 0;
}
if (y>=y1 && y<=y2)
{
if(x<=x1)
{
cout << "W";
}
else
{
cout << "E";
}
return 0;
}
if (x<=x1)
{
if(y<=y1)
{
cout << "SW";
}
else{
cout << "NW";
}
return 0;
}
if (y<=y1)
{
cout
<< "SE";
}
else
{
cout
<< "NE";
}
return 0;
}
Задача Balloon.
Герої Жюля Верна мандрували на повітряній кулі. У них був таймер та висотомір.
Таймер відміряв час з моменту старту в годинах, а висотомір – висоту, на якій у
цю мить знаходиться куля. Результати вимірів вони записували,
інколи – не щогодини, але якщо в час T1 висота складала Y1,
а в час T2 висота складала Y2, то між годинами T1 та T2 висота
рівномірно змінювалася від Y1 до Y2. Мандрівники вирішили
дізнатися, скільки часу тривав самий затяжний підйом (тобто максимальний
проміжок часу, на якому висота зростала).
Технічні умови.
Програма Balloon читає з пристрою стандартного введення (клавіатури)
число N (1 ≤ N ≤105) – кількість найдених записів. В наступних N стрічках
по 2 цілих числа А та В, де А – номер години польоту,
а В – висота в цей момент часу. (1 ≤ А, В ≤ 109). Гарантується,
що всі А різні. Програма виводить на пристрій стандартного введення
(екран) єдине число – тривалість самого затяжного підйому у годинах.
Приклад
Введення Виведення
10
3
1 6
2 20
3 15
4 10
6 13
7 20
8 20
9 20
10 20
11 21
Приклад кодування на С++
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<pair<int,int> > c;
int n,currh=0,maxx=0,curr=0,currtime=0,t[100500],h[100500];
int main()
{
int e=0;
scanf("%d",&n);
scanf("%d%d",&t[0],&h[0]);
for (int i=1;i<n;i++)
{
scanf("%d%d",&t[i],&h[i]);
if (t[i]<t[i-1]) e=1;
}
if (e==1)
{
c.resize(n);
for (int i=1;i<n;i++)
{
c[i]=make_pair(t[i],h[i]);
}
sort(c.begin(),c.end());
for (int i=0;i<n;i++)
{
t[i]=c[i].first;
h[i]=c[i].second;
}
}
for (int i=0;i<n;i++)
{
if (h[i]>currh)
{
currh=h[i];
curr=curr+t[i]-currtime;
currtime=t[i];
}
else
{
if (curr>maxx)
{
maxx=curr;
}
curr=0;
currh=h[i];
currtime=t[i];
}
}
if (curr>maxx)
{
maxx=curr;
}
cout << maxx;
return 0;
}
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<pair<int,int> > c;
int n,currh=0,maxx=0,curr=0,currtime=0,t[100500],h[100500];
int main()
{
int e=0;
scanf("%d",&n);
scanf("%d%d",&t[0],&h[0]);
for (int i=1;i<n;i++)
{
scanf("%d%d",&t[i],&h[i]);
if (t[i]<t[i-1]) e=1;
}
if (e==1)
{
c.resize(n);
for (int i=1;i<n;i++)
{
c[i]=make_pair(t[i],h[i]);
}
sort(c.begin(),c.end());
for (int i=0;i<n;i++)
{
t[i]=c[i].first;
h[i]=c[i].second;
}
}
for (int i=0;i<n;i++)
{
if (h[i]>currh)
{
currh=h[i];
curr=curr+t[i]-currtime;
currtime=t[i];
}
else
{
if (curr>maxx)
{
maxx=curr;
}
curr=0;
currh=h[i];
currtime=t[i];
}
}
if (curr>maxx)
{
maxx=curr;
}
cout << maxx;
return 0;
}
четвер, 1 грудня 2016 р.
Генератор простих чисел за решетом Ератосфена На мові Pascal
Генератор простих чисел за решетом Ератосфена
На мові Pascal
var
a : array [1..5000] of boolean;
n,x,y : integer;
begin
write('n=');readln(n);
a[1] := false;
for x:=2 to N do a[x] := true;
for x:= 2 to N div 2{round(sqrt(N))} do
for y:= 2 to N div x do
a[x*y] := false;
for x:=1 to N do
if a[x] then write(x,' ');
readln;
end.
Для оптимізації решета Ератосфена можна перебирати тільки
непарні числа
Алгоритм записаний на псевдокоді
для i := 2, 3, 4, ..., пока i2 ≤ n:
если A[i]
= true:
для j
:= i2, i2 + i, i2 + 2i, ..., пока j ≤ n:
A[j]
:= false
Выход: числа i, для которых A[i] = true.
Генератор простих чисел за решетом Аткіна
program atkin;
var is_prime:array[1..10001] of boolean; jj:int64;
procedure dosieve(limit:int64);
var i,k,x,y:int64; n:int64;
begin
for i:=5 to limit do
is_prime[i]:=false;
for x:=1 to trunc(sqrt(limit)) do
for y:=1 to trunc(sqrt(limit)) do
begin
n:=4*sqr(x)+sqr(y);
if (n<=limit) and ((n mod 12 = 1) or (n mod 12 = 5)) then
is_prime[n]:=not is_prime[n];
n:=n-sqr(x);
if (n<=limit) and (n mod 12 = 7) then
is_prime[n]:=not is_prime[n];
n:=n-2*sqr(y);
if (x>y) and (n<=limit) and (n mod 12 = 11) then
is_prime[n]:=not is_prime[n];
end;
for i:=5 to trunc(sqrt(limit)) do
begin
if is_prime[i] then
begin
k:=sqr(i);
n:=k;
while n<=limit do
begin
is_prime[n]:=false;
n:=n+k;
end;
end;
end;
is_prime[2]:=true;
is_prime[3]:=true;
end;
begin
dosieve(10000);
for jj:=1 to 10000 do
if is_prime[jj] then
writeln(jj);
end.
Підписатися на:
Дописи (Atom)