torus711 のアレ

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

Codeforces #177, Division 2, A : Polo the Penguin and Segments

概要

n 個の重ならない開区間が与えられる。
各区間について、その幅を 1 広げる操作できる。
区間に含まれる数字の数を k で割り切れる値にするために必要な操作回数の最小値を求めよ。

解法

各区間について、その内包する数字の数を求め、その和を s とします。
s mod k が 0 ならば、操作を剃る必要が無いので 0 です。
それ以外の場合、k - ( s mod k ) 回の操作が必要になります。

コード

typedef long long LL;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n, k;
	cin >> n >> k;

	LL sum = 0;
	REP( i, 0, n )
	{
		int l, r;
		cin >> l >> r;
		sum += r - l + 1;
	}
	cout << ( sum % k ? k - ( sum % k ) : 0 ) << endl;

	return 0;
}