\u0628\u0627 \u0633\u0644\u0627\u0645 \u062f\u0648\u0628\u0627\u0631\u0647! \ud83d\ude42<\/p>\n
\u0627\u0645\u06cc\u062f\u0648\u0627\u0631\u06cc\u0645 \u06a9\u0647 \u0627\u0632 \u0627\u06cc\u0646 \u0645\u0633\u0627\u0628\u0642\u0647 \u0644\u0630\u062a \u0628\u0631\u062f\u0647\u200c\u0628\u0627\u0634\u06cc\u062f. \u0631\u0627\u0647\u0646\u0645\u0627\u06cc\u06cc\u200c\u0647\u0627\u060c \u0631\u0627\u0647\u200c\u062d\u0644\u200c\u0647\u0627\u060c \u06a9\u062f \u0635\u062d\u06cc\u062d \u0633\u0648\u0627\u0644\u0627\u062a \u0628\u0647 \u0647\u0645\u0631\u0627\u0647 \u0686\u0627\u0644\u0634\u200c\u0647\u0627\u060c \u0647\u0645\u06af\u06cc \u062f\u0631\u00a0\u0627\u062f\u0627\u0645\u0647\u200c\u06cc \u0645\u0637\u0644\u0628 \u0622\u0648\u0631\u062f\u0647 \u0634\u062f\u0647 \u0627\u0646\u062f. \u062f\u0631 \u0635\u0648\u0631\u062a\u06cc \u06a9\u0647 \u0628\u0631\u0627\u06cc \u0633\u0648\u0627\u0644\u0627\u062a \u0648 \u06cc\u0627 \u0686\u0627\u0644\u0634 \u0647\u0627 \u0631\u0627\u0647 \u062d\u0644 \u0647\u0627\u06cc \u062c\u062f\u06cc\u062f\u06cc \u062f\u0627\u0634\u062a\u06cc\u062f\u060c \u0645\u06cc \u062a\u0648\u0627\u0646\u06cc\u062f \u062f\u0631 \u0628\u062e\u0634 \u062f\u06cc\u062f\u06af\u0627\u0647 \u0647\u0627 \u0645\u0637\u0631\u062d \u06a9\u0646\u06cc\u062f. \ud83d\ude42<\/p>\n
<\/p>\n
\u0627\u06cc\u062f\u0647\u200c\u06cc \u0633\u0648\u0627\u0644: <\/span>\u0645\u062d\u0645\u062f\u0627\u0645\u06cc\u0646 \u0631\u06cc\u06cc\u0633\u06cc<\/p>\n \u0637\u0631\u0627\u062d\u06cc \u062a\u0633\u062a\u200c\u0647\u0627: <\/span>\u0645\u0647\u062f\u06cc \u0627\u0645\u06cc\u0631\u06cc – \u0645\u062d\u0645\u062f\u0627\u0645\u06cc\u0646 \u0631\u06cc\u06cc\u0633\u06cc \u067e\u06cc\u0634\u200c\u0646\u06cc\u0627\u0632: <\/span>–<\/p>\n \u0631\u0627\u0647\u0646\u0645\u0627\u06cc\u06cc: <\/span>\u0633\u0639\u06cc \u06a9\u0646\u06cc\u062f \u062a\u0645\u0627\u0645 \u062d\u0627\u0644\u0627\u062a \u0645\u062e\u062a\u0644\u0641 \u0628\u0631\u0627\u06cc \u0686\u0631\u062e\u0627\u0646\u062f\u0646 \u06cc\u062e \u0631\u0627 \u0628\u0647 \u062f\u0633\u062a \u0622\u0648\u0631\u06cc\u062f.<\/p>\n \u0631\u0627\u0647\u200c\u062d\u0644 \u0627\u0648\u0644: <\/span>\u0645\u06cc\u200c\u062f\u0627\u0646\u06cc\u0645 \u06a9\u0647 \u062f\u0631 \u06a9\u0644 \u06f6 \u062c\u0627\u06cc\u06af\u0634\u062a \u0627\u0632 \u0637\u0648\u0644\u060c \u0639\u0631\u0636 \u0648 \u0627\u0631\u062a\u0641\u0627\u0639 \u06cc\u062e \u0648\u062c\u0648\u062f \u062f\u0627\u0631\u062f \u0648 \u0628\u0646\u0627\u0628\u0631\u0627\u06cc\u0646 \u0645\u06cc \u062a\u0648\u0627\u0646 \u062a\u0645\u0627\u0645 \u0627\u06cc\u0646 \u06f6 \u062d\u0627\u0644\u062a \u0631\u0627 \u0628\u0647 \u062f\u0633\u062a \u0622\u0648\u0631\u062f. \u0627\u06af\u0631 \u062f\u0631 \u062d\u062f\u0627\u0642\u0644 \u06cc\u06a9\u06cc \u0627\u0632 \u0627\u06cc\u0646 \u062d\u0627\u0644\u0627\u062a \u0637\u0648\u0644 \u06cc\u062e \u06a9\u0648\u0686\u06a9\u200c\u062a\u0631 \u0645\u0633\u0627\u0648\u06cc \u0637\u0648\u0644 \u062c\u0639\u0628\u0647 \u0648 \u0639\u0631\u0636 \u06cc\u062e \u06a9\u0648\u0686\u06a9\u200c\u062a\u0631 \u0645\u0633\u0627\u0648\u06cc \u0639\u0631\u0636 \u062c\u0639\u0628\u0647 \u0628\u0627\u0634\u062f\u060c \u0622\u0646 \u0647\u0627 \u0632\u0646\u062f\u0647 \u062e\u0648\u0627\u0647\u0646\u062f \u0645\u0627\u0646\u062f. \u0628\u0631\u0627\u06cc\u00a0\u06a9\u0648\u062a\u0627\u0647\u200c\u0634\u062f\u0646 \u06a9\u062f \u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u06cc\u062f \u0627\u0632 \u062f\u0633\u062a\u0648\u0631\u06cc \u0645\u0627\u0646\u0646\u062f next permutation <\/span> \u0627\u0633\u062a\u0641\u0627\u062f\u0647 \u06a9\u0646\u06cc\u062f.<\/p>\n \u0631\u0627\u0647\u200c\u062d\u0644\u00a0\u062f\u0648\u0645: <\/span>\u06cc\u062e \u0631\u0627 \u0637\u0648\u0631\u06cc \u0645\u06cc\u200c\u0686\u0631\u062e\u0627\u0646\u06cc\u0645 \u06a9\u0647 \u0628\u0632\u0631\u06af\u200c\u062a\u0631\u06cc\u0646 \u0636\u0644\u0639 \u06cc\u062e\u060c \u0627\u0631\u062a\u0641\u0627\u0639 \u0622\u0646 \u0634\u0648\u062f. \u062f\u0648 \u0636\u0644\u0639 \u062f\u06cc\u06af\u0631 \u06cc\u062e \u0631\u0627 p <\/span> \u0648 q <\/span> \u062f\u0631 \u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u062f. \u0627\u06a9\u0646\u0648\u0646 \u0627\u06af\u0631 \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u06cc\u0645 \u06a9\u0647 min(p,q) \\leq min(a,b) <\/span> \u0648 max(p,q) \\leq max(a,b) <\/span>\u060c \u0622\u0646 \u0647\u0627 \u0632\u0646\u062f\u0647 \u062e\u0648\u0627\u0647\u0646\u062f \u0645\u0627\u0646\u062f.<\/p>\n \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc: <\/span> O(1) <\/span><\/p>\n \u06a9\u062f \u0645\u0633\u0626\u0644\u0647\u200c\u06cc \u0622\u0628 \u0628\u0647 \u0632\u0628\u0627\u0646 ++C<\/a><\/span><\/p>\n \u0686\u0627\u0644\u0634: <\/span>\u0641\u0631\u0636 \u06a9\u0646\u06cc\u062f \u0634\u0631\u0637 \u0642\u0631\u0627\u0631\u06af\u06cc\u0631\u06cc \u06cc\u06a9 \u062c\u0639\u0628\u0647\u200c\u06cc \u0645\u06a9\u0639\u0628 \u0645\u0633\u062a\u0637\u06cc\u0644\u06cc \u062f\u0631 \u062c\u0639\u0628\u0647\u200c\u06cc \u062f\u06cc\u06af\u0631 \u0628\u0647 \u0647\u0645\u06cc\u0646\u200c\u0635\u0648\u0631\u062a \u0628\u0627\u0634\u062f. \u0627\u06a9\u0646\u0648\u0646 \u0634\u0645\u0627 n <\/span> \u062a\u0627 \u062c\u0639\u0628\u0647\u200c\u06cc \u062f\u0631\u0628\u0627\u0632 \u062f\u0627\u0631\u06cc\u062f. \u0628\u0627\u06cc\u062f \u0628\u06af\u0648\u06cc\u06cc\u062f \u06a9\u0647 \u0622\u06cc\u0627 \u0631\u0648\u0634\u06cc \u0648\u062c\u0648\u062f \u062f\u0627\u0631\u062f \u06a9\u0647 \u062a\u0645\u0627\u0645 \u0627\u06cc\u0646 n <\/span> \u0631\u0627 \u062f\u0631 \u0647\u0645\u200c\u062f\u06cc\u06af\u0631 \u0642\u0631\u0627\u0631 \u062f\u0627\u062f \u06cc\u0627 \u062e\u06cc\u0631\u061f<\/p>\n \u0627\u06cc\u062f\u0647\u200c\u06cc \u0633\u0648\u0627\u0644: <\/span>\u0645\u0647\u062f\u06cc \u0627\u0645\u06cc\u0631\u06cc<\/p>\n \u0637\u0631\u0627\u062d\u06cc \u062a\u0633\u062a\u200c\u0647\u0627: <\/span>\u0645\u0647\u062f\u06cc \u0627\u0645\u06cc\u0631\u06cc \u067e\u06cc\u0634\u200c\u0646\u06cc\u0627\u0632: <\/span>–<\/p>\n \u0631\u0627\u0647\u0646\u0645\u0627\u06cc\u06cc: <\/span>\u0631\u0627\u0647\u200c\u062d\u0644 \u0633\u0648\u0627\u0644 \u062f\u0631 \u0645\u062a\u0646 \u0633\u0648\u0627\u0644 \u0648\u062c\u0648\u062f \u062f\u0627\u0631\u062f!<\/p>\n \u0631\u0627\u0647\u200c\u062d\u0644: <\/span>\u0627\u0628\u062a\u062f\u0627 \u062f\u0646\u0628\u0627\u0644\u0647 \u06cc a <\/span> \u0631\u0627 \u0637\u0648\u0631\u06cc \u062f\u0631\u0633\u062a \u06a9\u0646\u06cc\u062f \u06a9\u0647 a_i <\/span> \u0646\u0634\u0627\u0646\u200c\u062f\u0647\u0646\u062f\u0647\u200c\u06cc \u062a\u0639\u062f\u0627\u062f \u062a\u06a9\u0631\u0627\u0631\u200c\u0647\u0627\u06cc i <\/span> \u0627\u0645\u06cc\u0646 \u062d\u0631\u0641 \u0627\u0646\u06af\u0644\u06cc\u0633\u06cc (\u0628\u0632\u0631\u06af \u06cc\u0627 \u06a9\u0648\u0686\u06a9) \u062f\u0631 \u0631\u0634\u062a\u0647\u200c\u06cc \u0648\u0631\u0648\u062f\u06cc \u0628\u0627\u0634\u062f. \u0627\u06a9\u0646\u0648\u0646 \u0628\u0627 \u06cc\u06a9 \u062d\u0644\u0642\u0647 \u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u06cc\u062f \u0622\u0646\u200c\u0686\u0647 \u0645\u0633\u0626\u0644\u0647 \u062e\u0648\u0627\u0633\u062a\u0647\u200c\u0627\u0633\u062a \u0631\u0627 \u067e\u06cc\u0627\u062f\u0647\u200c\u0633\u0627\u0632\u06cc \u06a9\u0646\u06cc\u062f. \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc: <\/span> O(|S|) <\/span><\/p>\n \u06a9\u062f \u0645\u0633\u0626\u0644\u0647\u200c\u06cc \u0627\u0645\u0646\u06cc\u062a\u06cc \u0628\u0647 \u0632\u0628\u0627\u0646 ++C<\/a><\/span><\/p>\n \u0686\u0627\u0644\u0634 \u0627\u0648\u0644: <\/span>\u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u06cc \u0637\u0631\u0627\u062d\u06cc \u06a9\u0646\u06cc\u062f \u06a9\u0647 \u0628\u0627 \u06af\u0631\u0641\u062a\u0646 \u06cc\u06a9 \u0631\u0634\u062a\u0647 \u0645\u0627\u0646\u0646\u062f S <\/span>\u060c \u06cc\u06a9 \u0631\u0634\u062a\u0647\u200c \u062e\u0631\u0648\u062c\u06cc \u0628\u062f\u0647\u062f \u06a9\u0647 \u0631\u0645\u0632\u200c\u0634\u062f\u0647\u200c\u06cc \u0622\u0646\u060c \u0631\u0634\u062a\u0647\u200c\u06cc S <\/span> \u0628\u0627\u0634\u062f.<\/p>\n \u0686\u0627\u0644\u0634 \u062f\u0648\u0645: <\/span>\u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u06cc \u0637\u0631\u0627\u062d\u06cc \u06a9\u0646\u06cc\u062f \u06a9\u0647 \u0628\u0627 \u06af\u0631\u0641\u062a\u0646 \u06cc\u06a9 \u0631\u0634\u062a\u0647 \u0645\u0627\u0646\u0646\u062f S <\/span>\u060c \u0628\u0627\u0642\u06cc\u200c\u0645\u0627\u0646\u062f\u0647\u200c\u06cc \u062a\u0639\u062f\u0627\u062f \u0631\u0634\u062a\u0647\u200c\u0647\u0627\u06cc\u06cc \u06a9\u0647 \u0631\u0645\u0632\u200c\u0634\u062f\u0647\u200c\u06cc \u0622\u0646\u200c\u0647\u0627\u060c \u0631\u0634\u062a\u0647\u200c\u06cc S <\/span> \u0627\u0633\u062a\u060c \u0631\u0627 \u0628\u0631\u00a0 10^{9} + 7 <\/span> \u0628\u06af\u0648\u06cc\u062f.<\/p>\n \u0627\u06cc\u062f\u0647\u200c\u06cc \u0633\u0648\u0627\u0644: <\/span>\u0645\u062d\u0645\u062f\u0627\u0645\u06cc\u0646 \u0631\u06cc\u06cc\u0633\u06cc<\/p>\n \u0637\u0631\u0627\u062d\u06cc \u062a\u0633\u062a\u200c\u0647\u0627: <\/span>\u0645\u062d\u0645\u062f\u0627\u0645\u06cc\u0646 \u0631\u06cc\u06cc\u0633\u06cc \u067e\u06cc\u0634\u200c\u0646\u06cc\u0627\u0632: <\/span>–<\/p>\n \u0631\u0627\u0647\u0646\u0645\u0627\u06cc\u06cc:<\/span> \u0632\u0645\u0627\u0646\u06cc \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u0686\u0631\u0632\u0647 \u067e\u0627\u0633\u062e \u0635\u062d\u06cc\u062d \u0646\u0645\u06cc\u200c\u062f\u0647\u062f \u06a9\u0647 \u062d\u062f\u0627\u0642\u0644 \u062f\u0648 \u0639\u062f\u062f \u0628\u0631\u0627\u0628\u0631 \u062f\u0631 \u062f\u0646\u0628\u0627\u0644\u0647\u200c\u0627\u06cc \u06a9\u0647 \u0628\u0627\u06cc\u062f \u0645\u0631\u062a\u0628\u200c\u0633\u0627\u0632\u06cc \u0634\u0648\u062f\u060c \u0648\u062c\u0648\u062f \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u062f.<\/p>\n \u0631\u0627\u0647\u200c\u062d\u0644:<\/span> \u0641\u0631\u0636 \u06a9\u0646\u06cc\u062f \u06a9\u0647 \u0628\u062e\u0648\u0627\u0647\u06cc\u0645 \u062f\u0646\u0628\u0627\u0644\u0647\u200c\u06cc tmp <\/span> \u0631\u0627 \u0628\u0627 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u0686\u0631\u0632\u0647 \u0645\u0631\u062a\u0628\u200c\u0633\u0627\u0632\u06cc \u06a9\u0646\u06cc\u0645. \u062a\u0635\u0648\u0631 \u06a9\u0646\u06cc\u062f \u06a9\u0647 \u062f\u0648 \u0639\u062f\u062f i <\/span> \u0648 j <\/span> \u0648\u062c\u0648\u062f \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u062f \u06a9\u0647\u00a0 tmp_i = tmp_j <\/span>. \u062f\u0631 \u0627\u06cc\u0646 \u0635\u0648\u0631\u062a\u00a0\u0645\u06cc\u200c\u062f\u0627\u0646\u06cc\u0645 \u06a9\u0647 \u0647\u0631 \u0639\u062f\u062f\u06cc \u062f\u0631 \u0627\u06cc\u0646 \u062f\u0646\u0628\u0627\u0644\u0647 \u06a9\u0647 \u0627\u0632\u00a0 tmp_i <\/span>\u00a0\u06a9\u0648\u0686\u06a9\u200c\u062a\u0631 \u0628\u0627\u0634\u062f\u060c \u0627\u0632\u00a0 tmp_j <\/span> \u0646\u06cc\u0632\u00a0\u06a9\u0648\u0686\u06a9\u200c\u062a\u0631 \u0627\u0633\u062a \u0648 \u0628\u0627\u0644\u0639\u06a9\u0633\u061b \u0628\u0646\u0627\u0628\u0631\u0627\u06cc\u0646\u00a0\u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u06cc\u0645 \u0628\u06af\u0648\u06cc\u06cc\u0645 \u06a9\u0647 \u062f\u0631\u00a0\u0627\u06cc\u0646\u200c\u062c\u0627 \u0639\u062f\u062f\u00a0 t <\/span> \u0628\u0631\u0627\u06cc\u00a0\u0647\u0631\u200c\u062f\u0648 \u06cc\u06a9\u0633\u0627\u0646 \u0648 \u0645\u0633\u0627\u0648\u06cc \u0627\u0633\u062a\u061b \u067e\u0633 \u0645\u0627\u00a0\u0628\u0647\u200c\u062c\u0627\u06cc\u00a0\u0627\u06cc\u0646\u200c\u06a9\u0647 \u0647\u0631 \u062f\u0648 \u0639\u062f\u062f \u0631\u0627 \u062f\u0631\u00a0\u062f\u0646\u0628\u0627\u0644\u0647\u200c\u06cc \u0646\u0647\u0627\u06cc\u06cc \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u06cc\u0645\u060c \u0641\u0642\u0637 \u06cc\u06a9\u06cc \u0627\u0632\u00a0\u0622\u0646\u200c\u0647\u0627 \u0631\u0627 \u062f\u0631\u00a0\u062f\u0646\u0628\u0627\u0644\u0647\u200c\u06cc \u0646\u0647\u0627\u06cc\u06cc \u062e\u0648\u0627\u0647\u06cc\u0645\u200c\u062f\u0627\u0634\u062a. \u0627\u06a9\u0646\u0648\u0646 \u0645\u0633\u0626\u0644\u0647 \u0628\u0647 \u0627\u06cc\u0646\u200c\u0635\u0648\u0631\u062a \u062a\u0628\u062f\u06cc\u0644 \u0645\u06cc\u200c\u0634\u0648\u062f \u06a9\u0647 \u0628\u0627\u06cc\u062f \u062e\u0627\u0646\u0647\u200c\u0647\u0627\u06cc \u067e\u0631\u200c\u0646\u0634\u062f\u0647 \u0631\u0627 \u0637\u0648\u0631\u06cc \u067e\u0631 \u06a9\u0646\u06cc\u0645 \u06a9\u0647 \u062d\u062f\u0627\u0642\u0644 \u062f\u0648 \u0639\u062f\u062f \u0628\u0631\u0627\u0628\u0631 \u062f\u0631 \u062f\u0646\u0628\u0627\u0644\u0647\u200c\u06cc \u0646\u0647\u0627\u06cc\u06cc \u0648\u062c\u0648\u062f \u062f\u0627\u0634\u062a\u0647\u200c\u0628\u0627\u0634\u062f \u0648 Mex <\/span> \u062f\u0646\u0628\u0627\u0644\u0647\u200c\u06cc \u0646\u0647\u0627\u06cc\u06cc \u0628\u06cc\u0634\u06cc\u0646\u0647 \u0634\u0648\u062f. \u0628\u0631\u0627\u06cc \u0627\u06cc\u0646\u200c\u0645\u0633\u0627\u0644\u0647 \u0633\u0647 \u062d\u0627\u0644\u062a \u0632\u06cc\u0631 \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631 \u0645\u06cc\u200c\u06af\u06cc\u0631\u06cc\u0645:<\/p>\n \u062a\u0648\u062c\u0647 \u06a9\u0646\u06cc\u062f \u06a9\u0647 \u0633\u0647 \u062d\u0627\u0644\u062a \u0628\u0627\u0644\u0627 \u0628\u0631\u0627\u06cc \u0632\u0645\u0627\u0646\u06cc \u0628\u0648\u062f\u0646\u062f \u06a9\u0647 \u0647\u06cc\u0686 \u062f\u0648 \u0639\u062f\u062f\u06cc \u0627\u0632 \u0642\u0628\u0644 \u0628\u0631\u0627\u0628\u0631 \u0646\u0628\u0648\u062f\u0646\u062f \u0648 \u062f\u0631 \u0635\u0648\u0631\u062a\u06cc \u06a9\u0647 \u0627\u0632 \u0627\u0628\u062a\u062f\u0627 \u062f\u0648 \u0639\u062f\u062f \u0628\u0631\u0627\u0628\u0631 \u0648\u062c\u0648\u062f \u062f\u0627\u0634\u062a\u060c \u0627\u0632 \u0627\u0639\u062f\u0627\u062f \u06a9\u0645 \u0628\u0647 \u0632\u06cc\u0627\u062f \u067e\u0631 \u0645\u06cc\u200c\u06a9\u0646\u06cc\u0645.<\/p>\n \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc: <\/span> O(n) <\/span><\/p>\n \u06a9\u062f \u0645\u0633\u0626\u0644\u0647\u200c\u06cc \u062e\u0627\u0635 \u0628\u0647 \u0632\u0628\u0627\u0646 ++C<\/a><\/span><\/p>\n \u0686\u0627\u0644\u0634: <\/span>\u0641\u0631\u0636 \u06a9\u0646\u06cc\u062f \u06a9\u0647 \u0628\u0647\u200c\u062c\u0627\u06cc ans[t+1] = a[i]; <\/span> \u062f\u0631 \u06a9\u062f\u060c \u0639\u0628\u0627\u0631\u062a a[t+1] = a[i]; <\/span> \u0646\u0648\u0634\u062a\u0647\u200c\u0634\u062f\u0647\u200c\u200c\u0628\u0627\u0634\u062f \u0648 \u062f\u0646\u0628\u0627\u0644\u0647\u200c\u06cc \u0646\u0647\u0627\u06cc\u06cc\u060c a <\/span> \u0628\u0627\u0634\u062f. \u062f\u0631 \u0627\u06cc\u0646 \u0635\u0648\u0631\u062a \u067e\u0627\u0633\u062e \u0645\u0633\u0627\u0644\u0647 \u0628\u0647 \u0686\u0647 \u0635\u0648\u0631\u062a \u0628\u0648\u062f\u061f<\/p>\n \u0627\u06cc\u062f\u0647\u200c\u06cc \u0633\u0648\u0627\u0644: <\/span>\u0645\u062d\u0645\u062f\u0627\u0645\u06cc\u0646 \u0631\u06cc\u06cc\u0633\u06cc<\/p>\n \u0637\u0631\u0627\u062d\u06cc \u062a\u0633\u062a\u200c\u0647\u0627: <\/span>\u0645\u0647\u062f\u06cc \u0627\u0645\u06cc\u0631\u06cc \u067e\u06cc\u0634\u200c\u0646\u06cc\u0627\u0632: <\/span>\u0622\u0634\u0646\u0627\u06cc\u06cc \u0628\u0627 \u0646\u0638\u0631\u06cc\u0647\u200c \u0627\u0639\u062f\u0627\u062f\u060c \u0622\u0634\u0646\u0627\u06cc\u06cc \u0628\u0627 \u063a\u0631\u0628\u0627\u0644 \u0627\u0631\u0627\u062a\u0633\u062a\u0646\u060c \u0622\u0634\u0646\u0627\u06cc\u06cc \u0628\u0627 \u0645\u0631\u062a\u0628\u200c\u0633\u0627\u0632\u06cc<\/p>\n \u0631\u0627\u0647\u0646\u0645\u0627\u06cc\u06cc: <\/span>\u0633\u0639\u06cc \u06a9\u0646\u06cc\u062f \u0627\u0639\u062f\u0627\u062f \u0627\u0648\u0644 \u062a\u062c\u0632\u06cc\u0647 \u06a9\u0646\u0646\u062f\u0647\u200c\u06cc \u0648\u0631\u0648\u062f\u06cc \u0648 \u062a\u0648\u0627\u0646\u200c\u0647\u0627\u06cc \u0647\u0631\u06a9\u062f\u0627\u0645 \u0631\u0627 \u0628\u0647 \u062f\u0633\u062a \u0622\u0648\u0631\u06cc\u062f.<\/p>\n \u0631\u0627\u0647\u200c\u062d\u0644:<\/span> \u0645\u06cc \u062f\u0627\u0646\u06cc\u0645 \u06a9\u0647 \u0647\u0631 \u0639\u062f\u062f \u0631\u0627 \u0645\u06cc\u200c\u062a\u0648\u0627\u0646 \u0628\u0647 \u0635\u0648\u0631\u062a \u06cc\u06a9 \u0639\u0628\u0627\u0631\u062a \u06cc\u06a9\u062a\u0627 \u0645\u0627\u0646\u0646\u062f p_1 ^ {a_1} * p_2 ^ {a_2} * ... * p_k ^ {a_k} <\/span> \u0646\u0648\u0634\u062a \u06a9\u0647 \u062f\u0631 \u0622\u0646 \u062a\u0645\u0627\u0645 p_i <\/span> \u0647\u0627 \u0627\u0639\u062f\u0627\u062f \u0627\u0648\u0644 \u0628\u0627\u0634\u0646\u062f. \u062f\u0631 \u0627\u06cc\u0646 \u0633\u0648\u0627\u0644\u060c \u0645\u0627 \u0628\u0627\u06cc\u062f \u0628\u0627 \u067e\u0631\u0633\u06cc\u062f\u0646 \u0633\u0648\u0627\u0644\u200c\u0647\u0627\u06cc\u06cc\u060c \u0628\u0647\u200c\u0627\u0632\u0627\u06cc \u0647\u0631 \u0639\u062f\u062f \u0627\u0648\u0644 \u0645\u0627\u0646\u0646\u062f\u00a0 p_i <\/span> \u062f\u0631 \u0628\u0627\u0632\u0647\u200c\u06cc\u00a0 \\left [1, n \\right] <\/span>\u060c \u0628\u0632\u0631\u06af\u200c\u062a\u0631\u06cc\u0646 \u0639\u062f\u062f k <\/span> \u0631\u0627 \u067e\u06cc\u062f\u0627 \u06a9\u0646\u06cc\u0645 \u0628\u0647 \u0637\u0648\u0631\u06cc \u06a9\u0647 p_i ^ {k} | x <\/span>. (\u06cc\u0639\u0646\u06cc p_i ^ {k} <\/span>\u060c \u0639\u062f\u062f x <\/span> \u0631\u0627 \u0639\u0627\u062f \u06a9\u0646\u062f.) \u0628\u0631\u0627\u06cc \u0627\u06cc\u0646\u200c\u06a9\u0627\u0631\u060c \u0627\u0628\u062a\u062f\u0627 \u0628\u0632\u0631\u06af\u200c\u062a\u0631\u06cc\u0646 t <\/span> \u0628\u0647 \u0637\u0648\u0631\u06cc \u06a9\u0647 p_i ^ {t} \\leq n <\/span> \u0631\u0627 \u067e\u06cc\u062f\u0627 \u0645\u06cc\u200c\u06a9\u0646\u06cc\u0645 \u0648 \u0628.\u0645.\u0645 \u0639\u062f\u062f x <\/span> \u0648 p_i ^ {t} <\/span> \u0631\u0627 \u0645\u06cc\u200c\u067e\u0631\u0633\u06cc\u0645. \u067e\u0633 \u0627\u0628\u062a\u062f\u0627 \u0628\u0627 \u06cc\u06a9 \u063a\u0631\u0628\u0627\u0644 \u0627\u0631\u0627\u062a\u0633\u062a\u0646 \u062a\u0645\u0627\u0645 \u0627\u0639\u062f\u0627\u062f \u0627\u0648\u0644 \u062f\u0631 \u0628\u0627\u0632\u0647\u200c\u06cc\u00a0 \\left [1, n \\right] <\/span>\u060c \u0631\u0627 \u067e\u06cc\u062f\u0627 \u0645\u06cc\u200c\u06a9\u0646\u06cc\u0645 \u0648 \u0622\u0646 \u0631\u0627 \u062a\u0627 \u062c\u0627\u06cc\u06cc \u06a9\u0647 \u06a9\u0648\u0686\u06a9\u200c\u062a\u0631 \u0645\u0633\u0627\u0648\u06cc \u0639\u062f\u062f n <\/span> \u0647\u0633\u062a\u060c \u0628\u0647 \u062a\u0648\u0627\u0646 \u0645\u06cc\u200c\u0633\u0627\u0646\u06cc\u0645. \u062f\u0631 \u0646\u0647\u0627\u06cc\u062a \u062a\u0645\u0627\u0645 \u0627\u0639\u062f\u0627\u062f \u0631\u0627 \u06cc\u06a9 \u0628\u0627\u0631 \u0645\u0631\u062a\u0628\u200c\u0633\u0627\u0632\u06cc \u0648 \u0622\u0646\u200c\u0647\u0627 \u0631\u0627 \u0686\u0627\u067e \u0645\u06cc\u200c\u06a9\u0646\u06cc\u0645. \u06a9\u062f \u0645\u0633\u0626\u0644\u0647\u200c\u06cc \u062d\u062f\u0633\u06cc \u0628\u0647 \u0632\u0628\u0627\u0646 ++C<\/a><\/span><\/p>\n \u0686\u0627\u0644\u0634: <\/span>\u0641\u0631\u0636 \u06a9\u0646\u06cc\u062f \u06a9\u0647 \u0686\u0631\u0632\u0647 \u0628\u062a\u0648\u0627\u0646\u062f \u062d\u062f\u0627\u06a9\u062b\u0631 q <\/span> \u0645\u0631\u062a\u0628\u0647 \u067e\u0634\u062a \u0633\u0631 \u0647\u0645 \u062f\u0631\u0648\u063a \u0628\u06af\u0648\u06cc\u062f \u06cc\u0639\u0646\u06cc \u0627\u0632 \u0628\u06cc\u0646 \u0647\u0631 q+1 <\/span> \u067e\u0627\u0633\u062e \u067e\u0634\u062a \u0633\u0631 \u0647\u0645\u060c \u062d\u062f\u0627\u0642\u0644 \u06cc\u06a9\u06cc \u062f\u0631\u0633\u062a \u0628\u0627\u0634\u062f. \u062f\u0631 \u0622\u0646 \u0635\u0648\u0631\u062a \u0645\u0633\u0626\u0644\u0647 \u0628\u0647 \u0686\u0647 \u0635\u0648\u0631\u062a \u062d\u0644 \u0645\u06cc \u0634\u062f\u061f<\/p>\n <\/p>\n \u0627\u06cc\u062f\u0647\u200c\u06cc \u0633\u0648\u0627\u0644: <\/span>\u0645\u0647\u062f\u06cc \u0627\u0645\u06cc\u0631\u06cc<\/p>\n \u0637\u0631\u0627\u062d\u06cc \u062a\u0633\u062a\u200c\u0647\u0627: <\/span>\u0645\u062d\u0645\u062f\u0627\u0645\u06cc\u0646 \u0631\u06cc\u06cc\u0633\u06cc<\/p>\n \u067e\u06cc\u0634\u200c\u0646\u06cc\u0627\u0632: <\/span>\u0622\u0634\u0646\u0627\u06cc\u06cc \u0628\u0627 \u062a\u06a9\u0646\u06cc\u06a9 \u0628\u0631\u0646\u0627\u0645\u0647\u200c\u0646\u0648\u06cc\u0633\u06cc \u067e\u0648\u06cc\u0627\u060c \u0622\u0634\u0646\u0627\u06cc\u06cc \u0628\u0627 \u0646\u0638\u0631\u06cc\u0647\u200c\u0628\u0627\u0632\u06cc\u200c\u0647\u0627\u060c \u0622\u0634\u0646\u0627\u06cc\u06cc \u0628\u0627 \u0645\u0631\u062a\u0628\u200c\u0633\u0627\u0632\u06cc<\/p>\n \u0631\u0627\u0647\u0646\u0645\u0627\u06cc\u06cc:<\/span> \u0633\u0639\u06cc \u06a9\u0646\u06cc\u062f \u0627\u0632 \u062a\u06a9\u0646\u06cc\u06a9 \u0628\u0631\u0646\u0627\u0645\u0647\u200c\u0646\u0648\u06cc\u0633\u06cc \u067e\u0648\u06cc\u0627 \u0627\u0633\u062a\u0641\u0627\u062f\u0647 \u06a9\u0646\u06cc\u062f.<\/p>\n \u0631\u0627\u0647\u200c\u062d\u0644:\u00a0<\/span>\u0622\u0631\u0627\u06cc\u0647\u200c\u06cc \u062f\u0648 \u0628\u0639\u062f\u06cc\u00a0 dp <\/span> \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u062f. \u062f\u0631 \u0627\u06cc\u0646 \u0622\u0631\u0627\u06cc\u0647\u00a0 dp[x][turn] <\/span>\u00a0\u0646\u0634\u0627\u0646\u200c\u062f\u0647\u0646\u062f\u0647\u200c\u06cc \u0627\u06cc\u0646 \u0627\u0633\u062a \u06a9\u0647 \u0627\u06af\u0631\u00a0 x <\/span> \u0642\u0627\u0686 \u067e\u0646\u06cc\u0631\u00a0\u062f\u0627\u0634\u062a\u0647\u200c\u0628\u0627\u0634\u06cc\u0645 \u0648 \u0646\u0641\u0631\u00a0 turn <\/span> \u0634\u0631\u0648\u0639 \u06a9\u0646\u062f\u060c \u0686\u0647 \u06a9\u0633\u06cc \u0622\u062e\u0631\u06cc\u0646 \u0644\u0642\u0645\u0647 \u0631\u0627 \u0628\u0631\u00a0\u0645\u06cc\u200c\u062f\u0627\u0631\u062f.\u00a0\u0645\u06cc\u200c\u062a\u0648\u0627\u0646 \u0628\u0647 \u0633\u0627\u062f\u06af\u06cc \u062f\u06cc\u062f \u06a9\u0647 \u0627\u06af\u0631\u00a0 dp[n][1] <\/span> \u0628\u0631\u0627\u0628\u0631 \u0628\u0627 1 \u0628\u0627\u0634\u062f\u060c \u067e\u0627\u0633\u062e \u0645\u0633\u0626\u0644\u0647 charze \u0627\u0633\u062a \u0648 \u062f\u0631 \u063a\u06cc\u0631 \u0627\u06cc\u0646 \u0635\u0648\u0631\u062a \u067e\u0627\u0633\u062e \u0645\u0633\u0626\u0644\u0647 \u067e\u0634\u0645\u06a9 \u0627\u0633\u062a. \u0627\u0645\u0627 \u0628\u0647\u00a0\u0686\u0647\u200c\u0635\u0648\u0631\u062a\u00a0\u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u00a0<\/span>\u0622\u0631\u0627\u06cc\u0647\u200c\u06cc\u00a0 dp <\/span> \u0631\u0627\u00a0\u0628\u0631\u0648\u0632\u200c\u0631\u0633\u0627\u0646\u06cc \u06a9\u0631\u062f\u061f<\/p>\n \u0628\u0631\u0627\u06cc \u0627\u06cc\u0646\u200c\u06a9\u0627\u0631\u060c \u0627\u0628\u062a\u062f\u0627 \u062c\u0641\u062a \u062f\u0646\u0628\u0627\u0644\u0647\u200c\u0647\u0627\u06cc A <\/span> \u0648 B <\/span> \u0631\u0627 \u0628\u0647 \u0635\u0648\u0631\u062a \u063a\u06cc\u0631\u200c\u0646\u0632\u0648\u0644\u06cc \u0645\u0631\u062a\u0628\u200c\u0633\u0627\u0632\u06cc \u0645\u06cc\u200c\u06a9\u0646\u06cc\u0645. \u0628\u0631\u0627\u06cc \u0645\u062d\u0627\u0633\u0628\u0647\u200c\u06cc dp[x][turn] <\/span> \u0646\u06cc\u0632 \u062f\u0648 \u062d\u0627\u0644\u062a \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631 \u0645\u06cc\u200c\u06af\u06cc\u0631\u06cc\u0645:<\/p>\n \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc:\u00a0<\/span> O(n \\times (|A| + |B|)) <\/span><\/p>\n
\n<\/span><\/p>\n\n
\u0645\u0633\u0626\u0644\u0647\u200c\u06cc \u0627\u0645\u0646\u06cc\u062a\u06cc<\/a><\/h3>\n<\/li>\n<\/ul>\n
\n<\/span><\/p>\n
\n<\/span><\/p>\n\n
\u0645\u0633\u0626\u0644\u0647\u200c\u06cc \u062e\u0627\u0635<\/a><\/h3>\n<\/li>\n<\/ul>\n
\n<\/span><\/p>\n\n
impossible<\/code><\/strong> \u0627\u0633\u062a.<\/li>\n\n
\u0645\u0633\u0626\u0644\u0647\u200c\u06cc \u062d\u062f\u0633\u06cc<\/a><\/h3>\n<\/li>\n<\/ul>\n
\n<\/span><\/p>\n
\n\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc: <\/span> O(n \\sqrt{n} ) <\/span> (\u062a\u0648\u062c\u0647 \u06a9\u0646\u06cc\u062f \u06a9\u0647 \u0627\u06cc\u0646 \u0645\u0633\u0626\u0644\u0647 \u0631\u0627\u0647\u200c\u062d\u0644 O(n log n) <\/span> \u0646\u06cc\u0632 \u062f\u0627\u0631\u062f!)<\/p>\n\n
\u0645\u0633\u0626\u0644\u0647\u200c\u06cc \u0635\u0628\u062d\u0627\u0646\u0647<\/a><\/h3>\n<\/li>\n<\/ul>\n
\n