王は金貨を給料として忠実な騎士に支給した.質問G:金貨
タイトルは王が金貨を給料として忠実な騎士に支給したことを描いている.初日、騎士は金貨を受け取った.それから2日(翌日と3日目)、毎日2枚の金貨を受け取ります.それから三日(四、五、六日目)、毎日三枚の金貨を受け取ります.それから四日目(七、八、九、十日目)、毎日四枚の金貨を受け取る......;この給与支給パターンは、N日連続で毎日N枚の金貨を受け取ると、騎士はその後のN+1日連続で、毎日N+1枚の金貨を受け取る.
前のK日間、騎士が全部でどれだけの金貨を手に入れたか計算してください.入力入力は1行のみで、正の整数K(1≦K≦10000)が含まれており、金貨を発行する日数を示しています.出力は1行のみで、騎士が受け取った金貨の数という正の整数が含まれています.サンプル入力6サンプル出力14騎士に初日に金貨を受け取るように提示する.翌日と3日目、毎日2枚の金貨を受け取ります.四、五、六日目、毎日三枚の金貨を受け取ります.そのため、1+2+2+3+3+3=14枚の金貨を受け取った.
コードは簡単に見えますが、10分も早く考えました.
「n完全増分」を1個1,2個2連続として定義します...n個のnのシーケンス.例えば、1,2,2,2,2,3,3は完全な増加であるが、1,2,2,2,3,3は完全な増加ではない.
タイトルの金貨の数は2つの部分に分けることができて、前のkは完全に増加して、これはa部分で、その中のsize(a)の要素を設定します;および後のn−size(a)個の同じ数字は、いずれもk+1であり、これはb部分である.a部分とb部分の和加算を求めるのが答えです.a部分の和をsum(a)とする、明らかにb部分の和sum(b)を(n-size(a))(k+1)とする.
コード内のsumは、上記のk完全なインクリメントシーケンスの数と見なすことができる.sum=1+2+...+iを求め、sumがnより大きいとiが1ビット加算されすぎ、i-、このときのiが上のkとなる.
例として、8を入力と、金貨シーケンスは1,2,2,3,3,4,4となり、iは3となり、size(a)=6となる.
k完全増分シーケンスの和を観察すると、1^2+2^2+3^2+4^2+…+k^2で簡単に求めることができ、コード中のsumdはi完全増分シーケンスの要素和であり、sum(a)=sumdである.
また、sum(b)=(n−size(a)*(k+1)が最初に知られており、ここでkは現在iである.しかし、以前はi---でしたが、それはsumがnより大きいか等しいかのためです.このときsumは超えた部分を減算していない.したがってsize(a)=sum−(i+1)である.i+1は、当時sumが加算数(すなわちsumをn以上にする数)が、現在i--のiよりも1大きいためである.
では最後のansははっきり説明して、2つの部分とsum(a)+sum(b)でいいです.
今から見れば、この問題はそんなに考える必要はありません.直接シミュレーションすればいいです.以下はコードで、簡潔で分かりやすくて、注釈しません.
前のK日間、騎士が全部でどれだけの金貨を手に入れたか計算してください.入力入力は1行のみで、正の整数K(1≦K≦10000)が含まれており、金貨を発行する日数を示しています.出力は1行のみで、騎士が受け取った金貨の数という正の整数が含まれています.サンプル入力6サンプル出力14騎士に初日に金貨を受け取るように提示する.翌日と3日目、毎日2枚の金貨を受け取ります.四、五、六日目、毎日三枚の金貨を受け取ります.そのため、1+2+2+3+3+3=14枚の金貨を受け取った.
コードは簡単に見えますが、10分も早く考えました.
#include
#include
using namespace std;
int main() {
int i,j,sum=0,sumd=0,n,ans;
scanf("%d",&n);
for (i=1;;i++) {
sum+=i;
if (sum>=n) break;
}
i--;
for (j=1;j<=i;j++)
sumd+=j*j;
ans=(1+i)*(n-(sum-i-1))+sumd;
printf("%d
",ans);
return 0;
}
「n完全増分」を1個1,2個2連続として定義します...n個のnのシーケンス.例えば、1,2,2,2,2,3,3は完全な増加であるが、1,2,2,2,3,3は完全な増加ではない.
タイトルの金貨の数は2つの部分に分けることができて、前のkは完全に増加して、これはa部分で、その中のsize(a)の要素を設定します;および後のn−size(a)個の同じ数字は、いずれもk+1であり、これはb部分である.a部分とb部分の和加算を求めるのが答えです.a部分の和をsum(a)とする、明らかにb部分の和sum(b)を(n-size(a))(k+1)とする.
コード内のsumは、上記のk完全なインクリメントシーケンスの数と見なすことができる.sum=1+2+...+iを求め、sumがnより大きいとiが1ビット加算されすぎ、i-、このときのiが上のkとなる.
例として、8を入力と、金貨シーケンスは1,2,2,3,3,4,4となり、iは3となり、size(a)=6となる.
k完全増分シーケンスの和を観察すると、1^2+2^2+3^2+4^2+…+k^2で簡単に求めることができ、コード中のsumdはi完全増分シーケンスの要素和であり、sum(a)=sumdである.
また、sum(b)=(n−size(a)*(k+1)が最初に知られており、ここでkは現在iである.しかし、以前はi---でしたが、それはsumがnより大きいか等しいかのためです.このときsumは超えた部分を減算していない.したがってsize(a)=sum−(i+1)である.i+1は、当時sumが加算数(すなわちsumをn以上にする数)が、現在i--のiよりも1大きいためである.
では最後のansははっきり説明して、2つの部分とsum(a)+sum(b)でいいです.
今から見れば、この問題はそんなに考える必要はありません.直接シミュレーションすればいいです.以下はコードで、簡潔で分かりやすくて、注釈しません.
#include
using namespace std;
int main() {
int n,sum=0,cnt=0;
cin>>n;
for (int i=1;i<=n;i++) {
for (int j=0;j