Hatena::Grouptopcoder

yuyarinのtopcoder記

TopCoder, Google Code JamPKU JudgeOnlineICPC などのアルゴリズム系プログラミングコンテストの参加や練習の記録を残していきます.

アルゴリズムやテーマで分類した目次はこちら

2010/03/24

SRM 456 SilverDistance

| 21:43

http://www.topcoder.com/stat?c=problem_statement&pm=10699&rd=13909

System Test: Passed

将棋の銀を移動させるシンプルな問題.

前進は多くても1回で良いので,前進するケースを除く.start と goal の距離の差 dx, dy の偶奇が違う場合は前進が必要になるので,この場合は前進させておく.dy は sy, gy の大小関係に応じて +-1 する.

残りは斜め移動で行けるマスに何手で行けるかだけを考えればいい.これは (dx+dy)/2 + abs(dx-dy)/2 .この値に前進する場合は 1 を足せば,解答が得られる.

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

class SilverDistance
{
public:

int minSteps(int sx, int sy, int gx, int gy)
{
	int dx = (int)abs(sx-gx);
	int dy = (int)abs(sy-gy);
	int forward = 0;
	if((dx+dy)%2)
	{
		forward = 1;
		dy += ((sy>gy)?1:-1);
	}
	return (dx+dy)/2 + abs(dx-dy)/2 + forward;
}

};

SRM 456 CutSticks

| 21:43

http://www.topcoder.com/stat?c=problem_statement&pm=10563&rd=13909

System Test: Passed

長さ target_length 以上の棒が K 本以上作ることができるような target_length のうち最大の値を二分探索で求める.

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

#include <cmath>

using namespace std;

const double EPS = 1e-10;

class CutSticks
{
public:

int count_sticks(vector<int> &sticks, int n, int C, double target_length)
{
	int num_sticks = 0;
	for(int i=0;i<n;i++)
	{
		int stick_length = sticks[i];
		if(stick_length<target_length) continue;
		int cut_count = int(stick_length/target_length)-1;
		cut_count = min(cut_count,C);
		num_sticks += cut_count + 1;
		C -= cut_count;
	}
	return num_sticks;
}

double maxKth(vector <int> sticks, int C, int K)
{
	double max=1e10,mid=5e9,min=0.0;
	int loop_count = 0, loop_limit = 1000;
	int n = int(sticks.size());
	while(fabs(max-min)>EPS && (loop_count++<loop_limit))
	{
		if(count_sticks(sticks, n, C, mid)>=K)
			min = mid;
		else
			max = mid;
		mid = (max+min)/2;
	}
	//printf("%.10f\n",mid);
	return mid;
}
};

BuffyBuffy2011/07/22 11:35Thought it woduln't to give it a shot. I was right.

sufoemmgzsufoemmgz2011/07/22 17:37b20kOk <a href="http://kdmhvtcxcpku.com/">kdmhvtcxcpku</a>

bijazpbijazp2011/07/23 18:46cMgwD3 , [url=http://lrwovqzkyseo.com/]lrwovqzkyseo[/url], [link=http://ijbjudvcqwwe.com/]ijbjudvcqwwe[/link], http://ynwvekvmadlb.com/

rcrylkwffqrcrylkwffq2011/07/24 22:186PcbZ6 <a href="http://lyqcjkkrvyqu.com/">lyqcjkkrvyqu</a>

tfpszkfbtfpszkfb2011/07/25 02:49CcttKl , [url=http://helqvkusjrrm.com/]helqvkusjrrm[/url], [link=http://chqujgorbeee.com/]chqujgorbeee[/link], http://mgbsjaskvsjg.com/