Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <limits>
- #include <cstdlib>
- using namespace std;
- int64_t CalculateAll(int64_t m, int64_t n) {
- return (1 + m * n) * m * n / 2;
- }
- int64_t CalculateHorizontal(int64_t m, int64_t n, int64_t k) {
- int64_t first_half = (1 + k*m) * k*m / 2;
- return first_half;
- }
- int64_t CalculateHorizontalDiff(int64_t m, int64_t n, int64_t k) {
- int64_t first_half = (1 + k*m) * k*m / 2;
- return abs(2 * first_half - CalculateAll(m, n));
- }
- int64_t CalculateVertically(int64_t m, int64_t n, int64_t k) {
- int64_t first_column = (1 + m * (n - 1) + 1) * n / 2;
- int64_t first_half = first_column * k + k * (k - 1) / 2 * n;
- return first_half;
- }
- int64_t CalculateVerticallyDiff(int64_t m, int64_t n, int64_t k) {
- int64_t first_column = (1 + m * (n - 1) + 1) * n / 2;
- int64_t first_half = first_column * k + k * (k - 1) / 2 * n;
- return abs(2 * first_half - CalculateAll(m, n));
- }
- int main() {
- int t;
- std::cin >> t;
- while (t--) {
- int64_t m, n, one = 1;
- std::cin >> n >> m;
- int64_t horizontal_result = std::numeric_limits<int64_t>::max();
- int64_t vertical_result = std::numeric_limits<int64_t>::max();
- int64_t min_horizontal = 0, min_vertically = 0;
- int64_t all_sum = CalculateAll(m, n);
- int64_t left = 0, right = n - 1;
- while (right - left > 1) {
- int64_t median = (left + right) / 2;
- int64_t new_horizontal = CalculateHorizontal(m , n, median);
- if (2 * new_horizontal > all_sum) {
- right = median;
- } else {
- left = median;
- }
- }
- for (int64_t k = std::max(one, left - 1); k < std::min(n, right + 1); ++k) {
- int64_t new_horizontal = CalculateHorizontalDiff(m , n, k);
- if (new_horizontal < horizontal_result) {
- horizontal_result = new_horizontal;
- min_horizontal = k;
- }
- }
- left = 0, right = m - 1;
- while (right - left > 1) {
- int64_t median = (left + right) / 2;
- int64_t new_vertical = CalculateVertically(m , n, median);
- if (2 * new_vertical > all_sum) {
- right = median;
- } else {
- left = median;
- }
- }
- for (int64_t k = std::max(one, left - 1); k < std::min(right + 1, m); ++k) {
- int64_t new_vertical = CalculateVerticallyDiff(m , n, k);
- if (new_vertical < vertical_result) {
- vertical_result = new_vertical;
- min_vertically = k;
- }
- }
- if (vertical_result < horizontal_result) {
- std::cout << "V " << min_vertically + 1 << "\n";
- } else {
- std::cout << "H " << min_horizontal + 1 << "\n";
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement