565 - Pizza Anyone?

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

565 - Pizza Anyone?

Post by hank » Fri Feb 07, 2003 4:17 pm

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
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan

565 Pizza Anyone?

Post by eloha » Mon Nov 24, 2003 10:06 am

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

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Thu Jan 01, 2004 4:10 am

(** 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 :wink: ( See their ranking in the ranklist -! )
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

Post by Minilek » Fri Aug 06, 2004 9:20 am

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?

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Fri Aug 06, 2004 10:52 am

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
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

Post by Minilek » Fri Aug 06, 2004 10:57 am

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
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Sun Mar 05, 2006 9:16 pm

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
New poster
Posts: 14
Joined: Wed Jun 13, 2007 3:29 am
Location: Taiwan

Why "Stack was corrupted"?

Post by snail.123 » Mon Nov 26, 2007 9:59 am

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?
Last edited by snail.123 on Mon Nov 26, 2007 11:38 am, edited 2 times in total.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Nov 26, 2007 11:24 am

Your line 6 is wrong. It should be:

Code: Select all

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

snail.123
New poster
Posts: 14
Joined: Wed Jun 13, 2007 3:29 am
Location: Taiwan

Post by snail.123 » Mon Nov 26, 2007 11:35 am

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

back_tracker
New poster
Posts: 9
Joined: Sun Jun 19, 2011 12:03 am

Re: 565 Pizza Anyone?

Post by back_tracker » Tue Jun 28, 2011 4:39 pm

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
Learning poster
Posts: 69
Joined: Mon Feb 09, 2015 1:56 am

Re: 565 - Pizza Anyone?

Post by anacharsis » Wed Nov 18, 2015 11:15 pm

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
Learning poster
Posts: 69
Joined: Mon Feb 09, 2015 1:56 am

Re: 565 - Pizza Anyone?

Post by anacharsis » Wed Nov 18, 2015 11:25 pm

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

Post Reply

Return to “Volume 5 (500-599)”