スポンサーサイト

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

TopCoder Member SRM 505 Div2

本番中には解けなかった問題。悔しい。
ソース汚いな。。。

public class PerfectSequences{
public String fixIt(int[] seq){
boolean isValid = false;
for(int i=0;i if(check(i,seq))//seq[i]は、別の値に入れ替えてsumとprodが等しくなるか調べる
isValid = true;
}

String answer = isValid?"Yes":"No";
return answer;
}
private boolean check(int except, int[] seq){
int sum=0, prod=1;
//seq[except]以外の要素は全て計算
for(int i=0;i if(i == except){
continue;
}else{
sum+= seq[i];
prod *= seq[i];
}

}
for(int i=0;i<=100000000;i++){
if(sum + i == prod *i )
return true;
}
return false;
}

}

スポンサーサイト


Ants(POJ No.1852)

長さLcmの竿の上をn匹のアリが毎秒1cmのスピードで歩いています。アリが竿の端に到達するとアリは

  落ちていきます。また、竿の上は狭くてすれ違えないので、二匹のアリが出会うと、それぞれ反対を向い

て戻っていきます。各アリについて、現在の竿の左端からの距離x[i]はわかりますが、どちらの方向を向いて

いるのかはわかりません。すべてのアリが竿から落ちるまでにかかる最小の時間と最大の時間をそれぞれ求

めなさい。


#include <stdio.h>
#define N 3

int max(int num1, int num2);
int min(int num1, int num2);

int main(void){
int length = 10;
int ants[N] = {2,6,7};

//minimum
int min_t = 0;
int i;
for(i=0;i min_t = max(min_t,min(ants[i],length-ants[i]));
}
//maximum
int max_t = 0;
int j;
for(i=0;i max_t = max(max_t,max(ants[i],length-ants[i]));
}
//display
printf("min_t = %d, max_t = %d\n",min_t, max_t);

return 0;
}

int max(int num1, int num2){
int max = (num1>num2)?num1:num2;
return max;
}
int min(int num1, int num2){
int min = (num1 return min;
}

いくつかの棒の中から3本を選んでできるだけ周長が長い三角形を作る

2,3,4,5,10の中から3本を選んで、3辺の和ができるだけ大きい三角形を作り、その周長を返却するプログラム。
三角形が成り立つとき、
最も長い辺の長さ<残りの二辺の長さの和
という法則性がある。

7 int main(void){
8
9 int ret;
10 int array[N] = {2,3,4,5,10};
11
12 ret = solve(N, array);
13 printf("ret = %d\n", ret);
14
15 return 0;
16 }
17 int solve(int n, int array[]){
18 int i,j,k,answer,len, ma, rest;
19 for(i=0; i 20 for(j=i+1; j 21 for(k=j+1; k 22 len=array[i]+array[j]+array[k];//length
23 ma = max(array[i],max(array[j],array[k]));//longest
24 rest = len - ma;//rest
25
26 if(ma < rest)//三角形が作れる
27 answer = max(len,answer);//renew answer
28
29 }
30
31 }
32
33 }
34
35 return answer;
36 }
37
38 int max(int num1, int num2){
39 int max = (num1>num2)?num1:num2;
40 return max;
41 }

ハッシュマップ

ハッシュ値を生成する関数

#include <stdio.h>
#include <string.h>

#define HASH_SIZE 10

int make_hash(char *str, int hash_max){
int n, length, hash;
length=strlen(str);
for(n=0,hash=0;n<length;++n)
hash+=(int)str[n];
return hash %hash_max;
}

int main(void){
char str[100];
puts("please input string");
scanf("%s",str);
printf("hash value is %d\n", make_hash(str,HASH_SIZE));
return 0;
}

マージソート

マージソートのお勉強。
ポイントは、
・ブロックの大きさが完全に1になるまで分け続けること。
・ブロックの前半部分を、マージする前に一度buffという配列にコピーしている。
・配列のインデックスとして使用している変数がどこを指しているのか意識すると
マージソートを理解できる。
ここではkがマージして最終的に生成する配列arrayのインデックス
jが後半ブロックを指す
iが前半ブロック(arrayの前半をbuffにコピーしたもの)を指す

#include <stdio.h>
#include <time.h>

#define N 10
int array[N];

void disp(void){
int idx;
for(idx=0;idx<N;idx++)
printf("[%d]:%d\n", idx, array[idx]);
}

void merge_sort(int num, int array[]){
if(num < 2)
return;

int m = num/2;
merge_sort(m, array);
merge_sort(num-m, array+m);

int buff[num];
int i, j, k;
for(i=0;i<m;i++)
buff[i]=array[i];
i=k=0;
j=m;

while(i<m && j < num)
array[k++]=(buff[i]<array[j])? buff[i++] :array[j++];
while(i<m)
array[k++]=buff[i++];
while(j<num)
array[k++]=array[j++];
}



int main(void){

srand((unsigned int)time(NULL));
int idx;
for(idx=0;idx<N;idx++)
array[idx]=rand();
disp();
merge_sort(N, array);
puts("sort end");
disp();
}


プロフィール

tjnet777

Author:tjnet777
Solaris, VPNのサポート業務を1年

金融系SIerで業務アプリの開発、メンテを3年半

離職して大学院大学 1年生

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

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