Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2184-b888394a
この記事にトラックバックする(FC2ブログユーザー)

Round #102 DIV1 A問題/DIV2 C問題 - Help Farmer (この記事を編集する[管理者用])

Source

Codeforces Round #102 DIV1 A問題 (500pt)
Codeforces Round #102 DIV2 C問題 (1500pt)
Problem description

問題概要

1以上10^9以下の整数nが与えられるので,
 n = (A-1) * (B-2) * (C-2)
を満たす正整数A, B, Cに対して
 A*B*C - n
の最小値と最大値を求める問題.
ストーリーは,最初,高さA,幅B,奥行きCの場所に1*1*1のレンガがABC個あった.
(地面に接する面は除き)表面のレンガが焼きただれて,n個残った.
焼きただれたレンガの個数の最小値と最大値を求める.

解法

A, B, Cの全組合せを試せば良い.
それは,n=xyzみたいに分解すればよくて,x ≤ y ≤ zと仮定すれば,xはn^(1/3)まで探す,yは(n/x)^(1/2)まで探す,とすれば良い.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

int main(){
  int in;
  ll i,j,k,l,m,n;
  ll res1, res2;

  while(scanf("%d",&in)==1){
    n = in;
    res1 = res2 = 2*3*(n+2);

    for(i=1;i*i*i<=n;i++) if(n%i==0){
      m = n/i;
      for(j=i;j*j<=m;j++) if(m%j==0){
        k = m/j;

        l = (i+1)*(j+2)*(k+2);
        if(res1 > l) res1 = l; if(res2 < l) res2 = l;
        l = (i+2)*(j+1)*(k+2);
        if(res1 > l) res1 = l; if(res2 < l) res2 = l;
        l = (i+2)*(j+2)*(k+1);
        if(res1 > l) res1 = l; if(res2 < l) res2 = l;
      }
    }

    res1 -= n;
    res2 -= n;
    printf("%I64d %I64d\n",res1,res2);
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2184-b888394a
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。