Задача

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

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

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

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

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

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

Тесты

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

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

import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc = new Scanner(System.in);
		double h = sc.nextDouble();
		double w = sc.nextDouble();
    	double b = Math.max(h, w);
    	double a = Math.min(w, h);
    	double c = Math.min(Math.min(w,h), Math.max(b/3, a/2));
    	System.out.printf("%.4f", c);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner sc = new Scanner(System.in);

double h = sc.nextDouble();

double w = sc.nextDouble();

double b = Math.max(h, w);

double a = Math.min(w, h);

double c = Math.min(Math.min(w,h), Math.max(b/3, a/2));

System.out.printf("%.4f", c);

}

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

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

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

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

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

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

Ссылки

Условие задачи на сайте e-olymp
Код решения

Задача

Задача из журнала «Квант» №7 1970 г.
Квадратный лист бумаги разрезают по прямой на две части. Одну из полученных частей снова разрезают на две части, и так делают много раз. Какое наименьшее число разрезов $r$ нужно сделать, чтобы среди полученных частей оказалось $n$ $k$ -угольников?

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

Количество многоугольников $n$ .
Количество углов многоугольника $k$ .

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

Количество разрезов $r$ .

Пример получения двух шестиугольников за 5 разрезов

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

import java.util.*;
import java.lang.*;
import java.io.*;
import static java.lang.Math.*;

class Ideone {
        public static void main (String[] args) {
             Scanner sc = new Scanner(System.in);
             double r,n,k;
             n = sc.nextInt();
             k = sc.nextInt();
             r=k>3? n*(k-3)-1 : n>1? n-1 : 1;
             System.out.println(r);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import static java.lang.Math.*;

class Ideone {

public static void main (String[] args) {

Scanner sc = new Scanner(System.in);

double r,n,k;

n = sc.nextInt();

k = sc.nextInt();

r=k>3? n*(k-3)-1 : n>1? n-1 : 1;

System.out.println(r);

}

Решение

При каждом разрезе количество кусков бумаги $n$ увеличивается на $1$ . Общее количество вершин $k$ будет увеличиваться в зависимости от места разреза. Таким образом при разрезе через две стороны общее количество вершин будет увеличиваться на $4$ . При разрезе через две вершины общее количество вершин увеличивается на $2$ , а при разрезе через сторону и вершину — на $3$ .

При $k>3$ сначала разделим лист на $n$ четырёхугольников при помощи разрезов через противоположные стороны. На это нам понадобиться $n-1$ разрезов. Затем можем, при помощи разрезов через соседние стороны, превращать каждый четырехугольник в $k$ — угольник, на что понадобиться $k-4$ разрезов.Выходит, что на получение $n$ $k$ — угольников нужно сделать не меньше $n(k-4)+n-1$ разрезов, значит $r=n(k-3)-1$ .

Если же $k=3$ , то нам нужно, наоборот, уменьшить количество вершин. Тогда первый разрез сделаем через две вершины квадрата — получаем два треугольника, затем каждым разрезом через вершину и сторону увеличиваем количество треугольников на $1$ пока не получим $n$ . В таком случае $r= n-1$ . Исключение: если $n=1$ , то $r=1.$

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Tag Archives: квадрат

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

Задача

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

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

Тесты

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

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

Ссылки

KM31. Бумажные многоугольники

Задача

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

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

Тесты

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

Решение

Ссылка на Ideone

	Входные данные		Выходные данные
№	$n$	$k$	$r$
1	100	20	1699
2	14	3	13
3	1	3	1
4	40	360	14279
5	2	6	5