2011年9月4日日曜日

Codeforces Beta Round #85 Div. 1 Only

Codeforces Beta Round #85 Div. 1 Only (9/4 21:00~23:00)

■A. Petya and Inequiations

問題

n,x,yが与えられる.
a12+a22+…+an2≥x
a1+a2+…+an≤y
を満たす正整数の列
a1,a2,…,an
を求めよ.なければ,-1を返せ.

解法

a1+a2+…+an
の最小値はn.次に,
a1+a2+…+an=y
としたとき,
a12+a22+…+an2
の最大値は,
ak=1 (1≤k≤n-1)
an=y-(n-1)
のとき,この値(=(n-1)+(y-(n-1))2)がx以上なら数列(ak)が答え.
#85 Div. 1 A. Petya and Inequiations

■B. Petya and Divisors

問題

2つの数列
x1,…,xn
y1,…,yn
が与えられる.
各(xi, yi)について,
xi mod k=0 かつ (∀j:i-yi≤j<i) xj mod k ≠ 0
なる正整数kの数を求めよ.

解法

xiの各約数di,kについて,
それがx1,…,xi-1の約数である最後のインデックスp[di,k]を記録しておく.
p[di,k]<i-yiなら条件を満たす.
その後,
p[di,k]=i
と更新.
#85 Div. 1 B. Petya and Divisors

■Result

o---- 484pts. 278th
1689 -> 1684

ドカーン.

0 件のコメント: