Задача. Анфиса и цветы
Условие задачи
Мурзик одну из цветочных клумб сделал в виде шахматной доски размерами [latex]m[/latex] на [latex]n,[/latex] в каждой клеточке которой растет какой-то цветок. Иногда на эту клумбу он выводит на прогулку Анфису (да, не удивляйтесь, они действительно друзья). Анфиса, начиная всегда с верхнего левого угла передвигается по клумбе к правому нижнему и собирает цветы, причем таким образом, чтобы каждый раз проходить новым маршрутом, а Мурзик на выходе вручает ей кусочек сыра.
Посчитать, какое наибольшее количество кусочков сыра получит Анфиса, если она все время старается сохранить как можно больше цветов. При каждом очередном своем проходе Анфиса обязательно должна собрать как минимум один цветок.
Входные данные
В одной строке через пробел заданы два числа [latex]m[/latex] на [latex]n.[/latex]
Выходные данные
Вывести наибольшее количество кусочков сыра, которые может получить Анфиса.
Также условие задачи можно посмотреть здесь.
<р2>Реализация
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
import java.util.*; import java.lang.*; import java.io.*; import java.util.Scanner; class Ideone { public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); String reader = in.nextLine(); String[] s = reader.split(" "); long m = Long.parseLong(s[0]); long n = Long.parseLong(s[1]); long p = (m * n - (m + n - 1)) + 1; System.out.println(p); } } |
Проверить код можно тут.
Тестирование
| № | Входные данные (m, n) | Выходные данные |
| 1 | 2, 3 | 3 |
| 2 | 3, 3 | 5 |
| 3 | 3, 4 | 7 |
| 4 | 4, 3 | 7 |
| 6 | 5, 7 | 25 |
Алгоритм решения
Задана цветочная клумба в виде шахматной доски размерами [latex]m[/latex] на [latex]n[/latex]. Очевидно, что количество цветов на данной клумбе равно [latex]m\cdot n[/latex]. Пусть Анфиса, совершая свое очередное передвижение, начиная с левого верхнего угла клумбы и направляясь к правому нижнему, съедает [latex](m-1)\cdot (n-1)[/latex] цветов, так как, согласно условию задачи, Анфиса обязательно должна собрать как минимум один цветок при каждом проходе. После каждого такого прохода на выходе она получает один кусочек сыра.
Следовательно, имеет место следующая формула: [latex]p=(m-1)\cdot (n-1)+1[/latex], где [latex]p[/latex] — наибольшее количество кусочков сыра, которое может получить Анфиса. Действительно, если [latex]m=2[/latex], [latex]n=3[/latex], то получаем [latex]p=3[/latex].