結果

問題 No.159 刺さらないUSB
コンテスト
ユーザー koyumeishi
提出日時 2015-03-05 00:01:57
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 2,292 bytes
コンパイル時間 895 ms
コンパイル使用メモリ 83,508 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-01 23:42:59
合計ジャッジ時間 1,606 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;

//マルコフなんちゃらの練習

//[n*p] * [p*m] => [n*m]
template<class T>
vector< vector<T> > multmat(const vector<vector<T> > &A, const vector<vector<T>> &B, int n, int p, int m){
	vector<vector<T> > C(n, vector<T>(m,0));
	for(int i=0; i<n; i++){
		for(int k=0; k<p; k++){
			for(int j=0; j<m; j++){
				C[i][j] += A[i][k] * B[k][j];
				//C[i][j] %= mod;
			}
		}
	}
	return C;
}

//A[n*n]^k 
template<class T>
vector< vector<T> > mat_pow(vector<vector<T> > A, int k){
	int n = A.size();
	vector<vector<T> > ret(n, vector<T>(n, 0) );
	for(int i=0; i<n; i++){
		ret[i][i] = 1;
	}
	while(k>0){
		if(k&1) ret = multmat(A,ret, n,n,n);
		A = multmat(A,A, n,n,n);
		k>>=1;
	}
	return ret;
}

void print_vec(const vector<vector<double>> &v){
#ifdef DBG_
	for(auto l : v){
		for(auto x : l){
			cerr << x << "\t";
		}
		cerr << endl;
	}
	cerr << endl;
#endif
}

int main(){
	double p,q;
	cin >> p >> q;

	//遷移図的な何か
	// aは表の状態、 bは裏の状態、 sははじめ、 tは終わり
	// s -> a (p)
	//   -> b (1-p)
	// a -> t (q)
	//   -> b (1-q)
	// b -> a (1)
	// t -> t (1)

	//遷移行列
	vector<vector<double>> P(4, vector<double>(4,0));
	P = {
	//   s   a    b   t
		{0,  p, 1-p,  0},
		{0,  0, 1-q,  q},
		{0,  1,   0,  0},
		{0,  0,   0,  1}	// <- ここが吸収状態
	};
	print_vec(P);

	//初期状態
	vector<vector<double>> S(1, vector<double>(4,0));
	S = { {1,0,0,0} };
	print_vec(S);

	double p1, p2;

	auto P2 = mat_pow<double>(P, 2);	//0回ひっくり返す
	print_vec(P2);

	auto P3 = mat_pow<double>(P, 3);	//1回ひっくり返す
	print_vec(P3);

	auto P4 = mat_pow<double>(P, 4);	//2回ひっくり返す
	print_vec(P4);

	{
		auto tmp = multmat<double>(S, P3, 1,4,4);
		auto tmp_ = multmat<double>(S, P2, 1,4,4);

		print_vec(tmp);
		print_vec(tmp_);

		p1 = tmp[0][3] - tmp_[0][3];
	}
	{
		auto tmp = multmat<double>(S, P4, 1,4,4);
		auto tmp_ = multmat<double>(S, P3, 1,4,4);

		print_vec(tmp);
		print_vec(tmp_);

		p2 = tmp[0][3] - tmp_[0][3];
	}

	//cerr << p1 << " " << p2 << endl;
	cout << (p1<p2 ? "YES" : "NO") << endl;
	return 0;
}
0