結果
問題 |
No.1884 Sequence
|
ユーザー |
![]() |
提出日時 | 2025-04-16 15:42:43 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,656 bytes |
コンパイル時間 | 261 ms |
コンパイル使用メモリ | 82,476 KB |
実行使用メモリ | 147,204 KB |
最終ジャッジ日時 | 2025-04-16 15:45:38 |
合計ジャッジ時間 | 11,936 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 WA * 5 TLE * 2 |
ソースコード
import sys import math def get_all_divisors(n): if n == 0: return [] divisors = set() i = 1 while i * i <= n: if n % i == 0: divisors.add(i) divisors.add(n // i) i += 1 return sorted(divisors) def compute_gcd(arr): current_gcd = arr[0] for num in arr[1:]: current_gcd = math.gcd(current_gcd, num) return current_gcd def solve(): input = sys.stdin.read().split() N = int(input[0]) A = list(map(int, input[1:N+1])) known = [x for x in A if x > 0] m = len(known) if m == 0: print("Yes") return if m == 1: print("Yes") return sorted_known = sorted(known) s0 = sorted_known[0] sm = sorted_known[-1] if s0 == sm: print("Yes") return diffs = [] for i in range(m-1): diffs.append(sorted_known[i+1] - sorted_known[i]) g = compute_gcd(diffs) if g == 0: print("Yes") return divisors = get_all_divisors(g) for d in divisors: if d <= 0: continue valid = True for s in sorted_known: if (s - s0) % d != 0: valid = False break if not valid: continue steps = (sm - s0) // d if steps + 1 > N: continue required = N - steps - 1 if required < 0: continue max_x = min(required, (s0 - 1) // d) if max_x >= 0: print("Yes") return print("No") if __name__ == "__main__": solve()