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 7254. Отрезки

13/03/2021 by Євген Константинов

Задача

Петя очень любит игрушки в форме геометрических фигур. Недавно он заметил, что среди его игрушек нет ни одного треугольника. Это очень огорчило Петю, поэтому он отправился в ближайший магазин с целью покупки новенького треугольника. В магазине Пете сказали, что все треугольники уже давно раскупили, но в наличии есть [latex]N[/latex] прямых отрезков.

Отрезки пронумерованы последовательными натуральными числами, начиная с единицы. Отрезок номер [latex]i[/latex] характеризуется двумя числами — длиной [latex]L_i[/latex] и ценой [latex]C_i[/latex]. Петя очень умный, поэтому знает, что желаемый треугольник он может сложить из трех отрезков. Более того, наш герой знает, что треугольник возможно сложить только из таких трех отрезков, среди которых длина любого отрезка строго меньше суммарной длины двух других. Итак, мальчик решил купить ровно три таких отрезка. Разумеется, он хочет сэкономить как можно больше денег на мороженое, поэтому стремится потратить как можно меньше денег на покупку треугольника.

Задание

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

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

В первой строке входного файла записано единственное число [latex]N[/latex] — количество отрезков. В следующих [latex]N[/latex] строках записана информация о самих отрезках. Каждая такая строка содержит соответствующие [latex]L_i[/latex] [latex](1 \leqslant L_i \leqslant 10^9)[/latex] и [latex]C_i[/latex]. Цены образуют перестановку чисел от [latex]1[/latex] до [latex]N[/latex], то есть являются попарно различными натуральными числами, не превосходящими [latex]N[/latex].

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

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

Тесты

№	Входные данные	Выходные данные
1	4 1 1 2 2 3 3 4 4	9

Код

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

//Структура для представления одного отрезка
struct Line {
    int price;
    int length;
};

//Функция сортировщик по цене в порядке возрастания
bool comparator_price (Line i, Line j) { 
    return i.price < j.price;
}

int main() {
    int n, price, length, cheapest = INT_MAX;
    cin >> n;
    Line lines_by_price[n];
    
    for (int i = 0; i < n; i++) {
        Line l;
        cin >> length >> price;
        l.price = price;
        l.length = length;
        lines_by_price[i] = l;
    }
    
    //Сортируем все отрезки по цене, чтобы была возможность "отсечь"
    //слишком дорогие отрезки, когда цена одного(или двух) будет 
    //больше текущей минимальной
    sort(&lines_by_price[0], &lines_by_price[n], comparator_price);
    
    for (int i = 0; i < n; i++) {
        Line first_side = lines_by_price[i];
        if (first_side.price > cheapest) break;
        vector<Line> sides = {};
        //Перебираем все возможные тройки отрезков, отсекая
        //слишком дорогие, основываясь на сортировке по цене
        //и текущей минимальной цене
        for (int j = 0; j < n; j++) {
            if (lines_by_price[j].price != first_side.price && lines_by_price[j].length <= first_side.length) {
                sides.push_back(lines_by_price[j]);
                Line second_side = lines_by_price[j];
                if (first_side.price + second_side.price > cheapest) break;
                for (auto third_side: sides) {
                    if ((third_side.length != second_side.length && third_side.price != second_side.price) 
                    && first_side.length < second_side.length + third_side.length 
                    && second_side.length < first_side.length + third_side.length 
                    && third_side.length < second_side.length + first_side.length) {
                        if (first_side.price + second_side.price + third_side.price < cheapest) {
                            cheapest = first_side.price + second_side.price + third_side.price;
                        }
                        break;
                    }
                }
            }
        }
    }
    //Если ни одна тройка отрезков не подошла, значит составить
    //треугольник невозможно - выводим "-1"
    if (cheapest == INT_MAX) cheapest = -1;
    cout << cheapest;
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

#include <climits>

using namespace std;

//Структура для представления одного отрезка

struct Line {

int price;

int length;

};

//Функция сортировщик по цене в порядке возрастания

bool comparator_price (Line i, Line j) {

return i.price < j.price;

}

int main() {

int n, price, length, cheapest = INT_MAX;

cin >> n;

Line lines_by_price[n];

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

Line l;

cin >> length >> price;

l.price = price;

l.length = length;

lines_by_price[i] = l;

}

//Сортируем все отрезки по цене, чтобы была возможность "отсечь"

//слишком дорогие отрезки, когда цена одного(или двух) будет

//больше текущей минимальной

sort(&lines_by_price[0], &lines_by_price[n], comparator_price);

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

Line first_side = lines_by_price[i];

if (first_side.price > cheapest) break;

vector<Line> sides = {};

//Перебираем все возможные тройки отрезков, отсекая

//слишком дорогие, основываясь на сортировке по цене

//и текущей минимальной цене

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

if (lines_by_price[j].price != first_side.price && lines_by_price[j].length <= first_side.length) {

sides.push_back(lines_by_price[j]);

Line second_side = lines_by_price[j];

if (first_side.price + second_side.price > cheapest) break;

for (auto third_side: sides) {

if ((third_side.length != second_side.length && third_side.price != second_side.price)

&& first_side.length < second_side.length + third_side.length

&& second_side.length < first_side.length + third_side.length

&& third_side.length < second_side.length + first_side.length) {

if (first_side.price + second_side.price + third_side.price < cheapest) {

cheapest = first_side.price + second_side.price + third_side.price;

}

break;

}

//Если ни одна тройка отрезков не подошла, значит составить

//треугольник невозможно - выводим "-1"

if (cheapest == INT_MAX) cheapest = -1;

cout << cheapest;

return 0;

}

Решение

Для начала запишем все отрезки в массив в виде структур. Отсортируем их по цене в порядке возрастания, чтобы позже иметь возможность «отсекать» слишком дорогие отрезки. Далее мы начинаем перебирать все возможные тройки отрезков. На первом уровне цикла ставим условный оператор. Если на [latex]n[/latex]-ой итерации цикла будет отрезок с ценой больше текущей наименьшей цены треугольника, то мы можем выходить из массива и выводить текущую минимальную стоимость, т.к. все последующие отрезки будут дороже (пользуемся сортировкой и тем, что цены отрезков образуют перестановку от [latex]1[/latex] до [latex]N[/latex]). Далее на втором и третьем уровнях цикла мы также перебираем все отрезки от дешевых к дорогим и при обнаружении тройки отрезков, цена которых меньше текущей минимальной, записываем их в переменную [latex]cheapest[/latex]. При этом на втором уровне цикла проверяем, не больше ли сумма цен двух отрезков текущей минимальной, чтобы не проверять лишние тройки.

Ссылки

Related Images:

e-olymp 4720. Новая игра Серёжи

22/12/2020 by Кулік Віталій

Задача

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

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

Помогите Серёже понять, расстроится он или нет.

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

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

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

Программа должна выводить слово «SAD», если Серёжа расстроится (когда точка попадает на границу Серёжа считает её принадлежащей чёрному листу, потому что не любит расстраиваться), и «HAPPY» — в обратном случае.

Тесты

№	Входные данные	Выходные данные
1	2 10 5 3 4 4 6 1 2 9	HAPPY
2	2 10 5 3 4 4 6 1 6 3	SAD
3	0 0 0 0 1 1 1 1 0 0	HAPPY
4	1 3 3 1 2 3 4 1 3 2	SAD
5	1 3 3 1 2 3 4 1 2 2	HAPPY

Код

#include <iostream>
using namespace std;

struct dot
{
    int x, y;
    dot(){
        cin >> x >> y;
    }
};
struct square
{
    dot upper_left, lower_right;
    bool is_point_on(dot &p) const
    {
        return p.x < lower_right.x and p.x > upper_left.x and p.y < upper_left.y and p.y > lower_right.y;
    }
    bool is_point_in(dot &p) const
    {
        return p.x <= lower_right.x and p.x >= upper_left.x and p.y <= upper_left.y and p.y >= lower_right.y;
    }
};

int main() {
    square black, white;
    dot point;
    cout << ((black.is_point_in(point) and not white.is_point_on(point))?"HAPPY":"SAD");
}

#include <iostream>

using namespace std;

struct dot

{

int x, y;

dot(){

cin >> x >> y;

}

};

struct square

{

dot upper_left, lower_right;

bool is_point_on(dot &p) const

{

return p.x < lower_right.x and p.x > upper_left.x and p.y < upper_left.y and p.y > lower_right.y;

}

bool is_point_in(dot &p) const

{

return p.x <= lower_right.x and p.x >= upper_left.x and p.y <= upper_left.y and p.y >= lower_right.y;

}

};

int main() {

square black, white;

dot point;

cout << ((black.is_point_in(point) and not white.is_point_on(point))?"HAPPY":"SAD");

}

Сокращенный код

#include <iostream>
using namespace std;

int main() {
    int bl_up_x, bl_up_y, bl_dw_x, bl_dw_y;
    int wh_up_x, wh_up_y, wh_dw_x, wh_dw_y;
    int p_x, p_y;
    cin >> bl_up_x >> bl_up_y >> bl_dw_x >> bl_dw_y;
    cin >> wh_up_x >> wh_up_y >> wh_dw_x >> wh_dw_y;
    cin >> p_x >> p_y;
    bool is_in_black = p_x <= bl_dw_x and p_x >= bl_up_x and p_y <= bl_up_y and p_y >= bl_dw_y;
    bool is_in_white = p_x < wh_dw_x and p_x > wh_up_x and p_y < wh_up_y and p_y > wh_dw_y;
    cout << (is_in_black and not is_in_white ? "HAPPY" : "SAD");
}

#include <iostream>

using namespace std;

int main() {

int bl_up_x, bl_up_y, bl_dw_x, bl_dw_y;

int wh_up_x, wh_up_y, wh_dw_x, wh_dw_y;

int p_x, p_y;

cin >> bl_up_x >> bl_up_y >> bl_dw_x >> bl_dw_y;

cin >> wh_up_x >> wh_up_y >> wh_dw_x >> wh_dw_y;

cin >> p_x >> p_y;

bool is_in_black = p_x <= bl_dw_x and p_x >= bl_up_x and p_y <= bl_up_y and p_y >= bl_dw_y;

bool is_in_white = p_x < wh_dw_x and p_x > wh_up_x and p_y < wh_up_y and p_y > wh_dw_y;

cout << (is_in_black and not is_in_white ? "HAPPY" : "SAD");

}

Решение

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

Ссылки

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

Related Images:

e-olymp 75. Пираты и монеты

24/12/2018 by Даниил Мозгунов

Задача

[latex]n[/latex] пиратам удалось справедливо разделить клад из [latex]m[/latex] золотых монет — каждый получил свою часть согласно своему пиратскому рангу и стажу. Самый молодой пират взял [latex]a[/latex] монет, а каждый следующий пират брал на одну монету больше, чем предыдущий его коллега. Последним был капитан, которому досталось вдвое больше от запланированного, очевидно, что после него монет больше не осталось.

Сколько было пиратов вместе с капитаном, если известны [latex]a[/latex] и [latex]m[/latex]. Так как капитан без команды просто пират, то [latex]n > 1[/latex].

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

Два натуральных числа [latex]a[/latex] и [latex]m[/latex] ([latex]1 \leq a \leq 100, m < 15150[/latex]). Входные данные корректны.

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

Количество пиратов [latex]n[/latex].

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 25	3
2	3 24	4
3	4 38	5
4	5 55	6
5	6 75	7

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

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
    double a, m, n, b, c, d;
    cin>>a>>m; 
    b = 2 * a + 1;
    c = 2 * a - 2 - 2 * m;
    d = b * b - 4 * c;
    n = ( -b + sqrt(d) ) / 2;
    cout<<n;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double a, m, n, b, c, d;

cin>>a>>m;

b = 2 * a + 1;

c = 2 * a - 2 - 2 * m;

d = b * b - 4 * c;

n = ( -b + sqrt(d) ) / 2;

cout<<n;

return 0;

}

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

Для решения задачи воспользуемся формулой арифметической прогрессии, которая в данном случае равна: [latex](2a + n — 1)\frac{n}{2} + a + n — 1[/latex]. Отсюда получаем квадратное уравнение : [latex]\frac{n^{2}}{2} + n(a + \frac{1}{2}) + a — 1 = m[/latex], упростим и получим: [latex]n^{2} + 2an + n + 2a — 2 = 2m[/latex]. В коде задаем чему равно [latex]b[/latex], [latex]c[/latex] и [latex]d[/latex]. Где [latex]b[/latex] и [latex]c[/latex] — коэффициенты квадратного уравнения, а [latex]d[/latex] — дискриминант квадратного уравнения, который вычисляем по формуле: [latex]b^{2} — 4c[/latex]. Они нужны для нахождения корня данного квадратного уравнения. При этом ответом на задачу будет только один корень квадратного уравнения, так как количество пиратов не может принимать отрицательное значение. Поэтому вычисляем корень квадратного уравнения по формуле: [latex]\frac{-b + \sqrt{b}}{2}[/latex], тем самым получаем ответ на нашу задачу.

Код программы (с циклом)

#include <iostream>
using namespace std;

int main() {
    unsigned int a, m, n = 0;
    cin>>a>>m;
    while (m - 2 * a != 0){
            m -= a;
            a ++;
            n ++;
    }
    cout<<n + 1;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned int a, m, n = 0;

cin>>a>>m;

while (m - 2 * a != 0){

m -= a;

a ++;

n ++;

}

cout<<n + 1;

return 0;

}

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

В данном способе используем цикл. Как он работает: в условии цикла задаем проверку, когда наступит очередь капитана и будет выполнятся равенство вида [latex]m — 2a = 0[/latex] цикл прекратит свою работу. Пока это равенство не будет выполнятся цикл будет выполнять работу арифметической прогрессии, постоянно увеличивая количество монет [latex]a[/latex] на каждого пирата при этом, вычитая каждый раз из общего клада [latex]m[/latex], также, пока не выполняется данное равенство, считаем количество пиратов [latex]n[/latex], путем прибавления [latex]n + 1[/latex], пока работает цикл. И когда цикл прекращает свою работу, в конце учитываем капитана и к полученному количеству пиратов [latex]n[/latex] прибавляем [latex]n + 1[/latex]. И получаем ответ на нашу задачу.

Код программы (с условным оператором)

#include <iostream>
using namespace std;
 
int f(int a, int m, int n = 0) {
    if (m - 2*a == 0) {
        return n + 1;
    }
    else {
        return f(a + 1, m - a, n + 1);
    }
}
 
int main() {
    int a, m;
    cin >> a >> m;
    cout << f(a, m);
    return 0;
}

#include <iostream>

using namespace std;

int f(int a, int m, int n = 0) {

if (m - 2*a == 0) {

return n + 1;

}

else {

return f(a + 1, m - a, n + 1);

}

int main() {

int a, m;

cin >> a >> m;

cout << f(a, m);

return 0;

}

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

В данном способе воспользуемся рекурсивной функцией и условными операторами. Как это работает: внутри рекурсивной функции расписываем условные операторы, которые определяют равенством [latex]m — 2a = 0[/latex] — когда наступила очередь капитана, а пока это условие не выполняется, функция будет вызывать сама себя пока это условие не удовлетворится, функция каждый раз вызывается с новыми параметрами соответственно. Где [latex]a[/latex] — количество монет даваемое пиратам, увеличивается по рангу каждого пирата, [latex]m[/latex] — клад, от него отнимаем текущее [latex]a[/latex], и [latex]n[/latex] — количество пиратов, считаем пиратов. И в конце выводит количество пиратов. Задача решена.

Ссылки

Related Images:

e-olymp 1312. Шкаф

04/12/2018 by Николь Метри

Задача

Размеры шкафа [latex] a \times b \times c [/latex]. Возможно ли его пронести через дверной проём с размерами [latex]x \times y[/latex]? Считается, что шкаф проходит в проем, если размеры, которыми его будут вносить сквозь дверь, не больше соответствующих размеров двери.

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

Целые числа [latex] a, b, c, x, y (1 ≤ a, b, c, x, y ≤ 100)[/latex].

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

Вывести строку «YES«, если шкаф пронести возможно, и «NO» если нельзя.

Тесты

№	Ввод	Вывод
1	4 5 6 10 20	YES
2	4 5 6 3 4	NO
3	12 3 4 5 6	YES
4	12 3 6 5 6	YES
5	12 3 7 5 6	NO

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

#include <iostream>
using namespace std;

int main() {
    int a, b, c, y, x;
    std::cin >> a >> b >> c >> y >> x;
    if ((a<=y && b<=x) || (a<=x && b<=y) || (a<=y && c<=x) || (a<=x && c<=y) ||
        (b<=y && c<=x) || (b<=x && c<=y)) cout << "YES";
    else cout << "NO";
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b, c, y, x;

std::cin >> a >> b >> c >> y >> x;

if ((a<=y && b<=x) || (a<=x && b<=y) || (a<=y && c<=x) || (a<=x && c<=y) ||

(b<=y && c<=x) || (b<=x && c<=y)) cout << "YES";

else cout << "NO";

return 0;

}

Либо

#include <iostream>

using namespace std; 

bool skf(int q, int w, int e, int r){
    return ((q<=e && w<=r) || (q<=r && w<=e));
}

int main(){
    int a, b, c, x, y;
    cin >> a >> b >> c >> x >> y;
    if (skf(a, b, x, y) || skf(b, c, x, y) || skf(a, c, x, y)) cout << "YES";
    else cout << "NO";
return 0;

}

#include <iostream>

using namespace std;

bool skf(int q, int w, int e, int r){

return ((q<=e && w<=r) || (q<=r && w<=e));

}

int main(){

int a, b, c, x, y;

cin >> a >> b >> c >> x >> y;

if (skf(a, b, x, y) || skf(b, c, x, y) || skf(a, c, x, y)) cout << "YES";

else cout << "NO";

return 0;

}

Без условных операторов

#include <iostream>
using namespace std; 

bool skf(int q, int w, int e, int r){
    return ((q<=e && w<=r) || (q<=r && w<=e)); 
}

int main (){ 
    int a, b, c, x, y; 
    cin >> a >> b >> c >> x >> y; 
    (skf(a, c, x, y) or skf(b, c, x, y) or skf(a, b, x, y)) && cout << "YES";
    !(skf(a, c, x, y) or skf(b, c, x, y) or skf(a, b, x, y)) && cout << "NO";
    return 0; 
}

#include <iostream>

using namespace std;

bool skf(int q, int w, int e, int r){

return ((q<=e && w<=r) || (q<=r && w<=e));

}

int main (){

int a, b, c, x, y;

cin >> a >> b >> c >> x >> y;

(skf(a, c, x, y) or skf(b, c, x, y) or skf(a, b, x, y)) && cout << "YES";

!(skf(a, c, x, y) or skf(b, c, x, y) or skf(a, b, x, y)) && cout << "NO";

return 0;

}

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

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

Ссылки

Related Images:

e-olymp 2. Цифры

03/10/2018 by Владислав Шеванов

Задача

Вычислить количество цифр целого неотрицательного числа $n$.

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

Одно целое неотрицательное число $n$ [latex](0 \ge n \ge 2\cdot10^9)[/latex].

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

Количество цифр в числе $n$.

Тесты

Входные данные	Выходные данные
12345	5
1	1
353628	6
5454	4
0	1

Код программы (с использованием условных операторов)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    if( n <= 9 ) cout << 1;
    else if( n <= 99 ) cout << 2;
    else if( n <= 999 ) cout << 3;
    else if( n <= 9999 ) cout << 4;
    else if( n <= 99999 ) cout << 5;
    else if( n <= 999999 ) cout << 6;
    else if( n <= 9999999 ) cout << 7;
    else if( n <= 99999999 ) cout << 8;
    else if( n <= 999999999 ) cout << 9;
    else if( n <= 2000000000 ) cout << 10;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

if( n <= 9 ) cout << 1;

else if( n <= 99 ) cout << 2;

else if( n <= 999 ) cout << 3;

else if( n <= 9999 ) cout << 4;

else if( n <= 99999 ) cout << 5;

else if( n <= 999999 ) cout << 6;

else if( n <= 9999999 ) cout << 7;

else if( n <= 99999999 ) cout << 8;

else if( n <= 999999999 ) cout << 9;

else if( n <= 2000000000 ) cout << 10;

return 0;

}

Код программы (без использования условных операторов)

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

int main() {
    string n;
    cin >> n;
    cout << n.length();
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string n;

cin >> n;

cout << n.length();

return 0;

}

Решение

Для первого решения задачи используем череду условных операторов ( if, else), сравнивая $n$ с концами промежутков чисел с соответствующим количеством цифр. Обойтись без них можно, задав переменную string, присвоив ей значение числа $n$ и используя функцию length()в выводе (перед этим подключив библиотеку string).

Ссылки

E-Olymp

Ideone (с условными операторами)

Ideone (без условных операторов)

Related Images:

e-olymp 396. Дождь

15/04/2018 by Мороз Дима

Задача

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

Как это выглядит на координатной плоскости

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

Напишите программу, которая по координате $X$_$0$ точки появления капли над землей вычисляет координату $X$ точки соприкосновения капли с землей $(Y = 0)$.

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

Во входном файле в первой строке содержатся два целых числа через пробел – координата $X$_$0$ точки появления капли $(0 < X$_$0$ $< 10000)$ и количество отрезков-препятствий $N (0 ≤ N ≤ 100)$. Далее следует $N$ строк, каждая из которых содержит четыре разделенные пробелами числа $x$_$1$, $y$_$1$, $x$_$2$, $y$_$2$ – координаты левого и правого концов отрезка-препятствия (все числа целые и находятся в диапазоне от $0$ до $10000$, $x$_$1$ $ < x$_$2$, $y$_$1$ $≠$ $y$_$2$$)$. Отрезки не пересекаются и не соприкасаются.

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

В выходной файл вывести одно целое число – координату $X$ точки соприкосновения капли с землей.

Тесты

Входные данные	Выходные данные
30 4 25 35 40 30 1 32 20 30 33 22 50 29 18 10 33 19	18
12 5 12 9 13 5 17 8 19 5 13 10 10 7 6 17 4 12 13 4 5 12	13
40 3 12 30 21 39 41 5 45 70 20 30 25 35	40
70 6 45 75 598 37 489 48 726 47 673 873 46 36 60 735 373 762 483 73 364 59 462 375 583 457	726

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

#include <iostream>
using namespace std;
 
int main () 
{
    int x, n;
    cin >> x >> n;
    int N[n][4];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 4; j++)
            cin >> N[i][j];
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < n; j++) 
            for (int q = 0; q < 4; q++)
                if ((N[i][1] > N[j][1] || N[i][3] > N[j][3]) || ( (N[i][1] == N[j][1] || N[i][3] == N[j][3] ) && (N[i][0] > N[j][0] || N[i][2] > N[j][2]) ) )
                    swap(N[i][q], N[j][q]);
    for (int i = 0; i < n; i++) {
        if (x >= N[i][0] && x <= N[i][2]) 
            N[i][1] < N[i][3] ? x = N[i][0] : x = N[i][2];
        for (int j = 0; j < 4; j++)
            N[i][j] = 0;
    }
    cout << x;
 
    return 0;
}

#include <iostream>

using namespace std;

int main ()

{

int x, n;

cin >> x >> n;

int N[n][4];

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

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

cin >> N[i][j];

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

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

for (int q = 0; q < 4; q++)

if ((N[i][1] > N[j][1] || N[i][3] > N[j][3]) || ( (N[i][1] == N[j][1] || N[i][3] == N[j][3] ) && (N[i][0] > N[j][0] || N[i][2] > N[j][2]) ) )

swap(N[i][q], N[j][q]);

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

if (x >= N[i][0] && x <= N[i][2])

N[i][1] < N[i][3] ? x = N[i][0] : x = N[i][2];

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

N[i][j] = 0;

}

cout << x;

return 0;

}

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

Сортируем наш динамический массив по наибольшим координатам $y$ и, если $y$ равны, по координатам $x$.

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

Если $X$ $ ∈ [x$_$1$$, x$_$2$$]$, то наша капля пересечется с данной прямой. В противном случае мы просто игнорируем данное препятствие.
Тогда мы сравниваем координаты $y$_$1$ и $y$_$2$, выбираем из них наименьшее и присваиваем соответствующую координату $x$_$1$ или $x$_$2$ координате нашей капли $X$.
Повторяем до тех пор, пока не будут обработаны все препятствия и выводим последнюю присвоенную координату $X$ нашей капли, так как она и будет координатой $x$ соприкосновения капли с зимой.

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com

Related Images:

e-olymp 43. Количество участников олимпиады

01/12/2017 by Мороз Дима

Задача

Как известно, на вопрос о том, сколько у него учеников, древнегреческий учёный Пифагор отвечал так: «Половина моих учеников изучает математику, четвертая часть изучает природу, седьмая часть проводит время в молчаливом размышлении, остальную часть составляют три девы».

Секретарь олимпиады на вопрос: «Сколько зарегистрировано участников олимпиады по информатике?», отвечал подобно Пифагору: «$k$-тая часть участников начала решать первую задачу, $m$-тая часть – вторую, а $n$-ая – третью. В то же время $d$ участников решают проблему: «С чего начать?». Ваша задача определить количество участников олимпиады $s$ или вывести $-1$, если секретарь ошибся.

Входные данные: в одной строке заданы числа $k, n, m, d \left(1 ≤ k, n, m, d ≤ 1000 \right)$.

Выходные данные: вывести количество участников олимпиады $s$, или $-1$, если секретарь ошибся в своём сообщении.

Тесты

$k$	$n$	$m$	$d$	Выходные данные
2	4	7	3	28
4	5	2	1	20
3	7	5	4	-1
6	6	6	1	-1
2	3	6	4	-1
3	2	5	8	-1

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

#include <iostream>
#include <cmath>
using namespace std;
 
int main(){
    float k, n, m, d, s;
    cin >> k >> n >> m >> d;
    s = (d * k * n * m) / (k * n * m - k * m - k * n - m * n);
    if((1/k + 1/n + 1/m >= 1) || (floor(s/k) != s/k || floor(s/n) != s/n || floor(s/m) != s/m) || !(floor(s) == s)){
    cout << "-1";
    }else{
        cout << s;
    }
    
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main(){

float k, n, m, d, s;

cin >> k >> n >> m >> d;

s = (d * k * n * m) / (k * n * m - k * m - k * n - m * n);

if((1/k + 1/n + 1/m >= 1) || (floor(s/k) != s/k || floor(s/n) != s/n || floor(s/m) != s/m) || !(floor(s) == s)){

cout << "-1";

}else{

cout << s;

}

return 0;

}

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

Пусть $x$ — количество учеников Пифагора. Тогда $\frac{x} {2}$ — половина его учеников, тех, которые изучают математику. Следовательно, $\frac{x} {4}$ — ученики, которые изучают природу, а $\frac{x} {7}$ — ученики, которые проводят время в молчаливом размышлении. И, по условию задачи, есть так же три девы.
Получили уравнение вида $\frac{x} {2} + \frac{x} {4} + \frac{x} {7} + 3 = x$, в общем виде $\frac{x} {k} + \frac{x} {m} + \frac{x} {n} + d = x$.
Отсюда выходит, что $\frac{1} {k} + \frac{1} {m} + \frac{1} {n} + \frac{d} {x} = 1;$
$\frac{mnx + knx + kmx + kmnd} {kmnx} = 1;$
$(mn + kn + km)x + kmnd = kmnx;$
Отсюда получаем формулу $x = \frac{kmnd} {kmn — mn — kn — km}$.
Следовательно, если мы получаем целое число, то секретарь оказался прав, а если число дробное, то секретарь ошибся.

Для того, чтобы проверить, является ли переменная $x$ целым числом или нет, используем функцию floor() из встроенной библиотеки <cmath>.

Помимо этого делаем проверку для суммы чисел $\frac{1} {k}$, $\frac{1} {n}$ и $\frac{1} {m}$, так как если оно больше $1$, то количество учеников становится отрицательным, что невозможно. В случае, если $\frac{1} {k} + \frac{1} {n} + \frac{1} {m} = 1$, а $d > 0$, то, это тоже невозможно, а значит, секретарь ошибся.

Так же делаем проверку, которая определяет, не являются ли числа $\frac{q} {k}$, $\frac{q} {n}$ и $\frac{q} {m}$ дробными, так как это бы тоже было ошибкой секретаря (напрмер, если $k = 6$, $m = 6$, $n = 6$, $d = 1$, то при подстановке в формулу мы получаем, что количество участников равно $2$, но тогда получается, что один участник решал сразу три задачи, что, по условию задачи, невозможно).

Если условие не проходит проверки, то выводится «$-1$».

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com

Related Images:

Skynet: the Virus

14/10/2014 by Бронфен-Бова Роман

SKYNET FINALE — LEVEL 1

Los Angeles 2029 — Resistance HQ — Review of facts:

В минувшую субботу, сотни отважных бойцов рисковали своей жизнью, чтобы уничтожить Skynet. СТОП

Используя зараженных мото-терминаторов, им удалось привить смертельный вирус к Skynet. СТОП

Проблема: Skynet борется. СТОП

Джон, ещё раз, нам нужна ваша помощь. СТОП

Задача:

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

Первичная инициализация:

Первая строка: 3 целых числа N L E

N — Количество узлов, включая шлюзы
L — Количество связей
E — Количество шлюзов

Следующие L строк: по два числа на строку (N1, N2), означающие, что между узлами с индексами N1 и N2 присутствует связь.
Следующие E строк: по одному числу на строку, означающие индексы шлюзов.

Инициализация за каждый игровой тик:

Одно число — индекс связи, на которой находится Skynet агент.

Вывод за каждый игровой тик:

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

Программа:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int N; //Количество узлов, включая шлюзы
    int L; //Количество связей
    int E; //Количество шлюзов
    cin >> N >> L >> E; cin.ignore();
    
    int N1[L][2]; // Массив для связей
    for (int i = 0; i < L; i++) {
        cin >> N1[i][0] >> N1[i][1]; cin.ignore();
    }
    
    int EI[E]; // Индексы шлюзов
    for (int i = 0; i < E; i++) {
        cin >> EI[i]; cin.ignore();
    }
    
    // Алгоритм сортировки (его достаточно)
    for(int i = 0; i < L; i++){
        for(int k =0; k < E; k++){
            if(N1[i][1] == EI[k]) swap(N1[i][1],N1[i][0]);
        }
    }

    // игровой цикл
    while (1) {
        int SI; //Индекс связи, на которой находится Агент
        cin >> SI; cin.ignore();

        bool AgentIsNear = false; //Агент возле шлюза!
        
        for(int i = 0; i < L; i++){
            bool T = false; //Для прерывания цикла
            for(int k = 0; k < E; k++){
                if(EI[k] == N1[i][0] && SI == N1[i][1]){
                    cout << EI[k] << ' ' << SI << endl;
                    N1[i][0] = -1;
                    AgentIsNear = true;
                    T = true;
                    break;
                }
            }
            if(T) break;
        }
        
        if(!AgentIsNear){
            for(int i = 0; i < L; i++){
                bool T = false; //Для прерывания цикла
                for(int k = 0; k < E; k++){
                    if(N1[i][0] == EI[k]){
                        cout << EI[k] << ' ' << N1[i][1] << endl;
                        N1[i][0] = -1;
                        T = true;
                        break;
                    }
                }
                if(T) break;
            }
        }
        
    }
}

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

int N; //Количество узлов, включая шлюзы

int L; //Количество связей

int E; //Количество шлюзов

cin >> N >> L >> E; cin.ignore();

int N1[L][2]; // Массив для связей

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

cin >> N1[i][0] >> N1[i][1]; cin.ignore();

}

int EI[E]; // Индексы шлюзов

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

cin >> EI[i]; cin.ignore();

}

// Алгоритм сортировки (его достаточно)

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

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

if(N1[i][1] == EI[k]) swap(N1[i][1],N1[i][0]);

}

// игровой цикл

while (1) {

int SI; //Индекс связи, на которой находится Агент

cin >> SI; cin.ignore();

bool AgentIsNear = false; //Агент возле шлюза!

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

bool T = false; //Для прерывания цикла

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

if(EI[k] == N1[i][0] && SI == N1[i][1]){

cout << EI[k] << ' ' << SI << endl;

N1[i][0] = -1;

AgentIsNear = true;

T = true;

break;

}

if(T) break;

}

if(!AgentIsNear){

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

bool T = false; //Для прерывания цикла

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

if(N1[i][0] == EI[k]){

cout << EI[k] << ' ' << N1[i][1] << endl;

N1[i][0] = -1;

T = true;

break;

}

if(T) break;

}

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

Переходы между узлами занесены в двумерный массив N1, далее этот массив был своеобразно отсортирован (для удобства). В игровом цикле объявляем булевую переменную AgentIsNear — агент вблизи шлюза.

Первый цикл: Проверяем каждую клетку вокруг каждого шлюза на присутствие там агента. И если он таки там есть, блокируем переход, меняем первую переменную (отвечающую за шлюз) в массиве переходов (N1) на -1 (значение, которое никогда не встретится), изменяем AgentIsNear на true и прерываем цикл.

Второй цикл: так как агент гуляет где-то далеко, то мы блокируем любой свободный проход любого шлюза.

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

Программа проходит все тесты на MEDIUM и, что удивительно, половину тестов на HARD! Взято с CodinGame

Related Images:

Skynet: The Chasm

13/10/2014 by Іванов Вячеслав Володимирович

Вторая по списку игра на сайте codingame.com проверяет умение примата пользоваться условными операторами, интуицией и программой по физике за десятый класс. По легенде, на постапокалиптических просторах Земли будущего раскинулась зловещая империя враждебных человеку роботов, но инженерный гений непокоренных программистов-взломщиков дает человечеству шанс на выживание. Подрывная деятельность начинается с малого: под дистанционный контроль удалось взять кремниевые мозги скоростного робота, внешностью и повадками напоминающего модифицированный мотоцикл. Наша задача — создать алгоритм управления, позволяющий машине преодолевать препятствия.

Инициализация:
Каждый уровень поделен на три этапа:

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

До начала игрового цикла программа считывает данные о длине каждого из элементов уровня и сохраняет соответственно в переменные [latex]R, G, L[/latex].

Игровой цикл
На каждой итерации входной поток содержит:

Координату мотоцикла [latex]X[/latex].
Мгновенную скорость мотоцикла [latex]S[/latex].

В выходной поток необходимо вывести одну из четырех команд:

JUMP — совершить прыжок.
SPEED — увеличить скорость на единицу.
SLOW — уменьшить скорость на единицу.
WAIT — ждать следующего хода.

Прежде чем приступить к решению, проанализируем и формализуем задачу.
Continue reading →

Related Images:

Ю3.44

28/09/2014 by Іванов Вячеслав Володимирович

Задача: Леспромхоз ведёт заготовку деловой древесины. Первоначальный объем её на территории леспромхоза составлял [latex]p[/latex] кубометров. Ежегодный прирост составляет [latex]k[/latex]%. Годовой план заготовки — [latex]t[/latex] кубометров. Через сколько лет в бывшем лесу будут расти одни опята?

Тесты:

[latex]p[/latex]	[latex]k[/latex]%	[latex]t[/latex]	[latex]years[/latex]	Комментарий
111.50	14.57	16	Никогда	Пройден: прирост компенсирует вырубку
0	0	0	0	Пройден: абстрактный случай, но результат верный
20	10	30	1	Пройден
200	30	61	16	Пройден

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

#include <cstdio>
int main()
{
    double p = 0; scanf( "%lf", &p );
    double k = 0; scanf( "%lf", &k ); k /= 100; //перевод процентов в вид для расчетов
    double t = 0; scanf( "%lf", &t );
    int years = 0;

    if ( (p*(1 + k)-t) < p )
        {
            p = p * ( 1 + k ) - t;
            years++;
        }
    printf( "%d", years );
    }
    else 
     {
        printf("Никогда: система гармонична. ");
     }
    return 0;
}

#include <cstdio>

int main()

{

double p = 0; scanf( "%lf", &p );

double k = 0; scanf( "%lf", &k ); k /= 100; //перевод процентов в вид для расчетов

double t = 0; scanf( "%lf", &t );

int years = 0;

if ( (p*(1 + k)-t) < p )

{

p = p * ( 1 + k ) - t;

years++;

}

printf( "%d", years );

}

else

{

printf("Никогда: система гармонична. ");

}

return 0;

}

import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        double p = in.nextDouble();
        double k = in.nextDouble(); k /= 100; //нормализация процентов
        double t = in.nextDouble();
        int years = 0;
        if(p*(1+k)-t < p){ //если прирост не компенсирует вырубку
            while(p > 0){
                p = p*(1+k)-t;
                years++;
            }
            System.out.println(years);
        }
        else{
            System.out.println("Никогда: система гармонична.");
        }

    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.math.*;

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

double p = in.nextDouble();

double k = in.nextDouble(); k /= 100; //нормализация процентов

double t = in.nextDouble();

int years = 0;

if(p*(1+k)-t < p){ //если прирост не компенсирует вырубку

while(p > 0){

p = p*(1+k)-t;

years++;

}

System.out.println(years);

}

else{

System.out.println("Никогда: система гармонична.");

}

Формализация задачи:
Дано начальное значение [latex]p \ge 0[/latex]. На [latex]i[/latex]-м шаге оставшийся объем древесины вычисляется из рекуррентного соотношения: [latex]p_{i} = p_{i-1} (1 + \frac {k}{100})-t[/latex]. (*)
Определить шаг [latex]i[/latex] такой, что [latex]p_{i}<0[/latex].
Алгоритм решения:
Шаг 1: Проверка условия [latex]p_{1}[/latex] меньше [latex]p[/latex]. В случае, если если естественный прирост не компенсирует вырубку, начать рассчет. В противном случае лес никогда не опустеет, так как прирост и убыль скомпенсированы.
Шаг 2: До тех пор, пока [latex]p_{i}>0[/latex], рассчитывать [latex]p_{i}[/latex] по соотношению (*), где [latex]i[/latex] — количество прошедших лет.
Детали реализации:
В задаче используются два типа данных: целочисленный и с плавающей точкой двойной точности. Выбор продиктован отсутствием указания на конкретный тип входных данных в условии задачи. Протестировать работу программы можно по ссылке.
Реализация на Java: http://ideone.com/fyuDTg