565 - Pizza Anyone?

[hank]

I can't understand what the problem said!!

the input

Code: Select all

+A+B+C+D-E-F-G-H;
-A-B+C+D-E-F+G+H;
-A+B-C+D-E+F-G+H;

I don't know why the output is

Code: Select all

Toppings:

and
input

Code: Select all

+A+B+C+D;
+E+F+F+H;
+A+B-G;
+O+J-F;
+H+I+C;
+P;
+O+M+L;
+M-L+P;

why the output is

Code: Select all

Toppings: CELP

please help me!

[eloha]

I caculate all the possible combination topping for the constraints.
It works fine. But it is not fast enough. I got TLE.
Can anyone tell me your idea about this problem?

[Observer]

(** Late reply ! **)

My backtracking solution goes for less than 1 sec., so it isn't so bad after all......

But I believe that there must be some quicker method to solve this problem.. Maybe you should ask Whinii F., little joey or LittleJohn ( See their ranking in the ranklist -! )

[Minilek]

the input

[c]
+A+B+C+D-E-F-G-H;
-A-B+C+D-E-F+G+H;
-A+B-C+D-E+F-G+H;
[/c]

I don't know why the output is
[c]
Toppings:
[/c]

I think there are not unique answers for this problem. All three of them said they are happy as long as the pizza is -E, so a pizza with no toppings at all is definitely -E and thus satisfies them all. However, all 3 of them also said +D, so you could give them each a pizza with only topping D, and that will satisfy all of them too.

Are we supposed to return the pizza with the minimum number of toppings for this problem (and if there is a tie?). Or is this a problem with a special judge that accepts any valid answer?

[little joey]

Yes, many answers are acceptable, as is indicated by the yellow checkmark. In fact the answer my program gives to the first sample is "B".
By not including topping A, the second and third person are happy (they both have -A), and by including B, the first person is happy (he/she has +B), so all three people are happy. But there are many more pizzas satisfying all three requests, including the empty pizza.

[Minilek]

Yes, many answers are acceptable, as is indicated by the yellow checkmark.

Ah..so that is what they meant by a "special correction program"..

[yiuyuho]

It's a program that takes the output of your program as input and checks whether your output is correct. In this instance, it will check whether you decided that there is a valid pizza, and if so, it will read your toppings and see if they in fact satisfy everyone in the original input of the problem.

[snail.123]

Here's my code for "p565: Pizza Anyone?"

Code: Select all

#include <iostream>
using namespace std;

int main() {
   char ch;
   int n, req[1][12], i, sat, j, tp;

         // code deleted after AC

         req[0][n] = req[1][n] = 0; // value of n is changed unexpectedly here.

         // code deleted after AC
   }
}

When I ran it in Visual C++ 2005 Express, I got

Run-Time Check Failure #2 - Stack around the variable 'req' was corrupted.

I got "Runtime error" when I submitted it to OnlineJudge.

I traced my code and found the value of n was changed unexpectedly at line 10 as the remark shows.

I can't figure out what is going wrong. Can anyone help me with this?

[sclo]

Your line 6 is wrong. It should be:

Code: Select all

int n, req[2][12], i, sat, j, tp; 

[snail.123]

Thanks a lot! This error is kind of hard to spot for a Pascal programmer like me.

[back_tracker]

Guys, I really need help and I am sure all of you can answer my question.

I solved the problem and everything works fine. The problem is that how can I determine the end of the test cases I have, There is no specific number of test cases for this problem so How many test cases should I provide?????? The program won't terminate if there is no indecation for the end of the program. And here, there is no indecation, so WHEN SHOULD I END THE PROGRAM?????????????????

[anacharsis]

Some I/O
In:

Code: Select all

+C+K-P-H;
-E-A-P-D-L;
+P;
-C+E-L-I;
-E-H+B;
-N-J+H;
+B+A-P+F;
-O+K+F+G;
+B-H-P+E+L;
.
+H+O+D;
-K;
+C+E-J-K+D;
+B;
+H+L-P+M+K;
+J-O+F-I+H;
-N+L-B;
.
-E-O-I;
-F;
+D-H-P;
+I;
-N-P+B;
+J;
.
-F-K;
-B+O+N-J+A;
+B;
+N+O+L-P;
-C+K-E-I;
-G-B+F+A;
+N;
+P+K-B;
.
+D-H+J-B;
-L+F-N+C;
-D-G;
+J+G-M+D;
+N;
.
+G-F-M;
+H;
-O-F-M;
+A+H+C-B+E;
-A+C+B;
-N+H+J;
-D+P;
+F-I+K;
+M-F+E;
.
+G-D+O;
-O;
+E+H;
-L-C-E-J;
-A-N;
+O+L-I-G-M;
+N+D+M;
-M-J-L;
-F-G+I+A+P;
+C-L+J-D+I;
-H-F+K-I+J;
.
-M-G+P;
-D-E-O;
+I;
+H-G;
-O+N+P+C;
+N+E-K+J-I;
.
-L+P+J-G;
+L+P;
+E-I;
-J-F;
-K-O+C+E;
-F+O-C-E;
+P+D-E;
.
-P+D-H;
+M+N;
-P-H+B-K-C;
+D;
+E-B-G-F-I;
-P;
+A+P-C-H;
-L-J+F+P;
-H;
+I+P-A-G;
+L+N+E+F+K;
-E-O;
.
-C+M-K;
+A+F+H+D-G;
-I;
-O-A+L+C-F;
+C+P;
+L+I+K+H-P;
+N-J;
.
-H;
-L-H;
.
-A+M+F;
+I;
+O;
-O+F+B-D;
+J+A+H;
-I-A-M+B;
-K;
.
-G-C+N;
+D-A-G+P-F;
.
+G;
+C-O;
+H-K;
-L-P-C-E;
+N+K;
.
-K-E;
-C-I-D-B+J;
-D+E+O;
.
-K-D;
-E-N;
-I;
-F-A-B;
-E;
+C+F-G;
.
-F;
+K+A+F+I+L;
.
+M+O-N-P+B;
+O-F+D-H;
-J-F;
+L-E-J-G-A;
.
+O+J+K+L;
+A-D+I-C-P;
+N-J+C+H;
.
-N;
+F-N-E-B-I;
-J+A-N;
+N-B;
+P-K+O+M-F;
+B+P+E+D-A;
-P-G+D;
-I+O;
-I-B;
-A;
.
+E-M;
+F+P-B-H+D;
+K-D-E;
-P+A+H;
+P;
-K+C-H+O;
.
-A-F+B-D;
+N-B+D;
+N-D-E+M;
+O-J-I;
+F;
-E;
-H-L+M+I+D;
+M-N-G-I+E;
-G+M-I-H+B;
.
+D+P+N-I-A;
+L-P+M-O+B;
.
+N;
-J-K;
+K+N-A;
+I+B+J-M+G;
-C;
+G+C-J+A-P;
+E-P;
+B;
-O+E-B+G+I;
.
-K;
+G;
+P-E+H-N;
+K+F+D-A;
+J-P-E+G;
-O;
-P+I-O-G-A;
-I+B+E-P+D;
.
-M;
+E+C;
+J;
+C-K;
+K;
-N-I-G;
-D-G+M+K;
+O-D-L;
.
+N-H-E-J+D;
+O-L-C-A-F;
-I;
+N;
-C+M-J-B;
-N+L;
-I-A+K+O+P;
-K+C-O;
-P+B;
-F-G;
-F-P+C+E+L;
+E+N+F;
.
-C+K+F;
-F+G-L;
+E-B+I-C;
-H-O-J-E;
-C+E-N+H-G;
+I-H;
+M+L-O+B+E;
+A;
+I-O+P-G+M;
.
-D;
-C-M+D+G;
+D+C;
.
+K-A+E+B+N;
+F+H+D-K;
+C+A+O-M-D;
-C;
+B-M+N-L;
.
-P-J;
-O;
-N;
-F+E-M+C;
-I-E+M+G;
-F;
-P-E;
-G+D;
.
-P-A+F+L+C;
-K-G-B-P-A;
+F+B-J;
+P-G+K;
.
-M;
-A;
+K+M;
+K-L-O+I+J;
-L-N+M;
-P+E-N+M+D;
+B+D-A+K;
.
-J-F;
+H+G;
-I-C+J+B;
+E+M+N-B;
+K-N+B-L;
+N;
+N+C+B-I-H;
+L-N;
-D+G;
+D+F;
+M-H-I+G-J;
-O+L-M;
.
+B+C;
+B;
-D-B+K;
-K-F-N+H;
-K+A;
.
-D+L;
-K;
-A-K+E+C;
-D+M+O;
-G;
+F;
.
-F-P;
+H;
-L+B;
-O+J+G+L-B;
-D+O;
-E-O;
-H-G+E;
-E-J+G;
.
-L;
-N;
.
+I+E;
+L+P;
+A-C;
+B+J+N-O;
+N;
-O-B-C;
+N;
+O+G;
+N+H+P-I-E;
+G-J;
-D+C+A-F-L;
+L+M;
.
+L+E+O;
-O-I-P+D;
-P+N+A-G;
-I;
+O+F+I+B;
+E-K-P;
+E;
-D;
.
+A+P;
+B-L+E+K+F;
+G;
+N-E;
-A+F-D+G+H;
-L+F;
+N-H-L-K;
-L+N-K;
+C-B+F+M+O;
-D+J-M+L-A;
-B;
-K+J+L;
.
+O+L-M-E-H;
-G;
-N+G;
-E-J+G-M+A;
+G-A-L;
-J+L-E-H+M;
+A+L-E+G;
.
+N-J+C-H;
-H-P;
-A-K+F;
-I;
.
-C+M+L+J+A;
-A+I-F-N-L;
-O-B-N-C;
-P+O+H;
+K+J-E+D-H;
-C+H+E+I;
+D-I;
-P+F+H;
+B-F+I;
-L;
-L;
+N-E-K;
.
+J+H-M+A;
-H+D-B;
+N-H+D+J-M;
+F+C;
+C+P+O-J+B;
-N;
-C+P+H+B;
.
-C+N-P+D-I;
-G-L+F-K;
+O;
.
-N;
-P+D;
-C+E+L;
+N+B-L-K;
-F+A+L+E+O;
-O-M+J-I+N;
-C+D-A+I+O;
+A+L-B;
+D+C-J;
-A+I;
.
+O;
+N-L+A+I;
+B;
+D;
+E+M+F+H-L;
-I+H-A;
+L+J;
.
-J+F+E;
-E;
-K;
-D-P-I;
+D-H;
.

AC out:

Code: Select all

Toppings: BCEFHP
Toppings: BCDFHL
Toppings: BDIJ
Toppings: ABKLN
Toppings: CGN
Toppings: ABEH
Toppings: EM
Toppings: CEI
Toppings: CDEL
Toppings: ABDEFM
Toppings: AHP
Toppings: 
Toppings: BHIO
Toppings: 
Toppings: CGHK
Toppings: 
Toppings: C
Toppings: A
Toppings: BD
Toppings: ACJ
Toppings: D
Toppings: ACEP
Toppings: F
Toppings: B
Toppings: BEGN
Toppings: BG
Toppings: CJK
Toppings: CDELN
Toppings: AL
Toppings: CG
Toppings: BD
Toppings: CD
Toppings: B
Toppings: DIK
Toppings: BDEGLN
Toppings: AB
Toppings: F
Toppings: BEGH
Toppings: 
Toppings: ABEGHLN
Toppings: ABE
Toppings: AEFGJN
Toppings: A
Toppings: C
Toppings: ADH
Toppings: ACDH
Toppings: FO
Toppings: ABDIJ
Toppings: ABDEHJO
Toppings: F

[anacharsis]

I think the sample output could have been chosen to make things a bit more clear.
For example, the first input is

+A+B+C+D-E-F-G-H;
-A-B+C+D-E-F+G+H;
-A+B-C+D-E+F-G+H;
.

The sample output indicates that the empty pizza satisfies these preference lists.
It's true it does - it is WITHOUT E, so it satisfies all three prefs.
A pizza WITH D also satisfies, since that pref is on all 3 lists.

But so does a pizza WITH A!
This is the confusing one, because it looks like a conflict.
Some people want A, others don't, so how could it satisfy both.
Answer - the pizza WITH A is also WITHOUT C and WITHOUT E, so it satisfies at least one pref from each list.

Maybe this was clear to everyone - but I had a hard time with this problem, so I thought I'd offer my two cents