UVA 10025(수학)
2453 단어 uva
The ? 일?2 ? ... ? n = k problem
The problem
Given the following formula, one can set operators '+' or '-' instead of each '?', in order to obtain a given k ? 일?2 ? ... ? n = k
For example: to obtain k = 12 , the expression to be used will be: - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7
The Input
The first line is the number of test cases, followed by a blank line.
Each test case of the input contains integer k (0<=|k|<=1000000000).
Each test case will be separated by a single line.
The Output
For each test case, your program should print the minimal possible n (1<=n) to obtain k with the above formula.
Print a blank line between the outputs for two consecutive test cases.
Sample Input
2
12
-3646397
Sample Output
7
2701
먼저 첫 번째 s=1+2+3+...+n>=k의 첫 번째 n은 s-k가 짝수라고 가정하면 이때 n은 최소값이다. 그렇지 않으면 최소값은 n+1 또는 n+2(연속된 두 수에 반드시 하나의 홀수가 있기 때문에 s-k의 짝성을 바꿀 수 있다).... 때문에
우선 n개수의 짝수와 k의 짝수가 같아야 한다. 아무리 기호 n개수의 짝수가 바뀌어도 변하지 않기 때문에 짝성이 같으면 n-k는 짝수일 것이다. n-k는 짝수일 때 변호의 수는 (n-k)/2, s'=k, s-(s-k)=1+2+...
-(n-k)/2
+....n=k;그래서 이때 구한 n은 반드시 k를 구성할 수 있고 가장 작은 것이다. 코드는 다음과 같다.#include<stdio.h>
#include<math.h>
int main()
{
int i,k,n,m;
scanf("%d",&n);
while(n--)
{
scanf("%d",&k);
if(m==0)printf("3
");
else
{
k=k>0?k:-k;
m=sqrt(2*k);
for(i=m;i*(i+1)<2*k;i++);
while(1)
if((i*(i+1)/2-k)%2)i++;//
else break;
printf("%d
",i);
}
if(n)printf("
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
UVA - 10986 Sending email(Dijkstra 인접 테이블 + 우선 순위 대기열 최적화)
제목 대의:
s점에서 t점까지의 최소 거리를 구하는 그림을 주세요.
확인:
적나라한 최단길이지만 n이 너무 크면 인접 행렬을 사용할 수 없기 때문에 Dijkstra에 대한 인접표 + 우선 대기열 최적화가 필요합니다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
2
12
-3646397
7
2701
#include<stdio.h>
#include<math.h>
int main()
{
int i,k,n,m;
scanf("%d",&n);
while(n--)
{
scanf("%d",&k);
if(m==0)printf("3
");
else
{
k=k>0?k:-k;
m=sqrt(2*k);
for(i=m;i*(i+1)<2*k;i++);
while(1)
if((i*(i+1)/2-k)%2)i++;//
else break;
printf("%d
",i);
}
if(n)printf("
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
UVA - 10986 Sending email(Dijkstra 인접 테이블 + 우선 순위 대기열 최적화)제목 대의: s점에서 t점까지의 최소 거리를 구하는 그림을 주세요. 확인: 적나라한 최단길이지만 n이 너무 크면 인접 행렬을 사용할 수 없기 때문에 Dijkstra에 대한 인접표 + 우선 대기열 최적화가 필요합니다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
