Медали для всех, даром, и пусть никто не уйдет обыгранным!

Медали для всех, даром, и пусть никто не уйдет обыгранным!

Добрый день, уважаемые друзья! Глядя на нижеследующие ссылки (2011, 2012, 2013, 2014 — следует нажать ссылочку Standings), многие современники не спрашивают у меня, как прийти к подобным результатам. А зря. К сожалению, сам по себе ритуал еженедельного посещения кружка умелых информационных ручек с опцией прорешивания особо приглянувшихся задач способен перевести Вас лет за 5 из … Continue reading

С чего начать?

С чего начать?

Будем предполагать, что Ваша цель не просто изучить программирование, но и научиться решать задачи. Это означает, что Вы вероятно хотите получить в дальнейшем какую-то пользу от своих новых знаний и навыков, а не просто убиваете время. Сразу должен предупредить, что это потребует во много раз больше усилий, чем простое изучение синтаксиса и лексики С++, урду … Continue reading

Как не нужно решать задачи

Как не нужно решать задачи

Есть довольно подробные рекомендации, как нужно решать задачи по программированию (в т.ч. для студентов). В конце заметки я дам ссылки на одну из таких статей. Но я хотел бы сейчас привести наглядный пример того, как не надо решать задачи. Вот довольно простая задача про разрезание брусочка сыра (точнее прямоугольного параллелепипеда) на кубики со стороной 1. … Continue reading

Дистанционные учебные курсы

Дистанционные учебные курсы

Хочу порекомендовать пройти некоторые дистанционные учебные курсы на сайте Coursera. Чтобы не актуализировать постоянно ссылки и даты буду просто вставлять в начало ссылки. Надеюсь разберетесь на месте. Основы разработки на C++ №1 на русском Основы разработки на C++ №2 на русском Algorithms #1 на английском. Очень хороший и сложный курс. Algorithms #2 на английском. Такой … Continue reading

Образец: Принадлежит ли точка треугольнику?

Образец: Принадлежит ли точка треугольнику?

Задача. Даны три попарно не совпадающие и не лежащие на одной прямой точки [latex]A, B[/latex] и [latex]C[/latex], заданные своими координатами. Определить принадлежит ли точка [latex]D(x_d,y_d)[/latex] треугольнику [latex]ABC[/latex]. Сразу заметим, что задача легко обобщается для любого выпуклого многоугольника. Тесты В тестах нужно обязательно отразить следующие случаи: Точка строго вне треугольника Точка строго внутри треугольника Точка совпадает … Continue reading

e-olymp 8651. Браслети (Bangles)

e-olymp 8651. Браслети (Bangles)

Задача взята з сайту e-olymp Шпигунам-конкурентам вдалося потрапити на склад запасних частин фірми «Magic & Stupidity», яка виготовляла магічні браслети. Стало зрозуміло, що всі браслети складалися з чотирьох різних деталей, кожна з яких мала на кінцях замки різних типів (розрізнялися за номерами). Вони з’єднувалися по колу, причому у сусідніх частин замки повинні мати однаковий номер. … Continue reading

e-olymp 8655. Простая сумма

Даны три целых числа x, m и n. Вычислите $(1 + x + x^2 + \ldots + x^m) (mod\quad n)$. Задача взята с сайта e-olymp Входные данные Первая строка содержит количество тестов. Каждая следующая строка содержит три целых числа $x, m$ и $n (1 \le x, m, n \le 10^{16})$. Выходные данные Для каждого теста … Continue reading

e-olymp 685. Сумма на параллелепипеде

Задача Задана трехмерная таблица чисел [latex]a_{ijt}[/latex], где [latex]1\leq i\leq n[/latex], [latex]1\leq j\leq m[/latex], [latex]1\leq t\leq k[/latex]. Для заданных [latex]l_{x}, l_{y}, l_{z},r_{x}, r_{y}, r_{z}[/latex] найдите [latex]S_{l_{x}, l_{y}, l_{z},r_{x}, r_{y}, r_{z}}=\sum_{i=lx,j=ly,t=lz}^{i\leq rx,j\leq ry,t\leq rz}a_{ijt}[/latex] Входные данные В первой строке записаны размеры таблицы — [latex]n, m, k \left ( 1\leq n, m, k\leq 100 \right )[/latex]. Далее записано … Continue reading

e-olymp-751. Клад

Условие Найти закопанный пиратами клад просто: всё, что для этого нужно – это карта. Как известно, пираты обычно рисуют карты от руки и описывают алгоритм нахождения клада так: «Встаньте около одинокой пальмы. Пройдите тридцать шагов в сторону леса, потом семнадцать шагов в сторону озера, …, наконец десять шагов в сторону большого булыжника. Клад находится под … Continue reading

Минимальная реализация алгоритма RSA на C++

Минимальная реализация алгоритма RSA на C++

Описание программы Алгоритм асимметричного шифрования RSA основан на практической сложности факторизации больших чисел, что делает его на сегодняшний день одним из самых популярных криптографических алгоритмов. Однако он имеет свои отрицательные стороны, например среди них достаточно низкая скорость шифрования, поэтому зачастую используют смешанную криптосистему, в которой сначала две стороны передают симметричный ключ с помощью RSA, а … Continue reading

e-olymp 8688. Количество чисел без 8

Задача Напишите программу, которая определяет количество чисел от $1$ до $n$, в записи которых нет цифры $8$. Входные данные: В первой строке задано число $n$ $(1 \le n \le 10^{18})$. Выходные данные: Выведите одно число — количество чисел от $1$ до $n$, в записи которых нет цифры $8$. Тесты Входные данные Вывод программы 10 9 … Continue reading

e-olymp 209. Защита от копирования

e-olymp 209. Защита от копирования

Задача Давным-давно, в далекой-далекой галактике, когда еще не вышел мультфильм про смешариков, никто не знал про Гарри Поттера и про Властелина Колец, на далекой-далекой планете жили-были полчища смешариков. Их технологии были настолько совершенны, что они создали машину времени и перенеслись на ней в будущее, на планету «Земля», где одному из них совершенно случайно попалась первая … Continue reading

e-olymp 682. Сумма на отрезке

e-olymp 682. Сумма на отрезке

Задача Задан набор чисел $a_{1}, …, a_{n}$. Для заданных индексов $l$ и $r$ найдите $$S_{l,r}=a_{l}+a_{l+1}+..+a_{r}$$ Входные данные В первой строке записано количество чисел $n$ $\left(1 \leq n \leq 10^{6}\right)$. Во второй строке записаны числа $a_{i}$ $\left(1 \leq a_{i} \leq 1000\right)$, разделенные пробелом. На третьей строке записано число $m$ $\left(1 \leq m \leq 10^{6}\right)$ — количество … Continue reading

e-olymp 4749. Выручка театра

e-olymp 4749. Выручка театра

Задача В театре [latex]n[/latex] рядов по [latex]m[/latex] мест в каждом. Даны две матрицы — в первой записаны стоимости билетов. Вторая сообщает, какие билеты проданы, а какие — нет ([latex]1[/latex] — соответствующий билет продан, [latex]0[/latex] — не продан). Определите общую выручку от спектакля. Входные данные Сначала записано число [latex]n[/latex], затем число [latex]m[/latex] ([latex]n[/latex], [latex]m \leqslant 500[/latex]). … Continue reading

e-olymp 8358. Среднее значение — 1

e-olymp 8358. Среднее значение — 1

Задача. Среднее значение — 1 Проект «Средний вес школьника школы» решили выполнить Мамед с Самедом. Что они будут делать с этим числом, они не раскрывают. Они попросили взвеситься всех учеников школы и занесли результаты в таблицу. Помогите им подсчитать средний вес учеников. Но они просят, чтобы учеников с самым большим и с самым маленьким весом … Continue reading

e-olymp 8382. Пароль

e-olymp 8382. Пароль

Задача Назовем пароль криптостойким*, если выполнены $5$ критериев Пароль содержит строчные латинские буквы Пароль содержит заглавные латинские буквы Пароль содержит цифры Символы: ! » # $ % & ‘ ( ) * + Длина пароля не менее $8$ символов Требуется по данному паролю определить, сколько критериев криптостойкости выполнено. Входные данные Вводится одна строка, состоящая только из … Continue reading

e-olymp 2524. Строки Фибоначчи

e-olymp 2524. Строки Фибоначчи

Задача В математике достаточно часто применяются так называемые рекуррентные соотношения. Обычно они применяются для задания числовых последовательностей, но могут применяться и для задания последовательностей строк. Одним из примеров строк, задаваемых рекуррентным соотношением являются строки Фибоначчи $F_{0} = a$, $F_{1} = b$, … . Они задаются следующим образом: $F_{0} = a$, $F_{1} = b$, $F_{i} = F_{i-2}F_{i-1}$, $i >1$. Первые семь строк Фибоначчи выглядят следующим образом: $a$, $b$, $ab$, $bab$, $abbab$, $bababbab$, $abbabbababbab$. Дима занимается в кружке олимпиадного программирования и … Continue reading

e-olymp 2099. Два массива

Задача Даны два массива чисел. Требуется вывести те элементы первого массива (в том порядке, в каком они идут в первом массиве), которых нет во втором массиве. Входные данные Сначала подаётся количество [latex]n[/latex] элементов в первом массиве, затем [latex]n[/latex] чисел — элементы массива. Затем записано количество [latex]m[/latex] элементов во втором массиве. Далее заданы элементы второго массива. … Continue reading

e-olymp 8701. Кузнечик-попрыгунчик

e-olymp 8701. Кузнечик-попрыгунчик

Задача Кузнечик-попрыгунчик долго сидел на отметке [latex]0[/latex] числовой прямой, так долго, что придумал инновационную методологию своего перемещения. Такую, что за каждую итерацию движения он выполняет ровно два прыжка, перемещаясь сначала на [latex]a[/latex], а затем на [latex]b[/latex] единичных отрезков по числовой прямой, причем, если число положительное, то он движется вправо, а если отрицательное, то влево. Продолжительность … Continue reading

e-olymp 4852. Кратчайшее расстояние

e-olymp 4852. Кратчайшее расстояние

Задача взята с сайта e-olymp. Задача Дан ориентированный граф. Найдите кратчайшее расстояние от вершины $x$ до всех остальных вершин графа. Входные данные В первой строке содержатся два натуральных числа $n$ и $x$ $(1 \leqslant n \leqslant 1000, 1 \leqslant x \leqslant n)$ — количество вершин в графе и стартовая вершина соответственно. Далее в $n$ строках по $n$ чисел — матрица … Continue reading

e-olymp 2496. Конкатенация строк

Задача Во многих прикладных задачах необходимо осуществлять различные операции со строками. Две достаточно часто встречающиеся операции — это разворот строки и конкатенация двух или нескольких строк. В результате разворота строки $s$ получается строка $sR$, которая состоит из тех же символов, что и $s$, но идущих в обратном порядке. Например, в результате разворота строки «$abcde$» получается … Continue reading

e-olymp 5338. Полный граф — 2

e-olymp 5338. Полный граф — 2

Задача Обсуждая личную жизнь всевозможных злодеев, мы обделили своим вниманием графа Дуку. Так вот, граф Дуку на досуге любит складывать оригами. Он давно систематизировал свои познания в этой области следующим образом: всего граф знает n фигурок, причем для некоторых из них он знает, как получать из одной другую. Для обучения начинающих ситхов Дуку разработал специальную … Continue reading

e-olymp 4752.  Кинотеатр

e-olymp 4752.  Кинотеатр

Задача Однажды, ученики B-й школы города G решили съездить в кино. Администрация кинотеатра расположила их в зале размера $n × m$, который специально был подобран так, чтобы все места были заняты школьниками. Каждому посетителю кинотеатра был выдан свой номер. Школьники заняли свои места следующим образом: они входили в зал в порядке, в котором шли их … Continue reading

e-olymp 497. Лентяй

Задача Студент Валера являет собой классический пример лентяя. На занятия он практически не ходит, и только в конце семестра появляется в университете и сдает ”хвосты”. Его заветная мечта: найти такой день, когда можно будет сдать сразу все долги. У него есть расписание работы преподавателей, из которого точно известно, с какого и по какой день месяца … Continue reading