AtCoder AGC 036 A - Triangle (緑色, 400 点)

ちょっと面白い感じの構築問題！

• 問題へのリンク

問題概要

正の整数 が与えられる。

以下の条件を満たす 3 つの格子点 の組を一つ求めよ。

• 座標値はすべて 以上 以下の整数値
• 3 つの格子点からなる三角形の面積を 2 倍すると に一致

制約

• 

考えたこと

仮に 1 つの頂点を原点に固定することにすると、もう 2 つの座標を としたとき、

を満たすような整数 を探す問題となる。ただし に対して、 を満たさなければならない。

直感的には、 の値を大きくして、 の値を帳尻合わせに使えば良さそうだと思った。たとえば であれば

• 
• 

とかで OK。 とかであれば、

• 
• 

とかで OK。一般に、 を 以上の桁と、未満の桁とにわけてあげれば上手くいきそうだ。具体的には として、

    long long a = (S + p - 1) / p;
    long long d = p;
    long long b = a * p - S;
    long long c = 1;

というふうにすればできた。 は を で割って、小数点以下を切り上げた値となっている。

コード

#include <bits/stdc++.h>
using namespace std;

const long long p = 1000000000;
int main() {
    long long S;
    cin >> S;
    long long a = (S + p - 1) / p;
    long long d = p;
    long long b = a * p - S;
    long long c = 1;
    cout << "0 0 " << a << " " << b << " " << c << " " << d << endl;
}