글 읽기 - 시간초과 좀 봐주세요 ㅠ.,

cktmdgns 9년 전 0

이중 반복문이라 시간이 엄청 오래걸리는데

어떤식으로 해결해야하나요 ?!??

뭔가 공식같은걸 찾아내서 풀어야하나요???

#include<stdio.h>
int main (void)
{
	long long int x,y,z,i,n,j,k,sum[101]={0},de;
	scanf("%lld",&n);
	for(i=0;i<n;i++)
	{
	scanf("%lld %lld",&x,&y);
	for(j=x;j<=y;j++)
	{
		de=1;
		for(k=0;1;k++)
		{
			if(j/de!=0)
			{
				sum[i]+=(j/de)%10;
			de*=10;
			}
			else
			break;
		}
	}
	}

	for(i=0;i<n;i++)
	{
	printf("%lld\n",sum[i]);
	}

	return 0;
}

algoshipda 9년 전 1

(0 ≤ a ≤ b ≤10^15)라 a~b구간 사이를 일일히 조사하는 식이면 선형이여도 안되지 않을까요.

cktmdgns 9년 전 0

그럼 규칙을 찾아야하는 문제인가요???

Nada 9년 전 1

1~N까지의 합을 다이나믹을 이용해서 상수 시간만에 구할 수 있고

(1~b) - (1~a-1) 구간을 빼주는 식으로 구하면 총 O(1) 만에 풀 수가 있습니다.

자릿수 단위로 끊어서 생각해 보시면 될 거에요.

cktmdgns 9년 전 1

감사합니다 ㅎ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 좀 봐주세요 ㅠ.,

cktmdgns 9년 전 0

algoshipda 9년 전 1

cktmdgns 9년 전 0

Nada 9년 전 1

cktmdgns 9년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말