整数問題
問題 wavy numberとは、数字を10進法で書いたときの数字をx1,x2,x3,...,xnとすると x1<x2>x3<x4…が成り立つまたは、x1>x2<x3>x4…が成り立つ数のことを言う。Nの倍数のwavy numberでK番目に小さいものを求めよ。 答えが存在しない場合や10^14より大きく…
問題 二数a, bに対して次の操作ができる。 どちらか一方を2で割る(割り切れるときだけ) どちらか一方を3で割る(割り切れるときだけ) どちらか一方を5で割る(割り切れるときだけ) この操作を何度か行いa, bを等しくしたい。 必要な操作の回数の最小値は…
問題 n個の数aiが与えられる。 m = a1 * a2 * ... * anとする。 mをn個の数の積b1 * b2 * ... * bnとしてあらわす方法は何通りあるかmod 10^9 + 7で答えよ。 制約条件 n≦500 ai≦10^9
問題 全ての頂点が格子点であるような、単純多角形で、周の長さがLであるものを考える。 これらのうち、頂点数が最も少ないものであって、それが複数あるときは 最も長い辺と短い辺の長さの差が最小であるものを求めよ。 答えには最も長い辺と短い辺の長さの…
evima先生作問。 問題 自然数A, Bが与えられる。 最初X = 1で、Xに次の操作を繰り返し適用してX = A^Bとしたい。 操作の適用回数の最小値を求めよ。 1回の操作では以下のうちどれかを適用できる。 好きな素数pを選んでX = p*Xとする Xの好きな約数dを選んで…
問題 http://tdpc.contest.atcoder.jp/tasks/tdpc_dice
問題 二人のプレイヤーがn個の山を使って次のようなゲームをする。 手番のプレイヤーは、山をひとつ選ぶ。 この山の石の数をXとする。Xより小さいXの約数Yを選び、この山の石の数をYに変える。 操作のできなくなったプレイヤーの負け 最初の山のうち[A, B]の…
問題 ある数がn-dramaticであるとは、 n倍したときに10進法での最下位の数字が、最上位に巡回シフトされるような数を言う。最下位がkであるようなn-dramaticな数のうち最小であるものを求めよ。 制約条件 n, k≦9
問題 ある数が2で割り切れるかは、下一桁が2で割れるかを見ればよい。このような判別の仕方を2-typeという。 ある数が3で割り切れるかは各桁の和が3で割れるかを見ればよい。このような判別の仕方を3-typeという。 ある数が6で割り切れるかは、2-typeと3-typ…
問題 n段の階段があり、ちょうどn枚の長方形の板でできている。 長方形の板には重なりやはみだしがない。 このようにして作れる階段を全部つくり、階段を(一つの階段は一色で)それぞれk色のどれかで塗る。 このようにして出来上がるものは何通りあるか、mo…
問題 ある整数の素因数が全てk以下であるとき、その数はk-smoothであるという。 与えられた整数N以下の正の整数のうちk-smoothであるものの数を求めよ。 制約条件 N≦200000 k≦200000
問題 正の整数a,b,c,dに対するFrobenius数とは、w,x,y,z≧0に対してwa+xb+yc+zdとして表すことのできない最大の数である。1000000以下の、wa+xb+yc+zdとして表せない数の個数および、Frebonius数を求めよ。 Frebonius数が1000000より大きい場合-1を出力せよ。…
問題 x,y,zがN以下であるようなピタゴラス数(x^2+y^2=z^2を満たす自然数)のうち、 互いに素なものの個数および、N以下で、(互いに素ではないピタゴラス数も含む)どのピタゴラス数の1つにもなっていないような自然数の個数を出力せよ。 制約条件 N≦1000000
問題 lucky numberとは、4,7のことを言う。 almost lucky numberとは、各桁のうちlucky numberでない数が一つ以下の数のことを言う。 a以上b以下のalmost lucky numberの数を求めよ。 制約条件 a,b ≦ 10^16
数論+DPでスーパー苦手な感じの。 問題 4または7で割り切れる数をラッキーな数とする。 a以上b以下の全てのラッキーな数を10進数で表したとき、各数字の出現回数を求めよ。 制約条件 a,b≦10^16
問題概要 日本語なので本文参照(http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0222&lang=jp)n,n+2,n+6,n+8の4つの数字がすべて素数であるとき、それらを4つ子素数と呼ぶことにする。 Nlt;1億なるNが与えられたとき、4つ子素数で…
問題概要 maxNumまでの数に対してエラトステネスの篩を行ったとき、 最後に消去される合成数を求めよ。 maxNum≦10^9を満たす。
こういう問題すらすら解けるようになりたいorz デバッグ力もないし、とりわけ方針があやふやだからバグが何処にあるのかわからずはまって疑心暗鬼になり時間だけを浪費する。 問題概要 ある国の、1年目の7/1に一組のウサギのつがいがいる。 毎年3/1に満一歳…
Practiceで解いた奴。
minx≦x≦maxx,miny≦y≦maxy,minz≦z≦maxzを満たす整数の組 (x,y,z)の個数を求めよ。 ただし1≦minx,miny,minz,maxx,maxy,maxz≦1,000,000,000である。 数字が10億と大きいのでナイーブにループを回して数え上げる方法は取れない。 なんとか√10億(≒3万)くらい…
整数列{Ak}(0≦k<n)および非負整数Pが与えられるとき、 不等式|A0-X|+|A1-X|+……+|An-1-X| を満たすXの個数を求めよ。 ただし1 数え上げでは時間切れになるので少し計算が必要。 Aをソートして、akan-1の場合、X=akの場合に分けて それぞれ加算という方針で。…
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2086階乗の末尾の0の個数を求める問題。 基数を素因数分解して因数毎に何個入ってるか調べる。 ……だけなのだけどlong longではREになる模様。 unsigned long longならば最大のテストケ…
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2048素数表作る。 上位のCPU時間が短いのは篩の方法が違うからなのだろうか……