Print a Pedestal (Codeforces logo?) (Codeforces 1690A)
Tags: Greedy, constructive algorithms

Given the integer $$$n$$$ — the number of available blocks. You must use all blocks to build a pedestal. The pedestal consists of $$$3$$$ platforms for $$$2$$$-nd, $$$1$$$-st and $$$3$$$-rd places respectively. The platform for the $$$1$$$-st place must be strictly higher than for the $$$2$$$-nd place, and the platform for the $$$2$$$-nd place must be strictly higher than for the $$$3$$$-rd place. Also, the height of each platform must be greater than zero (that is, each platform must contain at least one block).  Example pedestal of $$$n=11$$$ blocks: second place height equals $$$4$$$ blocks, first place height equals $$$5$$$ blocks, third place height equals $$$2$$$ blocks.Among all possible pedestals of $$$n$$$ blocks, deduce one such that the platform height for the $$$1$$$-st place minimum as possible. If there are several of them, output any of them.

Input: The first line of input data contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.Each test case contains a single integer $$$n$$$ ($$$6 \le n \le 10^5$$$) — the total number of blocks for the pedestal. All $$$n$$$ blocks must be used.It is guaranteed that the sum of $$$n$$$ values over all test cases does not exceed $$$10^6$$$.

Output: For each test case, output $$$3$$$ numbers $$$h_2, h_1, h_3$$$ — the platform heights for $$$2$$$-nd, $$$1$$$-st and $$$3$$$-rd places on a pedestal consisting of $$$n$$$ blocks ($$$h_1+h_2+h_3=n$$$, $$$0 < h_3 < h_2 < h_1$$$). Among all possible pedestals, output the one for which the value of $$$h_1$$$ minimal. If there are several of them, output any of them.

Note: In the first test case we can not get the height of the platform for the first place less than $$$5$$$, because if the height of the platform for the first place is not more than $$$4$$$, then we can use at most $$$4 + 3 + 2 = 9$$$ blocks. And we should use $$$11 = 4 + 5 + 2$$$ blocks. Therefore, the answer 4 5 2 fits. In the second set, the only suitable answer is: 2 3 1.

Sample Inputs:
6
11
6
10
100000
7
8

Sample Outputs:
4 5 2
2 3 1
4 5 1
33334 33335 33331
2 4 1
3 4 1

Solution (Python):
import sys
from math import ceil
input = lambda : sys.stdin.readline()
ii = lambda : int(input())
si = lambda : input()
mi = lambda : map(int, input().split())
mf = lambda : map(float, input().split())
msi = lambda : map(str, input().strip().split(' '))
li = lambda : list(mi())
lf = lambda : list(mf())

def YES():
    print('YES')

def Yes():
    print('Yes')

def yes():
    print('yes')

def NO():
    print('NO')

def No():
    print('No')

def no():
    print('no')

class Solution:

    def __init__(self):
        return

    def solve(self):
        for _ in range(ii()):
            n = ii()
            if n == 7:
                sys.stdout.write(f'{2} {4} {1}\n')
            else:
                a = ceil(n / 3)
                b = a + 1
                c = n - a - b
                sys.stdout.write(f'{a} {b} {c}\n')
if __name__ == '__main__':
    Solution().solve()

Solution (Python):
import sys
from math import ceil
from functools import wraps, lru_cache
import functools
input = lambda : sys.stdin.readline()
ii = lambda : int(input())
si = lambda : input()
mi = lambda : map(int, input().split())
mf = lambda : map(float, input().split())
msi = lambda : map(str, input().strip().split(' '))
li = lambda : list(mi())
lf = lambda : list(mf())

def YES():
    print('YES')

def Yes():
    print('Yes')

def yes():
    print('yes')

def NO():
    print('NO')

def No():
    print('No')

def no():
    print('no')

class Solution:

    def __init__(self):
        return

    def turbo(func):
        cache = {}

        @wraps(func)
        def wrapper(*args, **kwargs):
            key = str(args) + str(kwargs)
            if key not in cache:
                cache[key] = func(*args, **kwargs)
            return cache[key]
        return wrapper

    def ignore_unhashable(func):
        uncached = func.__wrapped__
        attributes = functools.WRAPPER_ASSIGNMENTS + ('cache_info', 'cache_clear')

        @functools.wraps(func, assigned=attributes)
        def wrapper(*args, **kwargs):
            try:
                return func(*args, **kwargs)
            except TypeError as error:
                if 'unhashable type' in str(error):
                    return uncached(*args, **kwargs)
                raise
        wrapper.__uncached__ = uncached
        return wrapper

    @staticmethod
    @ignore_unhashable
    @lru_cache(maxsize=128)
    @turbo
    def solve():
        for _ in range(ii()):
            n = ii()
            if n == 7:
                sys.stdout.write(f'{2} {4} {1}\n')
            else:
                a = ceil(n / 3)
                b = a + 1
                c = n - a - b
                sys.stdout.write(f'{a} {b} {c}\n')
if __name__ == '__main__':
    Solution().solve()

Solution (Python):
import sys
from math import ceil
sys.stdin.reconfigure(line_buffering=True)
input = lambda : sys.stdin.readline()
ii = lambda : int(input())
si = lambda : input()
mi = lambda : map(int, input().split())
mf = lambda : map(float, input().split())
msi = lambda : map(str, input().strip().split(' '))
li = lambda : list(mi())
lf = lambda : list(mf())

def YES():
    print('YES')

def Yes():
    print('Yes')

def yes():
    print('yes')

def NO():
    print('NO')

def No():
    print('No')

def no():
    print('no')

class Solution:

    def __init__(self):
        return

    def solve(self):
        for _ in range(int(input())):
            n = int(input())
            if n == 7:
                sys.stdout.write(f'{2} {4} {1}\n')
            else:
                a = ceil(n / 3)
                b = a + 1
                c = n - a - b
                sys.stdout.write(f'{a} {b} {c}\n')
if __name__ == '__main__':
    Solution().solve()