Category Archives: 4. Потоковая обработка

Последовательная обработка потока данных.

Потоковая обработка

Опубликовано: 11/10/2014

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

нет комментариев

В классе и дома решаются следующие тренировочные задачи (1 балл):

Опубликованные решения

OCPC2021. Задача F. Электрик наносит ответный удар (код решения)

20/01/2024 by Александр Мармалюк

Условие

В заведении «Покосившийся Скворечник» главврач экономит на зарплате системного администратора, поэтому эту должность в свободное от уколов время занимает электрик Геннадий из палаты номер 404. На сегодняшнем дежурстве одна из розеток внезапно заговорила с Геннадием и посулила тому суперспособности, если он её раскрутит. Результатом их общения, однако, стал лишь удар тока по нерадивому электрику, и теперь Геннадий задумал месть: он устроит лживой розетке Очень Длинное Замыкание!

Дата-центр «Покосившегося Скворечника» устроен следующим образом: помимо разной аппаратуры, из стены в ряд торчат 2∙n коннекторов: это n штепселей и n розеток. Геннадий планирует разбить их на пары розетка-штепсель и соединить каждую пару одним проводом таким образом, что штепсель всегда находится левее соответствующей розетки – эту идею ему навеяли правила средневекового этикета. Чтобы замыкание было Очень Длинным, Геннадий хочет, чтобы суммарная длина проводов, использованных для его коварного замысла, была максимально возможной. Помогите ему! Ну, или не мешайте хотя бы, и просто подскажите, провод какой длины он должен отрезать от соседней линии электропередач, чтобы распилить его на столь нужные ему провода.

Первая строка ввода содержит целое число $n$ $(2 \leqslant n \leqslant 1000).$ Вторая строка содержит n целых чисел – координаты штепселей слева направо. Третья строка содержит n чисел – координаты розеток слева направо. Все числа во второй и третьей строках различны и находятся в диапазоне от $0$ до $10^5$.

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

Тесты

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

2 1 4 6 8	9
2 1 4 2 5	2
4 2 5 6 9 3 7 12 22	22
3 2 3 4 12 13 17	33

Код программы

#include <iostream>
using namespace std;
int main() {
    int n, res = 0;
    cin >> n;
    for (int tmp, i = 0; i < n; i++) {
        cin >> tmp;
        res -= tmp;
    }
    for (int tmp, i = 0; i < n; i++) {
        cin >> tmp;
        res += tmp;
    }
    cout << res;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, res = 0;

cin >> n;

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

cin >> tmp;

res -= tmp;

}

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

cin >> tmp;

res += tmp;

}

cout << res;

return 0;

}

Решение

Обратим внимание на то, что оптимальным будет решение подключать $i$-й штепсель к $i$-й розетке. В условии задачи сказано, что существует хотя бы один способ подключить все коннекторы так, чтобы соблюсти средневековое правило этикета. Значит, последовательно подключая самый левый свободный штепсель в самую левую свободную розетку (а поскольку коннекторы изначально упорядочены, это и значит $i$-й штепсель в $i$-й розетку), мы удовлетворим правило этикета. Теперь покажем, что суммарная длина проводов в любом другом подключении не меньше. Предположим, мы подключили $i$-й штепсель в $j$-ю розетку (и это первый случай подключения штепселя не на «свое» место). Поскольку все предыдущие розетки, если они есть, уже заняты, $j \gt i$. Если можно подключить $j$-й штепсель в $i$-ю розетку (т.е. $j$-й штепсель левее $i$-й розетки), то суммарная длина проводов не изменится. Если же $j$-й штепсель правее $i$-й розетки, то чтобы иметь возможность его подключить, надо переподключить штепсели между $i$-м и $j$-м (надо заметить, что такая возможность не гарантирована). В результате этого мы сэкономим провода на не более, чем расстояние между $i$-й розеткой и $j$-м штепселем. Но поскольку $k$-я розетка, в которую мы подключим $j$-й штепсель, обязательно правее самого штепселя, то суммарная длина проводов нового подключения будет больше исходной как минимум на расстояние между $k$-й розеткой и $j$-м штепселем, поскольку этот фрагмент провода «дублируется» подключением $i$-го штепселя в $j$-ю розетку.

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

Решение задачи на ideone.com

Ссылка на контест

Related Images:

e-olymp 7258. Числовые операции

12/04/2021 by Філіпенко Микита

Условие

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

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

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

Первая строка входного файла содержит число $T (1 \leqslant T < 10^4),$ которое задает количество чисел во входном файле, для которых требуется найти ответ. В последующих $T$ строках задано по одному натуральному числу $N_i$,$2\leqslant N_i < 10^9$, $1 \leqslant i \leqslant T$. Известно, что среди чисел $N_i, 1 \leqslant i \leqslant T$, нет одинаковых.

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

Выходной файл должен содержать $T$ чисел по одному в строке — в $i$-й строке должно быть записано наименьшее количество секунд, которое понадобится истратить Пете, чтобы, начав с единицы, записать на доске соответствующее число $N_i$.

Тесты

№

Ввод

Вывод

955

4

137

318

3028

300

39

40

71

50

Код

#include <iostream>

using namespace std;

int nonzero(int number) //функция, которая считает количество цифр, не равных нулю, кроме последней
{
  int count = 0;
  number /= 10;
  while (number != 0) {
    if (number % 10 != 0) count++;
    number /= 10;
  }
  return count;
}
int summa(int number) //функция, которая возвращает сумму цифр числа
{
  int sum = 0;
  while (number != 0) {
    sum += number % 10;
    number /= 10;
  }
  return sum;
}
bool edinica(int number) //функция, которая проверяет есть ли среди цифр числа, кроме последней, единица
{
  number /= 10;
  bool ok = false;
  while (number != 0) {
    if (number % 10 == 1) ok = true;
    number /= 10;
  }
  return ok;
}
int kol_vo(int number) //функция, вычисляющая кол-во цифр числа
{
  int count = 0;
  while (number != 0) {
    count++;
    number /= 10;
  }
  return count;
}
int formula(int number) //формула, по которой можно дойти от 1 до 10^(a-1),где a- кол-во цифр числа
{
  int a = kol_vo(number);
  return (5 * a - 1) * (a - 1);
}

int main() {
  //инициализируем переменную t и считываем ее с клавиатуры
  int t;
  cin >> t;
  //инициализируем переменную ni и задаем цикл, который будет работать пока мы вводим значения ni и t>0
  int ni;
  while (cin >> ni and t > 0) {
    //кладем в переменную kol_vo1 значение функции kol_vo от значения ni
    int kol_vo1 = kol_vo(ni);
    //появляется необходимость создать переменную, которая будет равна значению ni,так как с этим значением
    //в дальнейшем будут проводится операции, а в конце программы нам нужно будет обратиться к исходному значению ni 
    int a = ni;
    //задаем массив, размерность которого равна кол-ву цифр числа
    int b[kol_vo1];
    for (int i = 0; i < kol_vo1; i++) {
      b[i] = a % 10;
      a /= 10;
    }
    //далее производим проверку условия №2,которое описано в решении. Если число проходит условие, то 
    //выводим соответствующую формулу, указанную в условии №2
    bool ok = false;
    for (int i = 0; i < kol_vo1 - 1; i++) {
      if (b[i] == 0) ok = true;
      else {
        ok = false;
        break;
      }
    }
    if (b[kol_vo1 - 1] > 1 and ok == true) {
      cout << summa(--ni) + nonzero(--ni) - edinica(--ni) + formula(ni) << endl;
    }
    //далее производим проверку условия №1,которое описано в решении. Если число проходит условие, то 
    //выводим соответствующую формулу, указанную в условии №1
    bool ok2 = false;
    for (int i = 0; i < kol_vo1 - 1; i++) {
      if (b[i] != 0) ok2 = true;
    }
    if (ok2 == true) cout << summa(ni) + nonzero(ni) - edinica(ni) - 1 + formula(ni) << endl;
    //остались крайние случаи, когда число однозначное или кратное 10^n.Проверяем число на эти условия
    //и если оно является таковым, выводим соответствующие значения
    if (kol_vo1 == 1) cout << ni - 1 << endl;
    if (ni == 10 or ni == 100 or ni == 1000 or ni == 10000 or ni == 100000 or ni == 1000000 or ni == 10000000 or ni == 100000000 or ni == 1000000000) cout << formula(ni) << endl;
    //декрементируем переменную t
    t--;
  }
}

#include <iostream>

using namespace std;

int nonzero(int number) //функция, которая считает количество цифр, не равных нулю, кроме последней

{

int count = 0;

number /= 10;

while (number != 0) {

if (number % 10 != 0) count++;

number /= 10;

}

return count;

}

int summa(int number) //функция, которая возвращает сумму цифр числа

{

int sum = 0;

while (number != 0) {

sum += number % 10;

number /= 10;

}

return sum;

}

bool edinica(int number) //функция, которая проверяет есть ли среди цифр числа, кроме последней, единица

{

number /= 10;

bool ok = false;

while (number != 0) {

if (number % 10 == 1) ok = true;

number /= 10;

}

return ok;

}

int kol_vo(int number) //функция, вычисляющая кол-во цифр числа

{

int count = 0;

while (number != 0) {

count++;

number /= 10;

}

return count;

}

int formula(int number) //формула, по которой можно дойти от 1 до 10^(a-1),где a- кол-во цифр числа

{

int a = kol_vo(number);

return (5 * a - 1) * (a - 1);

}

int main() {

//инициализируем переменную t и считываем ее с клавиатуры

int t;

cin >> t;

//инициализируем переменную ni и задаем цикл, который будет работать пока мы вводим значения ni и t>0

int ni;

while (cin >> ni and t > 0) {

//кладем в переменную kol_vo1 значение функции kol_vo от значения ni

int kol_vo1 = kol_vo(ni);

//появляется необходимость создать переменную, которая будет равна значению ni,так как с этим значением

//в дальнейшем будут проводится операции, а в конце программы нам нужно будет обратиться к исходному значению ni

int a = ni;

//задаем массив, размерность которого равна кол-ву цифр числа

int b[kol_vo1];

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

b[i] = a % 10;

a /= 10;

}

//далее производим проверку условия №2,которое описано в решении. Если число проходит условие, то

//выводим соответствующую формулу, указанную в условии №2

bool ok = false;

for (int i = 0; i < kol_vo1 - 1; i++) {

if (b[i] == 0) ok = true;

else {

ok = false;

break;

}

if (b[kol_vo1 - 1] > 1 and ok == true) {

cout << summa(--ni) + nonzero(--ni) - edinica(--ni) + formula(ni) << endl;

}

//далее производим проверку условия №1,которое описано в решении. Если число проходит условие, то

//выводим соответствующую формулу, указанную в условии №1

bool ok2 = false;

for (int i = 0; i < kol_vo1 - 1; i++) {

if (b[i] != 0) ok2 = true;

}

if (ok2 == true) cout << summa(ni) + nonzero(ni) - edinica(ni) - 1 + formula(ni) << endl;

//остались крайние случаи, когда число однозначное или кратное 10^n.Проверяем число на эти условия

//и если оно является таковым, выводим соответствующие значения

if (kol_vo1 == 1) cout << ni - 1 << endl;

if (ni == 10 or ni == 100 or ni == 1000 or ni == 10000 or ni == 100000 or ni == 1000000 or ni == 10000000 or ni == 100000000 or ni == 1000000000) cout << formula(ni) << endl;

//декрементируем переменную t

t--;

}

Решение

Количество цифр в числе никогда не уменьшается, а может увеличиться только при добавлении к числу, состоящее только из девяток и единицы. Поэтому, для достижения числа $N$ сначала нужно дойти до числа $10$, потом до чисел $99$ и $100$ и так далее, пока количество цифр в числе не будет таким, какое требуется.
Наименьшее количество операций, необходимое для того, чтобы перейти от числа $10^{n-1}$ до заданного $n$ -значного числа $N$ можно посчитать следующим образом:
1. Если число $N$ содержит хотя бы одну цифру, отличную от нуля, кроме первой, то количество операций можно посчитать по формуле summa(N) + nonzero(N) – edinica(N) - 1, где summa(N) — сумма цифр числа, nonzero(N) — количество цифр, отличных от нуля, на всех позициях числа $N$, кроме последней, edinica(N) — число, которое равно единице, если хотя бы на одной позиции числа $N$, кроме последней, есть единица, или равна нулю, если единиц на этих позициях нет.
2. Если все цифры числа $N$, кроме первой, нулевые, а первая цифра больше единицы, то количество операций можно посчитать по формуле summa(N-1)+nonzero(N-1) – edinica(N-1).

Доказательство формул

Для дальнейшего удобства обозначим перестановку цифр числа через $\Rightarrow$.
Число $N$ -заданное число, число $n$ -количество цифр числа $N$. Если $n=1$, $N=7$, то для того, чтобы дойти от единицы до заданного числа, потребуется $N-1$ операций. В нашем случае $6$ операций
($1+1=2,
2+1=3,
…
6+1=7$)
Если $n\geq2$, то для этого достаточно привести пример цепочки, подсчитывающая количество операций, которая число $10^{n-1}$ превращает в $N$. Но вместо прямого порядка действий будем делать обратный эквивалентный. $N \Rightarrow 10^{n-1}$. За одну операцию мы можем или уменьшить число на единицу, или переставить в нем цифры так, чтобы на первом месте оказался не нуль. Могут возникнуть следующие случаи:
1. Если $N=10^{n-1}$, то количество операций равно summa(N) + nonzero(N) - edinica(N) - 1 $= $ $0$.
Например, возьмем число $1000$. Сумма цифр $= 1$, количество ненулевых цифр $= 1$, количество единиц $= 1$, соответственно значение $= 1+1-1-1 =0$.

2. Если $N!=10^{n-1}$ и первая цифра числа $N$ равна единице, то проводим следующие операции:
Сначала отнимаем от числа $N$ столько единиц, чтобы последняя цифра стала нулем, далее переставим местами последнюю цифру с какой-нибудь другой, отличной от нуля, кроме первой, и опять отнимем количество единиц, чтобы последняя цифра стала нулевой. Повторять будем до тех пор, пока все цифры, кроме первой, не станут нулями.
Например, возьмем число $137$.
$137-1=136$, $136-1=135$, $135-1=134$, $134-1=133$ ,$133-1=132$ ,$132-1=131$, $131-1=130$ ,$130 \Rightarrow 103$ , $103-1=102$, $102-1=101$, $101-1=100$
Количество операций $= 11$. Проверяем по формуле. summa(137)=11, nonzero(137)=2, edinica(137)=1. Итого получаем $11+2-1-1=11$

3. Если первая цифра числа $N$ больше единицы, но хотя бы на одной позиции числа, кроме последней, есть единица, то проводим следующие операции:
Сначала уменьшаем последнюю цифру, пока она не станет нулем, затем переставляем цифры: поставим на место первой цифры единицу, а первую цифру сделаем последней, а нуль, который стоял в конце числа, поставим на место бывшей первой цифры. После этого будем действовать согласно алгоритму пункта №2.
Например, число $318$.
$318-1=317$, $317-1=316$, $316-1=315$, $315-1=314$, $314-1=313$, $313-1=312$, $312-1=311$, $311-1=310$, $310 \Rightarrow 103$, $103-1=102$, $102-1=101$, $101-1=100$
Итого $12$ операций. Просчитываем по формуле summa(318)+nonzero(318)-edinica(318)-1.
Получаем $12+2-1-1=12$.

4. Если ни на одной из позиций числа $N$, кроме, возможно, последней, нет единиц, но в числе есть хотя бы одна ненулевая цифра, кроме первой, то проводим следующие операции:
Последнюю цифру делаем нулевой, переставляем последний нуль с любой ненулевой цифрой, кроме первой, пока на последнем месте не окажется последняя ненулевая цифра (не считая первую), последнюю ненулевую уменьшаем не до нуля, а до единицы, переставим единицу с первой цифрой, новую последнюю цифру сделаем нулевой.
Например, число $3028$.
$3028-1=3027$, $3027-1=3026$, $3026-1=3025$, $3025-1=3024$, $3024-1=3023$, $3023-1=3022$, $3022-1=3021$, $3021-1=3020$, $3020 \Rightarrow 3002$, $3002-1=3001$, $3001 \Rightarrow 1003$, $1003-1=1002$, $1002-1=1001$, $1001-1=1000$
Получаем $14$ операций. Проверяем по формуле summa(3028)+nonzero(3028)-edinica(3028)-1 $= 13+2-0-1=14$.

5. Если первая цифра числа $N$ больше единицы, а все другие цифры — нулевые, то проводим следующие операции:
Отнимем от числа $N$ единицу, а дальше будем использовать один из раннее написанных алгоритмов в пунктах 2-4.
Например, число $300$.
$300-1=299$, $299-1=298$, $298-1=297$, $297-1=296$, $296-1=295$ $=$ … $291-1=290$, $290 \Rightarrow 209$, $209-1=208$ $=$ … $202-1=201$, $201 \Rightarrow 102$, $102-1=101$, $101-1=100$
Итого $22$ операции. summa(300-1)+nonzero(300-1)-edinica(300-1) $= 20+2-0=22$.

6. Подсчет операций от $1$ до $10^{n-1}$.
Для того, чтобы перейти от числа $10^{n-1}$ к $10^n$, понадобится число $10^n – 1$,которое равно $k$. По предыдущим алгоритмам, понадобится:
summa(k)+ nonzero(k) – edinica(k) - 1 $=$ $9 \cdot n + (n-1) -0 -1=10 \cdot n – 2$ операций, где $n > 1$.
Если $n=1$, то количество операций $= 10 \cdot n – 2 =8$.

Количество операций можно посчитать по формуле $(5 \cdot n -1) \cdot (n – 1)$ ,где $n$- количество цифр заданного числа.

Ссылки

Related Images:

e-olymp 1243. Наименьшее общее кратное

20/12/2020 by Максим Ливитчук

Условие

Наименьшим общим кратным ($НОК$) множества натуральных чисел называется такое наименьшее натуральное число, которое делится на каждое число в этом множестве. Например, $НОК$ чисел $5$, $7$ и $15$ равно $105$.

Вам необходимо найти $НОК$ $m$ заданных чисел.

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

Первая строка содержит количество тестов. Каждый тест состоит из одной строки и содержит числа $m$ $n_1$ $n_2$ $n_3$ $\ldots$ $n_m$, где $m$($1 \leqslant m \leqslant 100$) — количество заданных чисел, $n_1$ $\ldots$ $n_m$ — сами числа. Все числа натуральные и лежат в границах $32$-битового целого.

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

Для каждого теста в отдельной строке вывести соответствующее значение $НОК$. Все выводимые числа лежат в границах $32$-битового целого.

Тесты

№	ввод	вывод
1	2 3 5 7 15 6 4 10296 936 1287 792 1	105 10296
2	3 1 36 5 2 2 2 2 2 5 987 1597 2584 4181 6765 10946 17711	36 2 38400890173772280
3	0

Код

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    cin >>n;
    for(int i=0; i<n; i++) {
        cin >>m;
        int temp, ans;
        cin >>ans;
        for(int j=1; j<m; j++) {
            cin >>temp;
            ans = ans/__gcd(ans, temp)*temp;
        }
        cout <<ans <<endl;
    }
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int n, m;

cin >>n;

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

cin >>m;

int temp, ans;

cin >>ans;

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

cin >>temp;

ans = ans/__gcd(ans, temp)*temp;

}

cout <<ans <<endl;

}

Код с алгоритмом Евклида

#include <iostream>
#include <algorithm>
using namespace std;

int gcd(int a, int b) {
  while(a and b) {
    if(a>b)
      a %= b;
    else
      b %= a;
  }
  return a+b;
}

int main() {
    int n, m;
    cin >>n;
    for(int i=0; i<n; i++) {
        cin >>m;
        int temp, ans;
        cin >>ans;
        for(int j=1; j<m; j++) {
            cin >>temp;
            ans = ans/gcd(ans, temp)*temp;
        }
        cout <<ans <<endl;
    }
}

#include <iostream>

#include <algorithm>

using namespace std;

int gcd(int a, int b) {

while(a and b) {

if(a>b)

a %= b;

else

b %= a;

}

return a+b;

}

int main() {

int n, m;

cin >>n;

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

cin >>m;

int temp, ans;

cin >>ans;

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

cin >>temp;

ans = ans/gcd(ans, temp)*temp;

}

cout <<ans <<endl;

}

Решение

$\DeclareMathOperator{\lcm}{lcm}$
$НОК$ ($\lcm$) проще всего считается по формуле $\operatorname {lcm}(a,b)={\frac {|a\cdot b|}{\operatorname {gcd}(a,b)}}$, где $\gcd$ — $НОД$. Для $\lcm$ от более чем двух чисел справедлива следующая формула: $\operatorname {lcm}(a_{1},a_{2},\ldots ,a_{n})=\operatorname {lcm}(\operatorname {lcm}(a_{1},a_{2},\ldots ,a_{{n-1}}),a_{n})$, из которой видно, что подсчёт $\lcm$ от $n$ чисел сводится к вычислению $n-1$-ого $\lcm$ от очередного числа и предыдущего результата вычислений.

$НОД$ ($\gcd$) в коде считается при помощи стандартной функции __gcd(a, b) из стандартной библиотеки algorithm в первом варианте кода или по алгоритму Евклида во втором.

Ссылки

Related Images:

e-olymp 1679. Честная цепочка

19/12/2020 by Максим Ливитчук

Условие

В подземных норах в долине рядом со скалами Крейд-Моор долгое время жили в мире и согласии два гномьих племени. Гномы обоих племен работали в шахтах, добывая драгоценные камни. Первое племя добывало исключительно изумруды, а второе племя — рубины. Однажды в честь великого праздника Файрвинд гномы решили принести в дар своей богине Мирабель цепочку из изумрудов и рубинов. Самые искусные кузнецы обоих племен работали над созданием этой цепочки, собирая на ней один за одним драгоценные камни. Но как только работа была окончена, решили вожди племен пересчитать камни каждого вида. Ведь если каких-то камней окажется меньше, то богиня может отвернуться от племени, которое пожадничало. Чтобы избежать подобных последствий, было решено подарить некоторый непустой фрагмент цепочки (то есть цепь, состоящую из нескольких камней, расположенных друг за другом в исходной цепочке), в котором будет рубинов ровно столько же, сколько и изумрудов. Возможно это может быть сделано несколькими способами. Для того, чтобы узнать сколько таких способов существует, гномы обратились за помощью к вам.

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

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

В единственной строке задается последовательность камней в исходной цепочке: символ E обозначает изумруд, символ R — рубин. Количество символов в строке не превышает $500000$.

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

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

Тесты

№	ввод	вывод
1	REER	3
2	REERREER	12
3	RRRRRRRR	0
4	EREREERERERREREREEERERERERERRREREREERERERERE	273
5	REEERREE	7

Код

#include <iostream>
#include <map>
using namespace std;

int main() {
    int cnt = 0;
    char buf;
    map<int, long long> mp;
    mp[0] = 1;
    while(cin >>buf) {
        if(buf=='R')
            cnt++;
        else
            cnt--;
        mp[cnt]++;
    }
    long long answer = 0;
    for(auto e: mp) {
        answer += e.second*(e.second-1)/2;
    }
    cout <<answer;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

int cnt = 0;

char buf;

map<int, long long> mp;

mp[0] = 1;

while(cin >>buf) {

if(buf=='R')

cnt++;

else

cnt--;

mp[cnt]++;

}

long long answer = 0;

for(auto e: mp) {

answer += e.second*(e.second-1)/2;

}

cout <<answer;

}

Компактный код

#include 
#include <map>
using namespace std;
 
int main() {
    int cnt = 0;
    char buf;
    map mp;
    mp[0] = 1;
    while(cin >>buf) mp[buf=='R'?++cnt:--cnt]++;
    long long a = 0;
    for(auto e: mp) a += e.second*(e.second-1)/2;
    cout <<a;
}

#include

#include <map>

using namespace std;

int main() {

int cnt = 0;

char buf;

map mp;

mp[0] = 1;

while(cin >>buf) mp[buf=='R'?++cnt:--cnt]++;

long long a = 0;

for(auto e: mp) a += e.second*(e.second-1)/2;

cout <<a;

}

Решение

Составим массив из $n+1$ чисел, каждое из которых будет располагаться в месте возможного начала или конца фрагмента цепочки, который гномы должны вручить богине. Число в самом начале цепочки возьмём равным $0$, а все следующие числа будут представлять из себя количество R минус количество E, встречающихся в фрагменте с начала до этого числа.

Наглядный пример такого массива для пятого примера (подписан как cnt)

На таком массиве наглядно видно, что правильным фрагментом будет любой, начинающийся и кончающийся одинаковым числом, ведь это значит что между этими числами равное количество как R($+1$), так и E($-1$), которые сокращаются.

Выделенные в том же примере фрагменты с началом и концом в 0 и -2

Так как нам не важны конкретные правильные фрагменты, а только их суммарное количество, нам будет достаточно знать, сколько раз в массиве встречается то или иное число. В коде эту информацию хранит ассоциативная таблица mp. Запись mp[cnt]++; создаёт новый равный нулю элемент по ключу cnt, если раньше в структуре его не было, после чего инкрементирует значение.
Сам же массив воспроизводится на ходу из ввода, в переменной cnt. В конце программы количество фрагментов считается как сумма $\frac{n(n-1)}{2}$, где $n$ — mp[i] для всех встречавшихся в массиве чисел.

Ссылки

Related Images:

e-olymp 7023. Тасование Ханафуда

11/12/2020 by Михайло Будіш

Задача

Есть несколько способов, чтобы перетасовать колоду карт. Одним из таких примеров является перетасовка для японской карточной игры «Ханафуда». Ниже показано, как ее выполнить.

Имеется колода из $n$ карт. Начиная с $p$-ой карты сверху, $c$ карт вынимаются и кладутся на вершину колоды, как показано на рисунке. Такую операцию назовем операциею срезки.

Напишите программу, которая моделирует перетасовку Ханафуда, и выведет номер карты, которая в конце будет находиться наверху.

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

Состоит из нескольких тестов. Каждый тест начинается со строки, содержащей два натуральных числа $n$ $(1 ≤ n ≤ 50)$ и $r$ $(1 ≤ r ≤ 50)$ — количество карт в колоде и количество операций срезания.

Каждая из следующих $r$ строк описывает операцию срезания. Они выполняются в перечисленном порядке. Каждая строка содержит два натуральных числа $p$ и $c$ $(p + c ≤ n + 1)$. Начиная с $p$-ой карты сверху, c карт вытаскиваются и кладутся наверх.

Последняя строка содержит два нуля.

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

Для каждого теста вывести в отдельной строке номер верхней карты после выполнения тасования. Считайте, что сначала карты пронумерованы числами от $1$ до $n$ снизу доверху.

Тесты

№	Входные данные	Выходные данные
1	5 2 3 1 3 1 10 3 1 10 10 1 8 3 0 0	4 4

Код

#include <iostream>
#include <string>
 
using namespace std;
 
struct Comma {
    int num, pos;
    Comma() {
        num = 0;
        pos = 0;
    }
};
 
int main() {
    int n, r;
    while(cin >> n >> r) {
        int p, c;
        string s;
        // Filling the array with cards' numbers separated by comma
        for (int i = n; i > 0; i--) s += (i == 1 ? to_string(1) : to_string(i) + ",");
        if (n > 0) {
            for (int i = 0; i < r; i++) {
                cin >> p >> c;
                // Create object with number of comma in string and its position
                Comma comma1, comma2;
                int s_len = s.length();
                if (p != 1) {
                    // -------- Looking for indexes of needed commas to pick 'c' cards
                    for (int j = 0; j < s_len; j++) {
                        if (comma1.num == p-1) {
                            comma1.pos = j;
                            comma1.num = 0;
                        }
                        if (comma2.num == p+c-1) {
                            comma2.pos = j;
                            comma2.num = 0;
                        }
                        if (comma1.pos == 0 && s[j] == ',') comma1.num += 1;
                        if (comma2.pos == 0 && s[j] == ',') comma2.num += 1;
                    }
                    // ---------------------------------------------------------------
 
 
                    // --------- Swapping cards ---------
                    string s1 = s.substr(comma1.pos, comma2.pos - comma1.pos);
                    s.erase(comma1.pos, comma2.pos - comma1.pos);
                    if (s1[s1.length()-1] != ',') s = s1 + ',' + s;
                    else s = s1 + s;
                    // ----------------------------------
                }
            }
            int k = 0;
            while (s[k] != ',') k++;
            string res = s.substr(0, k);
            cout << res << "\n";
        }
    }
}

#include <iostream>

#include <string>

using namespace std;

struct Comma {

int num, pos;

Comma() {

num = 0;

pos = 0;

}

};

int main() {

int n, r;

while(cin >> n >> r) {

int p, c;

string s;

// Filling the array with cards' numbers separated by comma

for (int i = n; i > 0; i--) s += (i == 1 ? to_string(1) : to_string(i) + ",");

if (n > 0) {

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

cin >> p >> c;

// Create object with number of comma in string and its position

Comma comma1, comma2;

int s_len = s.length();

if (p != 1) {

// -------- Looking for indexes of needed commas to pick 'c' cards

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

if (comma1.num == p-1) {

comma1.pos = j;

comma1.num = 0;

}

if (comma2.num == p+c-1) {

comma2.pos = j;

comma2.num = 0;

}

if (comma1.pos == 0 && s[j] == ',') comma1.num += 1;

if (comma2.pos == 0 && s[j] == ',') comma2.num += 1;

}

// ---------------------------------------------------------------

// --------- Swapping cards ---------

string s1 = s.substr(comma1.pos, comma2.pos - comma1.pos);

s.erase(comma1.pos, comma2.pos - comma1.pos);

if (s1[s1.length()-1] != ',') s = s1 + ',' + s;

else s = s1 + s;

// ----------------------------------

}

int k = 0;

while (s[k] != ',') k++;

string res = s.substr(0, k);

cout << res << "\n";

}

Решение

Решить данную задачу можно несколькими способами. Первая мысль, которая мне пришла в голову — поместить все числа в строку и совершать тасование с помощью методов работы со строками, такими как $erase$ и $substr$. В течении решения стало понятно, что просто записывать числа в строку будет неправильно, так как возможны и двузначные числа. Так как неизвестно какое число будет следующим (однозначное или двузначное), особенно после нескольких перестановок, появляется идея хранить в строке числа, разделенные между собой запятыми. И в дальнейшем, если мне понадобится вытащить 5 карт из колоды начиная с 17, то я дойду до 16 запятой и возьму все, что хранится после нее, до 17+5 запятой и переставлю эти числа в начало строки (наверх колоды). Также в процессе поиска позиции необходимой запятой мне нужно получить ее позицию в строке, поэтому я решил создать структуру $Comma$, которая будет хранить номер запятой в строке и ее позицию относительно всех символов в данной строке, чтобы использовать ее во время каждой перестановки.

Таким образом, получаем рабочее решение данной задачи.

P.S. Новые решения согласно советам преподавателя

#include <iostream>
#include <string>

using namespace std;

int main() {
    int n, r;
    while(cin >> n >> r) {
        int p, c;
        string s;
        for (int i = n; i > 0; i--) s += (char)i;
        if (n > 0) {
            for (int i = 0; i < r; i++) {
                cin >> p >> c;
                if (p != 1) {
                    string s1 = s.substr(p-1, c);
                    s.erase(p-1, c);
                    s = s1 + s;
                }
            }
            cout << (int)s[0] << "\n";
        }
    }
}

#include <iostream>

#include <string>

using namespace std;

int main() {

int n, r;

while(cin >> n >> r) {

int p, c;

string s;

for (int i = n; i > 0; i--) s += (char)i;

if (n > 0) {

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

cin >> p >> c;

if (p != 1) {

string s1 = s.substr(p-1, c);

s.erase(p-1, c);

s = s1 + s;

}

cout << (int)s[0] << "\n";

}

#include <iostream>

using namespace std;

struct Card {
    int number;
    Card *next;
    Card(int num, Card *nxt = 0) {
        number = num;
        next = nxt;
    };
};

int main() {
    int n, r;
    Card *top_card = 0;
    while(cin >> n >> r) {
        int p, c;
        for (int i = 1; i <= n; i++) {
            top_card = new Card(i, top_card);
        };
        if (n > 0) {
            for (int i = 0; i < r; i++) {
                cin >> p >> c;
                if (p != 1) {
                    Card *first_moving = 0, *last_moving = 0, *last_before_moving = top_card;
                    for (int j = 1; j < p - 1; j++) {
                        last_before_moving = last_before_moving->next;
                    }
                    first_moving = last_before_moving->next;
                    last_moving = first_moving;

                    for (int j = 1; j < c; j++) {
                        last_moving = last_moving->next;
                    }
                    last_before_moving->next = last_moving->next;
                    last_moving->next = top_card;
                    top_card = first_moving;
                }
            }
            cout << top_card->number << "\n";
        }
    }
}

#include <iostream>

using namespace std;

struct Card {

int number;

Card *next;

Card(int num, Card *nxt = 0) {

number = num;

next = nxt;

};

int main() {

int n, r;

Card *top_card = 0;

while(cin >> n >> r) {

int p, c;

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

top_card = new Card(i, top_card);

};

if (n > 0) {

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

cin >> p >> c;

if (p != 1) {

Card *first_moving = 0, *last_moving = 0, *last_before_moving = top_card;

for (int j = 1; j < p - 1; j++) {

last_before_moving = last_before_moving->next;

}

first_moving = last_before_moving->next;

last_moving = first_moving;

for (int j = 1; j < c; j++) {

last_moving = last_moving->next;

}

last_before_moving->next = last_moving->next;

last_moving->next = top_card;

top_card = first_moving;

}

cout << top_card->number << "\n";

}

Ссылки

Related Images:

e-olymp-7842. Четные индексы

03/05/2020 by Евгений Фищук

Задан массив из $n$ целых чисел. Выведите все его элементы с четными индексами. Нумерация начинается с $0$.

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

В первой строке записано число $n$. В следующей строке записано $n$ целых чисел. Все числа по модулю не превышают $100$.

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

Выведите все элементы массива с четными индексами.

№	Входные данные	Выходные данные
1	7 14 16 3 7 17 19 9	14 3 17 9
2	4 12 15 21 9	12 21
3	8 12 80 67 58 5900 473 78 64	12 67 5900 78

#include <iostream>
using namespace std;

int main()
{
    int n, a;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        if (i % 2 == 0)
            cout << a << " ";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n, a;

cin >> n;

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

{

cin >> a;

if (i % 2 == 0)

cout << a << " ";

}

return 0;

}

Решение

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

Ссылки

Условие задачи на e-olymp

Код программы на ideone

Related Images:

e-olymp 8956. Вывести массив 4

25/02/2020 by Кирилл Колесник

Задача

Задан массив из [latex]n[/latex] целых чисел. Выведите только его отрицательные элементы, изменив первоначальный порядок на противоположный.

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

Первая строка содержит число [latex]n (1 \leqslant n \leqslant 100)[/latex]. Во второй строке записаны [latex]n[/latex] целых чисел, каждое из которых не превышает по модулю [latex]100[/latex].

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

В первой строке выведите количество отрицательных элементов массива. Во второй строке выведите сами отрицательные элементы в обратном порядке. Если отрицательных элементов в массиве нет, то выведите [latex]«NO»[/latex].

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	7 -2 5 4 -3 7 -1 0	3 -1 -3 -2
2	5 2 1 0 1 5	NO
3	3 -1 -2 -3	3 -3 -2 -1

Код программы

#include <iostream>
using namespace std;

int main() {
    int n, count = 0;
    cin >> n; 
    int arr[n];
    for (int i = 0; i < n; i++){
        cin >> arr[i];
        if (arr[i] < 0){
            count++;
        }
    }
    if(count == 0){
        cout << "NO";
    } else {
        cout << count << endl;
        for (int c = n - 1; c >= 0; c--){
            if (arr[c] < 0){
                cout << arr[c] << " "; 
            }
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, count = 0;

cin >> n;

int arr[n];

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

cin >> arr[i];

if (arr[i] < 0){

count++;

}

if(count == 0){

cout << "NO";

} else {

cout << count << endl;

for (int c = n - 1; c >= 0; c--){

if (arr[c] < 0){

cout << arr[c] << " ";

}

return 0;

}

Решение задачи

Для решения этой задачи, прежде всего, необходимо объявить две целочисленные переменные ― [latex]n[/latex] и [latex]count[/latex]. Переменная [latex]n[/latex] считывает первое число в строке ввода, и после объявления некоторого массива arr[n], она становится значением числа его элементов. Переменной [latex]count[/latex] обязательно присваиваем значение [latex]0[/latex], ведь именно она позднее будет отвечать за подсчет отрицательных элементов заданного массива.

С помощью цикла for задаем массив, начиная с нулевого элемента и заканчивая [latex]n[/latex]-ым элементом (не включительно!). Внутри цикла размещаем условный оператор if, который прибавляет единицу к переменной count каждый раз, когда элемент массива отрицателен. После окончания цикла важно не забыть о еще одном условном операторе, который будет выводить [latex]«NO»[/latex] и заканчивать работу программы, если значение [latex]count[/latex] равно нулю (то есть именно в том случае, если в массиве не будет ни одного отрицательного элемента). Но если в массиве всё же есть отрицательные элементы, то программа должна продолжить работу, что мы и предусматриваем, выполняя все остальные операции в рамках оператора else. Отлично! Теперь полученное значение переменной [latex]count[/latex] (если оно больше нуля) можно вывести, однако это еще не конец, ведь также необходимо вывести все отрицательные элементы в обратном порядке, так что переходим на новую строку с помощью endl и продолжаем.

Реализация подобной процедуры не так сложна, как кажется. Для этого необходимо создать еще один цикл for, перебирающий массив с конца (то есть от [latex]n-1[/latex] до [latex]0[/latex] включительно). Внутри цикла вновь создаем условный оператор if, который каждый раз выводит элемент массива (с пробелом), если он оказывается отрицательным. Не забываем закрыть скобку оператора else, ведь эта процедура также выполняется внутри условного оператора.

Готово!

Related Images:

e-olymp 8666. Коровий котильон

18/01/2020 by Нина Хоробрых

Задача

В коровьем котильоне — причудливом танце весны — участвуют коровы (обозначаются $ «\gt»$) и быки (обозначаются $ «\lt»$), они кланяются друг другу во время танца. Схематически обозначим пару кланяющихся животных следующим образом: $ «\gt \lt»$. Иногда вторая пара скота может находиться между кланяющейся парой: $ «\gt \gt \lt \lt»$.

Иногда и большее количество коров и быков встречается на танцевальной площадке: $ «\gt \gt \lt \lt \gt \lt»$ (имеется вторая пара кланяющихся коров справа). Сложные аранжировки могут быть совершенно легальными танцевальными образованиями:

Фермер Джон замечает, что бездомная корова иногда пробирается в группу и разбалансирует ее: $ «\gt \gt \lt \lt \lt \lt»$. Это строго запрещено; Фермер Джон хочет наказать нарушителей.

Фермер Джон скопировал данные о том, как $500$ коров участвуют в танцевальной линии, и задался вопросом, правильно ли уравновешена танцевальная линия (то есть весь скот может быть спарен как минимум одним способом чтобы правильно кланяться друг другу). Он скопировал только направление, в котором кланялась каждая корова, без каких-либо лишних пробелов, чтобы можно было определить, какая корова какому быку кланяется. Строки похожи на пример из предыдущего абзаца: «>><&lt». Фермер Джон хочет чтобы Вы написали программу, определяющую правильность танцевальной линии.

Фермер Джон имеет $n$ записей танца $P_{i}$ состоящих из символов $ «\gt»$ и $ «\lt»$;’ различной длины $K_{i} (1 \leqslant K_{i} \leqslant 200)$. Выведите «legal» для тех строк, которые содержат правильные пары кланяющихся коров и «illegal» иначе.

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

Первая строка содержит одно число $n$ $(1 \leqslant n \leqslant 1000)$. Каждая из следующих $n$ строк содержит число и строку из $K$ символов $ «\gt»$ и $ «\lt»$: $K_{i}$и $P_{i}$.

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

Выведите в каждой строке «legal» или «illegal» в зависимости от того, содержит ли соответствующая входная строка допустимую конфигурацию.

Тесты

№	Входные данные	Выходные данные
1	2 6 >><<>< 4 ><<>	legal illegal
2	3 8 <>><><>< 6 ><>><< 9 >><>><<><	illegal legal illegal
3	5 4 ><>< 10 >>><<>><<< 8 >><<<>>< 3 >>< 12 ><>><>>><<<<	legal legal illegal illegal legal

Код

#include <iostream>
using namespace std;

int main() {
  int n, q, count;
  char ungulate;
  bool b;
  cin >> n;
 
  for ( int i = 0; i < n; i++ ) {
    int count = 0;
    b = true;
    cin >> q;
   
    for ( int j = 0; j < q; j++ ) {
      cin >> ungulate;
      if ( ungulate == '>' ) {
        count++;
      }
      else {
        count--;
      }
      if ( count < 0 ) {
        b = false;
      }
    }
    
    if ( count != 0 ) {
        b = false;
    }
    
    if ( b ) {
        cout << "legal" << endl; 
      } 
    else {
        cout << "illegal" << endl;
      }
  }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, q, count;

char ungulate;

bool b;

cin >> n;

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

int count = 0;

b = true;

cin >> q;

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

cin >> ungulate;

if ( ungulate == '>' ) {

count++;

}

else {

count--;

}

if ( count < 0 ) {

b = false;

}

if ( count != 0 ) {

b = false;

}

if ( b ) {

cout << "legal" << endl;

}

else {

cout << "illegal" << endl;

}

return 0;

}

Решение

Пара начинается с коровы и каждой из них должен соответствовать один бык, стоящий после неё. Для того, чтобы проверить правильность танцевальной линии, будем фиксировать количество встречающихся коров, а при встрече быка это число уменьшать. Отрицательное значение показывает на наличие быка без пары. В таком случае баланса уже не будет и проверять дальше смысла нет. В случае конечного результата $0$, в линии соблюден баланс — у каждого есть своя пара.

Ссылки

Код на ideone
Задача на e-olymp
Засчитанное решение на e-olymp

Related Images:

e-olymp 8674. Игра

02/01/2020 by Александр Рапчинский

Задача

Мурад и Ибрагим играют в следующую игру. Изначально дается число $1$. На своем ходу каждый игрок должен умножить текущее число на одно из целых чисел от $2$ до $9$ включительно. Цель состоит в том, чтобы получить число не меньше заданного целого числа $n$. Игрок, получивший такой номер первым, объявляется победителем. Мурад всегда начинает первым. Выясните, кто победит, если Мурад и Ибрагим будут играть оптимально.

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

Первая строка содержит одно число $t$ $(1 \leqslant t \leqslant 2500)$ — количество тестов. Каждая из следующих $t$ строк содержит одно целое число $n$ $(2 \leqslant n \leqslant 10^9)$.

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

Для каждого теста выведите в отдельной строке $1$, если Мурад выиграет игру, и $2$ иначе.

Тесты

№	Входные данные	Выходные данные
1	4 9 10 1149729 999999999	1 2 2 1
2	3 6 163 1234567	1 2 2
3	3 42 100 1000	1 1 1

Код программы

Решение с циклом для каждого отдельного теста:

#include <iostream>
using namespace std;
 
int main() {
    int k;
    double n;
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> n;
        bool p = true;
        while (n > 1) {
            n /= (p ? 9 : 2);
            p = !p;
        }
        cout << p + 1 << "\n";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int k;

double n;

cin >> k;

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

cin >> n;

bool p = true;

while (n > 1) {

n /= (p ? 9 : 2);

p = !p;

}

cout << p + 1 << "\n";

}

return 0;

}

Решение без цикла для каждого отдельного теста:

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int t, n;
    cin >> t;
    int x = 0;
    for (int i = 0; i < t; i++) {
        cin >> n;
        double l = n / pow(18, ceil(log(n) / log(18)));
        cout << ((2 * l <= 1) ? 1 : 2) << "\n";
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int t, n;

cin >> t;

int x = 0;

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

cin >> n;

double l = n / pow(18, ceil(log(n) / log(18)));

cout << ((2 * l <= 1) ? 1 : 2) << "\n";

}

return 0;

}

Решение

Для начала заметим, что победит тот игрок, чей ход выпадет на число из промежутка $[\frac{n}{9},n)$, так как любое число из этого промежутка можно умножить на соответствующее целое число из $[2,9]$ и получить число не меньшее чем $n$. Назовем такой промежуток «зеленой зоной» (в общем виде будет $[\frac{2n}{18^k},\frac{n}{18^{k-1}})$, $k \in \mathbb {N}$). Тогда очевидно, что проиграет тот игрок, чей ход выпадает на число из промежутка $[\frac{n}{18},\frac{n}{9})$, так как при умножении числа из этого промежутка на любое целое число из $[2,9]$, приводит к тому, что получается число из «зеленой зоны». Назовем такой промежуток «красной зоной» (в общем виде будет $[\frac{n}{18^k},\frac{2n}{18^k})$, $k \in \mathbb {N}$). Получаем, что промежуток $(0,n)$ делится на «красные» и «зеленые зоны». Тогда задача сводится к нахождению вида «зоны» в которой находится $1$.

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

Рассмотрим цепочку неравенств (учитывая, что $2 \leqslant n$ ): $$\lfloor \log _{18} n \rfloor \leqslant \log _{18} n \leqslant \lceil \log _{18} n \rceil$$

$$ 18^{\lfloor \log _{18} n \rfloor} \leqslant n \leqslant 18^{\lceil \log _{18} n \rceil}$$

$$\frac{1}{18^{\lceil \log _{18} n \rceil}} \leqslant \frac{1}{n} \leqslant \frac{1}{18^{\lfloor \log _{18} n \rfloor}}$$

$$\frac{n}{18^{\lceil \log _{18} n \rceil}} \leqslant 1 \leqslant \frac{n}{18^{\lfloor \log _{18} n \rfloor}}$$

Из общего вида «красной зоны» видно, что левый ее конец это число вида $\frac{n}{18^k}$, значит $\frac{n}{18^{\lceil \log _{18} n \rceil}}$ является левым концом «красной зоны», обозначим его как $l$. Тогда, $2l$ будет правым концом «красной зоны» исходя из её общего вида. Из полученного неравенства видно, что $1$ лежит между левыми концами соседних «красных зон». Получаем, что если $2l \leqslant 1$, то единица лежит в «зеленой зоне», а иначе — в «красной».

Ссылки

Условие задачи на e-olymp

Решение с циклом для каждого отдельного теста на ideone

Решение без цикла для каждого отдельного теста на ideone

Related Images:

e-olymp 6388. Муха Фон-Неймана

22/12/2019 by Кирилл Колесник

Задача

Следующая задача была предложена Джону Фон-Нейману:

Два велосипедиста [latex]a[/latex] и [latex]b[/latex] начинают поездку навстречу друг другу в одно и то же время с мест, находящихся на расстоянии [latex]250[/latex] друг от друга, [latex]a[/latex] движется со скоростью [latex]10[/latex] миль в час, [latex]b[/latex] движется со скоростью [latex]15[/latex] миль в час. В это же время муха взлетает с колеса велосипедиста [latex]a[/latex] и движется навстречу к [latex]b[/latex], затем разворачивается и летит обратно. Пока велосипедисты приближаются друг к другу, муха продолжает летать между ними, касаясь каждый раз переднего колеса велосипедистов, пока, наконец, не будет раздавлена колесами встретившихся велосипедов. Так как муха летает быстрее каждого из велосипедистов, она совершает бесконечное количество полетов, при этом пройдя конечное расстояние (бесконечный ряд сходится). Какое расстояние пролетела муха?

Фон-Нейман немедленно вычислил бесконечный ряд (в уме!), и получил верный ответ: [latex]200[/latex] миль.

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

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

Первая строка содержит количество тестов [latex]p (1 \leqslant p \leqslant 1000)[/latex].

Каждый тест состоит из одной строки, содержащей пять чисел: номер теста [latex]n[/latex] и четыре действительных числа: начальное расстояние между велосипедистами [latex]d (10 \leqslant d \leqslant 1000)[/latex], скорость первого велосипедиста [latex]a (1 \leqslant a \leqslant 30)[/latex] в милях в час, скорость второго велосипедиста [latex]b (1 \leqslant b \leqslant 30)[/latex] в милях в час и скорость мухи [latex]f (a \leqslant b < f \leqslant 50)[/latex] в милях в час.

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

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

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 1 250 10 15 20 2 10.7 3.5 4.7 5.5 3 523.7 15.3 20.7 33.3 4 1000 30 30 50 5 500 15 15 25	1 200.00 2 7.18 3 484.42 4 833.33 5 416.67

Код программы

#include <iostream>
using namespace std;
 
int main() {
    double p, d, a, b, f, t, flyDist;
    int n;
    cin >> p;
    for (int i = 0; i < p; i++){
        cin >> n >> d >> a >> b >> f;
        t = d / (a + b);
        flyDist = f * t;
        cout.precision(2);
        cout << fixed << n << " " << flyDist << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

double p, d, a, b, f, t, flyDist;

int n;

cin >> p;

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

cin >> n >> d >> a >> b >> f;

t = d / (a + b);

flyDist = f * t;

cout.precision(2);

cout << fixed << n << " " << flyDist << endl;

}

return 0;

}

Решение задачи

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

Согласно условию, велосипедисты [latex]a[/latex] и [latex]b[/latex] двигаются навстречу друг другу, а следовательно их скорость сближения (общая скорость) будет равна сумме скоростей каждого из велосипедистов: [latex]a + b[/latex]. По знакомой из школьного курса математики формуле [latex]S = V \times t[/latex] (тогда [latex]t = \frac { S }{ V }[/latex]), разделив расстояние между велосипедистами [latex]d[/latex] на их скорость сближения, найдем время [latex]t[/latex], спустя которое велосипедисты встретятся: [latex]t = d / (a + b)[/latex]. Муха, перелетающая с одного колеса на другое со скоростью [latex]f[/latex] достигнет момента своей погибели ровно тогда же, когда встретятся велосипедисты, то есть спустя то же время [latex]t[/latex]. Тогда, умножив скорость мухи на это время, то есть [latex]f\times t[/latex], получим расстояние [latex]flyDist[/latex], преодолённое мухой.
Для корректной реализации кода задачи сначала считываем количество тестов [latex]p[/latex], затем создаём цикл, внутри которого считываем все необходимые для вышеописанных действий переменные, производим нужные вычисления и, с помощью функции cout.precision и замечания fixed, выводим номер теста и его результат с точностью до двух десятичных знаков.

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

Related Images:

e-olymp 7841. Нечетные элементы

21/12/2019 by Алексей Богач

Условие

Задана последовательность из $n$ целых чисел. Выведите все ее нечетные элементы.

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

Первая строка содержит число $n$. Следующая строка содержит $n$ ($n$ $⩽$ $100$) целых чисел, которые по модулю не превосходят $100$.

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

Вывести все нечетные элементы последовательности в том же порядке как они встречаются на входе.

Тесты

№	Входные данные	Выходные данные
1	7 14 17 16 3 7 19 9	17 3 7 19 9
2	5 2 4 3 11 5	3 11 5

Код

#include <iostream>
using namespace std;

int main() {
    int n, a;
    cin >> n;
    for (int i = 0; i < n; ++i) { 
        cin >> a;
        if (a % 2) cout << a << " ";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, a;

cin >> n;

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

cin >> a;

if (a % 2) cout << a << " ";

}

return 0;

}

Решение

Для решения задачи, проверим каждое число последовательности на четность.

Ссылки

Задача на e-olymp
Код программы на Ideone

Related Images:

e-olymp 9104. Плоская земля

15/12/2019 by Александр Розин

Условие

Система образования Вас снова подвела — Ваше предложение о включении модели «Плоская Земля» в программу старшей школы было отклонено в шестой раз подряд. Коррумпированные ученые Круглой Земли отказываются прислушиваться к Вашим аргументам и игнорируют кучу данных, подтверждающих Ваши заявления.

Настало время урегулировать этот конфликт раз и навсегда. Вы путешествовали по всему земному шару и встречались с ведущими учеными Плоской Земли. Вместе Вы разработали блестящий план.

Ради противоречия предположим, что Земля — это сфера в трехмерном пространстве. Тогда, если предположить, что небо является бесконечной плоскостью в пространстве, такая Земля явно бросит на него тень! Эта тень была бы ортогональной проекцией Земли на небо. Поскольку в действительности на небе нет видимой тени, мы достигаем противоречия.

Осталось только выполнить расчеты. По заданным центру и радиусу Земли, а также уравнению небесной плоскости в виде [latex]ax + by + cz + d = 0[/latex] необходимо определить площадь ортогональной проекции Земли на небо. Обратите внимание, что в некоторых Ваших экспериментах Земля может пересекать небо — Вы не хотели бы вводить слишком много ненужных предположений, не так ли?

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

Первая строка содержит количество тестов [latex]n[/latex] [latex]\left(1\leqslant n\leqslant 10\right)[/latex]. Далее следует описание тестов.

Каждый тест описывается строкой, содержащей восемь целых чисел [latex] x, y, z, r, a, b, c, d [/latex]. Они обозначают координаты центра Земли, его радиус и уравнение неба соответственно. Все числа от [latex]1[/latex] до [latex]1000[/latex] включительно.

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

Для каждого теста выведите одно число: площадь проекции с не менее [latex]6[/latex] десятичными цифрами.

Тесты

№	Входные данные	Выходные данные
1	1 2 3 5 7 1 2 4 8	153.938040026
2	2 2 3 5 7 1 2 4 8 4 5 3 9 2 6 8 10	153.938040026 254.469004941
3	3 2 3 5 7 1 2 4 8 4 5 3 9 2 6 8 10 23 45 87 8 100 200 65 89	153.938040026 254.469004941 201.06192983

Код программы

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

int main() {
    // your code goes here
    int n, x, y, z, r, a, b, c, d;
    cin>>n;
    for(int i=0; i<n; i++){
            cin>>x>>y>>z>>r>>a>>b>>c>>d;
            cout<<setprecision(12)<<M_PI*r*r<<endl;
    }
    return 0;
}

#include <iostream>

#include <cmath>

#include <iomanip>

using namespace std;

int main() {

// your code goes here

int n, x, y, z, r, a, b, c, d;

cin>>n;

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

cin>>x>>y>>z>>r>>a>>b>>c>>d;

cout<<setprecision(12)<<M_PI*r*r<<endl;

}

return 0;

}

Решение

Для начала, определимся, чего от нас хотят авторы задачи. По сути, самой важной частью условия является третий абзац, из которого мы узнаем, что Земля — сфера, а также, что ортогональная проекция Земли на небо — это тень от Земли на небесную плоскость. Но, если существует тень, значит существует и светило (Солнце). Для того, что бы стало более понятно, проведём эксперимент. Представим, что Земля — это, к примеру, сфера, Солнце — это настольная лампа (Важно! Лампа будет давать параллельный пучок лучей), а небесная плоскость — это обычный лист бумаги. (Важно! В данном эксперименте размеры светила и размеры «Земли» будут совпадать). При направлении света на сферу, на лист бумаги будет отбрасываться тень (площадь которой нам и надо найти). Итак, как мы видим на рисунке, площадь проекции — это ничто иное, как площадь сечения сферы, проходящее по центральной оси этой сферы. А площадь сечения сферы по центральной оси — это площадь круга, которая вычисляется по формуле [latex]S=\pi r^2[/latex]. Таким образом, что бы рассчитать площадь проекции, из всех входящих данных нам понадобится только радиус Земли. Что бы у нас было число [latex]\pi[/latex], мы подключаем библиотеку cmath. Чтобы вывести число с [latex]6[/latex] десятичными знаками после запятой, подключаем библиотеку iomanip .

Related Images:

e-olymp 1327. Ладьи на шахматной доске

14/12/2019 by Эвелина Алексютенко

Задача

Ещё в детстве маленького Гарика заинтересовал вопрос: а сколькими способами на шахматной доске размером [latex]n \times n[/latex] можно расставить [latex] n [/latex] ладей так, чтобы они не били друг друга. Он очень долго решал эту задачку для каждого варианта, а когда решил — бросил шахматы.

А как быстро Вы управитесь с этой задачкой?

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

Размер шахматной доски — натуральное число, не превышающее [latex] 1000 [/latex].

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

Выведите ответ, найденный Гариком.

Тесты

Входные данные	Выходные данные
2	2
10	3628800
500	122013682599111006870123878542304692625357434280319284219241 358838584537315388199760549644750220328186301361647714820358 416337872207817720048078520515932928547790757193933060377296 085908627042917454788242491272634430567017327076946106280231 045264421887878946575477714986349436778103764427403382736539 747138647787849543848959553753799042324106127132698432774571 554630997720278101456108118837370953101635632443298702956389 662891165897476957208792692887128178007026517450776841071962 439039432253642260523494585012991857150124870696156814162535 905669342381300885624924689156412677565448188650659384795177 536089400574523894033579847636394490531306232374906644504882 466507594673586207463792518420045936969298102226397195259719 094521782333175693458150855233282076282002340262690789834245 171200620771464097945611612762914595123722991334016955236385 094288559201872743379517301458635757082835578015873543276888 868012039988238470215146760544540766353598417443048012893831 389688163948746965881750450692636533817505547812864000000000 000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000
999	402387260077093773543702433923003985719374864210714632543799 910429938512398629020592044208486969404800479988610197196058 631666872994808558901323829669944590997424504087073759918823 627727188732519779505950995276120874975462497043601418278094 646496291056393887437886487337119181045825783647849977012476 632889835955735432513185323958463075557409114262417474349347 553428646576611667797396668820291207379143853719588249808126 867838374559731746136085379534524221586593201928090878297308 431392844403281231558611036976801357304216168747609675871348 312025478589320767169132448426236131412508780208000261683151 027341827977704784635868170164365024153691398281264810213092 761244896359928705114964975419909342221566832572080821333186 116811553615836546984046708975602900950537616475847728421889 679646244945160765353408198901385442487984959953319101723355 556602139450399736280750137837615307127761926849034352625200 015888535147331611702103968175921510907788019393178114194545 257223865541461062892187960223838971476088506276862967146674 697562911234082439208160153780889893964518263243671616762179 168909779911903754031274622289988005195444414282012187361745 992642956581746628302955570299024324153181617210465832036786 906117260158783520751516284225540265170483304226143974286933 061690897968482590125458327168226458066526769958652682272807 075781391858178889652208164348344825993266043367660176999612 831860788386150279465955131156552036093988180612138558600301 435694527224206344631797460594682573103790084024432438465657 245014402821885252470935190620929023136493273497565513958720 559654228749774011413346962715422845862377387538230483865688 976461927383814900140767310446640259899490222221765904339901 886018566526485061799702356193897017860040811889729918311021 171229845901641921068884387121855646124960798722908519296819 372388642614839657382291123125024186649353143970137428531926 649875337218940694281434118520158014123344828015051399694290 153483077644569099073152433278288269864602789864321139083506 217095002597389863554277196742822248757586765752344220207573 630569498825087968928162753848863396909959826280956121450994 871701244516461260379029309120889086942028510640182154399457 156805941872748998094254742173582401063677404595741785160829 230135358081840096996372524230560855903700624271243416909004 153690105933983835777939410970027753472000000000000000000000 000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000

Программный код

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
vector<int> multiply (const vector<int> &s, int b, int base) {
  vector<int> c;
  int carry = 0;
  for (int i = 0; i < s.size(); i++) {
    long long res = (long long)s[i] * b + carry;
    carry = res / 1000;
    c.push_back(res % base);    
  }
  if (carry > 0) { // если в разряде переноса все еще остались цифры
    c.push_back(carry);
  }
  return c;
}
int main() {
  int n;
  int base = 1000;
  cin >> n;
  vector<int> res;
  res.push_back(0);
  res.push_back(1);
  for (int i = 1; i < n; i++) {
    res = multiply(res, i + 1, base);
  }
  cout << res[res.size() - 1];
  for (int i = res.size() - 2; i >= 1; i--) {
    cout << setw(3) << setfill('0') << res[i];
  }
}

#include <iostream>

#include <vector>

#include <iomanip>

using namespace std;

vector<int> multiply (const vector<int> &s, int b, int base) {

vector<int> c;

int carry = 0;

for (int i = 0; i < s.size(); i++) {

long long res = (long long)s[i] * b + carry;

carry = res / 1000;

c.push_back(res % base);

}

if (carry > 0) { // если в разряде переноса все еще остались цифры

c.push_back(carry);

}

return c;

}

int main() {

int n;

int base = 1000;

cin >> n;

vector<int> res;

res.push_back(0);

res.push_back(1);

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

res = multiply(res, i + 1, base);

}

cout << res[res.size() - 1];

for (int i = res.size() - 2; i >= 1; i--) {

cout << setw(3) << setfill('0') << res[i];

}

#include <iostream>
#include <string>
using namespace std;

string multiplication (string x, int y) { 
    int carry = 0, temporary = 0;
    string answer = "";
    for (int i = x.size() - 1; i >= 0; i--) {
    temporary = int(x[i] - '0') * y + carry;
    carry = temporary / 10;
    answer = char(temporary % 10 + '0') + answer;
}
while (carry) {
    answer = char(carry % 10 + '0') + answer;
    carry /= 10;
}
return answer;
}
int main() {
    int n;
    string s = "1";
    cin >> n;
    for (int i = 2; i <= n; i++) {
         s = multiplication(s, i);
    } 
    cout << s << endl;
}

#include <iostream>

#include <string>

using namespace std;

string multiplication (string x, int y) {

int carry = 0, temporary = 0;

string answer = "";

for (int i = x.size() - 1; i >= 0; i--) {

temporary = int(x[i] - '0') * y + carry;

carry = temporary / 10;

answer = char(temporary % 10 + '0') + answer;

}

while (carry) {

answer = char(carry % 10 + '0') + answer;

carry /= 10;

}

return answer;

}

int main() {

int n;

string s = "1";

cin >> n;

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

s = multiplication(s, i);

}

cout << s << endl;

}

Алгоритм решения

Алгоритм решения данной задачи заключается в том, что нужно вычислить [latex]n! = 1\times 2\times 3\times \cdots\times n [/latex] , используя длинную арифметику ( умножение длинного числа на короткое ).
Иллюстрация для восьми ладей:

В коде № 1 разбиваем вектор на ячейки по три цифры. Но, некоторые ячейки могут иметь менее чем три цифры. С учетом того, что перенос может состоять не из трех цифр, следует выводить результат так: cout << setw(3) << setfill('0') << res[i];.
В коде № 2 разбиваем строку посимвольно.

Детали реализации

Безусловно, для использования векторов и строк нам понадобятся соответствующие библиотеки: #include <vector> и #include <string>.
Для вывода данных в коде № 1 стоит подключить библиотеку #include <iomanip>.

Ссылки :
Задача на e-olymp
Код № 1 на ideone
Код № 2 на ideone
Засчитанное решение № 1
Засчитанное решение № 2

Related Images:

e-olymp 6387. Острова в потоке данных

13/12/2019 by Нина Хоробрых

Задача

Задана последовательность целых чисел $a_{1}, a_{2}, a_{3}, \ldots, a_{n}$. Островом в последовательности называется набор последовательно идущих чисел, каждый из которых больше элементов, находящихся перед и после самой подпоследовательности. В приведенных ниже примерах каждый остров в последовательности обозначен внизу скобкой. Скобка острова, который находится в другом острове, находится под соответствующей скобкой.

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

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

Первая строка содержит количество тестов $p \ (1 \leqslant p \leqslant 1000)$.

Каждый тест состоит из одной строки. Она содержит номер теста $k$, за которым следует $15$ неотрицательных целых чисел, разделенных пробелом. Первое и последнее число последовательности равны $0$. Каждое число отличается от предыдущего не более чем на $1$.

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

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

Тесты

№	Входные данные	Выходные данные
1	4 1 0 0 1 1 2 2 1 1 0 1 2 2 1 1 0 2 0 1 2 3 4 3 2 1 2 3 4 3 2 1 0 3 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 4 0 1 2 3 4 5 6 7 6 5 4 3 2 1 0	1 4 2 7 3 7 4 7
2	3 1 0 1 2 3 2 1 0 1 2 3 4 3 2 1 0 2 0 0 1 2 2 2 1 1 1 0 0 1 1 0 0 3 0 1 1 1 2 2 2 2 3 4 3 2 2 1 0	1 7 2 3 3 4
3	6 1 0 1 2 2 2 3 4 5 6 5 4 3 2 1 0 2 0 1 0 0 0 0 1 1 1 0 1 2 1 1 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 1 2 3 4 5 6 7 6 5 4 3 2 1 0 5 0 1 0 1 2 1 0 1 2 2 2 1 0 0 0 6 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0	1 6 2 4 3 0 4 7 5 5 6 2

Код

#include <iostream>
using namespace std;
#define AMNT 15
 
int main() {
    int p, k;
    int current, previous; 
    cin >> p;
    while ( p--) {
        cin >> k; 
        int isl = 0; 
        cin >> current;       // ввод 1-го элемента последовательности
        previous = current;     
        for ( int j = 1; j < AMNT ; j++ ){
            cin >> current;        //ввод остальных элементов
            if ( current > previous ) { 
                isl++;
            }
            previous = current;
        }
        cout << k << " " << isl << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

#define AMNT 15

int main() {

int p, k;

int current, previous;

cin >> p;

while ( p--) {

cin >> k;

int isl = 0;

cin >> current; // ввод 1-го элемента последовательности

previous = current;

for ( int j = 1; j < AMNT ; j++ ){

cin >> current; //ввод остальных элементов

if ( current > previous ) {

isl++;

}

previous = current;

}

cout << k << " " << isl << endl;

}

return 0;

}

Решение

Для решения задачи следует выявить закономерность образования острова в последовательности. Рассмотрим подробно.
Начнем с набора наибольших чисел в последовательности. С двух сторон от него идут числа, меньшие на $1$, которые образуют между собой уже другой остров. И так пока по краям не будут нули. Соответственно, чтобы узнать количество островов в последовательности, необходимо посчитать сколько раз элемент последовательности (подпоследовательности) больше предыдущего.

Ссылки

Код на ideone
Задача на e-olymp
Засчитанное решение на e-olymp

Related Images:

e-olymp 6260. Организация соревнования

12/12/2019 by Александр Шкафер

Задача

Маленькие Дима и Петя хотят организовать соревнование. Их маленькие друзья выслали им несколько задач. Теперь Дима и Петя должны выбрать несколько задач для соревнования. Поскольку они еще маленькие, то не могут оценить качество задач, однако они знают что в хорошем контесте заглавия первой задачи начинаются с буквы $ A $ , заглавия второй задачи — с буквы $ B $ и так далее.

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

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

Первая строка содержит одно число $ n $ — количество предложенных задач, полученных маленькими братьями [latex](1 \leqslant n \leqslant 100)[/latex]

Следующие $ n $ строк содержат заглавия предложенных задач, по одной в строке. Длина каждого заглавия не превосходит $ 30 $ символов. Каждое заглавие начинается с заглавной буквы и содержит буквы только латинского алфавита, цифры и символы подчеркивания.

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

Вывести одно число — наибольшее возможное количество задач в хорошем соревновании. Если хорошего соревнования устроить нельзя, вывести $0$.

Тесты

№	Входные данные	Выходные данные
1.	10 Use Algorithm_of Branch Chill Cout_Hello_World General Duck Ping_pong Pong_ping End	5
2.	4 Spasibo_tebe John_von_Neumann Za Nuli_i_edunichki	0
3.	6 All Sample Simple Games_of_mind Google Bee	2
4.	7 Andreev_Borys Borys_Andreev C_P_P Demo_version E_Olymp Fraction General	7

Код

#include <iostream>
using namespace std;
 
int m[26];
 
int main() {
    int n;
    cin >> n;
    string s;
    for (int j = 0; j <= n; j++) {
        getline(cin, s);
        m[int(s[0] - 'A')]++; // от первой буквы названий задач отнимаем А, чтобы получить её номер в алфавите
    }
    int k = 0;
    for (int i = 0; i < 26; i++) { 
        if (m[i] != 0) k++;
        if (m[i] == 0) break;
    }
    cout << k;
    return 0;
}

#include <iostream>

using namespace std;

int m[26];

int main() {

int n;

cin >> n;

string s;

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

getline(cin, s);

m[int(s[0] - 'A')]++; // от первой буквы названий задач отнимаем А, чтобы получить её номер в алфавите

}

int k = 0;

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

if (m[i] != 0) k++;

if (m[i] == 0) break;

}

cout << k;

return 0;

}

Объяснение

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

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

Создаем массив.
Читаем строку циклом и определяем первую букву.
Кладем первую букву в массив, если разница отлична от нуля.

Ссылки

Задача на e-olymp
Код на ideone

Related Images:

e-olymp 124. Квадрат

08/12/2019 by Олег Сторожев

Условие задачи

Найдите периметр и площадь квадрата.

Входные данные:
Каждая строка является отдельным тестом и содержит одно целое число — длину стороны квадрата $n$ (1 $\leqslant$ $n$ $\leqslant$ 1000).

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

Тесты

№	Входные данные	Выходные данные
1	3 5 10	12 9 20 25 40 100
2	3 3 3	12 9 12 9 12 9
3	1000 1 500	4000 1000000 4 1 2000 250000

Код

#include <iostream>
using namespace std;
int main() {
    int n,P,S;
    while (cin >> n) {
        P = 4*n; // считаем периметр квадрата
        S = n*n; // считаем площадь квадрата
        cout << P << " " << S << "\n";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n,P,S;

while (cin >> n) {

P = 4*n; // считаем периметр квадрата

S = n*n; // считаем площадь квадрата

cout << P << " " << S << "\n";

}

return 0;

}

Решение

У нас дана сторона квадрата $n$.

Находим периметр квадрата, используя формулу $P = 4n$.
Находим площадь квадрата, используя формулу $S = n^{2}$.
Так как каждая новая строка — новое значение для стороны квадрата и таких строк неизвестное количество то используем while (cin >> n) для потоковой обработки данных.

Ссылки

Задача на сайте e-olymp
код решения Ideone

Related Images:

e-olymp 566. Письмо почтальона Печкина

05/12/2019 by Артем Рогулин

Задача

Дорогие ребята!
Наблюдая за тем, как Шарик распиливал нестандартную шахматную доску, я также решил задать для вас задачку: “А сколько разных квадратных и прямоугольных (не считая квадратных) досок мог бы получить при распиливании Шарик из найденной им нестандартной прямоугольной шахматной доски размером $M\times N$?”

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

В первой строке количество заданий Печкина $K$, в последующих $K$ строках по два целых числа $M$ и $N$ $(1 \leqslant K, M, N \leqslant 100)$, разделённых пробелом.

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

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

Тесты

№	Входные данные	Выходные данные
1.	1 3 2	8 10
2.	2 4 4 2 2	30 70 5 4
3.	4 3 3 25 46 100 100 1 1	14 22 12350 338975 338350 25164150 1 0

Код программы

#include <iostream>
using namespace std;

int main() {
    int k; // Количество заданий
    cin >> k;
    for(int l = 0; l < k; l++)
    {
        int m, n; // Размер шахматной доски
        cin >> m >> n;
        int res = 0; // Количество кусков, на которые мы можем разделить доску
        for(int i = min(m, n); i >= 0; i--) // Находим количество квадратов
        {
            res += (m - i) * (n - i);
        }
        cout << res; // Вывод количества квадратных досок
        res = res * - 1; // Чтобы не учитывать квадратные доски, сразу вычитаем их
        for(int i = m - 1; i >= 0; i--) // Находим количество прямоугольников
        {
            for(int j = n - 1; j >= 0; j--) 
            {
                res += (m - i) * (n - j);
            }
        }
        cout << ' ' << res << endl; // Вывод количества прямоугольников
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int k; // Количество заданий

cin >> k;

for(int l = 0; l < k; l++)

{

int m, n; // Размер шахматной доски

cin >> m >> n;

int res = 0; // Количество кусков, на которые мы можем разделить доску

for(int i = min(m, n); i >= 0; i--) // Находим количество квадратов

{

res += (m - i) * (n - i);

}

cout << res; // Вывод количества квадратных досок

res = res * - 1; // Чтобы не учитывать квадратные доски, сразу вычитаем их

for(int i = m - 1; i >= 0; i--) // Находим количество прямоугольников

{

for(int j = n - 1; j >= 0; j--)

{

res += (m - i) * (n - j);

}

cout << ' ' << res << endl; // Вывод количества прямоугольников

}

return 0;

}

Объяснение

Ответом на каждый запрос будет количество квадратов и прямоугольников которые можно получить из нашей шахматной доски размера $M\times N$. Для вычисления количества квадратов нам надо посчитать, сколько квадратов каждого возможного размера поместится в нашей шахматной доске. Аналогично для прямоугольников. Пример с доской $3\times 2$ разобран на картинке.

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

Для подсчёта квадратов, нам следует отдельно считать их количество для каждого возможного размера. Таким образом сначала идут квадраты $1\times 1$, то есть $M\cdot N$ квадратов. Далее, квадратов $2\times 2$ помещаются ровно на $1$ меньше горизонтально и на $1$ меньше вертикально, значит получаем $(M-1)\times (N-1)$. Соответственно, $(M — 2)\times (N — 2)$ для квадратов $3\times 3$. И так продолжаем пока квадрат помещается в нашу доску.

Аналогично мы поступаем и с прямоугольниками. Однако считая количество прямоугольников каждого размера, нам нужно считать сколько поместится прямоугольников размера $(1\times 1), (1\times 2)\dots (1\times N)$. Также $(2\times 1), (2\times 2)\dots (2\times N)$. И так до $(M\times 1), (M\times 2)\dots (M\times N)$. Это довольно просто реализовать используя вложенный цикл.

Не стоит забывать, что квадрат — тот же прямоугольник, но с равными сторонами и в нашем цикле мы считаем все прямоугольники. А так как квадраты мы не должны учитывать, то после нахождения числа прямоугольников, нам нужно вычесть из него количество квадратов. В коде после нахождения и вывода числа квадратов, мы домножили это число на $(-1)$ и и уже после прибавили к нему количество прямоугольников, таким образом не учитывая квадраты.

Ссылки

Условие на e-olymp.

Код на ideone.

Related Images:

e-olymp 4142. Большой XOR

03/12/2019 by Никита Репнин

Задача

Для заданного целого $x$ найти количество таких $a$, удовлетворяющих условию:

$ a $ xor $x > x $
$ 0 < a < x $

где $a$ и $x$ — целые, xor — битовый XOR оператор.

Имеются $q$ запросов, каждый из которых содержит целое число $x$. Для каждого запроса выведите общее количество значений $a$, удовлетворяющих условиям выше.

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

Первая строка содержит число запросов $q$ $(1 \leqslant q \leqslant 10^5)$. Каждая из следующих $q$ строк содержит значение $x$ $(1 \leqslant x \leqslant 10^{10})$.

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

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

Тесты

№	Входные данные	Выходные данные
1	2 2 10	1 5
2	3 13 3 16	2 0 15
3	5 1 7 4294967295 42 451	0 0 0 21 60

Код

#include <iostream>
using namespace std;
int main() {
    long q, x, res, two; 
    cin >> q;
    for(long i = 0; i < q; ++ i){
        cin >> x;
        res = 0;
        two = 1; // two = 2^0
        while(x > 0){
            if(x % 2 == 0) // проверяем равен ли бит нулю
                res += two;
            x >>= 1;  // двигаемся к следующему биту
            two <<= 1; // увеличиваем степень двойки
        }
        cout << res << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long q, x, res, two;

cin >> q;

for(long i = 0; i < q; ++ i){

cin >> x;

res = 0;

two = 1; // two = 2^0

while(x > 0){

if(x % 2 == 0) // проверяем равен ли бит нулю

res += two;

x >>= 1; // двигаемся к следующему биту

two <<= 1; // увеличиваем степень двойки

}

cout << res << endl;

}

return 0;

}

Решение

XOR выдаёт число, биты которого равны $1$, когда лишь у одного из чисел соответствующий бит равен $1$. Числа большие чем $x$ получаем лишь тогда, когда $2^{k}\leqslant a<2^{k+1}$, где $k$- номер бита числа $x$, который равен нулю. Таких $a$ существует $2^k$ штук для каждого такого бита.

Задача на e-olymp

Код программы на ideone

Засчитанное решение

Related Images:

e-olymp 6261. Устройство для анализа бюллетеня

30/11/2019 by Евгений Фищук

Задача

Избирательная комиссия Флатландии готовится к президентским выборам. Чтобы свести к минимуму человеческий фактор при подсчете голосов, они решили разработать автоматическое устройство для анализа бюллетеней (УАБ).

На пост президента баллотируются $n$ кандидатов. Бюллетень содержит одно квадратное поле для каждого кандидата. Избиратель должен отметить ровно одно из полей. Если поле не помечено или имеется два или более отмеченных поля, бюллетень недействителен. Каждый избиратель ставит свой бюллетень на специальный сканер в УАБ. Сканер анализирует отметки в бюллетене и создает специальную строку голосования из $n$ символов: ‘X’ для отмеченного поля и ‘.’ для немаркированного. Теперь строки голосования должны быть проанализированы, чтобы получить отчет. Ваша задача — разработать генератор отчетов для УАБ.

С учетом строк голосования для всех бюллетеней Ваша программа должна распечатать отчет о голосовании. Кандидаты в протоколе должны быть расположены в порядке убывания количества голосов. Если два кандидата имеют одинаковое количество голосов, они должны иметь тот же порядок, что и в бюллетене для голосования. Для каждого кандидата рассчитайте его / ее результат в процентах (если кандидат получил p голосов, результат в процентах составляет $ \frac{100p}{m}$ ). В последней строке отчета должен быть указан процент недействительных бюллетеней.

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

Первая строка содержит два целых числа $n$ и $m (2 \leqslant n \leqslant 10, 1 \leqslant m \leqslant 1000$) — количество кандидатов и количество бюллетеней. Следующие $n$ строк содержат фамилии кандидатов. Каждое имя представляет собой строку не более 100 английских букв. Нет ни одного кандидата с именем «Invalid».

Затем следуют $m$ строк, каждая из которых содержит одну строку голосования.

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

Выведите $n+1$ строк. Сначала выведите результаты для кандидатов в процентах. Для каждого кандидата выведите его / ее фамилию, затем пробел, а затем его / ее результат в процентах и знак процента ‘%‘. В последней строке должен быть указан процент недействительных бюллетеней: слово «Invalid», за которым следуют пробел, процент недействительных бюллетеней и знак процента.

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

Тесты

№	Входные данные	Выходные данные
1	4 7 Loudy Apples Dogman Miller .X.. X… …. ..X. ..XX ..X. ..X.	Dogman 42.86% Loudy 14.29% Apples 14.29% Miller 0.00% Invalid 28.57%
2	4 10 Loudy Apples Dogman Miller X……………….. X………………….. X……………… X…………………. X………….. x……………………….. X………………. X…………… X..x xxxx	Loudy 70.00% Apples 0.00% Dogman 0.00% Miller 0.00% Invalid 30.00%

Код программы

#include <iostream>
#include <string>
#include <iomanip>
#include <algorithm>
using namespace std;

struct candidates {
    string name;
    double numb;
};

bool c(candidates x, candidates y)
{
    return x.numb > y.numb;
}

int main() {
    int candidateNum, ballotNum;
    cin >> candidateNum >> ballotNum;
    candidates* candidate = new candidates[candidateNum+1];
    string s = "";
    for (int i = 0; i < candidateNum; i++)
    {
        cin >> s;
        candidate[i].name = s;
        candidate[i].numb = 0;
    }
    candidate[candidateNum].name = "Invalid";
    candidate[candidateNum].numb = 0;
    int count = 0, num;
    for (int i = 0; i < ballotNum; i++)
    {
        cin >> s;
        count = 0;
        for (int j = 0; j < candidateNum; j++)
        {
            if (s[j] == 'X')
            {
                count++;
                num = j;
            }
            if (isalpha(s[j]) && s[j] != 'X')
                count=2;
        }
        if (count == 1)
        {
            candidate[num].numb++;
        }
        else
            candidate[candidateNum].numb++;

    }
    sort(candidate, candidate + candidateNum,c);
    for (int i = 0; i <= candidateNum; i++)
    {
        cout << fixed << setprecision(2) << candidate[i].name << " " << candidate[i].numb*100/ballotNum << "%\n";
    }
    return 0;
}

#include <iostream>

#include <string>

#include <iomanip>

#include <algorithm>

using namespace std;

struct candidates {

string name;

double numb;

};

bool c(candidates x, candidates y)

{

return x.numb > y.numb;

}

int main() {

int candidateNum, ballotNum;

cin >> candidateNum >> ballotNum;

candidates* candidate = new candidates[candidateNum+1];

string s = "";

for (int i = 0; i < candidateNum; i++)

{

cin >> s;

candidate[i].name = s;

candidate[i].numb = 0;

}

candidate[candidateNum].name = "Invalid";

candidate[candidateNum].numb = 0;

int count = 0, num;

for (int i = 0; i < ballotNum; i++)

{

cin >> s;

count = 0;

for (int j = 0; j < candidateNum; j++)

{

if (s[j] == 'X')

{

count++;

num = j;

}

if (isalpha(s[j]) && s[j] != 'X')

count=2;

}

if (count == 1)

{

candidate[num].numb++;

}

else

candidate[candidateNum].numb++;

}

sort(candidate, candidate + candidateNum,c);

for (int i = 0; i <= candidateNum; i++)

{

cout << fixed << setprecision(2) << candidate[i].name << " " << candidate[i].numb*100/ballotNum << "%\n";

}

return 0;

}

Решение

Чтобы решить задачу создадим структуру с именами и результатами кандидатов. Сначала создадим массив кандидатов и заполним его. По вводу бюллетеней будем проверять не испорчены ли они. Если кроме «X» есть любой другой символ, или буква, или еще символы «X», то бюллетень испорчен, в остальных случаях он не испорчен. Если он не испорчен, добавляем к результату кандидата единицу, если нет — добавляем к счетчику испорченых бюллетеней единицу. Выводим в процентном соотношении с количеством бюллетеней результат каждого кандидата и количество испорченых бюллетеней.

Ссылки

Условие задачи на e-olymp

Код программы на ideone

Related Images:

e-olymp 972. Сортировка времени

26/06/2019 by Максим Евчук

Задача

Отсортируйте время согласно заданному критерию

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

Сначала задано число $n\, \left ( 1\leqslant n\leqslant 100 \right )$, а затем n моментов времени. Каждый момент времени задается 3 целыми числами — часы (от 0 до 23), минуты (от 0 до 60) и секунды (от 0 до 60)

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

Выведите моменты времени, упорядоченные в порядке неубывания (момент времени также выводится в виде трех чисел, ведущие нули выводить не нужно)

Тесты

№	Входные данные	Выходные данные
1	[latex]\begin{matrix} 4 & & \\ 10 &20 &30 \\ 7 &30 &00 \\ 23&59 &59 \\ 13&30 &30 \end{matrix}[/latex]	[latex]\begin{matrix} 7 & 30 &00 \\ 10&20 &30 \\ 13&30 &30 \\ 23& 59 & 59 \end{matrix}[/latex]
2	$\begin{matrix} 6\\ 12 &55 &59 \\ 8 &33 &34 \\ 6 &56 &46 \\ 10 &23 &52 \\ 3 &20 &00 \\ 19 &31 &0\\ 10&23&52 \end{matrix}$	$\begin{matrix} 3 &20 &0 \\ 6 &56 &46 \\ 8 &33 &34 \\ 10 &23 &52 \\ 12 &55 &59 \\ 19 &31 &0 \end{matrix}$

#include <iostream>

#include <algorithm>

using namespace std;
int main() {
  int hours[100];
  int mins[100];
  int secs[100];
  int all_time[100];
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> hours[i] >> mins[i] >> secs[i];
    all_time[i] = hours[i] * 3600 + mins[i] * 60 + secs[i];
  }
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (all_time[i] > all_time[j]) {
        swap(hours[i], hours[j]); swap(mins[i], mins[j]);
        swap(secs[i], secs[j]); swap(all_time[i], all_time[j]);
      }
    }
  }
  for (int i = 0; i < n; i++) cout << hours[i] << " " << mins[i] << " " << secs[i] << endl;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int hours[100];

int mins[100];

int secs[100];

int all_time[100];

int n;

cin >> n;

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

cin >> hours[i] >> mins[i] >> secs[i];

all_time[i] = hours[i] * 3600 + mins[i] * 60 + secs[i];

}

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

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

if (all_time[i] > all_time[j]) {

swap(hours[i], hours[j]); swap(mins[i], mins[j]);

swap(secs[i], secs[j]); swap(all_time[i], all_time[j]);

}

for (int i = 0; i < n; i++) cout << hours[i] << " " << mins[i] << " " << secs[i] << endl;

}

Решение

Создадим 4 массива где мы будем хранить время(отдельно часы, минуты, секунды), а также четвертый в котором мы будем хранить все время в одной удобной для нас единице измерения — секундах. Читаем поток ввода и переводим полученные данные, сравниваем их потом сортируем полученные результаты и выводим ответ.

Ссылки

e-olymp
ideone