public static void main(String[] args) {
int T = fs.nextInt();
for (int t = 0; t < T; t++) {
solve();
}
out.close();
}
private static void solve() {
int n = fs.nextInt();
int k = fs.nextInt();
int[] arr = fs.readArray(n);
int rounds = 0;
for(int i = 0;i<n;i++) {
if(arr[i]>k) {
out.println(-1);
return;
}
int sum = arr[i];
int j = i+1;
while (j<n && sum+arr[j] <= k) {
sum += arr[j++];
}
i = j-1;
rounds++;
}
out.println(rounds);
}
private static final FastScanner fs = new FastScanner();
private static final PrintWriter out = new PrintWriter(System.out);
public static class FastScanner {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer("");
String next() {
while (!st.hasMoreTokens())
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
int[] readArray(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = nextInt();
return a;
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextString() {
return next();
}
}
Thanks sir, but sorting work here for checking any element is greater then k.
for i in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
d = sorted(a)
i = 0
b = 0
c = []
if(d[-1] > k):
print(-1)
else:
while(len(a) > 0):
if(b+a[i] <= k):
b += a[i]
a.pop(i)
else:
c.append(b)
b = 0
if(b != 0):
c.append(b)
b = 0
print(len(c))
It works here.
here also you found your answer in unsorted array. you used sorted copy of given array just for impossible case . in your previous code you were finding answer in sorted array.
use carefully
a.sort()-- it will sort a
b=sorted(a) – here b will be sorted but not a
i also get confuse here many times.
I’ve caught your mistake. You’ve put a conditional return statement in the input loop. If there is some Wi > k in the input, you code returns from the function and starts treating further input as another test case whereas the actual current testcase wasn’t over.
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int i =0;i<T;i++){
int n = sc.nextInt();
int k = sc.nextInt();
int[] w = new int[n];
boolean b = true;
for(int j=0;j<n;j++){
w[j] = sc.nextInt();
}
for(int j = 0;j<n;j++){
if(w[j] > k){
System.out.println(-1);
b = false;
break;
}
}
if(b == true){
getCount(w,n,k);
}
}
}
public static void getCount(int[] w, int n,int k){
int tot = 0;
int count = 0;
for(int i = 0;i<n;i++){
tot += w[i];
if(tot>k){
tot =w[i];
count++;
}
}
System.out.println(++count);
}
Why this is giving wrong answer?
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int n,k;
cin>>n>>k;
int arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
int max=*max_element(arr, arr + n);
int h=0;
int sum=0;
for(int i=0;i<n;i++)
{
sum=sum+arr[i];
if(sum>k)
{ sum=arr[i];
h++;
}
}
if(max>k){
cout<<-1<<endl;
}
else{
cout<<h+1;
}
}
return 0;
}
for i in range(int(input())):
n,k=map(int,input().split())
w=list(map(int,input().split()))
p=0
count=0
if w[0]>k:
print("-1")
for j in range(n):
if p+w[j]<=k:
p+=w[j]
else:
count+=1
p=0
j-=1
count+=1
print(count)
@anyamanask you were not taking the whole input, that’s why you got the wrong answer, i tried to submit your code , and got ac , here’s the link CodeChef: Practical coding for everyone
and in setter’s code there is no need to check the sum>0 in last step , just print ans+1.
