11. 縦横斜め4つの数字の積の最大を出力する
実質、下、右、斜め下右、左だけでいいです。
#define smax 20 int table[smax][smax]; int main(void){ rep(i,smax) rep(j,smax) cin >> table[i][j]; int res=-1; rep(i,smax){ int a[4]={}; rep(j,smax){ if(j+3 < smax) a[0] = table[i][j]*table[i][j+1]*table[i][j+2]*table[i][j*3]; //右 if(i+3 < smax) a[1] = table[i][j]*table[i+1][j]*table[i+2][j]*table[i+3][j]; //下 if(i+3 < smax && j+3 < smax) a[2] = table[i][j]*table[i+1][j+1]*table[i+2][j+2]*table[i+3][j+3]; if(i-3 >= 0 && j+3 < smax) a[3] = table[i][j]*table[i-1][j+1]*table[i-2][j+2]*table[i-3][j+3]; res = max(res,*max_element(a,a+4)); } } cout << res << endl; return 0; }
12. 三角数の約数で501個以上の約数をもつ最初の値を求める
約数の個数には素因数分解を使うと楽にできます。
bool solve(int a){ map<int,int> ma; int i=2; for(;;){ if(a == 1) break; if(a % i == 0){ ma[i]++; a /= i; } else i++; } int s=1; for(map<int,int>::iterator it = ma.begin();it != ma.end();it++){ s *= (it->second+1); } if(s >= 501) return true; else return false; } int main(void){ int a=1; for(int i=2;;i++){ if(solve(a+i)){ cout << a+i << endl; break; } a += i; } return 0; }
13. 50桁の数字100個を足した値の10桁までを表示させます
boostのmultiprecisionを使いました。
#include<boost/multiprecision/cpp_int.hpp> #include<boost/lexical_cast.hpp> using namespace std; using namespace boost::multiprecision; int main(void){ mp_uint1024_t a[100]; rep(i,100) cin >> a[i]; mp_uint1024_t res=0; rep(i,100) res += a[i]; string str = boost::lexical_cast<string>(res); rep(i,10) cout << str[i]; cout << endl; return 0; }
14.1から1000000未満までの値で以下の式で繰り返し生成する数列を定義する。
n -> n/2(nが偶数)
n -> 3n+1(nが奇数)
コラッツ問題です。
これが1になるまで繰り返し実行する。
100万未満の数字のなかでどの数字から始めれば一番長い数列を形成するかを答える
#define smax 1000000 int table[smax]={}; int solve(ll a){ int cnt=0; int b=a; for(;;){ if(a == 1) break; else if(a < smax && table[a] != 0){ cnt += table[a]; break; } else if(a %2 == 0){ a /= 2; cnt++; } else{ a = 3*a+1; cnt++; } } table[b] = cnt; return cnt; } int main(void){ pair<int,int> pa(0,0); for(ll i=1;i<smax;i++){ if(pa.second < solve(i)+1){ pa.first = i; pa.second = solve(i)+1; } } cout << pa.first << endl; return 0; }
15.格子路の引き返しなしでの右上までに到達できる通り数を求める
典型的なDPでときます。大きさは20*20 long longじゃないと値が大きすぎて入りません。
#define smax 21 typedef long long ll; int main(void){ ll dp[smax][smax]={0}; for(int i=1;i<smax;i++){ for(int j=1;j<smax;j++){ dp[i][0] = dp[0][j] = 1; dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } cout << dp[smax-1][smax-1] << endl; return 0; }