問題の要約 長さNの正整数のみからなる数列A=(A1,...,AN)がある。 Aを10^100回連結した数列を数列Bとする。 Bの項を前から順に足したとき,和が初めてXを超えるのは何項目まで足したときか? すなわち,以下の式を満たす最小の整数kを求めよ。 Σ{i=1,k}Bi > X制…

問題の要約 整数A,BがK進法表記で与えられる。 A*Bを10進法表記で出力しろ。制約 1<=K<=10 1<=A,B<=10^5入力 K A B考え方 1,A,Bを10進法に直してからA*Bを出力すればよい。 2,K進法のXを10進法に直す方法。 K進法の第一位をX1として10進法に直すとX1*(K^0)と…

問題の要約 A以上B以下であるようなCの倍数を,1つ出力しろ。 条件を満たす数が存在しない場合は-1を出力しろ。制約 1<=A<=B<=1000 1<=C<=1000入力 A B C考え方 1,A,Bの範囲が小さいので,1*CからCの倍数をB以下まで探索する。 2,A以上のCの倍数があったらそれ…

問題の要約 今,目の前にN種類のチーズがある。 i種類目のチーズは1[g]あたりのおいしさがAiで,Bi[g]ある。 ピザのおいしさは,ピザに乗せたチーズのおいしさの総和で決まる。 乗せたチーズの重さは合計でW[g]以下である必要がある。 この条件のもとで,可能な…

問題の要約 正整数A,Bが与えられる。 A+Bを(十進法で)計算する時,繰り上がりが生じないならEasy,生じるならHardと出力する。制約 A,Bは整数 1<=A,B<=10^18考え方 1,制約からA,Bの値は大きすぎるのでstringで入力をもらう。 2,A,Bを一の位から順に,数字に直し…

問題の要約 縦2行,横2列のグリッドがある。 このグリッドは,各マスが黒か白であり,少なくとも2つの黒マスを含む。 各マスの色の情報は文字列S1,S2として,以下の形式で与えられる。 ・文字列Siのj文字目が#であれば上からiマス目,左からjマス目は黒 ・文字列S…

問題の要約 1から2Nの番号がついた2N人でじゃんけん大会をする。 大会はMラウンドからなり,各ラウンドは,全ての人が1度ずつ参加するような1対1のN試合からなる。 i=1,...,Mについて,iラウンド目の終了時点での順位を次のように決める。 ・iラウンド目までの…

問題の要約 N人の学生が試験を受けた。学生には学生1,学生2,...,学生Nと番号がついていて,学生iはai点を取った。 P点未満の点数を取った学生は"不可"となり単位を取得できない。"不可"となった学生の人数を答えよ。制約 1<=N<=10^5 1<=P<=100 1<=ai<=100(1<=i…

問題の要約 0以上9999以下の整数Nが与えられる。 Nの先頭に必要なだけ0をつけ,4桁の文字列にしたものを出力せよ。制約 0<=N<=9999入力 N考え方 1,文字列で入力を受け取る 2,文字列の長さ-4個の0を文字列の先頭に加える。実際のプログラム#include<iostream>#include<string> us</string></iostream>…

問題の要約 N本の導火線を一直線に接着したものがある。 左からi本目の導火線の長さはAicmで,1秒当たりBicmの一定の速度で燃える。 この導火線の左端と右端から同時に火をつけるとき,2つの火がぶつかる場所が着火前の導火線の左端から何cmの地点か求めよ。制…

問題の要約 空でない文字列に対し,先頭の文字を末尾に移動する操作を左シフト,末尾の文字を先頭に移動する操作を右シフトと呼ぶ。 英小文字からなる空でない文字列Sが与えられる。 Sに対し左シフトと右シフトをそれぞれ好きな回数(0回でもよい)行って得られ…

問題の要約 財布の中に100円硬貨が1枚以上入っており,それ以外には何も入っていない。 財布の中の合計金額がX円である可能性はあるか?制約 0<=X<=1000入力 X考え方 1,Xが100の倍数であるかどうかで条件分岐する。ただし,問題文からXが0のときは例外とする。#…

問題の要約 xy平面上に1からNまでの番号の付いたN個の点がある。 点iは(Xi,Yi)にあり,相異なる2点は異なる位置に存在する。 このN点から3点を選ぶとき,選ばれた3点を線分で結んだ図形が正の面積を持つ三角形になるような点の選び方の総数を求めよ。制約 入力…

問題の要約 縦H行,横W列のマス目があり,各マスには1つの整数が書かれている。 上からi行目,左からj列目のマスに書かれている整数はAi,j。 マス目が下記の条件を満たすか判定しろ。 1<=i1<i2<=Hおよび1<=j1<j2<=Wを満たすすべての整数の組(i1,i2,j1,j2)について,Ai1,j1+Ai2,j2 <= Ai2,j1+Ai1,j2が成り立つ。制約 2<=H,W<=50 1<=Ai,j<=10^9考え方 1,i1,i2,j1,j2を1ずらす。 1<=i1<i2<=H,1<=j1<j2<=W => 0<=i1</i2<=hおよび1<=j1<j2<=wを満たすすべての整数の組(i1,i2,j1,j2)について,ai1,j1+ai2,j2>

問題の要約 末尾がerまたはistであるような文字列Sが与えられる。 Sの末尾がerである場合はerを,istである場合はistを出力しろ。制約 2<=|S|<=20 Sは英小文字のみからなる。 Sの末尾はerまたはistである。入力 S考え方 1,erとistで条件分岐を考える。 制約か…

問題の要約 N=2^20項からなる数列A=(A0,A1,...,AN-1)があり,はじめ,全ての要素は-1。 Q個のクエリを順番に処理せよ。 i(1<=i<=Q)個目のクエリはti=1またはti=2を満たす整数ti及び整数xiで表され,内容は以下の通り。 ・ti=1のとき,以下の処理を順番に行う。 1…

問題の要約 N人の生徒が4日間にわたる試験を受けている。 それぞれの日に行われる試験は300点満点。すなわち,4日間を通した試験の満点は1200点。 現在3日目までの試験が終わり,これから4日目の試験が行われようとしている。 i(1<=i<=N)番目の生徒はj(1<=j<=3…

問題の要約 N人の友達がいる。それぞれ友達1,友達2,...,友達Nというあだ名で呼ばれている。 ある日,秘密を友達Xに知られてしまう。 i=1,2,...,Nについて,友達iが秘密を知ったとき,友達Aiがまだ秘密を知らなければ,友達iは秘密を友達Aiに教えてしまう。 秘密…

問題の要約 毎日S時0分に部屋の電気をつけ,毎日T時0分に消す。 電気をつけている間に日付が変わることもある。 X時30分に部屋の電気がついているかどうか判定しろ。制約 0<=S,T,X<=23 S≠T入力 S T X考え方 1,まずS<T,S>Tで条件分岐したい。 2,S<Tのとき 電気がついているのはSからTまで。 X時30分のときに電気がついているか判定しなければいけない。 XはS以上T未満の範囲ならok。 3,S>Tのとき 電気がつい</tのとき></t,s>…

問題の要約 電車がN個あり,電車1,電車2,...,電車Nと名前がついている。 はじめ電車どうしは連結しておらず,バラバラ。 クエリがQ個与えられるので,与えられた順番に処理しなさい。 クエリは次の3種類のいずれか。 ・1 x y:電車xの後部と,電車yの前部を連結さ…

問題の要約 10^100行7列の行列Aがあり,任意の整数対(i,j)(1<=i<=10^100,1<=j<=7)についてその成分は(i-1)*7+j。 N行M列の行列Bが与えられるので,BがAの一部の短形領域を(向きを変えずに)切り出したものであるかを判定しろ。制約 1<=N<=10^4 1<=M<=7 1<=Bi,j<…

問題の要約 N頂点N-1辺の木が与えられる。 頂点は1,2,...,Nの番号がついており,i番目の辺は頂点aiと頂点biを結んでいる。 この木がスターであるか判定しろ。 ただしスターとは,1つの頂点から他の全ての頂点に1本ずつ辺が出ている木のことである。制約 3<=N<=…

問題の要約 英小文字のみからなる長さ3の文字列Sが与えられる。 Sの各文字を並び替えて得られる文字列は,何種類あるか?制約 Sは英小文字のみからなる長さ3の文字列 入力 S 考え方 1,これは同じものがある順列である。 2,順列はC++ではnext_permutationで生成…

問題の要約 直交座標の上にN個の街があり,1,2,...,Nと番号がつけられている。 街iは地点(xi,yi)にあり,2つの異なる番号の街が同じ座標にあることはない。 魔法があり,魔法は整数の組(a,b)によって識別されていて,地点(x,y)にいるときに魔法(a,b)を使うと,(x+…

問題の要約 武術家の覚えられる技がN個あり,技1,2,...,Nと名前がついている。 1<=i<=Nについて,技iを習得するには時間Tiの修練が必要で,さらに,修練の開始時点で技Ai,1,Ai,2,...,Ai,Kiをすでに習得している必要がある。 ここで,1<=j<=Kiについて,Ai,j

問題の要約 1からNまでの番号のついたN個の数列が与えられる。 数列iは、長さLiでj(1<=j<=Li)番目の要素がai.jであるような数列である。 数列iと数列jは,Li=Ljかつすべてのk(1<=k<=Li)に対してai,k=aj,kが成り立つとき同じであるとみなす。 同じ数列は1種類…

問題の要約 実数Xが小数第三位まで入力される。 Xを小数第一位で四捨五入した結果として得られる整数を出力しなさい。制約 0<=X<=100入力 X考え方 1,小数を四捨五入する関数があればよい。 2,C++にはround関数があるのでそれを使う。 実際のプログラム#inclu…

問題の要約 N個の部署があり,i(1<=i<=N)番目の部署にはAi人の社員がいる。異なる部署に同じ社員はいない。 1つのプロジェクトをK個の部署から1人ずつ選出して作り、ちょうどK人から構成したい。 プロジェクトは最大でいくつ作れるか?1人が複数のプロジェクト…

問題の要約 正の整数Nが与えられる。 A<=B<=CかつABC<=Nであるような正の整数の組(A,B,C)の個数を求めよ。 制約上2^63未満であることが保証されている。制約 1<=N<=10^11入力 N 考え方 1,A=1,B=1のとき,Cは1からNまでのN個ある。 A=1,B=2のとき,Cは2からfloo…

問題の要約 1からNの番号のついたN人の人がいる。 人iはビルの面積をSiと予想。 本来のビルの面積は4ab+3a+3bである(a,bは正の整数)。 N人のうち、予想した面積が確実に誤りであるとわかる人数を求めよ。制約 1<=N<=20 1<=Si<=1000入力 N S1,...,SN 考え方 1…