{"problem":{"name":"C. Three Garlands","description":{"content":"Mishka is decorating the Christmas tree. He has got three garlands, and all of them will be put on the tree. After that Mishka will switch these garlands on. When a garland is switched on, it periodi","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF911C"},"statements":[{"statement_type":"Markdown","content":"Mishka is decorating the Christmas tree. He has got three garlands, and all of them will be put on the tree. After that Mishka will switch these garlands on.\n\nWhen a garland is switched on, it periodically changes its state — sometimes it is lit, sometimes not. Formally, if _i_\\-th garland is switched on during _x_\\-th second, then it is lit only during seconds _x_, _x_ + _k__i_, _x_ + 2_k__i_, _x_ + 3_k__i_ and so on.\n\nMishka wants to switch on the garlands in such a way that during each second after switching the garlands on there would be at least one lit garland. Formally, Mishka wants to choose three integers _x_1, _x_2 and _x_3 (not necessarily distinct) so that he will switch on the first garland during _x_1\\-th second, the second one — during _x_2\\-th second, and the third one — during _x_3\\-th second, respectively, and during each second starting from _max_(_x_1, _x_2, _x_3) at least one garland will be lit.\n\nHelp Mishka by telling him if it is possible to do this!\n\n## Input\n\nThe first line contains three integers _k_1, _k_2 and _k_3 (1 ≤ _k__i_ ≤ 1500) — time intervals of the garlands.\n\n## Output\n\nIf Mishka can choose moments of time to switch on the garlands in such a way that each second after switching the garlands on at least one garland will be lit, print _YES_.\n\nOtherwise, print _NO_.\n\n[samples]\n\n## Note\n\nIn the first example Mishka can choose _x_1 = 1, _x_2 = 2, _x_3 = 1. The first garland will be lit during seconds 1, 3, 5, 7, ..., the second — 2, 4, 6, 8, ..., which already cover all the seconds after the 2\\-nd one. It doesn't even matter what _x_3 is chosen. Our choice will lead third to be lit during seconds 1, 4, 7, 10, ..., though.\n\nIn the second example there is no way to choose such moments of time, there always be some seconds when no garland is lit.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Mishka 正在装饰圣诞树。他有三条彩灯串，都会被挂在树上。之后 Mishka 会打开这些彩灯串。\n\n当一条彩灯串被打开时，它会周期性地改变状态——有时亮着，有时不亮。形式上，如果第 #cf_span[i]- 条彩灯串在第 #cf_span[x]- 秒被打开，则它仅在秒数 #cf_span[x], #cf_span[x + ki], #cf_span[x + 2ki], #cf_span[x + 3ki] 等时刻亮起。\n\nMishka 希望以这样的方式打开彩灯串：在打开彩灯串后的每一秒，至少有一条彩灯串是亮着的。形式上，Mishka 需要选择三个整数 #cf_span[x1], #cf_span[x2] 和 #cf_span[x3]（不一定互不相同），使得他分别在第 #cf_span[x1]- 秒打开第一条彩灯串，第 #cf_span[x2]- 秒打开第二条，第 #cf_span[x3]- 秒打开第三条，并且从第 #cf_span[max(x1, x2, x3)] 秒开始，每一秒都至少有一条彩灯串亮着。\n\n请帮助 Mishka 判断这是否可能实现！\n\n第一行包含三个整数 #cf_span[k1], #cf_span[k2] 和 #cf_span[k3]（#cf_span[1 ≤ ki ≤ 1500]）——三条彩灯串的周期。\n\n如果 Mishka 可以选择打开彩灯串的时间，使得在打开彩灯串后的每一秒都至少有一条彩灯串亮着，请输出 _YES_。\n\n否则，输出 _NO_。\n\n在第一个例子中，Mishka 可以选择 #cf_span[x1 = 1], #cf_span[x2 = 2], #cf_span[x3 = 1]。第一条彩灯串会在秒数 #cf_span[1, 3, 5, 7, ...] 亮起，第二条会在 #cf_span[2, 4, 6, 8, ...] 亮起，这已经覆盖了第 #cf_span[2] 秒之后的所有秒数。即使 #cf_span[x3] 如何选择都无关紧要。我们的选择会使第三条彩灯串在秒数 #cf_span[1, 4, 7, 10, ...] 亮起。\n\n在第二个例子中，不存在任何选择方式，总会有某些秒数没有任何彩灯串亮着。\n\n## Input\n\n第一行包含三个整数 #cf_span[k1], #cf_span[k2] 和 #cf_span[k3]（#cf_span[1 ≤ ki ≤ 1500]）——三条彩灯串的周期。\n\n## Output\n\n如果 Mishka 可以选择打开彩灯串的时间，使得在打开彩灯串后的每一秒都至少有一条彩灯串亮着，请输出 _YES_。否则，输出 _NO_。\n\n[samples]\n\n## Note\n\n在第一个例子中，Mishka 可以选择 #cf_span[x1 = 1], #cf_span[x2 = 2], #cf_span[x3 = 1]。第一条彩灯串会在秒数 #cf_span[1, 3, 5, 7, ...] 亮起，第二条会在 #cf_span[2, 4, 6, 8, ...] 亮起，这已经覆盖了第 #cf_span[2] 秒之后的所有秒数。即使 #cf_span[x3] 如何选择都无关紧要。我们的选择会使第三条彩灯串在秒数 #cf_span[1, 4, 7, 10, ...] 亮起。\n\n在第二个例子中，不存在任何选择方式，总会有某些秒数没有任何彩灯串亮着。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ k_1, k_2, k_3 \\in \\mathbb{Z}^+ $ with $ 1 \\leq k_i \\leq 1500 $ be the periods of the three garlands.  \n\nLet $ x_1, x_2, x_3 \\in \\mathbb{Z}^+ $ be the start times (in seconds) when each garland is switched on.  \n\nDefine the set of seconds when garland $ i $ is lit as:  \n$$\nG_i = \\{ x_i + t \\cdot k_i \\mid t \\in \\mathbb{Z}_{\\geq 0} \\}\n$$\n\nLet $ T = \\max(x_1, x_2, x_3) $.  \n\n**Constraints**  \nWe require that for all $ s \\geq T $,  \n$$\ns \\in G_1 \\cup G_2 \\cup G_3\n$$\n\n**Objective**  \nDetermine whether there exist $ x_1, x_2, x_3 \\in \\mathbb{Z}^+ $ such that the union $ G_1 \\cup G_2 \\cup G_3 $ covers all integers $ s \\geq T $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF911C","tags":["brute force","constructive algorithms"],"sample_group":[["2 2 3","YES"],["4 2 3","NO"]],"created_at":"2026-03-03 11:00:39"}}