Все, что бы мы ни делали, имеет какую-то цель. Не всегда ее удается достигнуть, но для того чтобы это было возможно необходимо как следует сформулировать желаемый для себя результат, а потом продумать четкий план его достижения. Часто план сформулирован в виде предписаний или инструкций.

 Исполнитель – тот объект или субъект, для управления которым составлен алгоритм.
Характеристики исполнителя:

·         СКИ — система команд исполнителя – вся совокупность команд, которые исполнитель умеет выполнять.

·         среда – обстановка, в которой функционирует исполнитель.

Свойства алгоритма:

·         Понятность – алгоритм должен быть составлен только из команд, входящих в СКИ.

·         ​ Дискретность (детализация) – алгоритм разбивается на отдельные элементарные шаги, которые могут быть исполнены при помощи СКИ.

·         Однозначность (определенность или детерминированность) – каждый шаг алгоритма имеет единственность толкования выполнения действия и порядка их выполнения.

·         ​ Результативность (конечность) – выполнение алгоритма должно приводить к результату за конечное число шагов.

·         ​ Массовость – возможность применения алгоритма к классу однотипных задач, различающихся исходными данными.

Определенная последовательность действий исполнителя всегда применяется к некоторым исходным данным. Например: для приготовления пирога нужны соответствующие продукты, для решения математической задачи - решение квадратного уравнения – нужны числовые данные (значения его коэффициентов). Необходимый и достаточный набор данных для решения поставленной задачи (получения искомого результата) называется полным набором данных.

Способы записи алгоритмов.

На практике наиболее распространены следующие формы представления алгоритмов:

·         словесная (запись на естественном языке);

·         графическая (изображения из графических символов блок-схемы);

·         псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);

·         программная (тексты на языках программирования).

КуМир (Комплект Учебных МИРов) - система программирования, предназначенная для поддержки начальных курсов информатики и программирования в средней и высшей школе.

Сайт: http://www.niisi.ru/kumir/ и http://lpm.org.ru/kumir2/

В системе КуМир используется школьный алгоритмический язык с русской лексикой и встроенными исполнителями Робот и Чертёжник.

При вводе программы КуМир осуществляет постоянный полный контроль ее правильности, сообщая на полях программы об всех обнаруженных ошибках.

При выполнении программы в пошаговом режиме КуМир выводит на поля результаты операций присваивания и значения логических выражений. Это позволяет ускорить процесс освоения азов программирования.

В простейшем случае программа на КуМире выглядит так:

После «алг» (алгоритм) пишется имя алгоритма, между «нач» (начало) и «кон» (конец) пишутся команды алгоритма. При написании автоматически создаются отступы вначале строки, это делает программу более наглядной, удалять или пытаться сделать отступ самим не надо.

Приведенный алгоритм «Первый» не будет ничего делать, т. к. между «нач» и «кон» у него нет  команд.

Вот пример уже работоспособного алгоритма:

Его уже можно запустить на выполнение, он запросит у пользователя значения длины и ширины, вычислит и напечатает результат вычислений...

Эти команды используются практически во всех алгоритмах.

·         команда описания переменных

·         команда присваивания

·         команды ввода-вывода

Для запоминания информации в памяти используют величины.

Компьютер работает с информацией, хранящейся в его памяти. Отдельный информационный объект (число, символ, строка, таблица и пр.) называется величиной.

Величины в программировании, как и в математике, делятся на переменные и константы. Значение константы остается неизменной в течении всей работы программы, значение переменной величины может изменяться.

У каждой переменной есть имя, тип и текущее значение.

Придумывать имена переменным, как и самим алгоритмам, не обязательно, но желательно так, чтобы по ним было понятно назначение переменной в алгоритме. Имя – это последовательность слов, разделенных пробелами. Первое слово имени не должно начинаться с цифры. Ни одно из слов не должно быть ключевым словом (уже имеющим значение в АЯ, например: цел, кон и др.)

В именах можно использовать:

·         буквы (русские и латинские, прописные и строчные)

·         цифры

·         два специальных знака: @ _

Примеры возможных имен: m, x2, площадь, погода на завтра, Ноябрь 7, Седьмое ноября, дом_57б.

Также будьте внимательны при использовании имен, одинаково выглядящих на русском языке и записанных латинскими буквами. Переменные "x" (икс) и "x" (хэ) - это разные переменные.

Типы переменных

Существуют три основных типа величин, с которыми работает компьютер: числовой, символьный и логический.

Тип величины определяет какие значения она может принимать и какие действия с ней можно выполнять. В зависимости от типа переменной в памяти компьютера будет выделена определенная область. В КуМире числовые типы бывают двух видов: целочисленные и вещественные.

Числовые типы

·         цел - целые числа от -2147483647 до 2147483647

·         вещ - действительные числа от -1.797693 × 10³⁰⁸ до 1.797693 × 10³⁰⁸

Текстовые типы

·         сим - один любой символ

·         лит - строка символов

Для того чтобы компьютер мог работать с величиной, нужно указать тип и имя величины, например «цел n». Такое указание называется описанием величины.

Для того чтобы запомнить или изменить значение величины есть специальная команда — команда присваивания, которая записывается в виде:

Позволяет выводить на экран текстовые сообщения, значения переменных и результаты выражений.

Обратите внимание:

·         текстовые сообщения берутся в кавычки;

·         имена переменных и выражения перечисляются через запятую без кавычек;

·         нс - команда перехода на новую строку

Позволяет вводить с клавиатуры значения переменных перечисленных в этой команде

Алгоритм сложения двух чисел

Алгоритм нахождения суммы цифр двузначного числа

Задания

1.   Напишите алгоритм нахождения суммы цифр трехзначного числа

2.   Даны длины сторон прямоугольника. Найти его периметр и длину диагонали.

3.   Задачи для тренировки

4.   Задачи на целочисленное деление

Структура полного и неполного ветвления. Блок-схемы. Сложные условия (использование и, или, не)

Задачи для самостоятельного решения

Задачи на ветвление по уровням сложности

Циклическим называется алгоритм, в котором некоторая часть операций (тело цикла — последовательность команд) выполняется многократно. Однако слово «многократно» не значит «до бесконечности». Организация циклов, никогда не приводящая к остановке в выполнении алгоритма, является нарушением требования его результативности — получения результата за конечное число шагов.Если количество повторений заранее известно, то такой цикл называется арифметическим (или циклом с параметром). Если количество повторений для цикла заранее неизвестно, то такой цикл называется итерационным.

Задачи, решаемые с использованием циклических алгоритмов

·         Вычисление факториала целого положительного числа.

·         Возведение целого числа в натуральную степень.

·         Подсчет количества цифр в введенном целом произвольном числе.

·         Нахождение суммы чисел вводимых с клавиатуры.

Задачи для самостоятельной работы

1. Задачи на циклы по уровням сложности

2. Домашнее задание на циклы

Домашнее задание

Тема: Циклические алгоритмы

Задача 1. Система связи
Межпланетное общение в одной далекой-далекой галактике организовано по следующему принципу: планеты могут быть связаны либо напрямую посредством двусторонней линии космической связи, либо опосредованно, т.е. через цепочку планет между которыми установлено прямое сообщение. Подобная распределенная система хороша тем, что при выходе станции связи из строя на одной из планет остальные планеты практически всегда остаются в системе общения, т.к. от одной планеты до другой может быть несколько альтернативных маршрутов связи. Однако в этой системе могут быть критические участки – планеты (они называются ключевыми), на которых выход станций связи из строя может сделать невозможным сообщение между какими-то из оставшихся планет. Ваша задача – составить список ключевых планет, который потребуется при укреплении и модификации системы межпланетной связи.
Входной файл
В первой строке находится два числа: N (3≤N≤20) – количество планет и K (1≤K≤200) – количество прямых линий связи между планетами. Гарантируется, что любые две планеты соединены, по крайней мере, одним маршрутом связи. На каждой из следующих K строк через пробел располагается пара номеров планет, между которыми есть прямая линия связи. Планеты нумеруются последовательными натуральными числами, начиная с единицы.
Выходной файл
В выходном файле в первой строке находится количество ключевых планет, а далее по одному на строку содержатся перечисленные в порядке возрастания номера ключевых планет.
Примеры

Решение

Задача 2. Декодирование
Обновленное программное обеспечение для станций связи выполняет шифрование сигнала. Данная операция проходит в три этапа:
1. Каждый символ строки заменяется на код этого символа (см. таблицу кодов). Например, символ «M» заменяется на число 39.
2. Каждое из полученных чисел заменяется на двоичный код длины 8 (например, число 39 заменяется на комбинацию «00100111»). Полученные двоичные коды выписываются подряд без разделителей.
3. Группы из двух или более подряд идущих нулей заменяются на комбинацию, состоящую из двух чисел: количество нулей и число 0. Аналогично группы из двух или более подряд идущих единиц заменяются на комбинацию, состоящую из двух чисел: количество единиц и число 1. Между всеми числами в записи ставится пробел. Например, комбинация «00100111» будет заменена на «2 0 1 2 0 3 1».
Таблица кодов

Вы входите в команду, ответственную за декодирование поступившей информации на принимающей стороне. На вход Вам поступает уже зашифрованная строка, Ваша задача восстановить исходную строку.

Входной файл
В единственной строке входного файла содержится последовательность неотрицательных чисел, разделенных пробелом, являющаяся кодом исходной строки символов. Гарантируется, что введенный код является корректным, а исходная строка после декодирования содержит не более 20 символов.
Выходной файл
В выходной файл необходимо вывести строку символов, полученную в результате расшифровки кода. Строка может содержать символы английского алфавита в большом и малом регистре, точку и символ пробела. Длина строки ограничена 20 символами.
Примеры

Решение

Задача 3. Познакомиться с пришельцами

За круглой планетой небольших размеров находится круглый космический корабль пришельцев. Корабль наблюдателей O (корабль очень небольшой, можно считать его точкой), центр корабля пришельцев S и центр планеты P лежат на одной прямой. На какое минимальное расстояние d необходимо переместиться наблюдателям, чтобы увидеть корабль пришельцев?

Входной файл
В первой строке входного файла через пробел записаны радиусы космического корабля пришельцев и планеты. На второй строке располагается величина OP – расстояние между кораблем наблюдателей и центром планеты, а через пробел – величина OS – расстояние между кораблем наблюдателей и центром корабля пришельцев. Все величины – натуральные числа, меньшие 10000. Поверхности планеты и корабля пришельцев могут касаться друг друга.
Выходной файл
Вывести (с точностью не менее 5 знаков после запятой) значение d – минимальное расстояние, на которое необходимо сдвинуть корабль наблюдателей, чтобы увидеть корабль пришельцев.
Примеры

Решение

Обратите внимание! Требуется вывести итоговое значение с точностью не менее 5 знаков после запятой, т.е. если в ответе содержится больше знаков, необходимо вывести их все.

Задача 4. Трудности перевода
Простейшие языки существ, населяющих планеты системы Альфа Центавра состоят из двух звуков: «А» и «О». Исследователи различают несколько уровней подобных языков. В языке первого уровня нет никаких ограничений на сочетания исходных звуков. Язык второго уровня не может содержать слов, где встречалось бы два звука «О», идущих подряд. Языки третьего уровня содержат слова такие, что никакие три звука «О» не произносятся подряд. Для составления справочника языков исследователям необходимо уметь определять максимальное количество слов языка заданной длины в зависимости от уровня этого языка.
Например, максимальное количество слов длины 3 языка второго уровня равно пяти. Это слова «ААА», «ААО», «АОА», «ОАА», «ОАО». Слова же «ООА», «АОО», «ООО» не будут допустимыми.
Входной файл
В единственной строке входного файла через пробел записаны два натуральных числа: длина слов n и уровень языка m (1≤n≤20, 1≤m≤10).
Выходной файл
Содержит одно число – максимальное количество слов длины n в языке уровня m.
Примеры

Решение

Перейти к навигацииПерейти к поиску

Содержание

·         1Задача А. Выборы жрецов. 50 баллов

·         2Задача B. Призы. 100 баллов

·         3Задача С. Робот К-79. 50 баллов

·         4Задача D. Реклама. 100 баллов

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 3 с

Используемый объем памяти: 64 Мб

В стране Олимпиадии снова выборы.

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

Формат входных данных.

Во входном файле записано число N — количество графств в стране (1 <= N <= 5000), и далее для каждого графства записан номер Жреца- покровителя конфедерации, в которую оно входит (графства считаются по порядку их номеров). Затем указаны заявления от конфедераций. Сначала записано число М — количество поданных заявлений, а затем М пар чисел: первое число — номер текущего Жреца-покровителя, второе — номер желаемого Жреца-покровителя.

Все числа во входном файле разделяются пробелами и (или) символами перевода строки.

Формат выходных данных.

В выходной файл вывести для каждого графства одно число — номер его Жреца-покровителя после Великих Перевыборов. Сначала —для первого графства, затем — для второго и т.д.

Пример

Разбор задачи

Задача для начинающих

После внимательного чтения условия задачи становится понятно, что нужно считывать из входного файла (с консоли) номера жрецов-покровителей и затем заменить некоторые из них на новые.

Создаем два одинаковых массива, равных заданному числовому ряду:

1 1 5 3 1 5 1

1 1 5 3 1 5 1

Пробегаем по элементам исходного массива (первого) и при нахождении первого элемента первой пары, меняем найденный элемент на второй, но только во втором массиве. После первой замены массивы будут выглядеть так:

1 1 5 3 1 5 1

1 1 1 3 1 1 1

Аналогично, после второй замены массивы будут выглядеть так:

1 1 5 3 1 5 1

3 3 1 3 3 1 3

И выводим измененный второй массив! Вот как это можно было реализовать.

#include <iostream>

using namespace std;

int main()

{

 int n, m, a, b;

 cin >> n;

 int ms1[n], ms2[n];

 for(int i=0;i<n;i++){

   cin >>ms1[i];

   ms2[i] = ms1[i];

 }

 cin >>m;

  for(int j=0; j<m;j++){

   cin >> a >> b;

    for(int i=0;i<n;i++){

       if (ms1[i]==a) ms2[i] = b;

    }

  }

  for(int i=0;i<n;i++){

   cout << ms2[i]<< " ";

  }

   return 0;

}

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

Алиса и Боб стали победителями телевикторины, и теперь им предстоит выбрать себе призы. На выбор предлагается n призов, пронумерованных от 1 до n.

Распределение призов происходит следующим образом. Организаторы телевикторины сообщают победителям целое положительное число k (1 ≤ k ≤ n / 3). Сначала Алиса выбирает себе любые k подряд идущих номеров призов. Потом Боб выбирает себе k подряд идущих номеров призов, при этом он не может выбирать номера, которые уже выбрала Алиса. После этого победители забирают выбранные ими призы.

Алиса хорошо знает Боба, и для каждого приза выяснила его ценность для Боба, которая является целым положительным числом. Алиса обижена на Боба и хочет выбрать свои призы так, чтобы суммарная ценность призов, которые достанутся Бобу, была как можно меньше. При этом Алису не волнует, какие призы достанутся ей.

Требуется написать программу, которая по информации о ценности призов и значению k определит, для какого минимального значения x Алиса сможет добиться того, чтобы Боб не смог выбрать призы с суммарной ценностью больше x.

Формат входных данных

Первая строка входного файла содержит два целых числа: n — общее количество призов и k — количество подряд идущих номеров призов, которое должен выбрать каждый из победителей (3 ≤ n ≤ 100 000, 1 ≤ k ≤ n / 3).

Вторая строка содержит n целых положительных чисел: a₁, a₂, …, a_n. Для каждого приза указана его ценность для Боба (1 ≤ a_i ≤ 10⁹).

Формат выходных данных

Выходной файл должен содержать одно число — минимальное значение x, для которого Алиса сможет добиться того, чтобы Боб не смог выбрать призы с суммарной ценностью больше x.

Пример

Пояснение к примеру

В приведенном примере Алиса может, например, выбрать 4-й и 5-й призы. После этого для Боба оптимально выбрать 9-й и 10-й призы с суммарной ценностью 7.

Решение

Еще один пример:

Решение задачи сводится к исключению k призов и поиску наибольшей оставшейся суммы. И из всех наибольших сумм нужно найти наименьшую. Пример решения перебором (31 тест из 48 или 65 баллов из 100):

 #include <iostream>

 using namespace std;

 long long a[100001],mx,mn;

 int n,m,k,i,j;

 int main(){

 cin>>n>>k;

 a[0]=0;

  for(i=1;i<=n;i++) {

 cin>>m;

 a[i]=a[i-1]+m;

   }

  mn=0;

   for(j=1;j<=n-k+1;j++){

     mx=0;

      for(i=j+k;i<=n-k+1;i++)

         if(mx<a[i+k-1]-a[i-1])mx=a[i+k-1]-a[i-1];

      for(i=1;i<=j-k;i++)

            if(mx<a[i+k-1]-a[i-1])mx=a[i+k-1]-a[i-1];

       if(mn==0||mn>mx)mn=mx;

   }

   cout<<mn;

   return 0;

  }

Для решения этой подзадачи воспользуемся префиксными суммами и префиксными максимумами.

Сначала научимся за O(1) находить сумму значений ценности для любого отрезка номеров. Для этого вычислим значения

s[i] = a₁ + a₂ + … + a_i

для всех i от 0 до n. Это можно сделать одним линейным проходом.

Теперь сумма значений a_i на отрезке от L[eft] до R[ight] вычисляется как s[R] – s[L – 1].

Второй шаг решения: пусть Алиса выбрала отрезок номеров от A до A + k – 1. Теперь Боб может выбрать отрезок длины k с началом от 1 до A – k или с началом от A + k до n – k + 1. Для всех i от 1 до n вычислим следующую величину

pref[i] = max(s[k] – s[0], s[k+1] – s[1], …, s[i] – s[i – k])

и величину

suff[i] = max(s[i + k – 1] – s[i – 1], s[i + k] – s[i], …, s[n] – s[n – k])

Обе этих величины также можно вычислить одним линейным проходом.

Теперь для решения задачи достаточно перебрать ход Алисы, если Алиса выбрала отрезок призов от A до A + k – 1, то максимальное значение, которое может достаться Бобу это

max(pref[A – 1], suff[A + k])

Среди этих значений надо выбрать минимум.

Приведем код решения на С++

cin>>n>>k;

s[0]=0;

 for (int i = 1; i <= n; i++) { 

     cin>>a[i]; 

     s[i] = s[i - 1] + a[i]; 

  } 

 for (int i = k; i <= n; i++) { 

     pref[i] = max(pref[i - 1], s[i] - s[i - k]); 

  } 

suff[n-k+1]=s[n]-s[n-k];

 for (int i = n - k + 1; i >= 1; i--) { 

     suff[i] = max(suff[i + 1], s[i + k - 1] - s[i - 1]); 

  } 

long long best = 2e18; 

 for (int i = 1; i <= n - k + 1; i++) { 

     best = min(best, max(pref[i - 1], suff[i + k])); 

  } 

cout<<best;

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 3 секунды

Ограничение по памяти: 16 мегабайт

Петя написал программу движения робота К-79. Программа состоит из следующих команд:

·         S - сделать шаг вперед

·         L - повернуться на 90^o влево

·         R - повернуться на 90^o вправо

Напишите программу, которая по заданной программе для робота определит, сколько шагов он сделает прежде, чем впервые вернется на то место, на котором уже побывал до этого, либо установит, что этого не произойдет.

Формат входных данных

Во входном файле записана одна строка из заглавных латинских букв S, L, R, описывающая программу для робота. Общее число команд в программе не превышает 200, при этом команд S - не более 50.

Формат выходных данных

В выходной файл выведите, сколько шагов будет сделано (то есть выполнено команд S) прежде, чем робот впервые окажется в том месте, через которое он уже проходил. Если такого не произойдет, выведите в выходной файл число -1.

Примеры

Решение

Представим себе, что робот ходит по большой шахматной доске, каждым ходом перемещаясь на одну клетку влево, вправо, вперед или назад. Мы будем хранить в двумерном массиве путь робота и после каждого очередного хода проверять, не попал ли робот в клетку, в которой он уже был раньше. Чтобы отслеживать передвижения робота, нам нужно в каждый момент времени знать, в какую сторону он смотрит. Обозначим направления цифрами: 0 — направо, 1 — вперед, 2 — налево, 3 — назад. Тогда, если мы храним в переменной dir текущее направление движения, то поворот налево будет соответствовать прибавлению к dir единицы по модулю 4:

dir:= (dir + 1) % 4 {0->1, 1->2, 2->3, 3->0}

Поворот направо, аналогично, будет соответствовать вычитанию единицы по модулю 4 (или прибавление 3).

Заведем два массива:

int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};

Их смысл в следующем: если dir — текущее направление движения робота, то за один ход его координата х изменяется на dx[dir], а коор­дината у на dy [dir].

После этого несложно написать требуемую программу. Будем считать, что мы прочитали последовательность ходов робота в строковую переменную S.

Решение на я.п. Pascal

i:= 1; {номер анализируемого символа} 

step:= 0; {количество сделанных ходов S}

flag := false; {возвратились ли на пройденную ранее клетку}

х:= 0; {текущее }

у:= 0; {положение робота}

was[0][0] := true; {робот начинает движение в клетке (0,0)} 

repeat 

   case s [i] of

      ’L’: dir:= (dir + 1) mod 4;

      ’R’: dir:= (dir + 3) mod 4;

      ’S’: 

      begin

         inc(step); 

         x:= x + dx;

         у:= у + dy;

         if was[x][y] then flag:= true else was[x][y]:= true;

      end;  end;

      inc(i);

   until (i>length(s)) OR flag; 

 if flag then write(step) else write(-l);

Решение на я.п. С/С++

#include <iostream> 

using namespace std;

char s[201];

int a[101][101]={0};

int n=0,m,k,i=0,j,x=50,y=50,c=0;

int main(){

 cin.getline(s,201);

 a[x][y]=1;

  while(s[i]!='\n'){

    if(s[i]=='L')n=(n+1)%4;

    if(s[i]=='R')n=(n+3)%4;

    if(s[i]=='S'){

      c++;

       if(n==0) x++;

       if(n==1) y++;

       if(n==2) x--;

       if(n==3) y--;

       if(a[x][y]) {

         cout<<c; 

         return 0;

  }

     a[x][y]=1;

   }

      i++;

  }

 cout<<"-1";

 return 0;

 }

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 5 секунд

Ограничение по памяти: 4 мегабайта

В супермаркете решили время от времени транслировать рекламу новых товаров. Для того, чтобы составить оптимальное расписание трансляции рекламы, руководство супермаркета провело следующее исследование: в течение дня для каждого покупателя, посетившего супермаркет, было зафиксировано время, когда он пришел в супермаркет, и когда он из него ушел.

Менеджер по рекламе предположил, что такое расписание прихода-ухода покупателей сохранится и в последующие дни. Он хочет составить расписание трансляции рекламных роликов, чтобы каждый покупатель услышал не меньше двух рекламных объявлений. В то же время он выдвинул условие, чтобы два рекламных объявления не транслировались одновременно и, поскольку продавцам все время приходится выслушивать эту рекламу, общее число рекламных объявлений за день было минимальным.

Напишите программу, которая составит такое расписание трансляции рекламных роликов. Рекламные объявления можно начинать транслировать только в целые моменты времени. Считается, что каждое рекламное объявление заканчивается до наступления следующего целого момента времени. Если рекламное объявление транслируется в тот момент времени, когда покупатель входит в супермаркет или уходит из него, покупатель это объявление услышать успевает.

Формат входных данных

Во входном файле записано сначала число N — количество покупателей, посетивших супермаркет за день(1≤N≤3000). Затем идет N пар натуральных чисел A_i, B_i, задающих соответственно время прихода и время ухода покупателей из супермаркета (0<A_i<B_i<10⁶).

Формат выходных данных

В выходной файл выведите сначала количество рекламных объявлений, которое будет протранслировано за день. Затем выведите в возрастающем порядке моменты времени, в которые нужно транслировать рекламные объявления.

Если решений несколько, выведите любое из них.

Пример

Решение

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

Пример из условия в такой интерпретации будет выглядеть следующим образом:

Отсортируем все отрезки по возрастанию правых границ, а при их равенстве – по убыванию левых.

Ограничение на количество отрезков (N≤3000) позволяет применить не только быструю сортировку, но и алгоритм сортировки с квадратичной временной сложностью, например метод «пузырька».

К сожалению, приведенный в задаче тест, не позволяет разработать универсальный алгоритм решения задачи.

Рассмотрим следующий пример. Пусть дано четыре отсортированных отрезка: [1,6], [3,7], [12,14], [14,16].

В самом первом отрезке [1,6] должны содержаться две точки. Их необходимо поставить как можно правее, то есть в точках с целочисленными координатами 5 и 6. Почему? Поскольку это отрезок с наименьшей правой границей, то раньше него другие отрезки не могли закончиться. Но могли начаться другие отрезки! А чем правее мы располагаем точки, тем больше шанс, что они одновременно попадут и в другие отрезки – что нам выгодно. Еще раз обратим внимание на факт, что не существует более выгодной расстановки точек, чем данная: поскольку никакой другой отрезок раньше наших точек не заканчивается, то мы не упускаем ни одну потенциальную возможность улучшить расстановку точек.

В нашем примере расставленные две точки сразу попали и в отрезок [3,7]. А вот если бы мы поставили точки, например, в координатах 1 и 2, то такая расстановка была бы неэффективной – мы покрыли бы ей только один отрезок, а не два.

Назовем точку 6 последней расставленной точкой, а точку 5 – предпоследней. Переходим к следующему отрезку [3,7] – но внутри него уже стоят две точки, поскольку левая граница отрезка меньше, чем предпоследняя расставленная точка. Следующий отрезок – [12, 14]. В нем не стоит еще ни одной точки, так как левая граница отрезка больше последней расставленной точки. Из аналогичных соображений ставим в нем две точки как можно правее.

Последний отрезок – [14, 16]. В нем уже содержится одна из поставленных точек, так как последняя расставленная точка равна левой границе отрезка. Ставим еще одну точку в правую границу отрезка – координата равна 16. При этом предыдущей точкой станет точка 14.

Легко видеть, что такой алгоритм расстановки точек всегда дает оптимальный результат.

Итак, для каждого отрезка мы смотрим, нужно ли поставить в нем одну или две точки и если да, то ставим их как можно правее.

Если Вы уже поняли алгоритм решения, то для закрепления понимания разберите еще два теста:

Тест 1:

10

88 99

188 190

190 199

162 165

1 52

76 89

99 130

135 153

52 76

165 188

И второй тест:

10

1 900000

3 30000

7 20000

6 25000

4 27000

10 10000

100 5000

1000 3000

1500 2500

2000 2004

Сравните ответы:

Тест 1: 13 точек

Тест 2: 2 точки

Если алгоритм понятен, то предлагаю самостоятельно составить программу!

Перейти к навигацииПерейти к поиску

Школьный этап Всероссийской олимпиады школьников по информатике.

Содержание

·         1Задача А. Клад

o    1.1Решение

·         2Задача В. Целые точки

o    2.1Разбор

·         3Задача С. Представление чисел

o    3.1Разбор

·         4Задача D. Удав

o    4.1Разбор

Найти закопанный пиратами клад просто: всё, что для этого нужно – это карта. Как известно, пираты обычно рисуют карты от руки и описывают алгоритм нахождения клада так: «Встаньте около одинокой пальмы. Пройдите тридцать шагов в сторону леса, потом семнадцать шагов в сторону озера, …, наконец десять шагов в сторону большого булыжника. Клад находится под ним». Большая часть таких указаний просто сводится к прохождению какого-то количества шагов в одном из восьми направлений (1 – север, 2 – северо-восток, 3 – восток, 4 – юго-восток, 5 – юг, 6 – юго-запад, 7 – запад, 8 – северо-запад) (см. рис. ниже). Длина шага в любом направлении равна 1.

Путешествие по такому пути обычно является прекрасным способом посмотреть окрестности, однако в наше время постоянной спешки ни у кого нет времени на это. Поэтому кладоискатели хотят идти напрямую в точку, где зарыт клад. Например, вместо того, чтобы проходить три шага на север, один шаг на восток, один шаг на север, три шага на восток, два шага на юг и один шаг на запад, можно пройти напрямую, использовав около 3.6 шага (см. рис).

Вам необходимо написать программу, которая по указаниям пиратов определяет точку, где зарыт клад.

Формат входных данных

Первая строка входного файла содержит число N – число указаний (1≤N≤40). Последующие N строк содержат сами указания – номер направления (целое число от 1 до 8) и количество шагов (целое число от 1 до 1000). Числа разделены пробелами.

Формат выходных данных

В выходной файл выведите координаты X и Y точки (два вещественных числа, разделённые пробелом), где зарыт клад, считая, что ось O_x направлена на восток, а ось O_y – на север. В начале кладоискатель должен стоять в начале координат. Координаты необходимо вывести с погрешностью не более 10^-3.

Примеры

Решение

Большинство участников решило эту задачу следующим образом: выбрали два накопителя (x и y) и с помощью оператора case of (я.п. Pascal) обрабатывали входные данные (при вводе данных).

А можно было сократить код программы, если обратить внимание на рисунок (смотри ниже несколько подправленный мною исходный рисунок):

Как видно из рисунка направление 1 совпадает с осью y, а 3 - с осью x. Допустим, направление - переменная napr. Тогда, для направления 1 можно записать y=shag*cos((pi/4)*(napr - 1)), а x=shag*sin((pi/4)*(napr-1)). (pi/4) - это 45⁰, выражение (cos(45⁰*(1-1)))=cos(0⁰)=1, то есть для 1 направления y=shag, а выражение sin((pi/4)*(napr-1))=sin(45⁰*(1-1)))=0. Следовательно, для направления 1 координаты y и x принимают значения: y=shag, а x=0.

Рассмотрите значения приведенных выражений для всех направлений и Вы увидите, что для всех направлений можно применить данные выражения для вычисления координат. А это позволяет сократить код программы. Смотрите приведенные тексты программ:

#include <iostream>

#include <cstdio>

#include <iomanip>

#include <cmath>

using namespace std;

int main(){

const double PI = 3.14159265;

long n, i, l;

int napr;

double x=0,y=0;

cin >> n;

  for(i=0;i<n;i++){

    cin >> napr >> l;

    x =x + l*sin((PI/4)*(napr-1));

    y =y + l*cos((PI/4)*(napr-1));

  }

    cout << fixed << setprecision(3) << x << " " << y;

    return 0;

}

#include <iostream>

#include <math.h>

#include <stdio.h>

#include <iomanip>

using namespace std;

int main()

{

    int n,e,s;

    float x,y;

    x=0;

    y=0;

    cin>>n;

    for (int i=0; i!=n;i++)

    {

        cin>>e;

        cin>>s;

        if (e==1) {y+=s;}

        if (e==2) {x+=s/sqrt(2); y+=s/sqrt(2);}

        if (e==3) {x+=s;}

        if (e==4) {x+=s/sqrt(2); y-=s/sqrt(2);}

        if (e==5) {y-=s;}

        if (e==6) {x-=s/sqrt(2); y-=s/sqrt(2);}

        if (e==7) {x-=s;}

        if (e==8) {x-=s/sqrt(2); y+=s/sqrt(2);}

    }

    cout<<fixed<<setprecision(3)<<x<<" "<<y;

    return 0;

}

Многоугольник (не обязательно выпуклый) на плоскости задан координатами своих вершин. Требуется подсчитать количество точек с целочисленными координатами, лежащих внутри него (но не на его границе).

Формат входных данных

В первой строке содержится N (3≤N≤1000) – число вершин многоугольника. В последующих N строках идут координаты (X_i, Y_i) вершин многоугольника в порядке обхода по часовой стрелке. X_i, Y_i - целые числа, по модулю не превосходящие 1000000.

Формат выходных данных

В выходной файл вывести одно число – искомое число точек.

Примеры

Разбор

Данная задача решается просто, если использовать формулу Пика, которая устанавливает связь между площадью многоугольника, количеством точек с целочисленными координатами, расположенными внутри многоугольника и количеством точек с целочисленными координатами, находящимися на гранях многоугольника:

S = K + G/2 - 1, откуда K = S - G/2 + 1

где:

   S - площадь многоугольника;

   K - количество точек с целочисленными координатами, расположенными внутри многоугольника;

   G - количество точек с целочисленными координатами, расположенными на гранях многоугольника.

Алгоритм решения задачи:

1. Вычислить площадь многоугольника. Многоугольник надо разбить на треугольники, вычислить площади отдельных треугольников, а затем просто сложить все площади треугольников. По условию задачи многоугольник может быть как выпуклый, так и не выпуклый. Поэтому для вычисления площади единичного треугольника надо воспользоваться произведением векторов (смотрите литературу: С.М. Окулов "Программирование в алгоритмах" или Е.А. Андреева, Ю.Е. Егоров "Вычислительная геометрия", ж. Информатика, №№39, 40, 41 за 2002 г.).

Возьмем данные теста 1. Многоугольник задан вершинами с целочисленными координатами (в порядке обхода):

-1 -1

-1 1

1 1

1 -1

Допишем еще одну строку в матрице, в которой отразим значения первой вершины. И тогда, матрица вершин будет выглядеть так:

-1 -1

-1 1

1 1

1 -1

-1 -1 

Произведение векторов вычисляется как x1*y2 - x2*y1 (смотри приведенные выше источники литературы). Следовательно, если заведем две переменных - накопителя s_1 и s_2, в которые будем добавлять результаты вычислений: x1*y2(в s_1) и x2*y1(в s_2). То, по окончании обхода, просто суммируем значения этих переменных: s = s_1 + s_2. И так как произведение векторов - это площадь параллелограмма, у которого стороны - векторы, то результат необходимо разделить на 2 (так как площадь искомого треугольника в два раза меньше площади параллелограмма). Площадь найдена. Для данного теста s = -4 ((-4 - 4)/2). Для дальнейших вычислений возьмем значение площади по модулю! Рисунок ниже поясняет процесс нахождения площади многоугольника.

Пояснение к рисунку: за начало векторов лучше взять начало координат, тогда координаты векторов - координаты вершин (а они задаются).

2. Определить количество точек с целочисленными координатами, лежащих на сторонах многоугольника (G). Для этого можно воспользоваться зависимостью между НОД'ом (наибольшим общим делителем) и G: G = НОД(Δx, Δy) + 1. По рисунку слева видно, что количество точек с целочисленными координатами, лежащими на гранях составляет 8(шт.). Получите это же значение, решая через НОД(Δx, Δy)!

3. Определить количество точек с целочисленными координатами, лежащих внутри многоугольника как разность между найденной площадью n-угольника и G.

Тест 1. K = |-4| - 8/2 + 1 = 1. Что и отражено в качестве ответа в тесте 1 задачи.

 Пояснение. Площадь треугольника, приведенного на рисунке ниже, составляет 9 (по рисунку видно, что треугольник прямоугольный, и по рисунку

можно определить длины катетов: 3√2). Обозначим на треугольнике точки с целочисленными координатами (смотри второй рисунок). 

Подсчитаем Площадь треугольника, используя формулу Пика. K = 4, G = 12, S = 4 + 6 - 1 = 9.

#include <bits/stdc++.h>

using namespace std;

long long nod(long long a, long long b){

    if (min(a, b) == 0) return max(a, b);

    return nod(min(a,b), max(a, b) % min(a, b));

}

struct T{

    long long x, y;

};

int main()

{

    long long n;

    long long s = 0, p = 0, k;

    cin >> n;

    vector <T> m(n);

    for (int i = 0; i < n; i++) cin >> m[i].x >> m[i].y;

    for (int i = 0; i < n; i++) {

        if (i == n - 1) {

            s += m[i].x * m[0].y - m[i].y * m[0].x;

            continue;

        }

        s += m[i].x * m[i + 1].y - m[i].y * m[i + 1].x;

    }

    s = abs(s);

    s /= 2;

    for (int i = 0; i < n; i++) {

        if (i == n - 1) {

            p += nod(abs(m[i].x - m[0].x), abs(m[i].y - m[0].y));

            continue;

        }

     p += nod(abs(m[i].x - m[i + 1].x), abs(m[i].y - m[i + 1].y));

    }

    k = s - p / 2 + 1;

    cout << k;

    return 0;

}

{$APPTYPE CONSOLE}

uses

  SysUtils;

var a: array [1..1000,1..2] of Integer;  

    n,i,c,j: Integer;

    s,k,b,z:int64;

function nod(x,y: integer):Integer;

begin

   if y=0 then nod:=x else nod:=nod(y,x mod y);

end;

  begin

      readln(n);

      Readln(a[1,1],a[1,2]);

      s:=0;

      k:=0;

      for i:=2 to n do begin

        Readln(a[i,1],a[i,2]);

        z:=   int64((a[i,1]+a[i-1,1]))*int64((a[i-1,2]-a[i,2]));

        s:=s+z;

        if  abs(a[i,2]-a[i-1,2])<abs(a[i,1]-a[i-1,1]) then

        k:=k+nod(abs(a[i,1]-a[i-1,1]),abs(a[i,2]-a[i-1,2]))

         else k:=k+nod(abs(a[i,2]-a[i-1,2]),abs(a[i,1]-a[i-1,1]));

        end;

      s:=s+int64(a[1,1]+a[n,1])*int64(a[n,2]-a[1,2]);

      if  abs(a[1,2]-a[n,2])<abs(a[1,1]-a[n,1]) then

        k:=k+int64(nod(abs(a[1,1]-a[n,1]),abs(a[1,2]-a[n,2])))

        else k:=k+int64(nod(abs(a[1,2]-a[n,2]),abs(a[1,1]-a[n,1])));

      if s<0 then s:=-s;

      b:=s+2-k;

      Writeln(b div 2);

      end.

Дано натуральное число N. Требуется представить его в виде суммы двух натуральных чисел A и B таких, что НОД (наибольший общий делитель) чисел A и B — максимален.

Формат входных данных

Во входном файле записано натуральное число N (2≤N≤10⁹)

Формат выходных данных

В выходной файл выведите два искомых числа A и B. Если решений несколько, выведите любое из них.

Примеры

Разбор

Рассмотрим типы чисел, которые подаются на вход программе:

1. Числа четные. В этом случае максимальный НОД может быть только если каждое число - половинка входного (смотри второй тест: 16).

2. Простое число. Мы знаем, первым простым числом является число 2, а все остальные простые числа - нечетные числа. С четным все понятно (смотри пункт 1).

 Рассмотрим пример возможных пар чисел для простого числа: 11. Это

 1, 10;

 2, 9;

 3, 8;

 4, 7;

 5, 6.

 Далее пары повторяются, только A > B.

Как видно из приведенных пар чисел - НОД в каждой паре равен 1. Поэтому, ответом будет любая из пар A, B, в сумме равных введенному числу N.

3. Нечетное число, имеющее делители.

Допустим, что A, B - числа, которые надо найти, а d - их наибольший делитель. Если числа A и B - делятся на d, то и N (A + B) также делится на d. Следовательно, на роль d претендует наибольший делитель числа N и меньший N. Но тогда e = N: d - наименьший делитель числа N и больший 1.

Представим число N в виде суммы двух чисел: N = N:e + (N - N:e). Оба числа делятся на d, поэтому можно считать, что A=N:e, а B=N - N:e. И вся задача сводится к нахождению наименьшего делителя числа N, большего 1. Для этого достаточно перебрать все делители от 2 до √N. Но перебор требует достаточно большого времени.

Посмотрите код решения задачи (C/C++):

#include <iostream>

#include <cstdio>

#include <cmath>

using namespace std;

int main()

{

int i=2;

long n;

cin >> n;

int c = sqrt(n);      (!!)

 while((n%i!=0) & (i<=c)){

    i++;

 }

cout << n/i << " " << n - n/i;

    return 0;

}

Обратите внимание на строку кода (!!). Если Вы запишите вместо переменной c в логическое выражение While.. выражение, указанное в строке (!!), то выполнение кода будет замедлено, так как каждый раз, проверяя условие, исполнитель будет выполнять математическое действие, а не сравнивать текущее значение с константой. Помните о таких мелочах!

Из зоопарка города Энска сбежал удав. Спасаясь от погони, он залез в местную канализацию. Канализация представляет собой набор колодцев, соединенных прямыми горизонтальными трубами, причем все колодцы, кроме двух, закрыты крышками. В один из открытых колодцев удав залез и хочет вылезти из другого открытого колодца. При этом он, естественно, хочет проползти наименьшее расстояние. Также, поскольку удав уже старый и страдает ревматизмом, он может изгибаться максимум на угол α (другими словами, если удав переползает из одной трубы в другую, направление движения может измениться не больше, чем на угол α). Требуется определить кратчайший маршрут в канализации от одного открытого колодца до другого, причем такого, чтобы он изгибался максимум на угол α (см. пример). Переползать из одной трубы в другую удав может лишь в колодце, являющемся концом обеих труб. По трубе удав может ползти в любом направлении.

Входные данные.

В первой строке входного файла через пробел записано три целых числа – N, M и α (1<N≤50, 0≤M≤1225, 0≤α≤180), где N – количество колодцев, а M – количество труб, соединяющих эти колодцы. В следующей строке записаны номера начального и конечного колодца маршрута. Далее в N строках записаны координаты колодцев (по два целых числа, по модулю не превосходящие 10000). В следующих M строках записана информация о трубах – по два числа в строке, означающих номера колодцев, соединенных соответствующей трубой. Колодцы пронумерованы начиная с единицы.

Выходные данные.

В первую строку выходного файла необходимо вывести одно число – длину кратчайшего маршрута с точностью до трех знаков после запятой, или –1, если такого маршрута не существует. Если маршрут существует, то в следующую строку необходимо вывести последовательно номера колодцев этого маршрута, разделенные пробелом.

Пример

Разбор

Разберем тест, приведенный в условии задачи:

На рисунках отражена последовательность шагов алгоритма решения задачи. По условию задачи удаву необходимо попасть из колодца 1 в колодец 4.

Движение начинается из п. 1 (длина пути равна 0) - обход в ширину - в пп.2 и 3. При этом вес вершины 2 становится равным 1, а вес вершины 3 - √2 (смотри рисунок "Шаг первый").

"Шаг второй". Рассмотрим движение удава из п.3 в п.4 (векторами красного цвета показано направление движения удава к узлу 3 и новое направление движения удава - к пункту 4). Как видно из построения - удаву необходимо повернуться на угол, больше 90⁰, что по условию задачи сделать нельзя. Следовательно, на втором шаге вес вершины 3 становится равным 2.

"Шаг третий" и последний. Удав переходит в колодец 4. При этом длина его пути становится равным 3, а путь (который мы запоминали в отдельном массиве) становится 1 2 3 4.

Вот один из способов решения задачи (язык Pascal, решение взято с сайта Московских олимпиад):

{APPTYPE CONSOLE}

uses

  SysUtils;

var

  N:Integer;

  P:array[1..50] of record X, Y: LongInt; end;

  G:array[1..50, 1..50] of Boolean;

  A:Integer;

  St, En:Integer;

procedure Inp;

var

  I, M, J, K:Integer;

begin

  Read(N, M, A, St, En);

  if (N>50) or (M>(N*(N-1)) div 2) or (A>180) or (St>N) or (En>N) then

    RunError(255);

  for I:=1 to N do

    begin

      if (SeekEof) then RunError(255);

      Read(P[I].X, P[I].Y);

    end;

  FillChar(G, Sizeof(G), 0);

  for I:=1 to M do

    begin

      if (SeekEof) then RunError(255);

      Read(J, K);

      if (J>N) or (K>N) then RunError(255);

      if (G[J, K]) then RunError(255);

      G[J, K]:=True;

      G[K, J]:=True;

    end;

end;

var

  D:array[1..50, 1..50] of Extended;

  Pr:array[1..50, 1..50] of Integer;

function Dot(X1, Y1, X2, Y2:LongInt):Extended;

begin

  Dot:=(X1*X2+Y1*Y2)/(Sqrt(X1*X1+Y1*Y1)*Sqrt(X2*X2+Y2*Y2));

end;

function Dist(A, B:Integer):Extended;

begin

  Dist:=Sqrt(Sqr(P[A].X-P[B].X)+Sqr(P[A].Y-P[B].Y));

end;

procedure Run;

var

  CA:Extended;

  I, J, Mi, Mj:Integer;

  W:array[1..50, 1..50] of Boolean;

  Px, Py:Integer;

begin

  CA:=Cos(A*PI/180);

  for I:=1 to N do

    for J:=1 to N do

      D[I, J]:=-1;

  for I:=1 to N do

    if (G[I, En]) then

      D[I, En]:=Dist(I, En);

  FillChar(W, Sizeof(W), 0);

  repeat

    Mi:=-1;

    for I:=1 to N do

      for J:=1 to N do

        if (not W[I, J]) and (D[I, J]<>-1) and ((Mi=-1) or (D[I, J]<D[Mi, Mj])) then

          begin

            Mi:=I;

            Mj:=J;

          end;

    if (Mi=-1) then Break;

    Px:=P[Mi].X-P[Mj].X;

    Py:=P[Mi].Y-P[Mj].Y;

    W[Mi, Mj]:=True;

    for I:=1 to N do

      if (G[Mi, I]) and (Dot(Px, Py, P[I].X-P[Mi].X, P[I].Y-P[Mi].Y)>=CA-1E-6) and

         ((D[I, Mi]=-1) or (D[I, Mi]>D[Mi, Mj]+Dist(Mi, I))) then

         begin

           D[I, Mi]:=D[Mi, Mj]+Dist(Mi, I);

           Pr[I, Mi]:=Mj;

         end;

  until False;

end;

procedure Out;

var

  I, J, Mi:Integer;

begin

  Mi:=-1;

  for I:=1 to N do

    if (D[St, I]<>-1) and ((Mi=-1) or (D[St, I]<D[St, Mi])) then

      Mi:=I;

  if (Mi=-1) then

    WriteLn(-1)

  else

    begin

      WriteLn(D[St, Mi]:0:3);

      I:=St; J:=Mi;

      while True do

        begin

          Write(I, ' ');

          if (I=En) then Break;

          Mi:=Pr[I, Mi];

          I:=J;

          J:=Mi;

        end;

      WriteLn;

    end;

end;

begin

  Inp;

  Run;

  Out;

end.

Перейти к навигацииПерейти к поиску

Задача А. Выращиваем бактерии

Вы — большой любитель бактерий. Вам хочется вырастить немного бактерий в коробочке.

Изначально коробочка пуста. Каждое утро можно положить любое количество бактерий в коробочку. Каждую ночь каждая бактерия делится на две бактерии.

Когда-нибудь вы надеетесь увидеть ровно x бактерий в коробочке.

Какое минимальное количество бактерий вам суммарно надо положить в коробочку для достижения этой цели?

Входные данные

В единственной строке записано одно целое число x (1 ≤ x ≤ 10⁹) — количество бактерий.

Выходные данные

Единственная строка, содержащая одно целое число — ответ на задачу.

Примеры тестов

Входные данные

5

Выходные данные

2

Входные данные

8

Выходные данные

1

Решение.

Можно было бы просто сказать: переведи число в двоичную систему счисления и подсчитай в нем количество единиц.

Докажем, что данный метод решения верный. Для этого построим двоичное дерево. Почему двоичное? В тексте задачи мною выделены опорные моменты:

1) каждое утро можно положить любое количество бактерий;

2) каждую ночь каждая бактерия делится на две бактерии;

3) количество дней размножения бактерий не играет роли.

На дереве справа красным цветом будем показывать количество бактерий, добавляемых в коробочку каждое утро.

Тест 1 Надо получить 5 бактерий.

В первое утро в коробочку положили 1 бактерию.

На второе утро в коробочке лежало уже 2 бактерии.

На третье утро в коробочке было уже 4 бактерии. Для того, чтобы получить 5 бактерий, в это утро в коробочку добавили еще 1 бактерию.

Тест 2. Надо получить 8 бактерий.

По дереву слева видно, что, если не добавлять одну бактерию на третье утро, а оставить бактерии размножаться далее, то на четвертое утро в коробочке будет 8 бактерий.

Разберем еще один тест: надо получить 13 бактерий.

Если не добавлять бактерий, то цепочка размножений будет такой: 1 - 2 - 4 - 8 - 16. То есть, на пятое утро в коробочке будет лишнее количество бактерий (нам надо получить 13 бактерий)!

Дерево, приведенное на рисунке ниже, показывает, как достичь этого результата:

По дереву видно, что для достижения результата, необходимо добавить 1 бактерию на второй день и 1 - на четвертый.

Подведем итог наших рассуждений. Красным цветом выделены цепочки добавления бактерий. 5 - 101, 8 - 1000 и 13 - 1101. А это и есть двоичное представление числа x.

Задача В. Музыка

Мальчик Лёша любит слушать музыку со своего смартфона.

Но памяти у смартфона не очень много, поэтому Лёша слушает любимые композиции в известной социальной сети НаСвязи.

К сожалению, интернет в Екатеринозаводске не очень быстрый, и песня загружается очень медленно. Но Лёша весьма нетерпелив. Песня длится ровно T секунд. Лёша прогружает первые S секунд композиции и включает песню. Когда воспроизведение доходит до момента, который ещё не прогрузился, Лёша моментально включает песню заново (при этом загруженная часть песни остаётся в памяти телефона, и процесс скачивания продолжается с того же места), и так происходит до тех пор, когда песня скачается полностью и Лёша дослушает до конца. За q секунд реального времени интернет позволяет скачать q - 1 секунду трека.

Подскажите Лёше, сколько раз он запустит песню, включая самый первый запуск.

Входные данные

В единственной строчке записаны три целых числа T, S, q (2 ≤ q ≤ 10⁴, 1 ≤ S < T ≤ 10⁵).

Выходные данные

Выведите одно целое число — количество запусков композиции.

Примеры тестов

Входные данные

5 2 2

Выходные данные

2

Входные данные

5 4 7

Выходные данные

1

Входные данные

6 2 3

Выходные данные

1

Примечание

В первом тесте песня проигрывается в два раза быстрее, чем скачивается, а значит через четыре секунды Лёша впервые дослушает до момента, который ещё не прогрузился, и запустит песню заново. Ещё через две секунды песня скачается полностью, а значит Лёша запустит песню два раза.

Во втором тесте песня уже почти скачана, и Лёша запустит её всего один раз.

В третьем тесте из условия загрузка заканчивается и Лёша завершает прослушивание песни в один и тот же момент. Обратите внимание, что в таком случае Лёша не перезапускает песню заново.

Решение.

Пусть перед очередным запуском песни прогружено S секунд. Найдем, сколько будет загружено песни перед следующим запуском плеера:

(x/q)=(x-S)/(q-1).

Отсюда выражаем x: x = qS.

Очевидно, что будем умножать q на S до тех пор, пока S<T. А количество умножений - это количество запусков песни - ответ на вопрос задачи.

Задача D. Фото на память

На вечеринке встретились n друзей, они давно не собирались все вместе и поэтому решили сделать общее групповое фото.

Упрощённо процесс фотографирования можно описать следующим образом. На фотографии каждый из друзей занимает прямоугольник из пикселей: i-й из них занимает прямоугольник ширины w_i пикселей и высоты h_i пикселей. На групповом фото все фотографируемые стоят в ряд, таким образом минимальный размер в пикселях фотографии, включающей всех друзей, составляет W × H, где W — суммарная ширина всех фотографируемых, а H — максимальная из высот всех фотографируемых.

Как это обычно и бывает, друзья сфотографировались n раз — на j-й (1 ≤ j ≤ n) фотографии присутствовали все, кроме j-го из них, ведь он был фотографом.

Выведите минимальный размер в пикселях каждого из сделанных фото.

Входные данные

В первой строке записано целое число n (2 ≤ n ≤ 200 000) — количество друзей.

Далее следует n строк: i-я из них содержит информацию об i-м из друзей. В строке содержится пара целых чисел w_i, h_i (1 ≤ w_i ≤ 10, 1 ≤ h_i ≤ 1000) — ширина и высота в пикселях соответствующего ему прямоугольника.

Выходные данные

Выведите n разделённых пробелами чисел b₁, b₂, ..., b_n, где b_i — общее количество пикселей на минимальной фотографии, вмещающей всех друзей, кроме i-го из них.

Примеры тестов

Входные данные

3

1 10

5 5

10 1

Выходные данные

75 110 60

Входные данные

3

2 1

1 2

2 1

Выходные данные

6 4 6

Решение.

Это третья из простых задач. Сложность реализации - использование массива и большое количество "друзей" (200000), из-за чего задача могла не пройти по времени. В условии задачи детально прописаны условия, которые необходимо было выполнить (читайте текст задачи до тех пор, пока ясно не представите, что же необходимо определить).

Что же требуется найти? На групповом фото все фотографируемые стоят в ряд, следовательно, ширина фотографии равна ширине фотографии всех n друзей, за исключением фотографа. Высота общей фотографии - максимальная из всех возможных (не учитывается высота снимка фотографа). Таким образом, для решения задачи необходимо знать:

1) ширину всех фотографий, без ширины фотографии того, кто в этот момент фотографирует (W_i = s - w_i ).

2) если высота фотографии того, кто фотографирует друзей, совпадает с максимальной, то надо знать второй по максимальной высоте снимок (H_i - максимальное из всех h_j).

Для подсчета W_i необходимо найти сумму всех фотографий по ширине (w_j). Для ответа на второй вопрос (максимальное значение фотографии) достаточно найти два максимума из всех h_j.

Все определяется за один проход: заполнение массива, определение суммы s и определение двух максимумов.

Текст решения задачи на языке С:

Задача С. Задача про ломаную

Дана ломаная, проходящая через точки (0, 0) – (x, x) – (2x, 0) – (3x, x) – (4x, 0) – ... - (2kx, 0) – (2kx + x, x) – ....

Мы знаем, что ломаная проходит через точку (a, b).

Найдите наименьшее возможное положительное значение x, при котором это верно, либо определите, что такого значения x не существует.

Входные данные

В единственной строке записано два положительных целых числа a и b (1 ≤ a, b ≤ 10⁹).

Выходные данные

Выведите единственную строку, содержащую ответ. Если подходящего x не существует, выведите  - 1.

Ответ будет засчитан, если его относительная или абсолютная погрешность не превышает 10^- 9.

Примеры тестов

Входные данные

3 1

Выходные данные

1.000000000000

Входные данные

1 3

Выходные данные

-1

Входные данные

4 1

Выходные данные

1.250000000000

Примечание

Изображения к первому и третьему тесту из условия:

Это задача - полностью математическая. Геометрия.

Точка x может быть расположена либо на восходящей ветви, либо на нисходящей. НО НЕ ВНЕ ЛОМАНОЙ! Следуя постулатам математики, выведите уравнение ломаной, обращая внимание на то, что общей точкой для восходящей и нисходящей линий ломаной является общая точка x.

То есть, справедливо, что (a-b, 0)/(a+b,0). Обозначим через с (a - b) или (a + b). Можно сделать еще один вывод, что с/(2*x) должно быть целым числом и положительным. Отсюда следует, что x должно быть равным или больше b. Эти два условия обеспечивают принадлежность точки с координатами (a, b) ломаной.

Обозначим через y=c / (2 * x). Откуда, x = c / (2 * y) ≥ b и нам предстоит найти максимальное значение y (оно должно быть целым!). После некоторых математических преобразований, мы получаем ответ вот в таком виде:

. Очевидно, что решения не существует, при a < b.

Фактически, первое число в функции min либо не существует, либо оно больше второго числа, поэтому функцию не будем применять, а найдем выражение .

Вот один из вариантов реализации задачи (язык С(С++)):

Задача Е. Поврежденный XML

(Текст условия задачи возьмите из файла или с Контестера). Запишу только задание: Требуется написать программу, которая по строке, которую получил Петров, восстановит исходную XML-строку, которую отправлял Иванов.

Данная задача на точное программирование. Так как в задаче сказано, что исходный код и поврежденный отличаются только в одном символе, то необходимо найти две части которые отличаются только на один символ.

При решении задачи в качестве первого этапа необходимо выделить и удалить правильные коды. Для этого можно применить стек - "последним пришел - первым ушел!". Стек - это строковая переменная, в которую записываем символы строки по ходу чтения из файла. Набирая определенный блок (подстроку) (блок - часть строки, которая начинается с открывающего тега и оканчивается закрывающим), ищем совпадение в стеке с набранным блоком (не забывая, про правильность кода XML - примеры правильных кодов приведены в условии задачи). Если найдем "пару" для блока - удаляем обе части кода XML. Таким образом, достигая конца заданной строки, в стеке накапливается некоторая подстрока, в которой есть обе части "неисправного" XML-кода. А вот далее и наступает черед точного программирования.

Необходимо выполнить проверку (построение) и поиск неисправного кода. Для этого Вам необходимо предусмотреть проверку всех возможных вариантов отличия левой и правой частей кода XML.

Скачано с www.znanio.ru