問題演習 注意：個人用なので見る意味ないよ

C - Snack　ABC148 / 

---

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点: $300$ 点

問題文

高橋君はパーティを企画しています。

パーティーでは参加者に $1$ 人 $1$ 個以上のお菓子を配る予定です。

高橋君は参加者の人数が $A$ 人か $B$ 人のどちらかになるだろうという予想を立てました。

どちらの場合でも均等に配りきることができるようなお菓子の個数の最小値を求めてください。

ただし、 $1$ 個のお菓子を分割して複数人で分けることはできないものとします。

制約

• $1\le A,B\le {10}^5$
• $A\ne B$
• 入力はすべて整数

C - HonestOrUnkind2　ABC147 / 

---

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : $300$ 点

問題文

$1$ から $N$ までの番号がついた $N$ 人の人がいます。彼らはみな、必ず正しい証言を行う「正直者」か、真偽不明の証言を行う「不親切な人」のいずれかです。

人 $i$ は $A_i$ 個の証言を行っています。人 $i$ の $j$ 個目の証言は $2$ つの整数 $x_{ij}$ , $y_{ij}$ で表され、$y_{ij}=1$ のときは「人 $x_{ij}$ は正直者である」という証言であり、$y_{ij}=0$ のときは「人 $x_{ij}$ は不親切な人である」という証言です。

この $N$ 人の中には最大で何人の正直者が存在し得るでしょうか？

制約

• 入力は全て整数
• $1\le N\le 15$
• $0\le A_i\le N-1$
• $1\le x_{ij}\le N$
• $x_{ij}\ne i$
• $x_{i{j}_1}\ne x_{i{j}_2}(j_1\ne j_2)$
• $y_{ij}=0,1$

 C - Buy an Integer ABC 146 / 

---

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : $300$ 点

問題文

高橋くんは整数を $1$ つ買いに整数屋さんに行きました。

整数屋さんには $1$ 以上 ${10}^9$ 以下の整数が売られていて、整数 $N$ を買うためには $A\times N+B\times d\left(N\right)$ 円が必要です。ここで、$d\left(N\right)$ は $N$ の十進表記での桁数です。

高橋くんの所持金が $X$ 円のとき、高橋くんの買うことのできる最も大きい整数を求めてください。ただし、買うことのできる整数が $1$ つもない場合は $0$ を出力してください。

制約

• 入力は全て整数である。
• $1\le A\le {10}^9$
• $1\le B\le {10}^9$
• $1\le X\le {10}^{18}$

 C - Average Length ABC145 / 

---

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : $300$ 点

問題文

座標平面上に $N$ 個の町があります。町 $i$ は、座標 ( $x_i$ , $y_i$ ) に位置しています。町 $i$ と町 $j$ の間の距離は $\sqrt{{\left({}_i-{}_j\right)}^2+{\left(y_i-y_j\right)}^2}$ です。

これらの町を全て $1$ 回ずつ訪れるとき、町を訪れる経路は全部で $N!$ 通りあります。$1$ 番目に訪れる町から出発し、$2$ 番目に訪れる町、$3$ 番目に訪れる町、$\dots$、を経由し、$N$ 番目に訪れる町に到着するまでの移動距離 (町から町への移動は直線移動とします) を、その経路の長さとします。これらの $N!$ 通りの経路の長さの平均値を計算してください。

制約

• $2\le N\le 8$
• $-1000\le x_i\le 1000$
• $-1000\le y_i\le 1000$
• $\left(x_i,y_i\right)\ne \left(x_j,y_j\right)$ ( $i\ne j$ のとき)
• (21:12 追記) 入力中の値はすべて整数である。

C - Walk on Multiplication Table ABC144 / 

---

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : $300$ 点

問題文

高橋君は無限に広い掛け算表の上にいます。

掛け算表のマス $(i,j)$ には整数 $i\times j$ が書かれており、高橋君は最初 $(1,1)$ にいます。

高橋君は $1$ 回の移動で $(i,j)$ から $(i+1,j)$ か $(i,j+1)$ のどちらかにのみ移ることができます。

整数 $N$ が与えられるので、$N$ が書かれているマスに到達するまでに必要な移動回数の最小値を求めてください。

制約

• $2\le N\le {10}^{12}$
• $N$ は整数である。