Ideone.com

download

copy

// ランダムフォレスト多クラス分類（random forest classification）
// なお、データセットはRに付属しているirisを使用しました。
 
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>
 
using namespace std;
#define SZ(a) ((int)(a).size())
 
 
// 乱数は、xorを使ってますが、メルセンヌツイスターの方がよいかも知れません。
class RandXor
{
public:
	RandXor()
	{
		init();
	}
 
	void init()
	{
		x=123456789;
		y=362436069;
		z=521288629;
		w= 88675123;
	}
 
	inline unsigned int random()
	{
		unsigned int t;
		t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
	}
private:
	unsigned int x;
	unsigned int y;
	unsigned int z;
	unsigned int w;
};
 
static RandXor  randxor;    // マルチスレッド対応にするなら、木ごとに乱数用オブジェクトを用意して、シードを変えましょう。
 
 
typedef double FeatureType;
typedef int AnswerType;
static const int NUM_CLASSES = 3; // 分類のときのクラス数
enum 
{
	LEFT,
	RIGHT,
	NUM_LR,
};
 
struct TreeNode {
	bool leaf;          // 葉（=子がない）ならtrue
	int level;          // ノードの深さ。ルートノードは0
	int featureID;      // 説明変数ID。x0, x1, x2... の0,1,2の部分
	FeatureType value;  // 分割する値
	AnswerType answer;  // ノード内（=領域内）の目的変数yの平均値
	vector <int> bags;	// ノード内（=領域内）に含まれるデータのID
	int left;           // 左側の子のノードID
	int right;          // 右側の子のノードID
 
	TreeNode() {
		leaf = false;
		level = -1;
		featureID = -1;
		value = 0;
		answer = 0;
		left = -1;
		right = -1;
	}
};
 
class DecisionTree
{
public:
	DecisionTree() { }
 
	// 学習。訓練データをいれて、決定木を作成する。
	// features           説明変数x0,x1,x2...
	// answers            目的変数y
	// minNodeSize        ノード内
	// maxLevel           ノードの深さの最大値
	// numRandomFeatures  領域を分けるときに試す説明変数（グラフでは軸）の数
	// numRandomPositions 領域を分けるときに試すデータ（グラフでは点）の数
	DecisionTree(const vector <vector <FeatureType> >& features,
		const vector <AnswerType>& answers,
		int minNodeSize,
		int maxLevel,
		int numRandomFeatures,
		int numRandomPositions)
	{
		const int numData       = SZ(features);
		const int numFeatures   = SZ(features[0]);
		assert(numData==SZ(answers));
		assert(numData>1);
 
		TreeNode root;  // ルートのノード
		root.level = 0;
 
		root.bags.resize(numData);
		for (int i = 0; i < numData; i++)
		{
			// ここで、同じIDが選ばれる可能性があるが、問題なし。
			root.bags[i] = randxor.random()%numData;
		}
		m_nodes.emplace_back(root);
 
		int curNode = 0;
		// m_nodesに子ノードがどんどん追加されていく幅優先探索
		while (curNode < SZ(m_nodes))
		{
			TreeNode &node = m_nodes[curNode];
 
			// 現在のノードに入っている目的変数が、すべて同じかどうかを調べる
			// （その場合は、ノードを分ける必要がなくなる）
			bool equal = true; // すべて同じならtrue
			for (int i=1;i<SZ(node.bags);i++) 
			{
				if (answers[node.bags[i]] != answers[node.bags[i - 1]])
				{
					equal = false;
					break;
				}
			}
 
			// 葉になる条件のチェック
			if (equal || SZ(node.bags) <= minNodeSize || node.level >= maxLevel)
			{
				// 葉にして子ノードは増やさない。
				setLeaf( node, curNode, answers );
				continue;
			}
 
			// どこで分けるのがベストかを調べる
			int bestFeatureID = -1;
			int bestLeft=0, bestRight=0;
			FeatureType bestValue = 0;
			double bestGini = 1e99;  // ジニ係数
 
			for(int i=0;i<numRandomFeatures;i++)
			{
				// x0,x1,x2...の、どの軸で分けるかを決める
				const int featureID = randxor.random()%numFeatures;
				for(int j=0;j<numRandomPositions;j++)   // どの位置で分けるか
				{
					const int positionID = randxor.random()%SZ(node.bags);
					const FeatureType splitValue = features[node.bags[positionID]][featureID];
 
					int total[NUM_LR] = {};  // splitValue未満, splitValue以上の個数
					int freq[NUM_LR][NUM_CLASSES]={};	// [どっち側か][クラス] = 個数
 
					for (int p : node.bags)
					{
						int lr = RIGHT;
						if (features[p][featureID] < splitValue)
						{
							lr = LEFT;
						}
						total[lr]++;
						freq[lr][answers[p]]++;
					}
 
					// nodeBagのデータが"未満"か"以上"のどちらかに全部偏ってるので
					// 分け方として意味がないので、すぐやめる。
					if (total[LEFT] == 0 || total[RIGHT] == 0)
						continue;
 
					// ジニ係数を求める（分類用）
					double gini = 0;
 
					for(int lr = 0; lr < NUM_LR; ++lr)
					{
						double tmpGini = 1.0;
						for(int c=0; c<NUM_CLASSES;++c)
						{
							double ratio = (double)freq[lr][c]/total[lr];
							tmpGini -= ratio*ratio;
						}
						gini += tmpGini * total[lr]/SZ(node.bags);
					}
					// BEGIN CUT HERE
//					cout << " curNode=" << curNode << " gini=" << gini << endl;
					// END CUT HERE
 
 
					if (gini < bestGini)
					{
						bestGini = gini;
						bestValue = splitValue;
						bestFeatureID = featureID;
						bestLeft = total[LEFT];
						bestRight = total[RIGHT];
					}
				}
			}
 
			// 左か右にどちらかに偏るような分け方しかできなかった場合は、葉にする
			// （すべての分け方を試すわけではないので、こういうことは起こりえます）
			if (bestLeft == 0 || bestRight == 0)
			{
				setLeaf( node, curNode, answers );
				continue;
			}
 
			// うまく分けれたので、新しい子ノードを２つ追加する
			TreeNode left;
			TreeNode right;
 
			left.level = right.level = node.level + 1;
			node.featureID = bestFeatureID;
			node.value = bestValue;
			node.left = SZ(m_nodes);
			node.right = SZ(m_nodes) + 1;
 
			left.bags.resize(bestLeft);
			right.bags.resize(bestRight);
			for (int p : node.bags)
			{
				if (features[p][node.featureID] < node.value)
				{
					left.bags[--bestLeft] = p;
				}
				else
				{
					right.bags[--bestRight] = p;
				}
			}
 
			m_nodes.emplace_back(left);
			m_nodes.emplace_back(right);
			curNode++;
		}
	}
 
	// 予測
	// features テスト用の説明変数x0,x1,x2のセット
	// 返り値   目的変数yの予測値
	AnswerType estimate(const vector <FeatureType>& features) const
	{
		// ルートからたどるだけ
		const TreeNode *pNode = &m_nodes[0];
		while (true)
		{
			if (pNode->leaf) 
			{
				break;
			}
 
			const int nextNodeID = features[pNode->featureID] < pNode->value ? pNode->left : pNode->right;
			pNode = &m_nodes[nextNodeID];
		}
 
		return pNode->answer;
	}
 
private:
 
	// nodeを葉にして、curNodeを次のノードへ進める
	void setLeaf( TreeNode& node, int& curNode, const vector<AnswerType>& answers ) const
	{
		node.leaf = true;
 
		// 分類の場合は、多数決（ここで平均を使う手法もあるよう）
		int freq[NUM_CLASSES]={};
		for (int p : node.bags) 
		{
			freq[answers[p]]++;
		}
		int bestFreq = -1;
		int bestC = -1;
		for (int c = 0; c < NUM_CLASSES; ++c)
		{
			if(freq[c]>bestFreq)
			{
				bestFreq = freq[c];
				bestC = c;
			}
		}
 
		node.answer = bestC;
 
		curNode++;
	}
 
	vector < TreeNode > m_nodes;    // 決定木のノードたち。m_nodes[0]がルート
};
 
class RandomForest {
public:
	RandomForest()
	{
		clear();
	}
 
	void clear()
	{
		m_trees.clear();
	}
 
	// 訓練
	// 繰り返し呼ぶことで木を追加することもできる。
	// features           説明変数x0,x1,x2...のセット
	// answers            目的変数yのセット
	// treesNo　　　　　　追加する木の数
	// minNodeSize        ノード内
 
	void train(const vector <vector <FeatureType> >& features,
		const vector <AnswerType>& answers,
		int treesNo,
		int minNodeSize)
	{
		for(int i=0;i<treesNo;i++)
		{
			m_trees.emplace_back(DecisionTree(features, answers, minNodeSize, 16, 2, 5));
		}
	}
 
 
	// 分類の予測
	// features テスト用の説明変数x0,x1,x2のセット
	// 返り値   目的変数yの予測値
	AnswerType estimateClassification(vector <FeatureType> &features)
	{
		if (SZ(m_trees) == 0)
		{
			return 0;
		}
 
		// 多数決
		int freq[NUM_CLASSES]={};
		for(int i=0;i<SZ(m_trees);i++)
		{
			freq[m_trees[i].estimate(features)]++;
		}
 
		int bestFreq = -1;
		int bestC = -1;
		for (int c = 0; c < NUM_CLASSES; ++c)
		{
			if(freq[c]>bestFreq)
			{
				bestFreq = freq[c];
				bestC = c;
			}
		}
 
		return bestC;
	}
 
private:
	vector < DecisionTree > m_trees;    // たくさんの決定木
};
 
int main()
{
	int numAll;         // 全データ数
	int numTrainings;   // 訓練データ数
	int numTests;       // テストデータ数
	int numFeatures;    // 説明変数の数
 
	// y = f(x0,x1,x2,...)
	// x0,x1,x2は説明変数です。コード上ではfeatureと命名してます。
	// yは目的変数です。コード上ではanswerという命名をしてます。
 
 
	cin >> numAll >> numTrainings >> numTests >> numFeatures;
	assert(numTrainings+numTests<=numAll);
 
	// 全データ
	vector < vector <FeatureType> > allFeatures(numAll, vector <FeatureType> (numFeatures));
	vector < AnswerType >       allAnswers(numAll);
 
	for(int i = 0 ; i < numAll; ++i)
	{
		for (int k = 0; k < numFeatures; ++k)
		{
			cin >> allFeatures[i][k];
		}
		cin >> allAnswers[i];
		assert(allAnswers[i]>=0);
		assert(allAnswers[i]<NUM_CLASSES);
	}
 
	// シャッフル用
	vector < int > shuffleTable;
	for (int i = 0; i < numTrainings+numTests; ++i)
	{
		shuffleTable.emplace_back(i);
	}
	random_shuffle(shuffleTable.begin(), shuffleTable.end());
 
	// 訓練データ
	vector < vector <FeatureType> > trainingFeatures(numTrainings, vector <FeatureType>(numFeatures));
	vector < AnswerType >       trainingAnswers(numTrainings);
	for (int i = 0; i < numTrainings; ++i)
	{
		trainingFeatures[i] = allFeatures[shuffleTable[i]];
		trainingAnswers[i]  = allAnswers[shuffleTable[i]];
	}
 
	// テストデータ
	vector < vector <FeatureType> > testFeatures(numTests, vector <FeatureType>(numFeatures));
	vector < AnswerType >       testAnswers(numTests);
	for (int i = 0; i < numTests; ++i)
	{
		testFeatures[i] = allFeatures[shuffleTable[numTrainings+i]];
		testAnswers[i]  = allAnswers[shuffleTable[numTrainings+i]];
	}
 
	// ランダムフォレストを使って予測
	RandomForest* rf = new RandomForest();
 
	// 木を徐々に増やしていく
	int numTrees = 0;
	for (int k = 0; k < 20; ++k)
	{
		// 学習
		const int numAdditionalTrees = 1;
		rf->train(trainingFeatures, trainingAnswers, numAdditionalTrees, 1);
		numTrees += numAdditionalTrees;
 
		// 予測と結果表示
		cout << "-----" << endl;
		cout << "numTrees=" << numTrees << endl;
		double totalError = 0.0;
		for (int i = 0; i < numTests; ++i)
		{
			const AnswerType myAnswer = rf->estimateClassification(testFeatures[i]);
			int diff = 0;
			if(myAnswer!=testAnswers[i])
			{
//				cout << "Failure! i=" << i << " myAnswer=" << myAnswer << " testAnswer=" << testAnswers[i] << endl;
				diff = 1;
			}
			totalError += diff;
		}
		cout << "totalError=" << totalError << endl;
	}
 
	delete rf;
 
	return 0;
}

Ly8g44Op44Oz44OA44Og44OV44Kp44Os44K544OI5aSa44Kv44Op44K55YiG6aGe77yIcmFuZG9tIGZvcmVzdCBjbGFzc2lmaWNhdGlvbu+8iQovLyDjgarjgYrjgIHjg4fjg7zjgr/jgrvjg4Pjg4jjga9S44Gr5LuY5bGe44GX44Gm44GE44KLaXJpc+OCkuS9v+eUqOOBl+OBvuOBl+OBn+OAggoKI2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPGNzdGRsaWI+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGFzc2VydC5oPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBTWihhKSAoKGludCkoYSkuc2l6ZSgpKQoKCi8vIOS5seaVsOOBr+OAgXhvcuOCkuS9v+OBo+OBpuOBvuOBmeOBjOOAgeODoeODq+OCu+ODs+ODjOODhOOCpOOCueOCv+ODvOOBruaWueOBjOOCiOOBhOOBi+OCguefpeOCjOOBvuOBm+OCk+OAggpjbGFzcyBSYW5kWG9yCnsKcHVibGljOgoJUmFuZFhvcigpCgl7CgkJaW5pdCgpOwoJfQoKCXZvaWQgaW5pdCgpCgl7CgkJeD0xMjM0NTY3ODk7CgkJeT0zNjI0MzYwNjk7CgkJej01MjEyODg2Mjk7CgkJdz0gODg2NzUxMjM7Cgl9CgoJaW5saW5lIHVuc2lnbmVkIGludCByYW5kb20oKQoJewoJCXVuc2lnbmVkIGludCB0OwoJCXQ9KHheKHg8PDExKSk7eD15O3k9ejt6PXc7IHJldHVybiggdz0od14odz4+MTkpKV4odF4odD4+OCkpICk7Cgl9CnByaXZhdGU6Cgl1bnNpZ25lZCBpbnQgeDsKCXVuc2lnbmVkIGludCB5OwoJdW5zaWduZWQgaW50IHo7Cgl1bnNpZ25lZCBpbnQgdzsKfTsKCnN0YXRpYyBSYW5kWG9yICByYW5keG9yOyAgICAvLyDjg57jg6vjg4Hjgrnjg6zjg4Pjg4nlr77lv5zjgavjgZnjgovjgarjgonjgIHmnKjjgZTjgajjgavkubHmlbDnlKjjgqrjg5bjgrjjgqfjgq/jg4jjgpLnlKjmhI/jgZfjgabjgIHjgrfjg7zjg4njgpLlpInjgYjjgb7jgZfjgofjgYbjgIIKCgp0eXBlZGVmIGRvdWJsZSBGZWF0dXJlVHlwZTsKdHlwZWRlZiBpbnQgQW5zd2VyVHlwZTsKc3RhdGljIGNvbnN0IGludCBOVU1fQ0xBU1NFUyA9IDM7IC8vIOWIhumhnuOBruOBqOOBjeOBruOCr+ODqeOCueaVsAplbnVtIAp7CglMRUZULAoJUklHSFQsCglOVU1fTFIsCn07CgpzdHJ1Y3QgVHJlZU5vZGUgewoJYm9vbCBsZWFmOyAgICAgICAgICAvLyDokYnvvIg95a2Q44GM44Gq44GE77yJ44Gq44KJdHJ1ZQoJaW50IGxldmVsOyAgICAgICAgICAvLyDjg47jg7zjg4njga7mt7HjgZXjgILjg6vjg7zjg4jjg47jg7zjg4njga8wCglpbnQgZmVhdHVyZUlEOyAgICAgIC8vIOiqrOaYjuWkieaVsElE44CCeDAsIHgxLCB4Mi4uLiDjga4wLDEsMuOBrumDqOWIhgoJRmVhdHVyZVR5cGUgdmFsdWU7ICAvLyDliIblibLjgZnjgovlgKQKCUFuc3dlclR5cGUgYW5zd2VyOyAgLy8g44OO44O844OJ5YaF77yIPemgmOWfn+WGhe+8ieOBruebrueahOWkieaVsHnjga7lubPlnYflgKQKCXZlY3RvciA8aW50PiBiYWdzOwkvLyDjg47jg7zjg4nlhoXvvIg96aCY5Z+f5YaF77yJ44Gr5ZCr44G+44KM44KL44OH44O844K/44GuSUQKCWludCBsZWZ0OyAgICAgICAgICAgLy8g5bem5YG044Gu5a2Q44Gu44OO44O844OJSUQKCWludCByaWdodDsgICAgICAgICAgLy8g5Y+z5YG044Gu5a2Q44Gu44OO44O844OJSUQKCglUcmVlTm9kZSgpIHsKCQlsZWFmID0gZmFsc2U7CgkJbGV2ZWwgPSAtMTsKCQlmZWF0dXJlSUQgPSAtMTsKCQl2YWx1ZSA9IDA7CgkJYW5zd2VyID0gMDsKCQlsZWZ0ID0gLTE7CgkJcmlnaHQgPSAtMTsKCX0KfTsKCmNsYXNzIERlY2lzaW9uVHJlZQp7CnB1YmxpYzoKCURlY2lzaW9uVHJlZSgpIHsgfQoKCS8vIOWtpue/kuOAguiok+e3tOODh+ODvOOCv+OCkuOBhOOCjOOBpuOAgeaxuuWumuacqOOCkuS9nOaIkOOBmeOCi+OAggoJLy8gZmVhdHVyZXMgICAgICAgICAgIOiqrOaYjuWkieaVsHgwLHgxLHgyLi4uCgkvLyBhbnN3ZXJzICAgICAgICAgICAg55uu55qE5aSJ5pWweQoJLy8gbWluTm9kZVNpemUgICAgICAgIOODjuODvOODieWGhQoJLy8gbWF4TGV2ZWwgICAgICAgICAgIOODjuODvOODieOBrua3seOBleOBruacgOWkp+WApAoJLy8gbnVtUmFuZG9tRmVhdHVyZXMgIOmgmOWfn+OCkuWIhuOBkeOCi+OBqOOBjeOBq+ippuOBmeiqrOaYjuWkieaVsO+8iOOCsOODqeODleOBp+OBr+i7uO+8ieOBruaVsAoJLy8gbnVtUmFuZG9tUG9zaXRpb25zIOmgmOWfn+OCkuWIhuOBkeOCi+OBqOOBjeOBq+ippuOBmeODh+ODvOOCv++8iOOCsOODqeODleOBp+OBr+eCue+8ieOBruaVsAoJRGVjaXNpb25UcmVlKGNvbnN0IHZlY3RvciA8dmVjdG9yIDxGZWF0dXJlVHlwZT4gPiYgZmVhdHVyZXMsCgkJY29uc3QgdmVjdG9yIDxBbnN3ZXJUeXBlPiYgYW5zd2VycywKCQlpbnQgbWluTm9kZVNpemUsCgkJaW50IG1heExldmVsLAoJCWludCBudW1SYW5kb21GZWF0dXJlcywKCQlpbnQgbnVtUmFuZG9tUG9zaXRpb25zKQoJewoJCWNvbnN0IGludCBudW1EYXRhICAgICAgID0gU1ooZmVhdHVyZXMpOwoJCWNvbnN0IGludCBudW1GZWF0dXJlcyAgID0gU1ooZmVhdHVyZXNbMF0pOwoJCWFzc2VydChudW1EYXRhPT1TWihhbnN3ZXJzKSk7CgkJYXNzZXJ0KG51bURhdGE+MSk7CgoJCVRyZWVOb2RlIHJvb3Q7ICAvLyDjg6vjg7zjg4jjga7jg47jg7zjg4kKCQlyb290LmxldmVsID0gMDsKCgkJcm9vdC5iYWdzLnJlc2l6ZShudW1EYXRhKTsKCQlmb3IgKGludCBpID0gMDsgaSA8IG51bURhdGE7IGkrKykKCQl7CgkJCS8vIOOBk+OBk+OBp+OAgeWQjOOBmElE44GM6YG444Gw44KM44KL5Y+v6IO95oCn44GM44GC44KL44GM44CB5ZWP6aGM44Gq44GX44CCCgkJCXJvb3QuYmFnc1tpXSA9IHJhbmR4b3IucmFuZG9tKCklbnVtRGF0YTsKCQl9CgkJbV9ub2Rlcy5lbXBsYWNlX2JhY2socm9vdCk7CgoJCWludCBjdXJOb2RlID0gMDsKCQkvLyBtX25vZGVz44Gr5a2Q44OO44O844OJ44GM44Gp44KT44Gp44KT6L+95Yqg44GV44KM44Gm44GE44GP5bmF5YSq5YWI5o6i57SiCgkJd2hpbGUgKGN1ck5vZGUgPCBTWihtX25vZGVzKSkKCQl7CgkJCVRyZWVOb2RlICZub2RlID0gbV9ub2Rlc1tjdXJOb2RlXTsKCgkJCS8vIOePvuWcqOOBruODjuODvOODieOBq+WFpeOBo+OBpuOBhOOCi+ebrueahOWkieaVsOOBjOOAgeOBmeOBueOBpuWQjOOBmOOBi+OBqeOBhuOBi+OCkuiqv+OBueOCiwoJCQkvLyDvvIjjgZ3jga7loLTlkIjjga/jgIHjg47jg7zjg4njgpLliIbjgZHjgovlv4XopoHjgYzjgarjgY/jgarjgovvvIkKCQkJYm9vbCBlcXVhbCA9IHRydWU7IC8vIOOBmeOBueOBpuWQjOOBmOOBquOCiXRydWUKCQkJZm9yIChpbnQgaT0xO2k8U1oobm9kZS5iYWdzKTtpKyspIAoJCQl7CgkJCQlpZiAoYW5zd2Vyc1tub2RlLmJhZ3NbaV1dICE9IGFuc3dlcnNbbm9kZS5iYWdzW2kgLSAxXV0pCgkJCQl7CgkJCQkJZXF1YWwgPSBmYWxzZTsKCQkJCQlicmVhazsKCQkJCX0KCQkJfQoKCQkJLy8g6JGJ44Gr44Gq44KL5p2h5Lu244Gu44OB44Kn44OD44KvCgkJCWlmIChlcXVhbCB8fCBTWihub2RlLmJhZ3MpIDw9IG1pbk5vZGVTaXplIHx8IG5vZGUubGV2ZWwgPj0gbWF4TGV2ZWwpCgkJCXsKCQkJCS8vIOiRieOBq+OBl+OBpuWtkOODjuODvOODieOBr+Wil+OChOOBleOBquOBhOOAggoJCQkJc2V0TGVhZiggbm9kZSwgY3VyTm9kZSwgYW5zd2VycyApOwoJCQkJY29udGludWU7CgkJCX0KCgkJCS8vIOOBqeOBk+OBp+WIhuOBkeOCi+OBruOBjOODmeOCueODiOOBi+OCkuiqv+OBueOCiwoJCQlpbnQgYmVzdEZlYXR1cmVJRCA9IC0xOwoJCQlpbnQgYmVzdExlZnQ9MCwgYmVzdFJpZ2h0PTA7CgkJCUZlYXR1cmVUeXBlIGJlc3RWYWx1ZSA9IDA7CgkJCWRvdWJsZSBiZXN0R2luaSA9IDFlOTk7ICAvLyDjgrjjg4vkv4LmlbAKCgkJCWZvcihpbnQgaT0wO2k8bnVtUmFuZG9tRmVhdHVyZXM7aSsrKQoJCQl7CgkJCQkvLyB4MCx4MSx4Mi4uLuOBruOAgeOBqeOBrui7uOOBp+WIhuOBkeOCi+OBi+OCkuaxuuOCgeOCiwoJCQkJY29uc3QgaW50IGZlYXR1cmVJRCA9IHJhbmR4b3IucmFuZG9tKCklbnVtRmVhdHVyZXM7CgkJCQlmb3IoaW50IGo9MDtqPG51bVJhbmRvbVBvc2l0aW9ucztqKyspICAgLy8g44Gp44Gu5L2N572u44Gn5YiG44GR44KL44GLCgkJCQl7CgkJCQkJY29uc3QgaW50IHBvc2l0aW9uSUQgPSByYW5keG9yLnJhbmRvbSgpJVNaKG5vZGUuYmFncyk7CgkJCQkJY29uc3QgRmVhdHVyZVR5cGUgc3BsaXRWYWx1ZSA9IGZlYXR1cmVzW25vZGUuYmFnc1twb3NpdGlvbklEXV1bZmVhdHVyZUlEXTsKCgkJCQkJaW50IHRvdGFsW05VTV9MUl0gPSB7fTsgIC8vIHNwbGl0VmFsdWXmnKrmuoAsIHNwbGl0VmFsdWXku6XkuIrjga7lgIvmlbAKCQkJCQlpbnQgZnJlcVtOVU1fTFJdW05VTV9DTEFTU0VTXT17fTsJLy8gW+OBqeOBo+OBoeWBtOOBi11b44Kv44Op44K5XSA9IOWAi+aVsAoKCQkJCQlmb3IgKGludCBwIDogbm9kZS5iYWdzKQoJCQkJCXsKCQkJCQkJaW50IGxyID0gUklHSFQ7CgkJCQkJCWlmIChmZWF0dXJlc1twXVtmZWF0dXJlSURdIDwgc3BsaXRWYWx1ZSkKCQkJCQkJewoJCQkJCQkJbHIgPSBMRUZUOwoJCQkJCQl9CgkJCQkJCXRvdGFsW2xyXSsrOwoJCQkJCQlmcmVxW2xyXVthbnN3ZXJzW3BdXSsrOwoJCQkJCX0KCgkJCQkJLy8gbm9kZUJhZ+OBruODh+ODvOOCv+OBjCLmnKrmuoAi44GLIuS7peS4iiLjga7jganjgaHjgonjgYvjgavlhajpg6jlgY/jgaPjgabjgovjga7jgacKCQkJCQkvLyDliIbjgZHmlrnjgajjgZfjgabmhI/lkbPjgYzjgarjgYTjga7jgafjgIHjgZnjgZDjgoTjgoHjgovjgIIKCQkJCQlpZiAodG90YWxbTEVGVF0gPT0gMCB8fCB0b3RhbFtSSUdIVF0gPT0gMCkKCQkJCQkJY29udGludWU7CgoJCQkJCS8vIOOCuOODi+S/guaVsOOCkuaxguOCgeOCi++8iOWIhumhnueUqO+8iQoJCQkJCWRvdWJsZSBnaW5pID0gMDsKCgkJCQkJZm9yKGludCBsciA9IDA7IGxyIDwgTlVNX0xSOyArK2xyKQoJCQkJCXsKCQkJCQkJZG91YmxlIHRtcEdpbmkgPSAxLjA7CgkJCQkJCWZvcihpbnQgYz0wOyBjPE5VTV9DTEFTU0VTOysrYykKCQkJCQkJewoJCQkJCQkJZG91YmxlIHJhdGlvID0gKGRvdWJsZSlmcmVxW2xyXVtjXS90b3RhbFtscl07CgkJCQkJCQl0bXBHaW5pIC09IHJhdGlvKnJhdGlvOwoJCQkJCQl9CgkJCQkJCWdpbmkgKz0gdG1wR2luaSAqIHRvdGFsW2xyXS9TWihub2RlLmJhZ3MpOwoJCQkJCX0KCQkJCQkvLyBCRUdJTiBDVVQgSEVSRQovLwkJCQkJY291dCA8PCAiIGN1ck5vZGU9IiA8PCBjdXJOb2RlIDw8ICIgZ2luaT0iIDw8IGdpbmkgPDwgZW5kbDsKCQkJCQkvLyBFTkQgQ1VUIEhFUkUKCgoJCQkJCWlmIChnaW5pIDwgYmVzdEdpbmkpCgkJCQkJewoJCQkJCQliZXN0R2luaSA9IGdpbmk7CgkJCQkJCWJlc3RWYWx1ZSA9IHNwbGl0VmFsdWU7CgkJCQkJCWJlc3RGZWF0dXJlSUQgPSBmZWF0dXJlSUQ7CgkJCQkJCWJlc3RMZWZ0ID0gdG90YWxbTEVGVF07CgkJCQkJCWJlc3RSaWdodCA9IHRvdGFsW1JJR0hUXTsKCQkJCQl9CgkJCQl9CgkJCX0KCgkJCS8vIOW3puOBi+WPs+OBq+OBqeOBoeOCieOBi+OBq+WBj+OCi+OCiOOBhuOBquWIhuOBkeaWueOBl+OBi+OBp+OBjeOBquOBi+OBo+OBn+WgtOWQiOOBr+OAgeiRieOBq+OBmeOCiwoJCQkvLyDvvIjjgZnjgbnjgabjga7liIbjgZHmlrnjgpLoqabjgZnjgo/jgZHjgafjga/jgarjgYTjga7jgafjgIHjgZPjgYbjgYTjgYbjgZPjgajjga/otbfjgZPjgorjgYjjgb7jgZnvvIkKCQkJaWYgKGJlc3RMZWZ0ID09IDAgfHwgYmVzdFJpZ2h0ID09IDApCgkJCXsKCQkJCXNldExlYWYoIG5vZGUsIGN1ck5vZGUsIGFuc3dlcnMgKTsKCQkJCWNvbnRpbnVlOwoJCQl9CgoJCQkvLyDjgYbjgb7jgY/liIbjgZHjgozjgZ/jga7jgafjgIHmlrDjgZfjgYTlrZDjg47jg7zjg4njgpLvvJLjgaTov73liqDjgZnjgosKCQkJVHJlZU5vZGUgbGVmdDsKCQkJVHJlZU5vZGUgcmlnaHQ7CgoJCQlsZWZ0LmxldmVsID0gcmlnaHQubGV2ZWwgPSBub2RlLmxldmVsICsgMTsKCQkJbm9kZS5mZWF0dXJlSUQgPSBiZXN0RmVhdHVyZUlEOwoJCQlub2RlLnZhbHVlID0gYmVzdFZhbHVlOwoJCQlub2RlLmxlZnQgPSBTWihtX25vZGVzKTsKCQkJbm9kZS5yaWdodCA9IFNaKG1fbm9kZXMpICsgMTsKCgkJCWxlZnQuYmFncy5yZXNpemUoYmVzdExlZnQpOwoJCQlyaWdodC5iYWdzLnJlc2l6ZShiZXN0UmlnaHQpOwoJCQlmb3IgKGludCBwIDogbm9kZS5iYWdzKQoJCQl7CgkJCQlpZiAoZmVhdHVyZXNbcF1bbm9kZS5mZWF0dXJlSURdIDwgbm9kZS52YWx1ZSkKCQkJCXsKCQkJCQlsZWZ0LmJhZ3NbLS1iZXN0TGVmdF0gPSBwOwoJCQkJfQoJCQkJZWxzZQoJCQkJewoJCQkJCXJpZ2h0LmJhZ3NbLS1iZXN0UmlnaHRdID0gcDsKCQkJCX0KCQkJfQoKCQkJbV9ub2Rlcy5lbXBsYWNlX2JhY2sobGVmdCk7CgkJCW1fbm9kZXMuZW1wbGFjZV9iYWNrKHJpZ2h0KTsKCQkJY3VyTm9kZSsrOwoJCX0KCX0KCgkvLyDkuojmuKwKCS8vIGZlYXR1cmVzIOODhuOCueODiOeUqOOBruiqrOaYjuWkieaVsHgwLHgxLHgy44Gu44K744OD44OICgkvLyDov5TjgorlgKQgICDnm67nmoTlpInmlbB544Gu5LqI5ris5YCkCglBbnN3ZXJUeXBlIGVzdGltYXRlKGNvbnN0IHZlY3RvciA8RmVhdHVyZVR5cGU+JiBmZWF0dXJlcykgY29uc3QKCXsKCQkvLyDjg6vjg7zjg4jjgYvjgonjgZ/jganjgovjgaDjgZEKCQljb25zdCBUcmVlTm9kZSAqcE5vZGUgPSAmbV9ub2Rlc1swXTsKCQl3aGlsZSAodHJ1ZSkKCQl7CgkJCWlmIChwTm9kZS0+bGVhZikgCgkJCXsKCQkJCWJyZWFrOwoJCQl9CgoJCQljb25zdCBpbnQgbmV4dE5vZGVJRCA9IGZlYXR1cmVzW3BOb2RlLT5mZWF0dXJlSURdIDwgcE5vZGUtPnZhbHVlID8gcE5vZGUtPmxlZnQgOiBwTm9kZS0+cmlnaHQ7CgkJCXBOb2RlID0gJm1fbm9kZXNbbmV4dE5vZGVJRF07CgkJfQoKCQlyZXR1cm4gcE5vZGUtPmFuc3dlcjsKCX0KCnByaXZhdGU6CgoJLy8gbm9kZeOCkuiRieOBq+OBl+OBpuOAgWN1ck5vZGXjgpLmrKHjga7jg47jg7zjg4njgbjpgLLjgoHjgosKCXZvaWQgc2V0TGVhZiggVHJlZU5vZGUmIG5vZGUsIGludCYgY3VyTm9kZSwgY29uc3QgdmVjdG9yPEFuc3dlclR5cGU+JiBhbnN3ZXJzICkgY29uc3QKCXsKCQlub2RlLmxlYWYgPSB0cnVlOwoKCQkvLyDliIbpoZ7jga7loLTlkIjjga/jgIHlpJrmlbDmsbrvvIjjgZPjgZPjgaflubPlnYfjgpLkvb/jgYbmiYvms5XjgoLjgYLjgovjgojjgYbvvIkKCQlpbnQgZnJlcVtOVU1fQ0xBU1NFU109e307CgkJZm9yIChpbnQgcCA6IG5vZGUuYmFncykgCgkJewoJCQlmcmVxW2Fuc3dlcnNbcF1dKys7CgkJfQoJCWludCBiZXN0RnJlcSA9IC0xOwoJCWludCBiZXN0QyA9IC0xOwoJCWZvciAoaW50IGMgPSAwOyBjIDwgTlVNX0NMQVNTRVM7ICsrYykKCQl7CgkJCWlmKGZyZXFbY10+YmVzdEZyZXEpCgkJCXsKCQkJCWJlc3RGcmVxID0gZnJlcVtjXTsKCQkJCWJlc3RDID0gYzsKCQkJfQoJCX0KCgkJbm9kZS5hbnN3ZXIgPSBiZXN0QzsKCgkJY3VyTm9kZSsrOwoJfQoKCXZlY3RvciA8IFRyZWVOb2RlID4gbV9ub2RlczsgICAgLy8g5rG65a6a5pyo44Gu44OO44O844OJ44Gf44Gh44CCbV9ub2Rlc1swXeOBjOODq+ODvOODiAp9OwoKY2xhc3MgUmFuZG9tRm9yZXN0IHsKcHVibGljOgoJUmFuZG9tRm9yZXN0KCkKCXsKCQljbGVhcigpOwoJfQoKCXZvaWQgY2xlYXIoKQoJewoJCW1fdHJlZXMuY2xlYXIoKTsKCX0KCgkvLyDoqJPnt7QKCS8vIOe5sOOCiui/lOOBl+WRvOOBtuOBk+OBqOOBp+acqOOCkui/veWKoOOBmeOCi+OBk+OBqOOCguOBp+OBjeOCi+OAggoJLy8gZmVhdHVyZXMgICAgICAgICAgIOiqrOaYjuWkieaVsHgwLHgxLHgyLi4u44Gu44K744OD44OICgkvLyBhbnN3ZXJzICAgICAgICAgICAg55uu55qE5aSJ5pWweeOBruOCu+ODg+ODiAoJLy8gdHJlZXNOb+OAgOOAgOOAgOOAgOOAgOOAgOi/veWKoOOBmeOCi+acqOOBruaVsAoJLy8gbWluTm9kZVNpemUgICAgICAgIOODjuODvOODieWGhQoKCXZvaWQgdHJhaW4oY29uc3QgdmVjdG9yIDx2ZWN0b3IgPEZlYXR1cmVUeXBlPiA+JiBmZWF0dXJlcywKCQljb25zdCB2ZWN0b3IgPEFuc3dlclR5cGU+JiBhbnN3ZXJzLAoJCWludCB0cmVlc05vLAoJCWludCBtaW5Ob2RlU2l6ZSkKCXsKCQlmb3IoaW50IGk9MDtpPHRyZWVzTm87aSsrKQoJCXsKCQkJbV90cmVlcy5lbXBsYWNlX2JhY2soRGVjaXNpb25UcmVlKGZlYXR1cmVzLCBhbnN3ZXJzLCBtaW5Ob2RlU2l6ZSwgMTYsIDIsIDUpKTsKCQl9Cgl9CgoKCS8vIOWIhumhnuOBruS6iOa4rAoJLy8gZmVhdHVyZXMg44OG44K544OI55So44Gu6Kqs5piO5aSJ5pWweDAseDEseDLjga7jgrvjg4Pjg4gKCS8vIOi/lOOCiuWApCAgIOebrueahOWkieaVsHnjga7kuojmuKzlgKQKCUFuc3dlclR5cGUgZXN0aW1hdGVDbGFzc2lmaWNhdGlvbih2ZWN0b3IgPEZlYXR1cmVUeXBlPiAmZmVhdHVyZXMpCgl7CgkJaWYgKFNaKG1fdHJlZXMpID09IDApCgkJewoJCQlyZXR1cm4gMDsKCQl9CgoJCS8vIOWkmuaVsOaxugoJCWludCBmcmVxW05VTV9DTEFTU0VTXT17fTsKCQlmb3IoaW50IGk9MDtpPFNaKG1fdHJlZXMpO2krKykKCQl7CgkJCWZyZXFbbV90cmVlc1tpXS5lc3RpbWF0ZShmZWF0dXJlcyldKys7CgkJfQoKCQlpbnQgYmVzdEZyZXEgPSAtMTsKCQlpbnQgYmVzdEMgPSAtMTsKCQlmb3IgKGludCBjID0gMDsgYyA8IE5VTV9DTEFTU0VTOyArK2MpCgkJewoJCQlpZihmcmVxW2NdPmJlc3RGcmVxKQoJCQl7CgkJCQliZXN0RnJlcSA9IGZyZXFbY107CgkJCQliZXN0QyA9IGM7CgkJCX0KCQl9CgoJCXJldHVybiBiZXN0QzsKCX0KCnByaXZhdGU6Cgl2ZWN0b3IgPCBEZWNpc2lvblRyZWUgPiBtX3RyZWVzOyAgICAvLyDjgZ/jgY/jgZXjgpPjga7msbrlrprmnKgKfTsKCmludCBtYWluKCkKewoJaW50IG51bUFsbDsgICAgICAgICAvLyDlhajjg4fjg7zjgr/mlbAKCWludCBudW1UcmFpbmluZ3M7ICAgLy8g6KiT57e044OH44O844K/5pWwCglpbnQgbnVtVGVzdHM7ICAgICAgIC8vIOODhuOCueODiOODh+ODvOOCv+aVsAoJaW50IG51bUZlYXR1cmVzOyAgICAvLyDoqqzmmI7lpInmlbDjga7mlbAKCgkvLyB5ID0gZih4MCx4MSx4MiwuLi4pCgkvLyB4MCx4MSx4MuOBr+iqrOaYjuWkieaVsOOBp+OBmeOAguOCs+ODvOODieS4iuOBp+OBr2ZlYXR1cmXjgajlkb3lkI3jgZfjgabjgb7jgZnjgIIKCS8vIHnjga/nm67nmoTlpInmlbDjgafjgZnjgILjgrPjg7zjg4nkuIrjgafjga9hbnN3ZXLjgajjgYTjgYblkb3lkI3jgpLjgZfjgabjgb7jgZnjgIIKCgoJY2luID4+IG51bUFsbCA+PiBudW1UcmFpbmluZ3MgPj4gbnVtVGVzdHMgPj4gbnVtRmVhdHVyZXM7Cglhc3NlcnQobnVtVHJhaW5pbmdzK251bVRlc3RzPD1udW1BbGwpOwoKCS8vIOWFqOODh+ODvOOCvwoJdmVjdG9yIDwgdmVjdG9yIDxGZWF0dXJlVHlwZT4gPiBhbGxGZWF0dXJlcyhudW1BbGwsIHZlY3RvciA8RmVhdHVyZVR5cGU+IChudW1GZWF0dXJlcykpOwoJdmVjdG9yIDwgQW5zd2VyVHlwZSA+ICAgICAgIGFsbEFuc3dlcnMobnVtQWxsKTsKCglmb3IoaW50IGkgPSAwIDsgaSA8IG51bUFsbDsgKytpKQoJewoJCWZvciAoaW50IGsgPSAwOyBrIDwgbnVtRmVhdHVyZXM7ICsraykKCQl7CgkJCWNpbiA+PiBhbGxGZWF0dXJlc1tpXVtrXTsKCQl9CgkJY2luID4+IGFsbEFuc3dlcnNbaV07CgkJYXNzZXJ0KGFsbEFuc3dlcnNbaV0+PTApOwoJCWFzc2VydChhbGxBbnN3ZXJzW2ldPE5VTV9DTEFTU0VTKTsKCX0KCgkvLyDjgrfjg6Pjg4Pjg5Xjg6vnlKgKCXZlY3RvciA8IGludCA+IHNodWZmbGVUYWJsZTsKCWZvciAoaW50IGkgPSAwOyBpIDwgbnVtVHJhaW5pbmdzK251bVRlc3RzOyArK2kpCgl7CgkJc2h1ZmZsZVRhYmxlLmVtcGxhY2VfYmFjayhpKTsKCX0KCXJhbmRvbV9zaHVmZmxlKHNodWZmbGVUYWJsZS5iZWdpbigpLCBzaHVmZmxlVGFibGUuZW5kKCkpOwoKCS8vIOiok+e3tOODh+ODvOOCvwoJdmVjdG9yIDwgdmVjdG9yIDxGZWF0dXJlVHlwZT4gPiB0cmFpbmluZ0ZlYXR1cmVzKG51bVRyYWluaW5ncywgdmVjdG9yIDxGZWF0dXJlVHlwZT4obnVtRmVhdHVyZXMpKTsKCXZlY3RvciA8IEFuc3dlclR5cGUgPiAgICAgICB0cmFpbmluZ0Fuc3dlcnMobnVtVHJhaW5pbmdzKTsKCWZvciAoaW50IGkgPSAwOyBpIDwgbnVtVHJhaW5pbmdzOyArK2kpCgl7CgkJdHJhaW5pbmdGZWF0dXJlc1tpXSA9IGFsbEZlYXR1cmVzW3NodWZmbGVUYWJsZVtpXV07CgkJdHJhaW5pbmdBbnN3ZXJzW2ldICA9IGFsbEFuc3dlcnNbc2h1ZmZsZVRhYmxlW2ldXTsKCX0KCgkvLyDjg4bjgrnjg4jjg4fjg7zjgr8KCXZlY3RvciA8IHZlY3RvciA8RmVhdHVyZVR5cGU+ID4gdGVzdEZlYXR1cmVzKG51bVRlc3RzLCB2ZWN0b3IgPEZlYXR1cmVUeXBlPihudW1GZWF0dXJlcykpOwoJdmVjdG9yIDwgQW5zd2VyVHlwZSA+ICAgICAgIHRlc3RBbnN3ZXJzKG51bVRlc3RzKTsKCWZvciAoaW50IGkgPSAwOyBpIDwgbnVtVGVzdHM7ICsraSkKCXsKCQl0ZXN0RmVhdHVyZXNbaV0gPSBhbGxGZWF0dXJlc1tzaHVmZmxlVGFibGVbbnVtVHJhaW5pbmdzK2ldXTsKCQl0ZXN0QW5zd2Vyc1tpXSAgPSBhbGxBbnN3ZXJzW3NodWZmbGVUYWJsZVtudW1UcmFpbmluZ3MraV1dOwoJfQoKCS8vIOODqeODs+ODgOODoOODleOCqeODrOOCueODiOOCkuS9v+OBo+OBpuS6iOa4rAoJUmFuZG9tRm9yZXN0KiByZiA9IG5ldyBSYW5kb21Gb3Jlc3QoKTsKCgkvLyDmnKjjgpLlvpDjgIXjgavlopfjgoTjgZfjgabjgYTjgY8KCWludCBudW1UcmVlcyA9IDA7Cglmb3IgKGludCBrID0gMDsgayA8IDIwOyArK2spCgl7CgkJLy8g5a2m57+SCgkJY29uc3QgaW50IG51bUFkZGl0aW9uYWxUcmVlcyA9IDE7CgkJcmYtPnRyYWluKHRyYWluaW5nRmVhdHVyZXMsIHRyYWluaW5nQW5zd2VycywgbnVtQWRkaXRpb25hbFRyZWVzLCAxKTsKCQludW1UcmVlcyArPSBudW1BZGRpdGlvbmFsVHJlZXM7CgoJCS8vIOS6iOa4rOOBqOe1kOaenOihqOekugoJCWNvdXQgPDwgIi0tLS0tIiA8PCBlbmRsOwoJCWNvdXQgPDwgIm51bVRyZWVzPSIgPDwgbnVtVHJlZXMgPDwgZW5kbDsKCQlkb3VibGUgdG90YWxFcnJvciA9IDAuMDsKCQlmb3IgKGludCBpID0gMDsgaSA8IG51bVRlc3RzOyArK2kpCgkJewoJCQljb25zdCBBbnN3ZXJUeXBlIG15QW5zd2VyID0gcmYtPmVzdGltYXRlQ2xhc3NpZmljYXRpb24odGVzdEZlYXR1cmVzW2ldKTsKCQkJaW50IGRpZmYgPSAwOwoJCQlpZihteUFuc3dlciE9dGVzdEFuc3dlcnNbaV0pCgkJCXsKLy8JCQkJY291dCA8PCAiRmFpbHVyZSEgaT0iIDw8IGkgPDwgIiBteUFuc3dlcj0iIDw8IG15QW5zd2VyIDw8ICIgdGVzdEFuc3dlcj0iIDw8IHRlc3RBbnN3ZXJzW2ldIDw8IGVuZGw7CgkJCQlkaWZmID0gMTsKCQkJfQoJCQl0b3RhbEVycm9yICs9IGRpZmY7CgkJfQoJCWNvdXQgPDwgInRvdGFsRXJyb3I9IiA8PCB0b3RhbEVycm9yIDw8IGVuZGw7Cgl9CgoJZGVsZXRlIHJmOwoKCXJldHVybiAwOwp9Cgo=

Success #stdin #stdout 0s 3444KB

stdin

copy

MTUwIDI1IDEyNSA0CjUuMSAzLjUgMS40IDAuMiAwCjQuOSAzICAgMS40IDAuMiAwCjQuNyAzLjIgMS4zIDAuMiAwCjQuNiAzLjEgMS41IDAuMiAwCjUgICAzLjYgMS40IDAuMiAwCjUuNCAzLjkgMS43IDAuNCAwCjQuNiAzLjQgMS40IDAuMyAwCjUgICAzLjQgMS41IDAuMiAwCjQuNCAyLjkgMS40IDAuMiAwCjQuOSAzLjEgMS41IDAuMSAwCjUuNCAzLjcgMS41IDAuMiAwCjQuOCAzLjQgMS42IDAuMiAwCjQuOCAzICAgMS40IDAuMSAwCjQuMyAzICAgMS4xIDAuMSAwCjUuOCA0ICAgMS4yIDAuMiAwCjUuNyA0LjQgMS41IDAuNCAwCjUuNCAzLjkgMS4zIDAuNCAwCjUuMSAzLjUgMS40IDAuMyAwCjUuNyAzLjggMS43IDAuMyAwCjUuMSAzLjggMS41IDAuMyAwCjUuNCAzLjQgMS43IDAuMiAwCjUuMSAzLjcgMS41IDAuNCAwCjQuNiAzLjYgMSAgIDAuMiAwCjUuMSAzLjMgMS43IDAuNSAwCjQuOCAzLjQgMS45IDAuMiAwCjUgICAzICAgMS42IDAuMiAwCjUgICAzLjQgMS42IDAuNCAwCjUuMiAzLjUgMS41IDAuMiAwCjUuMiAzLjQgMS40IDAuMiAwCjQuNyAzLjIgMS42IDAuMiAwCjQuOCAzLjEgMS42IDAuMiAwCjUuNCAzLjQgMS41IDAuNCAwCjUuMiA0LjEgMS41IDAuMSAwCjUuNSA0LjIgMS40IDAuMiAwCjQuOSAzLjEgMS41IDAuMiAwCjUgICAzLjIgMS4yIDAuMiAwCjUuNSAzLjUgMS4zIDAuMiAwCjQuOSAzLjYgMS40IDAuMSAwCjQuNCAzICAgMS4zIDAuMiAwCjUuMSAzLjQgMS41IDAuMiAwCjUgICAzLjUgMS4zIDAuMyAwCjQuNSAyLjMgMS4zIDAuMyAwCjQuNCAzLjIgMS4zIDAuMiAwCjUgICAzLjUgMS42IDAuNiAwCjUuMSAzLjggMS45IDAuNCAwCjQuOCAzICAgMS40IDAuMyAwCjUuMSAzLjggMS42IDAuMiAwCjQuNiAzLjIgMS40IDAuMiAwCjUuMyAzLjcgMS41IDAuMiAwCjUgICAzLjMgMS40IDAuMiAwCjcgICAzLjIgNC43IDEuNCAxCjYuNCAzLjIgNC41IDEuNSAxCjYuOSAzLjEgNC45IDEuNSAxCjUuNSAyLjMgNCAgIDEuMyAxCjYuNSAyLjggNC42IDEuNSAxCjUuNyAyLjggNC41IDEuMyAxCjYuMyAzLjMgNC43IDEuNiAxCjQuOSAyLjQgMy4zIDEgICAxCjYuNiAyLjkgNC42IDEuMyAxCjUuMiAyLjcgMy45IDEuNCAxCjUgICAyICAgMy41IDEgICAxCjUuOSAzICAgNC4yIDEuNSAxCjYgICAyLjIgNCAgIDEgICAxCjYuMSAyLjkgNC43IDEuNCAxCjUuNiAyLjkgMy42IDEuMyAxCjYuNyAzLjEgNC40IDEuNCAxCjUuNiAzICAgNC41IDEuNSAxCjUuOCAyLjcgNC4xIDEgICAxCjYuMiAyLjIgNC41IDEuNSAxCjUuNiAyLjUgMy45IDEuMSAxCjUuOSAzLjIgNC44IDEuOCAxCjYuMSAyLjggNCAgIDEuMyAxCjYuMyAyLjUgNC45IDEuNSAxCjYuMSAyLjggNC43IDEuMiAxCjYuNCAyLjkgNC4zIDEuMyAxCjYuNiAzICAgNC40IDEuNCAxCjYuOCAyLjggNC44IDEuNCAxCjYuNyAzICAgNSAgIDEuNyAxCjYgICAyLjkgNC41IDEuNSAxCjUuNyAyLjYgMy41IDEgICAxCjUuNSAyLjQgMy44IDEuMSAxCjUuNSAyLjQgMy43IDEgICAxCjUuOCAyLjcgMy45IDEuMiAxCjYgICAyLjcgNS4xIDEuNiAxCjUuNCAzICAgNC41IDEuNSAxCjYgICAzLjQgNC41IDEuNiAxCjYuNyAzLjEgNC43IDEuNSAxCjYuMyAyLjMgNC40IDEuMyAxCjUuNiAzICAgNC4xIDEuMyAxCjUuNSAyLjUgNCAgIDEuMyAxCjUuNSAyLjYgNC40IDEuMiAxCjYuMSAzICAgNC42IDEuNCAxCjUuOCAyLjYgNCAgIDEuMiAxCjUgICAyLjMgMy4zIDEgICAxCjUuNiAyLjcgNC4yIDEuMyAxCjUuNyAzICAgNC4yIDEuMiAxCjUuNyAyLjkgNC4yIDEuMyAxCjYuMiAyLjkgNC4zIDEuMyAxCjUuMSAyLjUgMyAgIDEuMSAxCjUuNyAyLjggNC4xIDEuMyAxCjYuMyAzLjMgNiAgIDIuNSAyCjUuOCAyLjcgNS4xIDEuOSAyCjcuMSAzICAgNS45IDIuMSAyCjYuMyAyLjkgNS42IDEuOCAyCjYuNSAzICAgNS44IDIuMiAyCjcuNiAzICAgNi42IDIuMSAyCjQuOSAyLjUgNC41IDEuNyAyCjcuMyAyLjkgNi4zIDEuOCAyCjYuNyAyLjUgNS44IDEuOCAyCjcuMiAzLjYgNi4xIDIuNSAyCjYuNSAzLjIgNS4xIDIgICAyCjYuNCAyLjcgNS4zIDEuOSAyCjYuOCAzICAgNS41IDIuMSAyCjUuNyAyLjUgNSAgIDIgICAyCjUuOCAyLjggNS4xIDIuNCAyCjYuNCAzLjIgNS4zIDIuMyAyCjYuNSAzICAgNS41IDEuOCAyCjcuNyAzLjggNi43IDIuMiAyCjcuNyAyLjYgNi45IDIuMyAyCjYgICAyLjIgNSAgIDEuNSAyCjYuOSAzLjIgNS43IDIuMyAyCjUuNiAyLjggNC45IDIgICAyCjcuNyAyLjggNi43IDIgICAyCjYuMyAyLjcgNC45IDEuOCAyCjYuNyAzLjMgNS43IDIuMSAyCjcuMiAzLjIgNiAgIDEuOCAyCjYuMiAyLjggNC44IDEuOCAyCjYuMSAzICAgNC45IDEuOCAyCjYuNCAyLjggNS42IDIuMSAyCjcuMiAzICAgNS44IDEuNiAyCjcuNCAyLjggNi4xIDEuOSAyCjcuOSAzLjggNi40IDIgICAyCjYuNCAyLjggNS42IDIuMiAyCjYuMyAyLjggNS4xIDEuNSAyCjYuMSAyLjYgNS42IDEuNCAyCjcuNyAzICAgNi4xIDIuMyAyCjYuMyAzLjQgNS42IDIuNCAyCjYuNCAzLjEgNS41IDEuOCAyCjYgICAzICAgNC44IDEuOCAyCjYuOSAzLjEgNS40IDIuMSAyCjYuNyAzLjEgNS42IDIuNCAyCjYuOSAzLjEgNS4xIDIuMyAyCjUuOCAyLjcgNS4xIDEuOSAyCjYuOCAzLjIgNS45IDIuMyAyCjYuNyAzLjMgNS43IDIuNSAyCjYuNyAzICAgNS4yIDIuMyAyCjYuMyAyLjUgNSAgIDEuOSAyCjYuNSAzICAgNS4yIDIgICAyCjYuMiAzLjQgNS40IDIuMyAyCjUuOSAzICAgNS4xIDEuOCAyCg==

150 25 125 4
5.1 3.5 1.4 0.2 0
4.9 3   1.4 0.2 0
4.7 3.2 1.3 0.2 0
4.6 3.1 1.5 0.2 0
5   3.6 1.4 0.2 0
5.4 3.9 1.7 0.4 0
4.6 3.4 1.4 0.3 0
5   3.4 1.5 0.2 0
4.4 2.9 1.4 0.2 0
4.9 3.1 1.5 0.1 0
5.4 3.7 1.5 0.2 0
4.8 3.4 1.6 0.2 0
4.8 3   1.4 0.1 0
4.3 3   1.1 0.1 0
5.8 4   1.2 0.2 0
5.7 4.4 1.5 0.4 0
5.4 3.9 1.3 0.4 0
5.1 3.5 1.4 0.3 0
5.7 3.8 1.7 0.3 0
5.1 3.8 1.5 0.3 0
5.4 3.4 1.7 0.2 0
5.1 3.7 1.5 0.4 0
4.6 3.6 1   0.2 0
5.1 3.3 1.7 0.5 0
4.8 3.4 1.9 0.2 0
5   3   1.6 0.2 0
5   3.4 1.6 0.4 0
5.2 3.5 1.5 0.2 0
5.2 3.4 1.4 0.2 0
4.7 3.2 1.6 0.2 0
4.8 3.1 1.6 0.2 0
5.4 3.4 1.5 0.4 0
5.2 4.1 1.5 0.1 0
5.5 4.2 1.4 0.2 0
4.9 3.1 1.5 0.2 0
5   3.2 1.2 0.2 0
5.5 3.5 1.3 0.2 0
4.9 3.6 1.4 0.1 0
4.4 3   1.3 0.2 0
5.1 3.4 1.5 0.2 0
5   3.5 1.3 0.3 0
4.5 2.3 1.3 0.3 0
4.4 3.2 1.3 0.2 0
5   3.5 1.6 0.6 0
5.1 3.8 1.9 0.4 0
4.8 3   1.4 0.3 0
5.1 3.8 1.6 0.2 0
4.6 3.2 1.4 0.2 0
5.3 3.7 1.5 0.2 0
5   3.3 1.4 0.2 0
7   3.2 4.7 1.4 1
6.4 3.2 4.5 1.5 1
6.9 3.1 4.9 1.5 1
5.5 2.3 4   1.3 1
6.5 2.8 4.6 1.5 1
5.7 2.8 4.5 1.3 1
6.3 3.3 4.7 1.6 1
4.9 2.4 3.3 1   1
6.6 2.9 4.6 1.3 1
5.2 2.7 3.9 1.4 1
5   2   3.5 1   1
5.9 3   4.2 1.5 1
6   2.2 4   1   1
6.1 2.9 4.7 1.4 1
5.6 2.9 3.6 1.3 1
6.7 3.1 4.4 1.4 1
5.6 3   4.5 1.5 1
5.8 2.7 4.1 1   1
6.2 2.2 4.5 1.5 1
5.6 2.5 3.9 1.1 1
5.9 3.2 4.8 1.8 1
6.1 2.8 4   1.3 1
6.3 2.5 4.9 1.5 1
6.1 2.8 4.7 1.2 1
6.4 2.9 4.3 1.3 1
6.6 3   4.4 1.4 1
6.8 2.8 4.8 1.4 1
6.7 3   5   1.7 1
6   2.9 4.5 1.5 1
5.7 2.6 3.5 1   1
5.5 2.4 3.8 1.1 1
5.5 2.4 3.7 1   1
5.8 2.7 3.9 1.2 1
6   2.7 5.1 1.6 1
5.4 3   4.5 1.5 1
6   3.4 4.5 1.6 1
6.7 3.1 4.7 1.5 1
6.3 2.3 4.4 1.3 1
5.6 3   4.1 1.3 1
5.5 2.5 4   1.3 1
5.5 2.6 4.4 1.2 1
6.1 3   4.6 1.4 1
5.8 2.6 4   1.2 1
5   2.3 3.3 1   1
5.6 2.7 4.2 1.3 1
5.7 3   4.2 1.2 1
5.7 2.9 4.2 1.3 1
6.2 2.9 4.3 1.3 1
5.1 2.5 3   1.1 1
5.7 2.8 4.1 1.3 1
6.3 3.3 6   2.5 2
5.8 2.7 5.1 1.9 2
7.1 3   5.9 2.1 2
6.3 2.9 5.6 1.8 2
6.5 3   5.8 2.2 2
7.6 3   6.6 2.1 2
4.9 2.5 4.5 1.7 2
7.3 2.9 6.3 1.8 2
6.7 2.5 5.8 1.8 2
7.2 3.6 6.1 2.5 2
6.5 3.2 5.1 2   2
6.4 2.7 5.3 1.9 2
6.8 3   5.5 2.1 2
5.7 2.5 5   2   2
5.8 2.8 5.1 2.4 2
6.4 3.2 5.3 2.3 2
6.5 3   5.5 1.8 2
7.7 3.8 6.7 2.2 2
7.7 2.6 6.9 2.3 2
6   2.2 5   1.5 2
6.9 3.2 5.7 2.3 2
5.6 2.8 4.9 2   2
7.7 2.8 6.7 2   2
6.3 2.7 4.9 1.8 2
6.7 3.3 5.7 2.1 2
7.2 3.2 6   1.8 2
6.2 2.8 4.8 1.8 2
6.1 3   4.9 1.8 2
6.4 2.8 5.6 2.1 2
7.2 3   5.8 1.6 2
7.4 2.8 6.1 1.9 2
7.9 3.8 6.4 2   2
6.4 2.8 5.6 2.2 2
6.3 2.8 5.1 1.5 2
6.1 2.6 5.6 1.4 2
7.7 3   6.1 2.3 2
6.3 3.4 5.6 2.4 2
6.4 3.1 5.5 1.8 2
6   3   4.8 1.8 2
6.9 3.1 5.4 2.1 2
6.7 3.1 5.6 2.4 2
6.9 3.1 5.1 2.3 2
5.8 2.7 5.1 1.9 2
6.8 3.2 5.9 2.3 2
6.7 3.3 5.7 2.5 2
6.7 3   5.2 2.3 2
6.3 2.5 5   1.9 2
6.5 3   5.2 2   2
6.2 3.4 5.4 2.3 2
5.9 3   5.1 1.8 2

stdout

copy

-----
numTrees=1
totalError=48
-----
numTrees=2
totalError=39
-----
numTrees=3
totalError=15
-----
numTrees=4
totalError=14
-----
numTrees=5
totalError=8
-----
numTrees=6
totalError=12
-----
numTrees=7
totalError=10
-----
numTrees=8
totalError=11
-----
numTrees=9
totalError=8
-----
numTrees=10
totalError=8
-----
numTrees=11
totalError=8
-----
numTrees=12
totalError=8
-----
numTrees=13
totalError=8
-----
numTrees=14
totalError=8
-----
numTrees=15
totalError=8
-----
numTrees=16
totalError=8
-----
numTrees=17
totalError=8
-----
numTrees=18
totalError=8
-----
numTrees=19
totalError=8
-----
numTrees=20
totalError=8

https://ideone.com/1einvv

language:

C++14 (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language