2002 - The Almost Lucky Numbers

通过次数

提交次数

旧版界面

时间限制 : 1 秒内存限制 : 128 MB

John and Brus believe that the digits 4 and 7 are lucky and all others are not. According to them, an almost lucky number is a number that contains at most one non-lucky digit in its decimal representation. Return the total number of almost lucky numbers between a and b, inclusive.

题目输入

Each line contains two integers a,b<=1,000,000

题目输出

For each line of input,output the total number of almost lucky numbers between a and b, inclusive.

输入/输出样例

输入格式

4 7
8 19

输出格式

4
4

C语言解答

#include<stdio.h>

int main()
{
    int a, b, t;
    while(scanf("%d%d", &a, &b) != EOF){
       int sum = 0;
       for(int i = a; i <= b; i++){
       t = i;
       int count = 0 ;
       while(t){
         if((t % 10 != 4 ) && (t % 10 != 7)) count++;
         t = t / 10;
       }
       if(count < 2) sum++;
       }
       printf("%d\n", sum);
    }
    return 0;
}

C++解答

#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <map>
using namespace std;
vector<int>v;
int vis[10];
bool is_ok(int n){
    memset(vis,0,sizeof(vis));
    while(n){
        vis[n%10]++;
        n/=10;
    }
    int ans=0;
    for(int i=0;i<=9;i++){
        if(i==4 || i==7)
            continue;
        else
            ans+=vis[i];
    }
    if(ans>1)
        return false;
    return true;
}
int main()
{
    v.clear();
    for(int i=0;i<=1000000;i++){
        if(is_ok(i))
            v.push_back(i);
    }
    int a,b;
    while(cin>>a>>b){
        if(a>b)
            swap(a,b);
        while(!is_ok(a))
            a++;
        while(!is_ok(b))
            b--;
        cout<<lower_bound(v.begin(),v.end(),b)-
        lower_bound(v.begin(),v.end(),a)+1<<endl;
    }
    return 0;
}

Java解答

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
	static long a, b, tmp;
	static int cnt;

	static void dfs(long n, boolean has) {
		if (n > a)
			return;
		if (n >= b && n <= a)
			cnt++;
		dfs(n * 10 + 4, has);
		dfs(n * 10 + 7, has);
		if (has)
			for (int i = (n == 0 ? 1 : 0); i <= 9; i++) {
				if (i == 4 || i == 7)
					continue;
				dfs(n * 10 + i, false);
			}
	}

	public static void main(String[] args) {
		InputReader cin = new InputReader(System.in);
		OutputWriter out = new OutputWriter(System.out);
		while (cin.hasNext()) {
			a = cin.nextLong();
			b = cin.nextLong();
			if (a < b) {
				tmp = a;
				a = b;
				b = tmp;
			}
			cnt = 0;
			dfs(0, true);
			out.println(cnt);
		}
      	out.close();
	}
}

class InputReader {
	private boolean finished = false;

	private InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar;
	private int numChars;
	private SpaceCharFilter filter;

	public InputReader(InputStream stream) {
		this.stream = stream;
	}

	public int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int peek() {
		if (numChars == -1)
			return -1;
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				return -1;
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public String nextString() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return isWhitespace(c);
	}

	public static boolean isWhitespace(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private String readLine0() {
		StringBuilder buf = new StringBuilder();
		int c = read();
		while (c != '\n' && c != -1) {
			if (c != '\r')
				buf.appendCodePoint(c);
			c = read();
		}
		return buf.toString();
	}

	public String nextLine() {
		String s = readLine0();
		while (s.trim().length() == 0)
			s = readLine0();
		return s;
	}

	public String nextLine(boolean ignoreEmptyLines) {
		if (ignoreEmptyLines)
			return nextLine();
		else
			return readLine0();
	}

	public BigInteger nextBigInteger() {
		try {
			return new BigInteger(nextString());
		} catch (NumberFormatException e) {
			throw new InputMismatchException();
		}
	}

	public char nextCharacter() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		return (char) c;
	}

	public double nextDouble() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		double res = 0;
		while (!isSpaceChar(c) && c != '.') {
			if (c == 'e' || c == 'E')
				return res * Math.pow(10, nextInt());
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		}
		if (c == '.') {
			c = read();
			double m = 1;
			while (!isSpaceChar(c)) {
				if (c == 'e' || c == 'E')
					return res * Math.pow(10, nextInt());
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				m /= 10;
				res += (c - '0') * m;
				c = read();
			}
		}
		return res * sgn;
	}

	public boolean isExhausted() {
		int value;
		while (isSpaceChar(value = peek()) && value != -1)
			read();
		return value == -1;
	}

	public boolean hasNext() {
		return !isExhausted();
	}

	public String next() {
		return nextString();
	}

	public SpaceCharFilter getFilter() {
		return filter;
	}

	public void setFilter(SpaceCharFilter filter) {
		this.filter = filter;
	}

	public interface SpaceCharFilter {
		public boolean isSpaceChar(int ch);
	}
}

class OutputWriter {
	private final PrintWriter writer;

	public OutputWriter(OutputStream outputStream) {
		writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(
				outputStream)));
	}

	public OutputWriter(Writer writer) {
		this.writer = new PrintWriter(writer);
	}

	public void print(Object... objects) {
		for (int i = 0; i < objects.length; i++) {
			if (i != 0)
				writer.print(' ');
			writer.print(objects[i]);
		}
	}

	public void print(int[] array) {
		for (int i = 0; i < array.length; i++) {
			if (i != 0)
				writer.print(' ');
			writer.print(array[i]);
		}
	}

	public void print(long[] array) {
		for (int i = 0; i < array.length; i++) {
			if (i != 0)
				writer.print(' ');
			writer.print(array[i]);
		}
	}

	public void printLine(int[] array) {
		print(array);
		writer.println();
	}

	public void printLine(long[] array) {
		print(array);
		writer.println();
	}

	public void printLine() {
		writer.println();
	}

	public void printLine(Object... objects) {
		print(objects);
		writer.println();
	}

	public void print(char i) {
		writer.print(i);
	}

	public void printLine(char[] array) {
		writer.println(array);
	}

	public void printFormat(String format, Object... objects) {
		writer.printf(format, objects);
	}

	public void println(Object... objects) {
		print(objects);
		writer.println();
	}

	public void println() {
		writer.println();
	}

	public void printf(String format, Object... args) {
		writer.printf(format, args);
	}

	public void close() {
		writer.close();
	}

	public void flush() {
		writer.flush();
	}
}

上一题下一题代码讨论统计