読者です 読者をやめる 読者になる 読者になる

torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder, SRM 625, Division 2, Level 1 : AddMultiply

問題概要

 非負整数 y ( y \leq 500 ) が与えられる。次の条件を満たすタプル ( a, b, c ) を一つ求めよ。

  • a \times b + c = y
  • -1000 \leq a, b, c \leq 1000
  • a, b, c \not\in \{ 0, 1 \}

 少なくとも一つ、条件を満たすタプルが存在することが保証される。

解法

 まず、a \times b + c = y より c = y - a \times b です。負数に関しては下限以外の制約が無いことを考えると、a \times b によって y の上限を超える正整数を作ることができれば、c は自動的に決まります。a, b についても、両方を負数にして適当な大きさの正整数を作ることができます。従って、例えば ( -512, -1, y - 512 ) などは条件を満たすタプルです。

コード

using VI = vector<int>;

class AddMultiply
{
public:
	vector <int> makeExpression( int y )
	{
		return VI{ -512, -1, y - 512 };
	}
};