Форум » Обработка числовых последовательностей » № 4193 А. Богданов постановка » Ответить
№ 4193 А. Богданов постановка
глебарзамас: (№ 4193) (А. Богданов) Набор данных состоит из групп натуральных чисел, каждая группа записана в отдельной строке. В любой группе содержится не менее двух чисел. Из каждой группы нужно выбрать одно или несколько чисел так чтобы их сумма была чётной. Какую максимальную сумму выбранных чисел, не кратную 5, можно получить? Пример входного файла: 4 4 1 3 5 6 2 3 6 2 5 8 2 7 12 Из каждой строки выбираем числа с четной суммой (3+5+6)+(6)+(8)+(12)=40. Чтобы сумма не делилась на 5, можно уменьшить её на 2, заменив в первой группе 3 на 1. Ответ: 40-2=38. Постановка вопроса непонятна. Либо: 1. 4 1 3 5 6 - ищем сумму всех подпоследовательностей в группе 4 + (3+5+6) + (1+3) +6 + (3+5) + ... = равно четному; допустимы наборы разной длины от 1 до 5 ? Нужна максимальная четная сумма из всех возможных наборов? либо 2. из 4 1 3 5 6 берем только НЕпрерывную последовательность, но это в условии не сказано. В примере для первой группы 4 1 3 5 6 взяли (3+5+6), хотя есть еще четная сумма 4+(3+5+6). Вроде как нужно непрерывную. Тогда нельзя брать (1+..+5+6), получается что числа неподряд идут.
Ответов - 7
Danov: Цитирую: Входные данные. ... в первой строке количество групп чисел N (N ≤ 100000). В каждой из следующих N строк ... записан сначала размер группы K (N ≤ 20), а затем – K натуральных чисел, не превышающих 1000. > либо 2. из 4 1 3 5 6 берем только НЕпрерывную последовательность, но это в условии не сказано. Верно. Этого в условии нет. Берем ЛЮБЫЕ числа сумма которых четна
глебарзамас: Danov пишет: Цитирую: Спасибо, недочитал. Я почему-то собирался искать четную сумму всех возможных наборов, это интереснее.
Анонимный участник: Если выбрать так: 1: 4 3 5 6 = 18 2: 2 6 = 8 3: 2 8 = 10 4: 12 = 12 то сумма=48 и не делится на 5. В примере ответ 38, почему нельзя использовать приведённый выше выбор?
Danov: Цитирую: Входные данные. ... в первой строке количество групп чисел N (N ≤ 100000). В каждой из следующих N строк ... записан сначала размер группы K (N ≤ 20), а затем – K натуральных чисел, не превышающих 1000. у вас в первой строке 4 3 5 6 из строки где было "4 1 3 5 6". 4 это количество "1 3 5 6" ))) внимательность повышается многократным перечитыванием!
глебарзамас: Danov пишет: ок ... записан сначала размер группы K (N ≤ 20), а затем – K натуральных чисел, не превышающих 1000 Вот тут непонятно про К. Если имеется в виду, что "...сначала размер группы K (К ≤ 20), а ..." то в строке не более 20 чисел. Тогда можно попробовать разобрать на суммы перебором всех сочетаний этих чисел. Вообще задача новая, интересная и, самое главное, ее могут дать в ЕГЭ. Решений я не нашел, предлагаю посмотреть мое.
глебарзамас: [pre2] var summax, max1, max2, d_min, k :integer; mass: array[1..20] of integer; sa :string; function findSubSum(valueString, suffix : string) : string; var i,j,nn,m,x:integer; begin if(valueString = '') then begin if(suffix <> '') then begin //suffix - полученная подпоследовательность m := 0; for i:= 1 to k do begin if pos(sa[ i ], suffix) > 0 then begin nn := pos(sa[ i ], sa); m := m + mass[nn]; end; end; if m mod 2 = 0 then if m > max1 then begin max1 := m end else if (m > max2) and (max1 <> m) and ((max1 - m) mod 5 <> 0) then max2 := m; end; exit; end; findSubSum(Copy(valueString,2,length(valueString)-1 ), suffix + valueString[1]); findSubSum(Copy(valueString,2,length(valueString)-1 ), suffix); end; var i,j,n,m:integer; t:text; var value :string; begin assign(t,'27-67b.txt'); reset(t); readln(t,n); sa := 'abcdefghijklmnopqrst'; summax := 0; d_min := 10001; for i:= 1 to n do begin read(t,k); for j:= 1 to k do read(t,mass[j]); readln(t); value:= ''; for m:=1 to k do value := value + sa[m]; max1 := 0; max2 := 0; findSubSum(value, ''); summax := summax + max1; if (max2 > 0) and ((max1 - max2) < d_min) then d_min := (max1 - max2); end; println(' === ',summax, ' === ', d_min); if summax mod 5 = 0 then println(' ответ ',summax - d_min) else println(' ответ ',summax); println(milliseconds / 1000); end. [/pre2]
глебарзамас: Этот код печатает === 134271400 === 204 ответ 134271196 5.829 За 5 секунд 100000 наборов это вроде нормально. Идея известная, находим максимальную сумму и, если надо, вычитаем d_min. Само решение получилось длинное, и еще и с полным перебором, но как сократить не знаю. Если кто поправит, буду благодарен ЗЫ. вот тут "findSubSum(Copy(valueString,2,length(..." пробовал срезом передавать, выдает ошибку почему-то. ЗЗЫ. Задание 67 из сборника. Можно было обойтись анализом четных -нечетных.
полная версия страницы