Codeforces Round #609(Div.2) B.Modulo Equality(사고)

9567 단어 CodeBlocks
time limit per test3 seconds memory limit per test256 megabytes inputstandard input outputstandard output You are given a positive integer m and two integer sequence: a=[a1,a2,…,an] and b=[b1,b2,…,bn]. Both of these sequence have a length n.
Permutation is a sequence of n different positive integers from 1 to n. For example, these sequences are permutations: [1], [1,2], [2,1], [6,7,3,4,1,2,5]. These are not: [0], [1,1], [2,3].
You need to find the non-negative integer x, and increase all elements of ai by x, modulo m (i.e. you want to change ai to (ai+x)modm), so it would be possible to rearrange elements of a to make it equal b, among them you need to find the smallest possible x.
In other words, you need to find the smallest non-negative integer x, for which it is possible to find some permutation p=[p1,p2,…,pn], such that for all 1≤i≤n, (ai+x)modm=bpi, where ymodm — remainder of division of y by m.
For example, if m=3, a=[0,0,2,1],b=[2,0,1,1], you can choose x=1, and a will be equal to [1,1,0,2] and you can rearrange it to make it equal [2,0,1,1], which is equal to b.
Input The first line contains two integers n,m (1≤n≤2000,1≤m≤109): number of elemens in arrays and m.
The second line contains n integers a1,a2,…,an (0≤ai
The third line contains n integers b1,b2,…,bn (0≤bi
It is guaranteed that there exists some non-negative integer x, such that it would be possible to find some permutation p1,p2,…,pn such that (ai+x)modm=bpi.
Output Print one integer, the smallest non-negative integer x, such that it would be possible to find some permutation p1,p2,…,pn such that (ai+x)modm=bpi for all 1≤i≤n.
Examples inputCopy 4 3 0 0 2 1 2 1 outputCopy 1 inputCopy 1 inputCopy 3 2 0 1 outputCopy 1 inputCopy 5 10 0 0 0 0 1 2 1 2 1 0 0 outputCoput 0 두 가지 생각: 조건에 맞는 x를 찾을 때까지 a 시퀀스 b 시퀀스를 폭력적으로 일치시킵니다.b 시퀀스 일치, O (n) 에서 유일한 x 찾기
분명히 두 번째 해결 방법을 선택했다
#include 
using namespace std;
typedef long long ll; 
ll a[2050],b[2050],c[2050];
void check()
{
	ll n,m,i,j,x,minx;
	scanf("%lld%lld",&n,&m);
	for(i=0;i<n;i++)
		scanf("%lld",&a[i]);
	for(i=0;i<n;i++)
		scanf("%lld",&b[i]);
	sort(b,b+n);
	minx=m;
	for(i=0;i<n;i++)
	{
		x=(a[0]-b[i]+m)%m;
		for(j=0;j<n;j++)
			c[j]=(a[j]+x)%m;
		sort(c,c+n);
		for(j=0;j<n;j++)
		{
			if(c[j]!=b[j])
				break;
			if(j==n-1)
					minx=min(x,minx);
		}
	}
	printf("%lld",minx);
	return;
}
int main()
{
    check();
    return 0;
}

좋은 웹페이지 즐겨찾기