Problem:


Score : 400 points

Problem Statement

There are N squares in a row.
The leftmost square contains the integer A, and the rightmost contains the integer B. The other squares are empty.

Aohashi would like to fill the empty squares with integers so that the following condition is satisfied:

For any two adjacent squares, the (absolute) difference of the two integers in those squares is between C and D (inclusive).

As long as the condition is satisfied, it is allowed to use arbitrarily large or small integers to fill the squares.
Determine whether it is possible to fill the squares under the condition.

Constraints

3 \leq N \leq 500000

0 \leq A \leq 10^9

0 \leq B \leq 10^9

0 \leq C \leq D \leq 10^9

All input values are integers.

Input

Input is given from Standard Input in the following format:

N A B C D

Output

Print YES if it is possible to fill the squares under the condition; print NO otherwise.

Sample Input 1

5 1 5 2 4

Sample Output 1

YES

For example, fill the squares with the following integers: 1, -1, 3, 7, 5, from left to right.

Sample Input 2

4 7 6 4 5

Sample Output 2

NO

Sample Input 3

48792 105960835 681218449 90629745 90632170

Sample Output 3

NO

Sample Input 4

491995 412925347 825318103 59999126 59999339

Sample Output 4

YES



Sample input:
5 1 5 2 4


Sample output:
YES

Submission status: Runtime Error

Solution code:
from fractions import gcd
N,A,B,C,D=map(int,input().split())
if B<A:
	A,B=B,A
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = egcd(b % a, a)
        return (g, y - (b // a) * x, x)
if C==0 and D==0:
    if A==B:
        print("YES")
    else:
        print("NO")
elif C==0 or D==0:
    if D==0:
        C,D=D,C
    if (B-A)%D==0 and abs(B-A)//D<N:
        print("YES")
    else:
        print("NO")
else:
    if abs(B-A)%gcd(C,D):
        assert False
        print("NO")
    else:
        (g,x,y)=egcd(C,D)
        times=(B-A)//g
        #xC+yD=B-A
        x*=times
        y*=times
#        x+=D*alpha
#        y-=C*alpha
        C//=g
        D//=g
        alphamin=-10**100
        alphamax=10**100
        while alphamax-alphamin>1:
            mid=alphamin+(alphamax-alphamin)//2
            if abs(x+mid*D)+abs(y-mid*C)>abs(x+mid*D+D)+abs(y-mid*C-C):
                alphamin=mid
            else:
                alphamax=mid
        x=x+alphamax*D
        y=y-alphamax*C
        a=list(range(-50,50))
        if any(abs(x+i*D)+abs(y-C*i)<N and (abs(x+i*D)+abs(y-i*C))%2!=N%2 for i in a):
            print("YES")
        else:
            print("NO")

Submission status: Runtime Error

Solution code:
import numpy as np
k = np.abs(B-A)//D
l = np.abs(B-A)%D
times = k + 2 * np.ceil (l/ (D-C))
if times > N-2:
    print("NO")
else:
    print("YES")

Submission status: Runtime Error

Solution code:
#N A B C D
s = input().split()
N = int(s[0])
A = int(s[1])
B = int(s[2])
C = int(s[3])
D = int(s[4])

operation = [-D , -C , +C , +D]

#A に opeをすると 4通りの答えがかえってくる
#残り演算回数を出す
#答えと残り演算回数から、到達可能な数字の範囲を出す
#答えがあればopeを行う
#答えがなければそこで終了
#最後まで到達できれば終了

def Kanousei(x , left) : 
    return [x - left * D , x - left * C , x + left * C , x + left * D]

def Kanousei_hantei(kanousei , left) : 
    if left == 1 : 
        return ( (B >= kanousei[0])  & (B <= kanousei[1]) ) |  ( (B >= kanousei[2]) & (B <= kanousei[3]) ) 
    else : 
        return ( (B >= kanousei[0])  ) |  (  (B <= kanousei[3]) ) 

turn = 1
left = N - turn
kanousei = Kanousei(A , left)
kanousei_hantei = Kanousei_hantei(kanousei , left)

def search(x , turn) : 
    left = N - turn
    kanousei = Kanousei(x , left)
    kanousei_hantei = Kanousei_hantei(kanousei , left)
    if kanousei_hantei == True :   #可能性があったらopeする
        if left == 1 :
            print(x)
            return True
        else : 
            for ope in operation : 
                flag = search(x + ope , turn + 1 )
                return flag
    return False

if search(A , turn) : print("YES")
else : print("NO")

Submission status: Runtime Error

Solution code:
from fractions import gcd
N,A,B,C,D=map(int,input().split())
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = egcd(b % a, a)
        return (g, y - (b // a) * x, x)
if C==0 and D==0:
    if A==B:
        print("YES")
    else:
        print("NO")
elif C==0 or D==0:
    if D==0:
        C,D=D,C
    if (A-B)%D==0 and abs(A-B)//D<N:
        print("YES")
    else:
        print("NO")
else:
    if abs(B-A)%gcd(C,D):
        print("NO")
    else:
        assert False
        (g,x,y)=egcd(C,D)
        times=(B-A)//g
        #xC+yD=B-A
        x*=times
        y*=times
#        x+=D*alpha
#        y-=C*alpha
        alphamin=-10**100
        alphamax=10**100
        while alphamax-alphamin>1:
            mid=alphamin+(alphamax-alphamin)//2
            if abs(x+mid*D)+abs(y-mid*C)>abs(x+mid*D+D)+abs(y-mid*C-C):
                alphamin=mid
            else:
                alphamax=mid
        x=x+alphamax*D
        y=y-alphamax*C
        a=list(range(-50,50))
        if any(abs(x+i*D)+abs(y-C*i)<N and (abs(x+i*D)+abs(y-i*C))%2!=N%2 for i in a):
            print("YES")
        else:
            print("NO")

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <stdio.h>      /* printf, scanf, NULL */
#include <stdlib.h>
#include <math.h>
#include <iomanip>      // std::setprecision
#include <algorithm>
#include <vector>
using namespace std;

int n,a,b,c,d,e;

int main(){
    cin >> n >> a >> b >> c >> d;
    long long i, j, k;
    long long dist = b - a;
    long long minp, maxp, minn, maxn;
    minp = b + c - a; maxp = b + d - a; minn = b - d - a; maxn = b - c - a;
    //cout << minp << " " << maxp << " " << minn << " " << maxn << "\n";
    for(i = 0; i <= n - 2; i++){
        long long mini,maxi;
        mini = i * c - (n - 2 - i) * d;
        maxi = i * d - (n - 2 - i) * c;
        //cout << i << " " << mini << " " << maxi <<"\n";
        if(minp <= maxi && maxp >= mini){
            cout << "YES" << "\n";
            return 0;
        }
        else if(minn <= maxi && maxn >= mini){
            cout << "YES" << "\n";
            return 0;
        }
    }
    cout << "NO" << "\n";
    return 0;

}

Submission status: Runtime Error

Solution code:
from math import gcd
N,A,B,C,D=map(int,input().split())
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = egcd(b % a, a)
        return (g, y - (b // a) * x, x)
if C==0 and D==0:
    if A==B:
        print("YES")
    else:
        print("NO")
elif C==0 or D==0:
    if D==0:
        C,D=D,C
    if (A-B)%D==0 and abs(A-B)//D<N:
        print("YES")
    else:
        print("NO")
else:
    if abs(B-A)%gcd(C,D):
        print("NO")
    else:
        (g,x,y)=egcd(C,D)
        times=(B-A)//g
        #xC+yD=B-A
        x*=times
        y*=times
#        x+=D*alpha
#        y-=C*alpha
        alphamin=-10**36
        alphamax=10**36
        while alphamax-alphamin>1:
            mid=alphamin+(alphamax-alphamin)//2
            if abs(x+mid*D)+abs(y-mid*C)>abs(x+mid*D+D)+abs(y-mid*C-C):
                alphamin=mid
            else:
                alphamax=mid
        x=x+alphamax*D
        y=y-alphamax*C
        a=[-1,0,1]
        if any(abs(x+i*D)+abs(y-C*i)<N and (abs(x+i*D)+abs(y-i*D))%2!=N%2 for i in a):
            print("YES")
        else:
            print("NO")

Submission status: Runtime Error

Solution code:
# encoding:utf-8
import math

def main():
	N, A, B, C, D = list(map(int, input().split()))
	cur_list = [(A, A)]

	for i in range(N - 1):
		cur_list = calcNextList(cur_list, C, D)
		cur_list =[x for x in cur_list if x[0] >= 0 and x[1] <= 10 ** 9]
		cur_list = merge(cur_list)

	print(cur_list)
	for x in cur_list:
		if x[0] <= B <= x[1]:
			print("YES")
			break
	else:
		print("NO")


# def Enlarge(input_taple, D):
# 	return((input_taple[0] - D, input_taple[1] + D))

def Duplicate(input_taple, C, D):
	first_tuple = (input_taple[0] + C, input_taple[1] + D)
	second_tuple = (input_taple[0] - D, input_taple[1] - C)
	return([first_tuple, second_tuple])

def calcNextList(cur_list, C, D):
	next_list = []
	for x in cur_list:
		next_list.extend(Duplicate(x, C, D))
	return(next_list)

def merge(cur_list):
	cur_list.sort()

	next_list = [cur_list[0]]

	for i in range(len(cur_list) - 1):
		if next_list[-1][1] >= cur_list[i+1][0]:
			merged = (next_list[-1][0], max(next_list[-1][1], cur_list[i+1][1]))
			next_list.pop()
			next_list.append(merged)
		else:
			next_list.append(cur_list[i+1])

	return(next_list)

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import sys

def diff(N,A,B,C,D):
    mini = (B+(N-1)*D-A)/(C+D)
    for i in xrange(mini, N-1):
        lower_bound = A + i*C - (N-i-1)*D
        upper_bound = A + i*D - (N-i-1)*C
        print(lower_bound, upper_bound)
        if lower_bound <= B and B <= upper_bound:
            return True
        elif B < lower_bound:
            return False

str = sys.stdin.readline().strip() #"491995 412925347 825318103 59999126 59999339"
N,A,B,C,D = map(int,str.strip().split(" "))
print("YES" if diff(N,A,B,C,D) else "NO")