首页 > 代码库 > 微软2017年预科生计划在线编程笔试
微软2017年预科生计划在线编程笔试
Legendary Items
答案是每一件物品需要的期望步数和
1 #include <bits/stdc++.h> 2 #define ll long long 3 #define ull unsigned long long 4 #define st first 5 #define nd second 6 #define pii pair<int, int> 7 #define pil pair<int, ll> 8 #define pli pair<ll, int> 9 #define pll pair<ll, ll> 10 #define pw(x) ((1LL)<<(x)) 11 #define lson l, m, rt<<1 12 #define rson m+1, r, rt<<1|1 13 #define FIN freopen("input.txt","r",stdin); 14 #define FOUT freopen("output.txt","w+",stdout); 15 using namespace std; 16 /***********/ 17 template <class T> 18 bool scan (T &ret) { 19 char c; 20 int sgn; 21 if (c = getchar(), c == EOF) return 0; //EOF 22 while (c != ‘-‘ && (c < ‘0‘ || c > ‘9‘) ) c = getchar(); 23 sgn = (c == ‘-‘) ? -1 : 1; 24 ret = (c == ‘-‘) ? 0 : (c - ‘0‘); 25 while (c = getchar(), c >= ‘0‘ && c <= ‘9‘) ret = ret * 10 + (c - ‘0‘); 26 ret *= sgn; 27 return 1; 28 } 29 template<typename N,typename PN>inline N flo(N a,PN b){return a>=0?a/b:-((-a-1)/b)-1;} 30 template<typename N,typename PN>inline N cei(N a,PN b){return a>0?(a-1)/b+1:-(-a/b);} 31 template<typename T> 32 inline int sgn(T a) {return a>0?1:(a<0?-1:0);} 33 template <class T1, class T2> 34 bool gmax(T1 &a, const T2 &b) { return a < b? a = b, 1:0;} 35 template <class T1, class T2> 36 bool gmin(T1 &a, const T2 &b) { return a > b? a = b, 1:0;} 37 38 template<class A, class B, class C> 39 struct Triple { 40 A st; B nd; C rd; 41 bool operator <(const Triple &rhs) const { 42 return st == rhs.st? (nd == rhs.nd? rd < rhs.rd: nd < rhs.nd): st < rhs.st; 43 } 44 }; 45 typedef Triple<int, int, int> tiii; 46 47 template<class T1, class T2> 48 ostream& operator <<(ostream &out, pair<T1, T2> p) { 49 return out << "(" << p.st << ", " << p.nd << ")"; 50 } 51 template<class A, class B, class C> 52 ostream& operator <<(ostream &out, Triple<A, B, C> t) { 53 return out << "(" << t.st << ", " << t.nd << ", " << t.rd << ")"; 54 } 55 template<class T> 56 ostream& operator <<(ostream &out, vector<T> vec) { 57 out << "("; for(auto &x: vec) out << x << ", "; return out << ")"; 58 } 59 const int inf = 0x3f3f3f3f; 60 const ll INF = 1e18; 61 const ll mod = 1e9+7; 62 const double eps = 1e-5; 63 const int N = 2e5+10; 64 /***********/ 65 66 double e(int p, int q){//当前概率p, 每次增长q 67 double ans = 0, ret = 1; 68 for(int i = 1; ; p += q, i++){ 69 if(p >= 100){ 70 ans += i*ret; 71 return ans; 72 } 73 ans += i*ret*p*0.01; 74 ret *= 1-p*0.01; 75 } 76 } 77 double f[101][101]; 78 int main(){ 79 for(int i = 0; i <= 100; i++) 80 for(int j = 1; j <= 100; j++) 81 f[i][j] = e(i, j); 82 int n, p, q; 83 while(~scanf("%d%d%d", &p, &q, &n)){ 84 double ans = 0; 85 for(int i = 0; i < n; i++) 86 if(p >> i) 87 ans += f[p>>i][q]; 88 else { 89 //(n-i)个f[0][q]累加精度损失过大, WA 90 ans += f[0][q]*(n-i); 91 break; 92 } 93 printf("%.2f\n", ans); 94 } 95 return 0; 96 }
微软2017年预科生计划在线编程笔试
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。