글 읽기 - 어떤 반례가 있을까요?

p_ce1052 1년 전 0

As 부터 Ae까지의 모든 i에 대해 i + p*Av 중 두 번째 새와 처음으로 만나는 시점을 모두 모읍니다.

모은 수는 2000개이고 모은 각각의 숫자 T에 대해

T + k* lcm(Av, Bv)에서 첫 번째 새와 두 번째 새가 만납니다.

따라서 k를 Cv까지 iterate해보면서 세 번째 새가 T + k* lcm(Av, Bv)에서 보이는지 확인합니다.

이런 식으로 O(n^2)에 풀었는데 계속 틀리더라구요. 반례가 있을까요?

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
const int mx = 5000000;
int cnt[mx+10];
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	ll a,b,c; cin>>a>>b>>c;
	ll x,y,z; cin>>x>>y>>z;
	ll p,q,r; cin>>p>>q>>r;
	for(int i=b; i<=c; i++){
		for(int j=i; j<=mx; j+=a) cnt[j]++;
	}
	ll ans = INT64_MAX;
	ll LCM = a*x / __gcd(a,x);
	for(int i=y; i<=z; i++){
		for(int j=i; j<=mx; j+=x){
			if(cnt[j]){//첫 번째 새와 두 번째 새가 만난다면
				for(int k=0; k<=5000; k++){
					ll t = j+LCM*k;
					t%=p;
					if(q<=t && t<=r){
						ans = min(ans,j+LCM*k);
						break;
					}
				}
				break;
			}
		}
	}
	if(ans==INT64_MAX) cout<<-1;
	else cout<<ans;
}

sweetiemashiro 1년 전 1

6 3 5

5 3 4

11 9 9

p_ce1052 1년 전 0

감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어떤 반례가 있을까요?

p_ce1052 1년 전 0

sweetiemashiro 1년 전 1

p_ce1052 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말