×

# EGBOBRD - Editorial

Author: Egor Bobyk
Tester: Mugurel Ionut Andreica
Editorialist: Lalit Kundu

Simple

# PREREQUISITES:

implementation, basic maths

# PROBLEM:

Some chefs go for a tour lasting $N$ days. They take packages of bread for food. Each package has $K$ pieces of breads. In $i$-th day, they eat $A_i$ pieces of bread.
Each day the last piece of bread of an open package goes bad. Find minimum number of packages required to complete the tour.

# EXPLANATION:

================
Let's think step by step here.

• Chefs should never leave more than one package open, since each night from each package one bread goes bad. So, it is intuitive.
• From previous statement, we can also imply that Chefs will keep opening packages on a day until that day's demand $A_i$ is met. And, leave the remaining(if remaining) breads for the next day.
• We can, in constant time, find the number of new packages to be opened if we know current(say $\textrm{cur}$) and required(say $\textrm{req}$) number of breads. We need to open $x$ packages such that $x*K + cur \ge req$ where $x \ge 0$. Now, we can easily define $x$ as $\textrm{ceil}(\frac{req - cur}{K})$ or basically in integer operations as
(req - cur)/K + ((req - cur)%K > 0)
Second term is required to satisfy the inequality.

This is our solution expressed as a pseudo code:

     N, K, A[] = input

cur = 0     //total number of breads available right now
ans = 0     //total number of packages opened till now

for i = 0 to N - 1:
//solve for inequality cur + x*K >= A[i] where x>=0
x = (A[i]-cur)/K + ((A[i]-cur)%K > 0)

//if x < 0, no package required
x = 0

ans += x

//change current number of breads left after consumption
cur = cur +x*K- A[i]

if (cur > 0)
cur--

print ans


# COMPLEXITY:

For each test case, complexity is $O(N)$ because we are traversing over number of days ie. $N$ here.

# AUTHOR'S, TESTER'S SOLUTIONS:

This question is marked "community wiki".

3.0k93164187
accept rate: 12%

19.8k350498541

Can we know the testcases used by judge please ?

(14 Jul '15, 15:01)

 0 Please help me out....I run this program but wrong answer Subtask1 task#0,Subtask2 task#3,Subtask3 task#7... Can anyone please rectify my problem and please tell me the case where the code would not be applied (at which value of N,K and A[i])........  import java.util.*; class TryIt { public static void main(String[] args) { Scanner in=new Scanner(System.in); long T=in.nextLong(); for(int i=0;i < T;i++){ long N=in.nextLong(); long K=in.nextLong(); long sum=0,count=0,quo=0,ans=0; for(int x=0;x < N;x++){ long A=in.nextLong(); sum=sum+A; if((A%K==0)&&(x<(N-1))){ count++; } } ans=sum+(N-1)-(count); quo=ans/K; if(ans%K==0){ System.out.println(quo); } else{ System.out.println((quo+1)); } } }  } answered 13 Jul '15, 16:31 11●1 accept rate: 0% Please HELP HELP .....Me out.......I have tried most of the test cases....... (14 Jul '15, 13:33) Try this: 1 5 4 6 3 5 1 6 Answer should be 6. Your code gives 7. (14 Jul '15, 17:55) bhambya2★ Thank You Very much (14 Jul '15, 18:33) But bhambya what is the value of K , N (i.e no of days and bread in each package...)..Please tell me that.... (14 Jul '15, 18:36) actually the new line didnt come there. T = 1, N = 5, K = 4, array : 6 3 5 1 6 (14 Jul '15, 21:22) bhambya2★ Thank You Very Much For Your Kind Info..... :) (14 Jul '15, 23:06) showing 5 of 6 show all

why i got only 15 pts .Can somebody check my code plz..

# include <iostream>

using namespace std;

int main() { int T; long int N,K,pk=0; long int *A,i,chk; long int rem,divi,temp; cin>>T;

    while(T--)
{
pk=0;
temp=0;//it stores the pieces remaining after eating current day's need
divi=0;
rem=0;
cin>>N>>K;
A=new long int[N];

for(i=0;i<N;i++)
cin>>A[i];
for(i=0;i<N;i++)
{

if(A[i]-temp>0)//if the left over pieces are less than those to be eaten
{

divi=(A[i]-temp)/K;
rem=(A[i]-temp)%K;
pk=pk+divi;

if(rem!=0)//is there need of more packets
{pk=pk+1;

}
else//no left over pieces perfectly divisible
temp=0;
}

else//if the left over pieces are greater than those to be eaten
{
if(i==N-1)//if its the last day then no need of extra pack
break;
else
if(temp==A[i])//if the left over pieces equal the requirement
temp=0;
else//if the left over pieces are still greater
temp=temp-A[i]-1;

}

}

cout<<pk<<"\n";
delete A;
}
return 0;
}


1
accept rate: 0%

@tejasvi96 this is because you have to use long long. check your code, http://www.codechef.com/viewsolution/7478446 , I just changed type to long long

(14 Jul '15, 08:58) 5★

thanx for the help avmnusng..

(14 Jul '15, 12:40)
 0 test case : 3 3 2 2 (i.e 4 days) for K = 6 optimal order :-- 3 from 1st packet, 3 from 2nd packet, 2 from 1st packet, 2 from 2nd packet, - total 2 packets opened your soln: post condition after each loop:-- i=0: x = 1 ans =1 cur = 2 i = 1: x = 1 ans = 2 cur = 4 i = 2: x = 0 ans = 2 cur =1 i = 3: x = 1 ans = 3 cur = 4 which gives the answer 3 which is actually wrong.. are you sure it is greedy ?? Is it not flawed?? shouldn't the approach be to minimize the no. of wasted breads?? answered 13 Jul '15, 23:04 1 accept rate: 0%
 0 @gridhar_m yes you are right...i checked My AC soln and your concept too answered 14 Jul '15, 09:03 5★apptica 949●2●10 accept rate: 17%
 0 I got only 15 pts. Can somebody check my code plz. Atleast let me know the test cases that are failing. Thanks in advance. answered 14 Jul '15, 23:25 13●3 accept rate: 0%

I got 75 pts And my only wrong answer is Sub-task 2 Task#3 Plz tell me which test case is my code not satisfying.

# include<math.h>

int main(void) {short int T; scanf("%hd",&T); while(T>0) { int n,i; scanf("%d",&n); long long int k,j=0; scanf("%lld",&k); int a[n]; for(i=0;i<n;i++) { scanf("%d",&a[i]); j+=a[i]; if(a[i]%k!=0 && i!=n-1 && j%k!=0) {j++;}

    }
if(j%k==0)
{printf("%lld\n",(j/k));}
else
{printf("%lld\n",(j/k+1));}
T--;
}
return 0;


}

2★ayan_97
1
accept rate: 0%

 0 They eat acc. to daily requirement. So go on adding the no of breads they eat daily AND add 1(bread that damages daily). Don't add 1 bread if(sum%k==0), because on that day no bread will remain. THUS, print sum/k or (sum/k)+1 which gives total no of packets required for throught the trip. TOO SIMPLE :) answered 15 Jul '15, 18:05 13●1●1●2 accept rate: 0% Job done with only few variables. (15 Jul '15, 18:08)
 0 Can anyone take a look at my submission. https://www.codechef.com/viewsolution/8536505. i am taking an array dp[] which contains the no of of packages opened after each day and another array left[] which contains no of left over breads after each day i am getting just one WA in subtask 2. answered 13 Oct '15, 01:59 1 accept rate: 0%
 0 Hey Thanks this is useful coding link.. Thanks for sharing.. Netsuite Partners answered 13 Oct '15, 12:01 0★stevee07 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,220
×1,191
×849
×141
×6

question asked: 26 Jun '15, 07:18

question was seen: 4,012 times

last updated: 13 Oct '15, 12:01