HDUOJ 2089

싫다
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7767    Accepted Submission(s): 2396
Problem Description
항 저 우 사람들 은 그 멍청 하고 끈적끈적 한 사람들 을 62 라 고 부른다.
항 저 우 교통 관리 국 은 택시 번호판 을 늘 리 는 경우 가 많다.최근 에 좋 은 소식 이 나 왔 다.앞으로 번호판 을 올 리 면 더 이상 불길 한 숫자 가 포함 되 지 않 는 다.그러면 개별 택시 기사 와 승객 들 의 심리 적 장 애 를 없 애고 대중 에 게 더욱 안전하게 서 비 스 를 제공 할 수 있다.
불길 한 숫자 는 4 나 62 가 들 어 있 는 모든 번호 다.예 를 들 면:
62315 73418 88914
모두 불길 한 번호 에 속한다.그러나 61152 에는 6 과 2 가 들 어 있 지만 62 일련 번 호 는 아니 기 때문에 불길 한 숫자 에 속 하지 않 는 다.
당신 의 임 무 는 매번 제시 하 는 번호판 구간 번호 에 대해 서 는 교통 관리 국 이 이번 에는 실제로 몇 대의 새 택시 에 번호판 을 찍 어야 하 는 지 추정 하 는 것 입 니 다.
 
Input
입력 한 것 은 모두 정수 대 n,m(0 
Output
모든 정수 쌍 에 대해 불길 한 숫자 가 없 는 통계 개 수 를 출력 하 는데 이 수 치 는 한 줄 의 위 치 를 차지한다.
 
Sample Input

   
   
   
   
1 100 0 0

 
Sample Output

   
   
   
   
80

 
Author
qianneng
 
이 문 제 는 배열 조합 방법 으로 계산 하려 고 했 으 나 생각 하지 못 했다.나중에 인터넷 의 알고리즘 을 참조 하여 만 든 셈 이지 만 140 ms 가 필요 하고 메모리 사용량 이 매우 높다.
4 나 62 가 함 유 된 숫자 를 선별 하 는 방법 은 나 는 그래도 매우 공교롭다 고 생각한다.AC 코드 는 다음 과 같 습 니 다.
#include <iostream>
using namespace std;
short int a[1000000];
int main()
{   
	int m,n,i,t,count;
	memset(a,0,sizeof(a));
	//     4 62   
	for(i=1;i<=999994;i++)
	{
		t=i;
		while(t)
		{
			if(t%10==4 || t%100==62)
			{
				a[i]=1;
				break;
			}
			t/=10;
		}
	}
	while(scanf("%d%d",&n,&m) && n)
	{
		count=0;
		for(i=n;i<=m;i++)
		{
			if(a[i]==0) count++;
		}
		printf("%d
",count); } return 0; }

좋은 웹페이지 즐겨찾기