游客 Signup | Login
中文 | En

2003 - The Lucky Game

通过次数

0

提交次数

0

Time Limit : 1 秒 Memory Limit : 128 MB

John and Brus believe that the digits 4 and 7 are lucky and all others are not. According to them, a lucky number is a number that contains only lucky digits in its decimal representation.

John and Brus play the following game. Initially, there is an interval of integers between a and b, inclusive. Then, John choose a subinterval of the initial interval that contains exactly jLen numbers. Finally, Brus chooses a subinterval of John's subinterval that contains exactly bLen numbers. The outcome of the game is the total number of lucky numbers in Brus's subinterval.

John follows the optimal strategy that maximizes the outcome. Brus follows the optimal strategy that minimizes the outcome. Return the outcome of the game.

Input

Each line contains four integers a,b,jLen,bLen.

1<=a<=b<=4747

1<=jLen<=b-a+1

1<=bLen<=jLen

Output

For each line of input,print the outcome of the game.

Examples

Input Format

1 10 2 1
4 8 3 2

Output Format

0
1

Solution C++

#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

class TheLuckyGameDivTwo {
    public:
        static const int MAX = 5000;

        int t[MAX];

        bool check(int n) {
            while (n) {
                int d = n%10;
                n /= 10;

                if (d != 4 && d != 7) {
                    return false;
                }
            }
            return true;
        }


        int find(int a, int b, int jLen, int bLen) {
            int ret;

            memset(t, 0, sizeof(t));

            t[a] = check(a);
            for (int i = a+1; i <= b; ++i) {
                t[i] = t[i-1]+check(i);
            }

            ret = -1;
            for (int i = a-1; i <= b-jLen; ++i) {
                int aa = i;
                int bb = i+jLen;

                int cur = 1000005;
                for (int j = aa; j <= bb-bLen; ++j) {
                    int tmp = t[j+bLen]-t[j];
                    cur = min(cur, tmp);
                }
                ret = max(ret, cur);
            }

            return ret;
        }
};
int main(){
  int a,b,jLen,bLen;
  class TheLuckyGameDivTwo solution;
  while(cin>>a>>b>>jLen>>bLen){
    cout<<solution.find(a,b,jLen,bLen)<<endl;
  }
  return 0;
}

Solution Java

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int[] ok=new int[5000];
        for(int i=1;i<=4747;i++){
            int p=i;
            while(p>0){
                if(p%10==4||p%10==7)
                    p/=10;
                else {
                    p=-1;
                    break;
                }
            }
            if(p==0) 
                ok[i]=1;
            else
                ok[i]=0;
        }
        int[] sum=new int[5000];
        sum[0]=0;
        for(int i=1;i<=4747;i++){
            if(ok[i]==1){
                sum[i]=sum[i-1]+1;            
            }
            else{
                sum[i]=sum[i-1];
            }
        }
        while(in.hasNext()){
            int a=in.nextInt();
            int b=in.nextInt();
            int jlen=in.nextInt();
            int blen=in.nextInt();
            int Max=sum[a+jlen-1]-sum[a-1];
            for(int i=a+1;i+jlen-1<=b;i++){
                if(sum[i+jlen-1]-sum[i-1]>Max){
                    Max=sum[i+jlen-1]-sum[i-1];
                }
            }
            int ans=0;
            for(int i=a;i+jlen-1<=b;i++){
                if(sum[i+jlen-1]-sum[i-1]==Max){
                    int ans1=sum[i+blen-1]-sum[i-1];
                    for(int j=i+1;j+blen-1<=i+jlen-1;j++){
                        ans1=Math.min(ans1,sum[j+blen-1]-sum[j-1]);
                    }
                    ans=Math.max(ans,ans1);
                }
            }
            System.out.println(ans);
        }
    }
}
请先登陆