Задача
Назовем квартетом четверку клеток на клетчатой бумаге, центры которых лежат в вершинах прямоугольника со сторонами, параллельными линиям сетки. Какое наибольшее число квартетов, не имеющих общих клеток, можно разместить на прямоугольнике [latex]mn[/latex] клеток?
Входные данные
[latex]m, n[/latex]Вывод
[latex]x[/latex] -кол-во квартетов.Тесты
| m | n | x |
| 8 | 6 | 12 |
| 16 | 7 | 24 |
| 17 | 8 | 29.75 |
| 15 | 11 | 37 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
import java.util.*; import java.lang.*; import java.io.*; class Ideone { public static void main(String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); int m = in .nextInt(); int n = in .nextInt(); boolean meven = m % 2 == 0 ? true : false; boolean neven = n % 2 == 0 ? true : false; double x; if (meven && neven) { x = m * n / 4; } else if (meven && !neven) { x = m * (n - 1) / 4; } else if (!meven && neven) { x = n * (m - 1) / 4; } else { if (n > m) { int tmp = n; n = m; m = tmp; } if ((n - 1) % 4 == 0) { x = m * (n - 1) / 4; } else { x = (m * (n - 1) - 2) / 4; } } System.out.println(x); } } |
Решение
Если [latex]m[/latex] и [latex]n[/latex] четные то на прямоугольнике [latex]mn[/latex] можно разместить [latex]\frac{mn}{4}[/latex] квартетов. Если [latex]m[/latex] четное, а [latex]n[/latex] нечетное (и наоборот), то можно разместить [latex]m(n-1)[/latex]. И наконец если [latex]m[/latex] и [latex]n[/latex] — нечетные, то нужно рассматривать два случая:
- [latex]n = 4k + 1[/latex], в этом случае у нас формула такая: [latex]\frac{m(n-1)}{4}[/latex]
- Иначе, у нас другая формула: [latex]\frac{ \left(m(n-1)-2\right)}{4}[/latex]
Ссылка на решение в ideone.