ACdream 그룹 트레이닝 경기(38)/J - Positive Negative Sign
J - Positive Negative Sign
Time Limit:
2000
MS
Memory Limit:
32768
KB
64bit IO Format:
unknown
Description
Given two integers: n and m and n is divisible by 2m, you have to write down the first n natural numbers in the following form. At first take first m integers and make their sign negative, then take next m integers and make their sign positive, the next m integers should have negative signs and continue this procedure until all the n integers have been assigned a sign. For example, let n be 12 and m be 3. Then we have
-1 -2 -3 +4 +5 +6 -7 -8 -9 +10 +11 +12
If n = 4 and m = 1, then we have
-1 +2 -3 +4
Now your task is to find the summation of the numbers considering their signs.
Input
Input starts with an integer T (≤ 10000), denoting the number of test cases.
Each case starts with a line containing two integers: n and m (2 ≤ n ≤ 109, 1 ≤ m). And you can assume that n is divisible by 2*m.
Output
For each case, print the case number and the summation.
Sample Input
이
12 3
4 1
Sample Output
Case 1: 18
Case 2: 2
분석:
간단한 문제.(자꾸 힘들게 끝내고 보니 간단한 문제였다...)
데이터 규모를 보면 왼쪽에서 오른쪽으로 계산하면 반드시 시간을 초과해야 한다는 것을 알 수 있다.(가소롭게도 한 번 더 해봤는데 그렇게 많은 시간을 낭비했어...)
이런 대규모 데이터는 단지 몇 가지 상황만 생각할 뿐이다. 2점?동규아니면 수학 공식?
분명히 이 문제는 수학 공식이다.우리는 n이 2m에서 제거될 수 있다는 것을 발견할 수 있다. 모든 수는 반드시 m개를 먼저 줄이고 m개를 더해야 한다.그러면 우리는 매번 1을 빼고 1을 더하면 마지막 결과는 m*m를 더 넣는다는 것을 한층 더 발견했다.예를 들어 -1,-2,-3,+4,+5,+6, (4-1)+(5-2)+(6-3)로 볼 수 있다.총 선감후 n/2m회 추가.그래서 마지막 결과는 m*m*n/2m=n*m/2입니다.
여기에 숫자의 범위를 관찰해야 한다. 최악의 경우 n=100000000m=500000000이기 때문에 마지막 답은 롱롱이 필요하다.#include <iostream>
using namespace std;
int main()
{
int t;
long long n,m;
cin>>t;
for (int i=0;i<t;i++)
{
cin>>n>>m;
long long ans=n*m/2;
cout<<"Case "<<i+1<<": "<<ans<<endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java 입출력 I/O
스트림(stream)
자바에서 입출력을 수행하려면 두 대상을 연결하고 데이터를 전송할 수 있는 무언가가 필요한데 이것을 스트림(stream)이라고 정의했다.
스트림은 단방향 통신만 가능하기 때문에 하나의 스트림으로 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include <iostream>
using namespace std;
int main()
{
int t;
long long n,m;
cin>>t;
for (int i=0;i<t;i++)
{
cin>>n>>m;
long long ans=n*m/2;
cout<<"Case "<<i+1<<": "<<ans<<endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java 입출력 I/O스트림(stream) 자바에서 입출력을 수행하려면 두 대상을 연결하고 데이터를 전송할 수 있는 무언가가 필요한데 이것을 스트림(stream)이라고 정의했다. 스트림은 단방향 통신만 가능하기 때문에 하나의 스트림으로 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.