BIT Magazine

Problem code: TRMAG

All submissions for this problem are available.

Taru likes reading. Every month he gets a copy of the magazine "BIT". The magazine contains information about the latest advancements in technology. Taru reads the book at night and writes the page number to which he has read on a piece of paper so that he can continue from there the next day. But sometimes the page number is not printed or is so dull that it is unreadable. To make matters worse Taru's brother who is really naughty tears of some of the pages of the Magazine and throws them in the dustbin. He remembers the number of leaves he had torn but he does not remember which page numbers got removed. When Taru finds this out he is furious and wants to beat him up. His brother apologizes, and says he won't ever do this again. But Taru did not want to be easy on him and he says "I will leave you only if you help me find the answer to this. I will tell you how many pages (Printed sides) were there in the Magazine plus the pages on which the page numbers were not printed. You already know the number of leaves you tore (T). Can you tell me the expected sum of the page numbers left in the Magazine?" Taru's brother replied "huh!! This is a coding problem". Please help Taru's brother.

Note: The magazine is like a standard book with all odd page numbers in front and the successive even page number on its back. If the book contains 6 pages, Page number 1 and Page number 2 are front and back respectively. Tearing a leaf removes both the front and back page numbers.

Input

The first line contains the number of test cases t. 3t lines follow. The first line of each test case contains the number of pages (printed sides) in the book. The second line's first integer is F, F integers follow which tell us the numbers of the page numbers not printed. The third line contains a single integer telling us the number of leaves Taru's brother tore.

Output

Output one real number correct up to 4 decimal digits which is equal to the expected sum of the page numbers left in the book.

Constraints

Number of printed Sides<=2000. All other values abide by the number of printed sides.

Example

Input:
2
10
2 1 2
2
10
1 8
0

Output:
31.2000
47.0000

Author: calc_saransh
Date Added: 29-07-2011
Time Limit: 1 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

How in the first case the

sherwin21990 @ 1 Sep 2011 04:11 PM
How in the first case the answer is 31.2000?

@admin: As the page numbers

vijay91 @ 1 Sep 2011 04:14 PM
@admin: As the page numbers are always integers how can their sum be a real number?

@vijay91 - We need to

saransh_adm @ 1 Sep 2011 04:42 PM
@vijay91 - We need to calculate the expected sum. @sherwin21990 - You are supposed to figure that out yourself

@admin - are the numbers in

go4soumya @ 1 Sep 2011 05:27 PM
@admin - are the numbers in the 2nd line of input separated by single spaces?

^yes

saransh_adm @ 1 Sep 2011 05:36 PM
^yes

can i get to know what is the

vickysirwani @ 1 Sep 2011 06:21 PM
can i get to know what is the runtime complexity of the solution??

Can number of pages be odd?

mukulgupta @ 1 Sep 2011 06:25 PM
Can number of pages be odd?

I think there is a closed

udayabhanug @ 1 Sep 2011 06:35 PM
I think there is a closed form solution for this as well, I am reasonably sure that this is not a coding problem.

no

mohsenp1 @ 1 Sep 2011 06:54 PM
no

@admin - My java code is

go4soumya @ 1 Sep 2011 06:58 PM
@admin - My java code is running fine in my computer but when I'm submitting it is showing runtime error(NZEC). I'm new here and participating for the first time. Can you help me, why am I getting this kind of error, or under what circumstances such errors are shown, so that I can fix my code accordingly.

please if u have time look my

amriteshanand @ 1 Sep 2011 07:06 PM
please if u have time look my submission i have no idea why it is giving wrong answer

@amriteshanand, it's

minib00m @ 1 Sep 2011 07:12 PM
@amriteshanand, it's competition, not practice section

can the number of printed

sanjay.iitg @ 1 Sep 2011 07:20 PM
can the number of printed sides be odd?

@admin:- can any body plz

jaid @ 1 Sep 2011 07:26 PM
@admin:- can any body plz tell me why is 2 1 2 written in 3 line if it asks the dull printed page no . and how sum of integers can be a real no .( with decimal )

in the second input data the

andyprit @ 1 Sep 2011 07:28 PM
in the second input data the number of numbered pages = 10 the unnumbered page = 8, so the expected sum becomes 1 + 2 + 3+ 4 + 5+ 6 + 7 + 9 + 10 = 47 however here the total number of printed pages = 9 , so can anybody explain for this case

I guess I will wait till

udayabhanug @ 1 Sep 2011 07:45 PM
I guess I will wait till someone blogs about it. All my solutions report "Wrong answer", I checked my formula repeatedly, and read the question many times, no luck. If my formula is wrong, I can ask about it here, but not very sure of it at this point. :-(. If someone is free, we can privately discuss over e-mail perhaps.

Does "Printed Sides" imply

rajrocks1992 @ 1 Sep 2011 08:09 PM
Does "Printed Sides" imply "Printed pages" ????

Printed Sides means the Sides

saransh_adm @ 1 Sep 2011 08:15 PM
Printed Sides means the Sides with matter for the magazine BIT written on it and not the page number printed. For case 2 there is matter printed on pg 1,2,3,4,5,6,7,8,9,10 and there is no page number 8 on the printed side 8, so sum = 47

Expected sum is a term

kozicode @ 1 Sep 2011 08:28 PM
Expected sum is a term associated with probability. Look it up for more info.

again the same ques Can the

procastinatorg @ 1 Sep 2011 08:34 PM
again the same ques Can the number of printed sides be odd ?? I am getting correct results for even number of pages at my computer by the solutions submitted here shows WA :(

It depends on the number of

kozicode @ 1 Sep 2011 08:43 PM
It depends on the number of pages. The number of printed sides can always be odd/even. If number of pages is even and number of unprinted pages in even, then the number of printed sides is even. And the same logic follows.

@admin, should not it be the

rockaustin2k6 @ 1 Sep 2011 08:50 PM
@admin, should not it be the output having exactly 4 digits after decimal places rather than having 4 correct digits?

@admin: Thanks for thee

vijay91 @ 1 Sep 2011 09:44 PM
@admin: Thanks for thee previous reply :-) One more question what if the number of pages (printed sides) in the book is odd?

if the number of pages is odd

mohsenp1 @ 1 Sep 2011 10:22 PM
if the number of pages is odd it means that the last page is blank and without pagenumber or it is black but with pagenumber

There is certainly a test

gajduk @ 1 Sep 2011 11:25 PM
There is certainly a test case with odd number of pages. How are you supposed to capitalize on that in your code I'm not sure.

Everything I did was perfect.

viswanathk @ 1 Sep 2011 11:55 PM
Everything I did was perfect. A floating point exception is killing it :(

@all... Yes the number of

saransh_adm @ 2 Sep 2011 12:42 AM
@all... Yes the number of printed sides can be odd... Visualize the scenario

Got a doubt. In the first

angad @ 2 Sep 2011 03:12 AM
Got a doubt. In the first case, lets suppose a scenario which gives us the least sum of number of pages. Meaning that the pages torn out are page number 9 and 10. and the missing pages are 1,2. then the sum of the pages are 3+4+5+6+7+8=33. which happens to be greater than the expected value of 31.2!!! hows that possible! am i missing something??

@angad In the least sum

ambujpandey @ 2 Sep 2011 03:44 AM
@angad In the least sum scenario, the pages torn would be 7,8,9,10 (remember 2 leaves are torn). So the sum would be 3+4+5+6 = 18.

ohh! got it. thanks! :)

angad @ 2 Sep 2011 03:56 AM
ohh! got it. thanks! :)

in first case::the 6

ritesh_gupta @ 2 Sep 2011 05:18 AM
in first case::the 6 combinations for the sum of remaining pages are:: 18,22,26,26,30,34 whose sum gives 156 ..then how is answer 31.20 ...???

@admin:can u giv another

nj91 @ 2 Sep 2011 08:20 AM
@admin:can u giv another example

@admin what is meant by

dinesh_reddy @ 2 Sep 2011 08:34 AM
@admin what is meant by expected sum? is it same as computing average in this case?

The input contains odd value

hhjami @ 2 Sep 2011 09:46 AM
The input contains odd value for n. How is that possible if its like a standard book????

This is outrageous, why do I

hhjami @ 2 Sep 2011 09:57 AM
This is outrageous, why do I need to handle for cases where the number of pages can be odd???

What is upper bound on number

tl268 @ 2 Sep 2011 10:02 AM
What is upper bound on number of test cases t?

@all ...test cases are around

saransh_adm @ 2 Sep 2011 11:10 AM
@all ...test cases are around 50... @all... the question requires u to visualise the scenario and think practically... and yes books to have odd number of printed sides... i repeat PRINTED SIDES

how can the result be in a

frankie619 @ 2 Sep 2011 11:35 AM
how can the result be in a decimal!!!!!!!!!!

^...the average of some

saransh_adm @ 2 Sep 2011 11:40 AM
^...the average of some integers can be a decimal number...

@Admin, I figured out an

kozicode @ 2 Sep 2011 11:55 AM
@Admin, I figured out an algorithm, but how're are we supposed to find all the combinations in time limit ? it seems to take for ever ! please some hints :(

The time complexity for

kozicode @ 2 Sep 2011 12:05 PM
The time complexity for finding combinations takes forever for 1000C10 (say) !

@Admin..... is this case

satya_patel @ 2 Sep 2011 03:53 PM
@Admin..... is this case pssible n(odd) 1 n+1 0 please tell if this not violates the condition of contest.........Thanx

finally got it :) :)

null_pointer @ 2 Sep 2011 05:31 PM
finally got it :) :)

Can any one provide me other

bittu_it @ 2 Sep 2011 08:49 PM
Can any one provide me other test case........

@admin if the printed sides

babytomato @ 2 Sep 2011 09:43 PM
@admin if the printed sides are odd, then the back side of a last page will be blank .does this back side have a page number ???

^no... it has nothing printed

saransh_adm @ 2 Sep 2011 09:54 PM
^no... it has nothing printed on it..

wots the output of 10 1 8 1

rijin @ 2 Sep 2011 09:59 PM
wots the output of 10 1 8 1

I am getting the output, but

viswanathk @ 2 Sep 2011 10:06 PM
I am getting the output, but wrong answer. Damn.

How can i participate in this

himms @ 2 Sep 2011 10:34 PM
How can i participate in this coding problem.??.can you tell me something about it.!!# ..

@rijin: output:37.6000

bittu_it @ 2 Sep 2011 10:40 PM
@rijin: output:37.6000

Finally I got it.........

bittu_it @ 2 Sep 2011 10:55 PM
Finally I got it.........

while printing the output

babytomato @ 2 Sep 2011 10:56 PM
while printing the output correct up to 4 decimal digits .........do we have to follow the rules of rounding off?

please give a test case for

deepsaggas @ 2 Sep 2011 11:04 PM
please give a test case for odd number of pages....

@bittu_it please give a

babytomato @ 2 Sep 2011 11:07 PM
@bittu_it please give a challenging test case ......

@admin in the test case : 5

babytomato @ 2 Sep 2011 11:22 PM
@admin in the test case : 5 2 3 5 1 answer i m getting is 4.6666666666666666.... now in the output it should be 4.6667 or 4.6666??

@babytomato yes we have to

satya_patel @ 2 Sep 2011 11:29 PM
@babytomato yes we have to follow rounding off rules........ @admin.............please ignore my above comment

@deepsaggas: for input: 15 2

bittu_it @ 2 Sep 2011 11:39 PM
@deepsaggas: for input: 15 2 5 10 3 output:65.6250

@babytomato: follow my above

bittu_it @ 2 Sep 2011 11:43 PM
@babytomato: follow my above test case.........

can the pages with missing

aryanurag @ 2 Sep 2011 11:56 PM
can the pages with missing page no. be considered in torn pages????

can anyone explain the first

black_syco @ 3 Sep 2011 12:08 AM
can anyone explain the first test case plz..... :(:(:( in first case::the 6 combinations for the sum of remaining pages are:: 18,22,26,26,30,34 whose sum gives 156 ..and average is 26......then how is answer 31.20 ...??? plz help...:(:(:

@saransh_adm: thanks for your

tendua @ 3 Sep 2011 12:10 AM
@saransh_adm: thanks for your comments. They are enough to solve the problem.

@admin- I submitted a code

sharky @ 3 Sep 2011 12:44 AM
@admin- I submitted a code with ID 644047 It's working perfectly in my PC, can you email me the test cases which my code is unable to pass. Please email at It'll be appreciated.

@admin- I submitted a code

sharky @ 3 Sep 2011 12:44 AM
@admin- I submitted a code with ID 644047 It's working perfectly in my PC, can you email me the test cases which my code is unable to pass. Please email at It'll be appreciated.

@admin email me at

sharky @ 3 Sep 2011 12:45 AM
@admin email me at prakharavasthi@gamil.com

@admin- I submitted a code

sharky @ 3 Sep 2011 12:46 AM
@admin- I submitted a code with ID 644047 It's working perfectly in my PC, can you email me the test cases which my code is unable to pass. Please email at prakharavasthi@gmail.com It'll be appreciated.

Output one real number

gajduk @ 3 Sep 2011 02:26 AM
Output one real number correct up to 4 decimal digits which is equal to the expected sum of the page numbers left in the book. This is missleading. The expected sum should be rounded up to 4 decimal digits.

@ ritesh_gupta and others In

ambujpandey @ 3 Sep 2011 06:56 AM
@ ritesh_gupta and others In the first test case, there are 10 possible combinations, summing up to 312. Therefore, taking average, 312/10 = 31.2

@bittu_it: Thanks for the

vijay91 @ 3 Sep 2011 10:15 AM
@bittu_it: Thanks for the testcase... I'm getting the same output 65.6250..but Online judge is giving WA... :-(

@ambujpandey : thanks a

cooltodinesh @ 3 Sep 2011 11:28 AM
@ambujpandey : thanks a lot...

Can someone please suggest an

kozicode @ 3 Sep 2011 03:07 PM
Can someone please suggest an algorithm to generate combinations in polynomial time ? Some links would be appreciated.

output of 2000 /n 0 /n 50

rijin @ 3 Sep 2011 04:53 PM
output of 2000 /n 0 /n 50

output of 2000 /n 0 /n 50

rijin @ 3 Sep 2011 04:53 PM
output of 2000 /n 0 /n 50

@admin please give a test

esolutionam @ 3 Sep 2011 05:07 PM
@admin please give a test case for odd number of pages.

@kozicode when you want to

okaoka @ 3 Sep 2011 05:35 PM
@kozicode when you want to generate combinations in C++, you can use "next_permutation". http://wordaligned.org/articles/next-permutation but before using "next_permutation", you should read @udayabhanug's post carefully.

My program is working for the

esolutionam @ 3 Sep 2011 05:50 PM
My program is working for the given test cases as well as the ones mentioned in comments but still on running it shows Wrong Answer. Anyone please give any other test case.

please someone tell how to

soni88 @ 3 Sep 2011 06:34 PM
please someone tell how to generate combinations in C....thanks

please can someone reply how

dazzling420 @ 3 Sep 2011 07:18 PM
please can someone reply how expectancy is calculated?

@admin could you please

rahulverma_cse @ 4 Sep 2011 12:48 AM
@admin could you please explain the term expected sum?

@admin::sexy problem..:)

ritesh_gupta @ 4 Sep 2011 02:03 AM
@admin::sexy problem..:)

@soni88 ::There is direct

ritesh_gupta @ 4 Sep 2011 03:06 AM
@soni88 ::There is direct method to find permutation (in stl algorithm) ,but There is no direct method to find combination in C/C++..@ rijin::The o/p will be 1900950.0000 for 2000 0 50,will fit in integer dt..,@himms ::any1 who has codechef a/c can participate in contest @ vijay91::be careful with precesion loss

u dont have to have all

aayush123 @ 4 Sep 2011 10:51 AM
u dont have to have all combinations u just need some observartion and a little maths calcutaion thats all .. :))

Please give some critical

esolutionam @ 4 Sep 2011 11:10 AM
Please give some critical test case.

@ritesh gupta...dude i m

biraj_patel @ 4 Sep 2011 01:25 PM
@ritesh gupta...dude i m getting 1900950.0000 answer but still here it showz WA>>> i have tried many cases shown by ppl above..but still WA..anny guess y so

@ritesh_gupta: i'm not

vijay91 @ 4 Sep 2011 10:14 PM
@ritesh_gupta: i'm not getting 1900950.0000 for 2000 0 50...Thanks for the reply :-) maybe i should use more appropriate datatype...

@vijay 1900950.0000 is

biraj_patel @ 4 Sep 2011 11:27 PM
@vijay 1900950.0000 is correct for 2000 0 50

@admin does single integer

getsam123 @ 5 Sep 2011 01:16 AM
@admin does single integer means single digit or its just normal integer

@getsam123::single integer

ritesh_gupta @ 5 Sep 2011 03:09 AM
@getsam123::single integer means one integer and yeah just normal integer.. @esolutionam ::its your work to generate the test case..i would suggest use brute force in order to check your answer,and yeah there are few cases in this discussion board ,try to utilise it

Hey guys can u tell me the

Illusion03 @ 5 Sep 2011 10:32 AM
Hey guys can u tell me the output for (2000,0,2000) and (50,0,50)?

anyone please give me the

paramanantham @ 5 Sep 2011 11:37 AM
anyone please give me the answer for 2000 0 1000 &2000 0 999

@parmanantham -: answer for

Illusion03 @ 5 Sep 2011 02:23 PM
@parmanantham -: answer for 1st is (0.0000) and for 2nd is (2001.0000).

finally got the logic huh!!

amanymca24 @ 5 Sep 2011 11:07 PM
finally got the logic huh!!

@admin-soln id 648229,please

psingh871 @ 6 Sep 2011 12:05 AM
@admin-soln id 648229,please check which test case is missing,i checked for more than 10 test cases n all mentioned in comments ,still i got all correct according to answer in commment,please check then were i m getting wrong answer......

can anybody provide more

psingh871 @ 6 Sep 2011 12:08 AM
can anybody provide more cructial cases i can misss

@admin: Answer of 1 1 0 0

jekin @ 6 Sep 2011 01:00 AM
@admin: Answer of 1 1 0 0 will be 1 or 3 ??

pls provide only one critical

paramanantham @ 6 Sep 2011 09:41 AM
pls provide only one critical case friend...

@all... the problem requires

saransh_adm @ 6 Sep 2011 01:12 PM
@all... the problem requires visualization of the scenario and some clever calculations.. the number of AC submissions suggest that the amount of information given in the problem statement is sufficient

:D Solved !

kozicode @ 7 Sep 2011 03:35 AM
:D Solved !

@admin.While all the page

pradeeps @ 7 Sep 2011 11:42 AM
@admin.While all the page numbers are integers.how can the answer be a decimal number.The sum will surely be an integer.

in 1st case

mmanoj001 @ 7 Sep 2011 02:46 PM
in 1st case 1,2,3,4,5,6,7,8,9,10 so we have 5 pairs (1,2) and 3,4 ..... so we remove 2 of them so we have 5c2 comination its 10 so how u get 45,41,37,33,34,30,26,26,22,18 its sum is 312 its avg is 31.2000

can we tear the pages which

navin25 @ 7 Sep 2011 04:36 PM
can we tear the pages which have unreadable page numbers.......?????

my submission id is 651427. i

navin25 @ 7 Sep 2011 04:58 PM
my submission id is 651427. i checked my solution for many test cases as well as the one given in the comments. then also i am getting werong answer please help me out....

5 2 3 5 1 answer anyone

rijin @ 7 Sep 2011 07:57 PM
5 2 3 5 1 answer anyone explain..is that (( 7+3+7+5+6) / 5)?

@all ,forget my last comment;

rijin @ 7 Sep 2011 08:17 PM
@all ,forget my last comment;

Why am i getting runtime

singh_637 @ 7 Sep 2011 10:36 PM
Why am i getting runtime error SIGFPE? I ran the code on my computer it is giving correct result.

I am not getting any divide

singh_637 @ 8 Sep 2011 12:17 AM
I am not getting any divide by zero error on my computer. I have also added if-else condition which will rule out the possiblity of getting divide by zero error. But your website is showing aforementioned error again and again. I am demoralised and unable to understand what to do. If you don't want to respond as contest is going on, kindly give response after the contest. That will ensure that i am not going back empty hand from this contest.

@admin please see my last two

aditya00kumar @ 10 Sep 2011 12:56 AM
@admin please see my last two submissions.last one was submitted successfully but previous one was showing wrong answer.but in both solution same thing is written in different ways.why???

i declared a global variable

oslbhavana @ 10 Sep 2011 03:02 PM
i declared a global variable but i am getting a compilation error that its not in scope. please help me

how those answers come.....

anshi555 @ 11 Sep 2011 12:07 PM
how those answers come.....

Hmmm, my idea and the formula

udayabhanug @ 12 Sep 2011 09:51 AM
Hmmm, my idea and the formula are right. There must have been some coding issue somewhere. Ok, this makes sense now.

Actually, this one's

udayabhanug @ 12 Sep 2011 09:53 AM
Actually, this one's complexity is O(n), where n is the number of pages, very trivial from the POV of complexity/run-time. Anyway, congratulations for all who solved it.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions