e-olymp 7612. Алекс и квадраты оригами

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

Задача

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

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

В одной строке два целых числа [latex] h [/latex] и [latex] w [/latex] [latex] \left ( 1\leqslant h,w\leqslant 1000 \right ) [/latex] — высота и ширина куска бумаги.

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

Выведите одно действительное число — наибольшую длину стороны квадратов. Всегда можно вырезать три одинаковых квадрата из листа бумаги размером [latex] h \times w[/latex] так, чтобы их стороны были параллельны сторонам листа.
Ответ следует вывести с точностью не меньше трех десятичных знаков.

Тесты

Входные данные	Выходные данные
30 11	10.0000
8 3	2.6667
210 297	105.0000
60 59	29.5000
250 100	83.3333

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

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

int main() {
    double h, w, ans = 0;
    cin >> h >> w;
    if (w < h) {
        swap (w, h);
    }
    ans = ( w >= 3 * h ? h : max (h / 2, w / 3) );
    cout << fixed << setprecision(4) << ans;
}

#include <iostream>

#include <algorithm>

#include <cmath>

#include <iomanip>

using namespace std;

int main() {

double h, w, ans = 0;

cin >> h >> w;

if (w < h) {

swap (w, h);

}

ans = ( w >= 3 * h ? h : max (h / 2, w / 3) );

cout << fixed << setprecision(4) << ans;

}

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
 
int main() {
    double h, w, tmp = 0,  ans = 0;
    cin >> h >> w;
    if (w < h) {
        tmp = h;
        h = w;
        w = tmp;
    }
    if (w >= 3 * h) {
        ans = h;
    }
    else {
        ans = max (h / 2, w / 3);
    }
    cout << fixed << setprecision(4) << ans;
}

#include <iostream>

#include <cmath>

#include <iomanip>

using namespace std;

int main() {

double h, w, tmp = 0, ans = 0;

cin >> h >> w;

if (w < h) {

tmp = h;

h = w;

w = tmp;

}

if (w >= 3 * h) {

ans = h;

}

else {

ans = max (h / 2, w / 3);

}

cout << fixed << setprecision(4) << ans;

}

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

Допустим, что [latex] w [/latex] всегда больше чем [latex] h [/latex] . Из условия следует, что варианта расположения данных квадратов два:

В первом случае ответом будет [latex] \max\left ( \frac{h}{2}, \frac{w}{3} \right ) [/latex]. Во втором же, ответом будет [latex] h [/latex] .

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

В первом коде программы используется используется библиотека
#include <algorithm> , которая включает в себя функцию swap() , так же, используется библиотека #include <cmath> , которая включает в себя функцию max() .
Для вывода ответа с точностью не меньше трех десятичных знаков используется библиотека
#include <iomanip> и манипуляторы fixed и setprecision() .

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

Related Images:

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

23/05/2019 by Инна Литвиненко

Задача

Обсуждая личную жизнь всевозможных злодеев, мы обделили своим вниманием графа Дуку. Так вот, граф Дуку на досуге любит складывать оригами. Он давно систематизировал свои познания в этой области следующим образом: всего граф знает n фигурок, причем для некоторых из них он знает, как получать из одной другую. Для обучения начинающих ситхов Дуку разработал специальную таблицу. В ячейке $[i, j]$ таблицы стоит «1», если граф может получить из фигурки $i$ фигурку $j$ одним сгибом. Иначе там стоит «0». Изначально в руках у графа Дуку чистый лист, то есть фигурка номер $x$ по его системе, сложить же он желает журавлика – фигурку номер $y$.
Найдите, за сколько операций граф достигнет желаемого.

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

В первой строке находится число $n (1 \leq n \leq 1000)$. В следующих $n$ строках задана таблица Дуку. В $(n + 1)$ — ой строке стоят числа $x$ и $y$.

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

Выведите минимальное количество операций, которые придется осуществить. Если же коварным планам Графа не суждено осуществиться, выведите «-1».

Тесты

№	Ввод	Вывод
1	4 0 0 1 0 0 0 0 1 1 0 0 1 0 1 1 0 1 2	3
2	4 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 2	-1
3	5 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 1 5	4
4	2 0 1 1 0 2 1	1
5	6 0 1 1 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 5 2	-1

Код

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

int main() {
    int n, x, y, v;
    cin >> n;
    int matrix[n + 1][n + 1], dist[n + 1]; 
    queue <int> plan;
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= n; j++)
            cin >> matrix[i][j];
    cin >> x >> y;
    for (int i = 1; i <= n; i++)
        dist[i] = -1;
    plan.push(x);
    dist[x] = 0;
    while (!plan.empty()) {
        v = plan.front();
        plan.pop();
        for (int i = 1; i <= n; i++) {
            if (dist[i] == -1 && matrix[v][i]) {
                plan.push(i);
                dist[i] = dist[v] + 1;
            }
        }
        if (v == y) plan.empty(); // если обработали вершину y, прекращаем обход
    } 
    cout << dist[y];
    return 0;
}

#include <iostream>

#include <queue>

using namespace std;

int main() {

int n, x, y, v;

cin >> n;

int matrix[n + 1][n + 1], dist[n + 1];

queue <int> plan;

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

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

cin >> matrix[i][j];

cin >> x >> y;

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

dist[i] = -1;

plan.push(x);

dist[x] = 0;

while (!plan.empty()) {

v = plan.front();

plan.pop();

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

if (dist[i] == -1 && matrix[v][i]) {

plan.push(i);

dist[i] = dist[v] + 1;

}

if (v == y) plan.empty(); // если обработали вершину y, прекращаем обход

}

cout << dist[y];

return 0;

}

Решение

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

Ссылки

Условие задачи на e-olymp
Код на Ideone
Описание алгоритма на сайте e-maxx.ru

Related Images:

e-olymp 7612. Алекс и квадраты оригами

06/12/2017 by Александра Рябова

Задача

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

В одной строке два целых числа [latex]h[/latex] и [latex]w[/latex] ([latex]1 ≤ h, w ≤ 1000[/latex]) — высота и ширина куска бумаги.

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

Выведите одно действительное число — наибольшую длину стороны квадратов. Всегда можно вырезать три одинаковых квадрата из листа бумаги размером [latex]h × w[/latex] так, чтобы их стороны были параллельны сторонам листа.

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

Тесты

Входные данные	Выходные данные
$100$ $100$	$50.000$
$10$ $80$	$10.000$
$50$ $76$	$25.333$
$60$ $27$	$20.000$
$8$ $3$	$2.667$

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

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

int main()
{
    cout.precision(4);
    double h, w = 0;
    cin >> h;
    cin >> w;
    double b = max(h, w);
    double a = min(w, h);
    double c = min(a, max(b/3, a/2));
    cout << fixed << c;
}

#include<iostream>

#include<cmath>

#include <iomanip>

using namespace std;

int main()

{

cout.precision(4);

double h, w = 0;

cin >> h;

cin >> w;

double b = max(h, w);

double a = min(w, h);

double c = min(a, max(b/3, a/2));

cout << fixed << c;

}

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

Существует два варианта оптимального расположения трех квадратов — три в один ряд,

или же два, соприкасающихся одной стороной, и третий над ними

Обозначим за [latex]a[/latex] меньшую сторону листа бумаги, а за [latex]b[/latex] — большую. Если [latex]a[/latex] не больше [latex]\frac{b}{3}[/latex], то оптимальным расположением квадратов в прямоугольнике будет первый вариант, а наибольшей возможной стороной квадратов является меньшая сторона листа бумаги [latex]a[/latex]. В противном случае рассмотрим два варианта:

Если [latex]\frac{a}{2}<\frac{b}{3}[/latex], то квадраты будут располагаться в прямоугольнике первым способом, и ответом будет служить число [latex]\frac{a}{2}[/latex].
Иначе квадраты будут располагаться в прямоугольнике вторым способом, и ответом будет служить число [latex]\frac{b}{3}[/latex].

Таким образом, в случае [latex]a>\frac{b}{3}[/latex] ответом будет служить большее из двух чисел [latex]\frac{a}{2}[/latex] и [latex]\frac{b}{3}[/latex].
Минимальное из [latex]\max\left(\frac{b}{3},\frac{a}{2}\right)[/latex] и [latex]a[/latex] число и будет ответом.
Проверим нашу формулу:если [latex]a<\frac{b}{3}[/latex], то [latex] \max\left(\frac{b}{3},\frac{a}{2}\right)=\frac{b}{3} [/latex], и тогда [latex]\min\left(a,\max\left(\frac{b}{3},\frac{a}{2}\right)\right)=a[/latex]. Иначе [latex]\min\left(a,\max\left(\frac{b}{3},\frac{a}{2}\right)\right)=\max\left(\frac{b}{3},\frac{a}{2}\right)[/latex], что нам и требуется.