例如 N = 18 L = 2:
5 + 6 + 7 = 18
3 + 4 + 5 + 6 = 18
都是满足要求的,但是我们输出更短的 5 6 7
数据范围:
, 
输入数据包括一行: 两个正整数N(1 ≤ N ≤ 1000000000),L(2 ≤ L ≤ 100)
从小到大输出这段连续非负整数,以空格分隔,行末无空格。如果没有这样的序列或者找出的序列长度大于100,则输出No
18 2
5 6 7
30 13
No
无法由非负整数构成
from sys import stdin
def check(N, L):
if N*2 % L == 0:
if (N*2/L+1-L)%2 == 0:
return (N*2/L+1-L)/2
return -1
if __name__ == "__main__":
ip_list = stdin.readline().rstrip().split(" ")
N = int(ip_list[0])
L = int(ip_list[1])
k = L
while k <=100:
x = check(N,k)
if x != -1:
break
k += 1
if x == -1:
print('No')
else:
res = ''
for i in range(k):
res += str(int(x+i))
if i < k-1:
res +=' '
print(res)
| importjava.util.Scanner; publicclassMain{ publicstaticvoidmain(String args[]){ Scanner sc=newScanner(System.in); intn=sc.nextInt(); intl=sc.nextInt(); intmid=n/l; intnum=0; while(mid>=(l-1)/2&&l<=100){ num=0; for(inti=-(l-1)/2;i<=l/2;i++){ num+=mid+i; } if(num>n) mid--; elseif(num<n) l++; elseif(num==n) break; } //System.out.print(num); if(l>100||num!=n){ System.out.print("No"); } elseif(num==n){ for(inti=-(l-1)/2;i<=(l/2);i++){ if(i==(l/2)) System.out.print(mid+i); else System.out.print((mid+i)+" "); } } } } |
1 2 3 4 5 6 7
前 n 个的和是:
1 : 1
2 : 3
3 : 6
4 : 10
...
例如: 对于给出的样例 18 2
长度应为 3
// sum(n) 表示从 1 开始前n个数的和
于是 18 - sum(3)(6) = 12 % 3 (0) 12 / 3 = 4
所以结果 为 1 2 3 全部加 4
5 6 7
基于这个思路可以得到下面的代码:
package main
import "fmt"
func main() {
var N, L int
var find = true
_, _ = fmt.Scanf("%d %d", &N, &L)
for find {
if move := (N - getSum(L)) / L; (N-getSum(L))%L == 0 {
for i := 1 + move; i < move+L; i++ {
fmt.Printf("%d ", i)
}
fmt.Print(move + L)
find = false
} else {
L++
}
if L > 100 {
fmt.Print("No")
find = false
}
}
}
func getSum(n int) int {
var res int
for i := 1; i <= n; i++ {
res += i
}
return res
}
/* input case
18 2
*/
""" 5 + 6 + 7 = 18 转化为 3*5 + 0 + 1 + 2 = 18 """ def factorial(n): if n < 2: return 1 else: return n + factorial(n-1) def show_ans(n, length): ans = [str(x) for x in range(n, n+length)] print ' '.join(ans) if __name__ == "__main__": N, L = [int(x) for x in raw_input().split()] get_ans = False for i in range(L, 101): fac = factorial(i-1) if N - fac < 0: print 'No' break if ((N - fac) % i) == 0: start = (N - fac) / i show_ans(start, i) get_ans = True break if not get_ans: print 'No'
#include<iostream>
using namespace std;
int main(){
int N, L;
cin >> N >> L;
int j, firstNum;
int minValue;
for (j = L; j <= 100; j++){
minValue = (j - 1) * j / 2;
if (N >= minValue && (N - minValue) % j == 0){
firstNum = (N - minValue) / j;
cout << firstNum;
for (int i = 1; i < j; i++)
cout << " " << firstNum + i;
return 0;
}
}
cout << "No";
return 0;
}
//换一种思维,自下而上,不用判奇偶
importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[] args){Scanner scan = newScanner(System.in);intN = scan.nextInt();intL = scan.nextInt();intbegin = 0;doublek = 0;doublen = (double)N;doublei = (double)L;for(;i <= 100; i++){k = (n-(i-1)*i/2)/i;//因为N = i*k+(i-1)+(i-2)+...+1;故if(k == Math.floor(k)){//若k为整数,则符合条件L = (int)i;begin = (int) k;break;}}if(i > 100){System.out.print("No");}else{for(intj = 0; j < L; j++){if(j == (L-1)){System.out.print((begin + j));break;}System.out.print((begin + j) + " ");}}}}
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int L = sc.nextInt();
for(int i = L; i <= 100; i++) {
if((2*N+i-i*i)%(2*i) == 0) {
int start = (2*N+i-i*i)/(2*i);
for(int j = 0; j < i-1; j++) {
System.out.print(start+j+" ");
}
System.out.print(start+i-1);
return;
}
}
System.out.print("No");
}
}
#include<iostream>
using namespace std;
int main() {
int N, L;
cin>>N>>L;
for(int i = L; i <= 100; i++) {
if((2*N+i-i*i)%(2*i) == 0) {
int start = (2*N+i-i*i)/(2*i);
for(int j = 0; j < i-1; j++) {
cout<<start+j<<" ";
}
cout<<start+i-1;
return 0;
}
}
cout<<"No"<<endl;
}
import java.util.Scanner;
/*
* 题目需要找出一段长度大于等于L的连续非负整数,使得其和等于N。L要尽可能小。
* 考虑是连续非负整数,所以其和我们能用中位数来表示,分两种情况:
* 情况一,长度为奇数的情况:
* 此时中位数一定是整数,N = 中位数 x L
* 情况二,长度为偶数的情况:
* 此时中位数肯定是xx.5的形式,N = xx.5 * L
* 所以我们从长度L开始枚举,至100为止,分奇偶讨论。
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(), l = in.nextInt();
in.close();
int bg = -1, ed = -1;
for (int i = l; i <= 100; ++i) {
// 奇数,中位数一定是整数
if (i % 2 == 1 && n % i == 0) {
int mid = n / i;
bg = mid - (i - 1) / 2;
ed = mid + (i - 1) / 2;
if (bg >= 0) // 答案要合法,即需要是非负整数
break;
}
// 偶数,中位数一定是0.5形式
if (i % 2 == 0 && (double)n / i - n / i == 0.5f) {
int mid = n / i;
bg = mid - i / 2 + 1;
ed = mid + i / 2;
if (bg >= 0)
break;
}
}
if (bg >= 0) {
for (int i = bg; i < ed; ++i) {
System.out.print(i + " ");
}
System.out.println(ed);
}
else {
System.out.println("No");
}
}
}
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scan=new Scanner(System.in);
int N=scan.nextInt();
int L=scan.nextInt();
int first;
int last;
for(;L<=100;L++){
first=((2*N/L)-L+1)/2;
last=first+L-1;
if(((first+last)*L)/2==N){
for(int i=0;i<L-1;i++){
System.out.print(first+" ");
first++;
}
System.out.print(last);
return;
}
}
System.out.print("No");
return;
}
} java版本
## Python 3.*
## Written by CheesePrawn on 25th May 2020
if __name__ == '__main__':
N, L = map(int, input().split(' '))
## 设定标签值,如果在接下来的程序中没有找到所需结果,最终输出No
not_find = True
## 根据题意 2<=L<=100, 界定循环次数
for l in range(L, 101):
## 根据公式进行计算
a_start = (2 * N - (l - 1) * l) / (2 * l)
## 如果所得结果为整数,即为我们所要找的起始值
if int(a_start) == a_start:
not_find = False
a_start = int(a_start)
## 依次输出,并以空格隔开,注意题意要求,最后一位结尾不需要空格,所以单独输出
for i in range(l - 1):
print(a_start + i, end=' ')
print(a_start + l - 1)
## 根据题意只需要找到最短的,l是从小到大,所以最先找到的即为所求,不用再进行循环了
break
## 如果没有找到,输出No
if not_find:
print("No")
参考lencha的解题思路 其实这题不需要等差公式。
考虑任意连续整数,假设是答案,长度为 K 。
去掉所有K个n以后必定是 1 + 2 + 3 + ... 的形式。
所以先求出 1 + 2 + 3 + ... + 100 的前缀和,从小到大试着减去对应长度的前缀和。检查剩下的数是否是长度的整数倍就可以了。
#include
using namespace std;
const int N = 110;
int q[N];
int main()
{
int n, l; cin >> n >> l;
for(int i = 1; i <= 100; i++) q[i] = i, q[i] += q[i - 1];
for(int i = l; i <= 100; i++)
{
int k = n - q[i];
if(k % i == 0)
{
for(int j = 1; j <= i; j++) cout << j + k / i << " \n"[j == i];
return 0;
}
}
cout << "No\n";
}
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner input = new Scanner(System.in);
int N = input.nextInt();
int L = input.nextInt();
show(N,L);
}
public static int show(int N,int L){
int i = L;
while(i <= 100){
int a = (2*N - i*(i-1))/(2*i);
if((2*N - i*(i-1))%(2*i) == 0 && a >= 0){
for(int j = 0;j < i-1;j++){
System.out.print(a + " ");
a = a + 1;
}
System.out.print(a);
return 0;
}
i = i + 1;
}
if(i > 100){
System.out.print("No");
return 0;
}
return 0;
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int L = sc.nextInt();
for (int i = L; i <= 100; i ++) {
if ((2 * N + i - i * i) % (2 * i) == 0) {
int a1 = (2 * N + i - i * i) / (2 * i);
for (int j = 0; j < i-1; j ++) {
System.out.print(a1 + j + " ");
}
System.out.println(a1 + i - 1);
return;
}
}
System.out.println("No");
}
}
#include<iostream>
(720)#include<cmath>
using namespace std;
int main(){
int n, l;
int minlen;
int k;
while(cin >> n >> l){
minlen = l;
while(minlen <= 100){
double a = (2 * n + minlen * (1 - minlen)) / double((2 * minlen));
if(ceil(a) == a){
for(k = a; k < a + minlen - 1; k++){
cout << k << " ";
}
cout << k;
break;
}
minlen++ ;
}
if(minlen == 101) cout << "No";
}
return 0;
} # 用异常方式跳出循环输出No
# 等差数列求和首先想到等差数列求和公式
import sys
lines = []
try:
while True:
line = sys.stdin.readline().strip()
if line == "":
break
lines.append(line.split())
N, L = int(lines[0][0]), int(lines[0][1])
List = []
l = L
while l <= 100:
a1 = (2 * N - l * (l - 1)) / (2 * l) # 等差数列之和公式
if int(a1)==a1 and a1>=0: # 判断是否为整数且为非负
for i in range(l - 1):
print(int(a1 + i), end=" ")
print(int(a1 + l - 1))
break
l = l + 1
else:
raise
except:
print("No")