例如 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")