Page 1 of 1
565 - Pizza Anyone?
Posted: Fri Feb 07, 2003 4:17 pm
by 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
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
please help me!
565 Pizza Anyone?
Posted: Mon Nov 24, 2003 10:06 am
by 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?
Posted: Thu Jan 01, 2004 4:10 am
by 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 -! )
Posted: Fri Aug 06, 2004 9:20 am
by 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?
Posted: Fri Aug 06, 2004 10:52 am
by 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.
Posted: Fri Aug 06, 2004 10:57 am
by 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"..
Posted: Sun Mar 05, 2006 9:16 pm
by 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.
Why "Stack was corrupted"?
Posted: Mon Nov 26, 2007 9:59 am
by 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?
Posted: Mon Nov 26, 2007 11:24 am
by sclo
Your line 6 is wrong. It should be:
Posted: Mon Nov 26, 2007 11:35 am
by snail.123
Thanks a lot! This error is kind of hard to spot for a Pascal programmer like me.
Re: 565 Pizza Anyone?
Posted: Tue Jun 28, 2011 4:39 pm
by 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?????????????????
Re: 565 - Pizza Anyone?
Posted: Wed Nov 18, 2015 11:15 pm
by 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
Re: 565 - Pizza Anyone?
Posted: Wed Nov 18, 2015 11:25 pm
by 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