XAYNHA - Xây nhà bằng đá quý

Tags: math

Problem

https://vn.spoj.com/problems/XAYNHA

https://oj.vnoi.info/problem/XAYNHA

Mr.Davion là một kiến trúc sư trẻ. Anh nhận được lời mời từ Mr.X do anh là một cao thủ vũ lâm trong làng …. Lego ! Mr.X giao cho anh N viên đá quý và yêu cầu anh xây một tòa nhà hoàn chỉnh và xây càng cao càng tốt nếu có thể. Tuy nhiên, có thể không đủ số viên đá để xây theo yêu cầu của Mr.X.

Hãy giúp Mr.Davion tính toán xem số lượng đá mà X giao cho có đủ hay không? Nếu đủ thì hãy thông báo là đủ, còn không thì phải thông báo cần bỏ đi / thêm vào bao nhiêu viên đá để xây được tòa nhà hoàn chỉnh sao cho thỏa mãn yêu cầu của Mr.X và số đá thêm / bớt đi là ít nhất có thể do khi bớt / thêm vào, cần chuyển đá quý qua lại nơi xây dựng và kho, rất tốn công sức .

Quy tắc xây và một số định nghĩa

  • Khối đá quý là một khối lập phương bao gồm những viên đá quý nhỏ
  • Xây bằng cách chồng các khối đá quý có độ dài các cạnh liên tiếp, khối có độ dài cạnh lớn hơn thì nằm ở dưới
  • Xây một tòa nhà hoàn chỉnh tức là tòa nhà không bị khuyết bất kỳ góc nào – hay nói cách khác, các khối xây nên không có khối nào bị “rút ruột”
  • Xây một tòa nhà level H tức là sử dụng H khối đá quý mà độ dài cạnh của các khối lần lượt là 1,2,3…,H. (Tòa nhà đã hoàn chỉnh)

Giới hạn

0 ≤ N ≤ 10^15

Input

  • Dòng 1: Ghi số T – số bộ test.
  • Dòng 2..T+1 : Mỗi dòng ghi duy nhất một số N – số viên đá mà Mr.X giao cho Davion

Output

Ghi ra T dòng. Mỗi dòng ghi những thông tin một trong hai dạng thông tin sau

  • 1 H : Nếu như đủ số đá và xây được tòa nhà level H
  • 0 K H : Nếu như không đủ số đá và cần thêm / bớt |K| viên đá để đạt được tòa nhà hoàn chỉnh với level H theo yêu cầu của Mr.X. (K > 0 khi cần loại bỏ |K| viên đá , ngược lại K < 0 khi cần thêm vào |K| viên đá).

Ví dụ

Input
3
9
8
442

Output
1 2
0 1 2
0 -1 6

Giải thích

9 = 1^3 + 2^3
8 = 1^3 + 2^3 - 1
442 = 1^3 + 2^3 + 3^3 + 4^3 + 5^3 + 6^3 + 1

Tutorial

Gợi ý: 1^3 + 2^3 + ... + n^3 = (n(n+1)/2)^2

Cần tìm level H (tức n trong công thức trên) để tối thiểu độ chênh lệch.


Submission

XAYNHA.cpp