Help the DJ
All submissions for this problem are available.
DJ N3xt0r could hardly sleep last night. He thought he was doing his job so well, but it seems like the dancers at the disco are looking for a whole different kind of music these days and the place has become nearly empty. Being the best DJ ever, he would not let that happen again. So he pulled some strings and gathered valuable information regarding the musical preferences of the dancers expected to attend the disco tonight. By 8.00PM, DJ N3xt0r has a file with the following info:
- The number of dancers (D) expected to attend tonight.
- The number of songs (S) on his laptop media library.
- The boredom factor (B) of the dancers: the number of songs disliked by a dancer that will play before he gets bored and leaves the disco.
- The musical preferences of the dancers represented by a D-row S-column matrix (M). If Mij = 1 then dancer i likes song j. If Mij = 0 he does not like the song.
He wants to build a playlist such that the number of dancers present when the party ends is maximized. Desperate, DJ N3xt0r seeks for your help. He will make you a VIP member of the disco if you write a program that performs the task. Notice that, as the playlist will be projected on a screen, dancers who don't see any song they like will leave immediately.
Input starts with two integers (1 <= D, S <= 500) separated by a single space. The next line contains the boredom factors of the dancers (1 <= B1, B2…, BD <= S) separated by single spaces. The next D lines describe the M matrix. Each line represents the musical preferences of a dancer, and will consist of S binary integers (0, 1) separated by single spaces.
Print the number of songs selected (P) for the playlist on a single line. Then print P integers, each one on a single line, indicating the songs selected, in any order. Notice that selecting a song more than once is not something a self-respecting DJ would ever do, so this will lead to Wrong Answer. The song numbers start from 0, i.e., print 0 when selecting the first song and S-1 when selecting the last.
Points scored for a single test will equal the number of dancers present when the party ends according to your playlist. The total score of the program is the sum of points scored in all tests.
2 3 3 4
1 0 0 0 0
0 0 1 0 0
1 1 1 0 1
0 1 0 0 0
|Time Limit:||0.4 - 3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, CS2, PAS fpc, PAS gpc, RUBY, PHP, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, TEXT|
Fetching successful submissions