2025.cpp

/**
source:https://acm.timus.ru/problem.aspx?num=2025
Пояснение к примененному алгоритму:
Основной сложностью задачи является то, что на момент помещения камня в кучу мы уже должны знать в какую именно кучу необходимо положить камень, что бы получить минимальную ds — разницу между суммами масс камней в кучах.
Таким образом, необходимо было просмотреть все возможные варианты размещения камней и определить тот, где ds минимальна. Сделать это можно с помощью построения дерева вариантов с его последующей обработкой и анализом или с помощью построения дерева рекурсии. Так как второй вариант позволяет во уже во время построения дерева определить минимальную ds и не требует памяти для хранения всего дерево, был реализован алгоритм, использующий рекурсию, а именно:
1) Алгоритм рекурсивно помещает каждый камень в одну из двух куч
2) Когда все камни разложены, текущая ds сравнивается с минимальной ds, и если она меньше, то минимальная обновляется
Использование рекурсии позволяет сравнить все возможные варианты расположения камней в кучах без их хранения в виде дерева.

*/
#include "stdio.h"
#include <cstdint>

int main()
{
    uint8_t t;
    uint16_t n, k, div, mod;
    scanf("%hhu", &t);
    for(uint8_t j = 0; j < t; j++)
    {
        scanf("%hu %hu", &n, &k);
        div = n / k;
        mod = n % k;
        printf("%d\n", mod * (mod - 1) / 2  * ( (div + 1) * (div + 1) )
        + (k - mod - 1) * (k - mod) / 2     * ( div * div )
        + (k - mod) * mod                   * ( div * div + 1 ) );
    }

    return 0;
}