{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:50.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/b3ea5885c6157e42e8a75bf0fa1e3ee8?v\u003d1715293566\" alt\u003d\"/problems/pizzaproblems/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003e\n\n \u003cp\u003eMe and my friends are ordering a big pizza to share. As you\n can imagine this is quite complicated, since everyone has\n different wishes about what should be on the pizza. For\n instance Gunnar wants bananas on the pizza, Emma doesn’t want\n bananas but wants olives, Marc wants there to be tomatoes, and\n so on. Fortunately, against all odds, we managed to come up\n with a selection of toppings such that everyone had at least\n \u003cspan class\u003d\"tex2jax_process\"\u003e$2/3$\u003c/span\u003e’s of their wishes\n fulfilled, which we unanimously decided was good enough.\u003c/p\u003e\n\n \u003cp\u003eBut then, disaster struck! We sent out Lukáš to buy the\n pizza, but he accidentally lost the piece of paper on which we\n had written down our carefully selected list of toppings. Now\n we’re back at square one, and have to construct a new selection\n of toppings. Given how long it took us to find the original\n selection of toppings, we have decided to lower our standards a\n bit and just try to find a selection such that everyone has\n \u003cem\u003estrictly\u003c/em\u003e more than \u003cspan class\u003d\"tex2jax_process\"\u003e$1/3$\u003c/span\u003e of their wishes fulfilled.\u003c/p\u003e\n\n \u003cp\u003eCan you help us with this? If you do, you’ll get some\n pizza!\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe first line of input contains an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le N \\le 10\\, 000$\u003c/span\u003e, the number of\n friends in the group (including yourself). Each of the next\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e lines contains the\n list of wishes of one of the friends. This list starts with an\n integer \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le w \\le 30$\u003c/span\u003e,\n the number of wishes this friend has, followed by a\n space-separated list of wishes. Each wish is either “\u003ctt class\u003d\"ttfamily\"\u003e+\u0026lt;topping\u0026gt;\u003c/tt\u003e” or “\u003ctt class\u003d\"ttfamily\"\u003e-\u0026lt;topping\u0026gt;\u003c/tt\u003e” where \u003ctt class\u003d\"ttfamily\"\u003e\u0026lt;topping\u0026gt;\u003c/tt\u003e is the name of a topping,\n indicating that this friend wants or does not want this\n topping. Each topping name appears at most once in each\n list.\u003c/p\u003e\n\n \u003cp\u003eTopping names are non-empty strings of up to \u003cspan class\u003d\"tex2jax_process\"\u003e$15$\u003c/span\u003e lower-case English letters\n ‘\u003ctt class\u003d\"ttfamily\"\u003ea\u003c/tt\u003e’-‘\u003ctt class\u003d\"ttfamily\"\u003ez\u003c/tt\u003e’.\n There are at most \u003cspan class\u003d\"tex2jax_process\"\u003e$250$\u003c/span\u003e\n different toppings.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eOutput a list of toppings (without repetitions, separated by\n spaces or newlines) such that each friend has strictly more\n than \u003cspan class\u003d\"tex2jax_process\"\u003e$1/3$\u003c/span\u003e of their wishes\n fulfilled. You may assume that there exists a list such that\n every friend has at least \u003cspan class\u003d\"tex2jax_process\"\u003e$2/3$\u003c/span\u003e of their wishes fulfilled.\u003c/p\u003e\n\n \u003cp\u003eYour list of toppings is not allowed to contain any toppings\n that are not mentioned in the input, nor is it allowed to\n contain repetitions.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\n4 +zucchini +mozzarella +mushrooms -artichoke\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003ezucchini\nmozzarella\nmushrooms\nartichoke\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n3 +redbeans +soylentgreen -bluecheese\n3 +redbeans -soylentgreen +bluecheese\n3 -redbeans +soylentgreen +bluecheese\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eredbeans\nsoylentgreen\nbluecheese\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}