UVA 10328 Coin Toss

Coin Toss

Time Limit: 3000ms

Memory Limit: 131072KB

This problem will be judged on UVA. Original ID: 10328
64-bit integer IO format: %lld Java class name: Main

Toss is an important part of any event. When everything becomes equal toss is the ultimate decider. Normally a fair coin is used for Toss. A coin has two sides head(H) and tail(T). Superstition may work in case of choosing head or tail. If anyone becomes winner choosing head he always wants to choose head. Nobody believes that his winning chance is 50-50. However in this problem we will deal with a fair coin and n times tossing of such a coin. The result of such a tossing can be represented by a string. Such as if 3 times tossing is used then there are possible 8 outcomes.

HHH HHT HTH HTT THH THT TTH TTT

As the coin is fair we can consider that the probability of each outcome is also equal. For simplicity we can consider that if the same thing is repeated 8 times we can expect to get each possible sequence once.

The Problem

In the above example we see 1 sequnce has 3 consecutive H, 3 sequence has 2 consecutive H and 7 sequence has at least single H. You have to generalize it. Suppose a coin is tossed n times. And the same process is repeated 2^n times. How many sequence you will get which contains a consequnce of H of length at least k.

The Input

The input will start with two positive integer, n and k (1<=k<=n<=100). Input is terminated by EOF.

The Output

For each test case show the result in a line as specified in the problem statement.

Sample Input

Sample Output

解题：解题思路跟zoj 3747 一样

dp[i][0] 表示连续u个正面且第i个是正面的方案数

需要注意的是这道题目是需要用大数的，也就是需要高精度

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef long long LL;
  4 #define MAXN 100
  5 struct HP {
  6     int len,s[MAXN];
  7     HP() {
  8         memset(s,0,sizeof(s));
  9         len=1;
 10     }
 11     HP operator =(const char *num) { //字符串赋值
 12         len=strlen(num);
 13         for(int i=0; i<len; i++) s[i]=num[len-i-1]-'0';
 14     }
 15 
 16     HP operator =(int num) { //int 赋值
 17         char s[MAXN];
 18         sprintf(s,"%d",num);
 19         *this=s;
 20         return *this;
 21     }
 22 
 23     HP(int num) {
 24         *this=num;
 25     }
 26 
 27     HP(const char*num) {
 28         *this=num;
 29     }
 30 
 31     string str()const { //转化成string
 32         string res="";
 33         for(int i=0; i<len; i++) res=(char)(s[i]+'0')+res;
 34         if(res=="") res="0";
 35         return res;
 36     }
 37 
 38     HP operator +(const HP& b) const {
 39         HP c;
 40         c.len=0;
 41         for(int i=0,g=0; g||i<max(len,b.len); i++) {
 42             int x=g;
 43             if(i<len) x+=s[i];
 44             if(i<b.len) x+=b.s[i];
 45             c.s[c.len++]=x%10;
 46             g=x/10;
 47         }
 48         return c;
 49     }
 50     void clean() {
 51         while(len > 1 && !s[len-1]) len--;
 52     }
 53 
 54     HP operator *(const HP& b) {
 55         HP c;
 56         c.len=len+b.len;
 57         for(int i=0; i<len; i++)
 58             for(int j=0; j<b.len; j++)
 59                 c.s[i+j]+=s[i]*b.s[j];
 60         for(int i=0; i<c.len-1; i++) {
 61             c.s[i+1]+=c.s[i]/10;
 62             c.s[i]%=10;
 63         }
 64         c.clean();
 65         return c;
 66     }
 67 
 68     HP operator - (const HP& b) {
 69         HP c;
 70         c.len = 0;
 71         for(int i=0,g=0; i<len; i++) {
 72             int x=s[i]-g;
 73             if(i<b.len) x-=b.s[i];
 74             if(x>=0) g=0;
 75             else {
 76                 g=1;
 77                 x+=10;
 78             }
 79             c.s[c.len++]=x;
 80         }
 81         c.clean();
 82         return c;
 83     }
 84     HP operator / (const HP &b) {
 85         HP c, f = 0;
 86         for(int i = len-1; i >= 0; i--) {
 87             f = f*10;
 88             f.s[0] = s[i];
 89             while(f>=b) {
 90                 f =f-b;
 91                 c.s[i]++;
 92             }
 93         }
 94         c.len = len;
 95         c.clean();
 96         return c;
 97     }
 98     HP operator % (const HP &b) {
 99         HP r = *this / b;
100         r = *this - r*b;
101         return r;
102     }
103 
104     HP operator /= (const HP &b) {
105         *this  = *this / b;
106         return *this;
107     }
108 
109 
110     HP operator %= (const HP &b) {
111         *this = *this % b;
112         return *this;
113     }
114 
115     bool operator < (const HP& b) const {
116         if(len != b.len) return len < b.len;
117         for(int i = len-1; i >= 0; i--)
118             if(s[i] != b.s[i]) return s[i] < b.s[i];
119         return false;
120     }
121 
122     bool operator > (const HP& b) const {
123         return b < *this;
124     }
125 
126     bool operator <= (const HP& b) {
127         return !(b < *this);
128     }
129 
130     bool operator == (const HP& b) {
131         return !(b < *this) && !(*this < b);
132     }
133     bool operator != (const HP &b) {
134         return !(*this == b);
135     }
136     HP operator += (const HP& b) {
137         *this = *this + b;
138         return *this;
139     }
140     bool operator >= (const HP &b) {
141         return *this > b || *this == b;
142     }
143 
144 
145 };
146 
147 istream& operator >>(istream &in, HP& x) {
148     string s;
149     in >> s;
150     x = s.c_str();
151     return in;
152 }
153 
154 ostream& operator <<(ostream &out, const HP& x) {
155     out << x.str();
156     return out;
157 }
158 const int maxn = 110;
159 HP dp[maxn][2];//dp[i][0]表示第i个正
160 int n,k;
161 HP solve(int u){
162     dp[0][0] = 1;
163     dp[0][1] = 0;
164     for(int i = 1; i <= n; ++i){
165         if(i <= u) dp[i][0] = dp[i-1][0] + dp[i-1][1];
166         if(i == u + 1) dp[i][0] = dp[i-1][0] + dp[i-1][1] - 1;
167         if(i > u + 1) dp[i][0] = dp[i-1][0] + dp[i-1][1] - dp[i - u - 1][1];
168         dp[i][1] = dp[i-1][0] + dp[i-1][1];
169     }
170     return (dp[n][0] + dp[n][1]);
171 }
172 int main(){
173     while(~scanf("%d%d",&n,&k))
174         cout<<solve(n) - solve(k-1)<<endl;
175     return 0;
176 }

View Code