Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Round #115 A問題 - Robot Bicorn Attack (この記事を編集する[管理者用])

Source

RazMERiq 2012 A問題
Codeforces Round #115 A問題
Problem description

問題概要

N文字 (30以下) の数字から成る文字列が与えられる.
それは,0以上1000000以下の整数A, B, Cを繋げて書いたものである.
leading zerosは許されない.(0は良い)
A+B+Cの最大値を求める問題.
もしくは,そのようなA, B, Cの3つ組が存在しないならそれを指摘する.

解法

2ヶ所,何処で区切るか全探索する.区切り方はO(N^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 MX 1000000

int len;
char in[100];
int res;

void solve(int depth, int st, int sum){
  int i,j,k;

  if(depth==3){
    if(st!=len) return;
    if(res < sum) res = sum;
    return;
  }

  k = 0;
  REP(i,st,len){
    k = k * 10 + (in[i] - '0');
    if(k > MX) break;
    solve(depth+1, i+1, sum+k);
    if(in[st]=='0') break;
  }
}

int main(){
  int i,j,k;

  scanf("%s",in);
  len = strlen(in);

  res = -1;
  solve(0,0,0);

  printf("%d\n",res);

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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