2011-11-01から1ヶ月間の記事一覧
問題 自然数nが与えられる。 nを素因数分解して出力せよ。 制約条件 言語はbefunge n≦255
問題 Tribonacci数とはt0=t1=0, t2=1 tn+3=tn+2+tn+1+tnを満たす数列を言う。 この数列のn番目の項をmod 26で求めよ。 制約条件 言語はbefunge n≦100
問題 三つの整数a,b,cが与えられる。 a^b mod cを求めよ。 制約条件 言語はbefunge a,b,c≦100
問題 n個の自然数が与えられる。 それらの和を求めよ。 制約条件 言語はbefunge n≦100 それぞれの数≦100
問題 与えられた文字列を反転した文字列を出力せよ。 制約条件 言語はbefunge 文字列の長さ≦100
問題 自然数nが与えられる。2n^2-nを求めよ。 制約条件 言語はbefunge n≦100
問題 nxnのチェス盤と二つの駒を使って二人が次のようなゲームをする。 最初先手の駒は(y1,x1)の位置に、後手の駒は(y2,x2)の位置におかれている。 二人は交互に、駒を上下左右の好きな方向へ、先手は1歩、後手は1歩または2歩動かす。 相手の駒を取ったプレ…
問題 nxmマスのタイルをk色を使って塗る。 ただし以下の条件が満たされなければならない。 どのような縦の直線にそってマスを(空でない)二つに分割したときも、両方で使われている色の数が等しい。 条件を満たすタイルの塗り方は何通りか、mod 10^9+7で求…
問題 n頂点m本の辺からなる無向グラフが与えられる。 このグラフの辺に適当な向き付けを与え、有向グラフにして、 全体を強連結(任意の2頂点u,vについてuからvへのパスが存在する)にすることができるか答えよ。できる場合は具体的な向き付けを一つ出力せよ…
問題 n人の人が以下のようなルールで列に並ぶ。 i番目の人が来て、列の最後尾に加わる。i番目の人は重要度a[i]と、常識度c[i]を持っている。 一つ前の人の重要度a[i-1]が、自分の重要度より低かったら、その人前へ割り込む。 割り込みはc[i]回だけできる。 n…
問題 n個のハンガーが一列に並んでいて、左から順に1からnの番号がついている。 以下のようなクエリがq個来るので処理せよ。 0 l r l以上r以下の番号のハンガーのうち、上着がかけられているハンガーの数を出力する。 (0以外の数字) 数字のidをもつ人が、次…
問題 m個の塩基配列が与えられる。 n文字の塩基配列で、全ての文字が塩基配列にカバーされている (すべてのiに対して、ある整数l≦i≦rが存在して、塩基配列のl文字目からr文字目までがいずれかの塩基配列に等しい) ようなものの数をmod 10^9+9で求めよ。 制…
問題 n桁のb進数の数のうち、leading zeroがないものを全てノートに書く。 1ページあたりc個の数字を書くものとするとき、最後のページに書かれる文字の数はいくつか求めよ。 制約条件 b≦10^(10^6) n≦10^(10^6) c≦10^9
問題 hxwマスのグリッドのそれぞれに、a-zの文字またはS,Tが書かれている。 SからTのマスへのパスを考えたとき、パス上にある文字をつなげた文字列をsとする。 sに現れるアルファベットの数がk個以下で、最小の長さをもつようなsを求めよ。 複数ある場合は辞…
問題 N行M列のグリッドがある。 このグリッドのi行j列にロボットがいて、 ロボットは1ターンに1度次の動きのうち、可能なものを等確率で一つ実行する。 その場から動かない 一列下の列に動く(最下段についたら止まる) 左に動く(グリッドからはみでる場合…
問題 n項の数列が与えられる。 この数列に対してt個のクエリに答えよ。クエリ: 整数l,rに対して、次の値を求める。 a[l],a[l+1],...,a[r]における、値sの出現回数をKsとする。 全ての整数sについて、Σs*Ks*ks 制約条件 n,t≦200000 1≦a[i]≦10^6
問題 n体の敵がいて、それぞれのHPはh[i]である。 魔法を敵iに向けて放つと、敵iにaのダメージを与え、(もし隣がいるなら)隣にもbずつのダメージを与える。 敵1と敵nには直接魔法を放つことはできない。 全ての敵のHPを0より小さくするのに必要な魔法の回…
問題 どの要素も互いに異なる項数nの数列a[i]が与えられる。 a[i],a[j]について、ある整数bが存在して、 {a[i],a[j],b} = {x^2, y^2, z^2 | x^2+y^2=z^2 かつx,y,zは互いに素} と書けるとき、a[i]とa[j]を同一視する。 a[i]は何個の部分に分かれているか、求…
問題 10円のチケットをn+m枚販売する。 この国には10円と20円の二つの硬貨しかなく、 10円のみを持った客がn人、20円のみを持った客がm人来るものとする。 手元にはk枚の10円がある。 客がランダムな順番で来るとき、全ての客におつりをきちんと返せる確率は…
問題 核反応を考える。 反応前のn個の元素のリストおよび、 反応後のm個の元素のリストが与えられる。 反応前の元素から核反応により反応後の元素を過不足なく作れるか判定せよ。 ただし、反応後の元素は直接作られなければならない。(途中で別の元素を経由…
問題 人に次のようなルールで所属するファミリーを決める。 ファミリーは4つある。 あらかじめ決められたファミリーがある人は、そのファミリーに所属する。 そうでない人は、今までに割り振られた人数が最も少ないファミリー(複数ある場合好きなものを選べ…
問題 文字列の、「4文字以下の(必ずしも連続しない)部分文字列」をその文字の略称にできるとする。与えられたn個の文字列の略称を、重複なく定められるかどうかを判定せよ。 重複なく定められる場合、その略称をどれか一組出力し、 そうでない場合-1を出力…
問題 n個の都市と、それらをつなぐm本の道がある。 1番の都市からn番の都市へ、使う数の道を最小にして移動したい。 ただし、決められた都市の組(a[i],b[i],c[i])がいくつかあり、 それらをこの順に通ることはできない。 n番の都市へ、使う道の本数を最小に…
問題 4つの整数が円周上に並んでいる。 この数に対して次の操作を1000回以下行い、 全ての数を1にすることができるか。 隣合う二数に1を足す 隣合う偶数を2で割る できるならその操作の内容をどれか一つ具体的に出力し、(最短手順でなくともよい) できない…
問題 トランプ54枚のうちnm枚がn行m列に並んでいる。ジョーカーを余っているカードの好きなものと取り替えてよい。 このとき、次のうちいずれかの条件を満たす3x3の正方形を重ならないように二つ取ることが出来るか判定せよ。 全てのスートが同じ 全ての数字…
問題 重み付き無向木が与えられる。 このグラフの二点を結ぶパス全てについて、 パス上で重みが最も重い辺(複数ある場合全て)に木を一本植えるという操作をする。 全ての操作の後、最も木が植えられている辺に植えられている木の本数および、 その本数の木…
問題 2*n-1個の箱があり、それぞれにりんごがa[i]個、みかんがo[i]個入っている。 この中からn個の箱を選び、選ばれた箱に入っているりんごの個数が全体のりんごの合計の半分以上、かつみかんの個数が全体のみかんの半分以上になるようにすることはできるか…
問題 WxHのチョコレートがある。これをn本の線分にしたがって切断する。 n本の直線は、両端点(x1,y1),(x2,y2)によって与えられる。切断後のそれぞれのチョコレートの片の面積を求めよ。 制約条件 W,H≦100 線分は座標軸に平行かつx1,y1,x2,y2は全て整数
問題 n個の頂点からなる有向グラフが与えられる。 それぞれの辺には最小流量、最大流量、およびコストが定められている。辺(u,v)に流量cのフローを流した場合、 c>0ならコスト(u,v)+c^2のコストがかかり、 c=0ならコストはかからない。 1番の頂点からn番の…
問題 数列C[i]が与えられる。 C[i]の各項について、 C[i]が正なら、連続する任意のC[i]項が正 C[i]が負なら、連続する任意の-C[i]項が負 という制約をつける。 この制約を全て満たす数列のうち、長さが最大のものを答えよ。無限に長い数列が作れる場合、-1を…