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

Задача

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

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

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

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

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

%d1%81%d0%bd%d0%b8%d0%bc%d0%be%d0%ba

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

Тесты

	Входные данные		Выходные данные
№	$n$	$k$	$r$
1	100	20	1699
2	14	3	13
3	1	3	1
4	40	360	14279
5	2	6	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.$