На этом форуме отвечают на конкретные вопросы. Фраза «я не понимаю, как решать» — это не вопрос. На вопрос «как решить задачу №X» вас отошлют к материалам сайта kpolyakov.spb.ru. За бессвязный поток слов и неспособность формулировать свои мысли — бан.

Если у вас не сходится ответ на какую-то задачу, пожалуйста сразу представляйте свое «правильное» решение.
Программы "заворачивайте" в тэг [pre2]...[/pre2], при этом сохраняются все отступы и применяется моноширинный шрифт. Если у вас используется сочетание "[i]" для обозначения элемента массива или строки, ставьте пробел после открывающей скобки. Иначе система выделит все дальнейшее курсивом.

Для регистрации на форуме щелкните по ссылке «Вход-регистрация» вверху страницы. В открывшееся окошко «ник» введите свою фамилию на русском языке (например, Иванов). В окошко «пароль» введите придуманный вами пароль, состоящий из латинских букв и цифр. Поставьте галочку в окошке «зарегистрироваться, я новый участник» и нажмите кнопку «ОК».

АвторСообщение



Сообщение: 18
ссылка на сообщение  Отправлено: 14.06.21 13:16. Заголовок: № 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), получается что числа неподряд идут.

Спасибо: 0 
ПрофильЦитата Ответить
Ответов - 7 [только новые]







Сообщение: 1
ссылка на сообщение  Отправлено: 14.06.21 16:28. Заголовок: Alex Danov - Автор задачи


Цитирую:
Входные данные. ... в первой строке количество групп чисел N (N ≤ 100000). В каждой из следующих N строк ... записан сначала размер группы K (N ≤ 20), а затем – K натуральных чисел, не превышающих 1000.

> либо 2. из 4 1 3 5 6 берем только НЕпрерывную последовательность, но это в условии не сказано.
Верно. Этого в условии нет. Берем ЛЮБЫЕ числа сумма которых четна

Спасибо: 1 
ПрофильЦитата Ответить



Сообщение: 19
ссылка на сообщение  Отправлено: 15.06.21 14:03. Заголовок: Danov пишет: Цитиру..


Danov пишет:

 цитата:
Цитирую:

Спасибо, недочитал.
Я почему-то собирался искать четную сумму всех возможных наборов, это интереснее.

Спасибо: 0 
ПрофильЦитата Ответить



Не зарегистрирован
ссылка на сообщение  Отправлено: 17.06.21 12:42. Заголовок: Пример входного файла


Если выбрать так:
1: 4 3 5 6 = 18
2: 2 6 = 8
3: 2 8 = 10
4: 12 = 12
то сумма=48 и не делится на 5. В примере ответ 38, почему нельзя использовать приведённый выше выбор?

Спасибо: 0 
Цитата Ответить





Сообщение: 2
ссылка на сообщение  Отправлено: 17.06.21 21:47. Заголовок: Цитирую: Входные дан..


Цитирую:
Входные данные. ... в первой строке количество групп чисел N (N ≤ 100000). В каждой из следующих N строк ... записан сначала размер группы K (N ≤ 20), а затем – K натуральных чисел, не превышающих 1000.

у вас в первой строке 4 3 5 6 из строки где было "4 1 3 5 6". 4 это количество "1 3 5 6" )))
внимательность повышается многократным перечитыванием!

Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 20
ссылка на сообщение  Отправлено: 20.06.21 16:48. Заголовок: Danov пишет: ок .....


Danov пишет:

 цитата:
ок ... записан сначала размер группы K (N ≤ 20), а затем – K натуральных чисел, не превышающих 1000


Вот тут непонятно про К. Если имеется в виду, что
"...сначала размер группы K (К ≤ 20), а ..." то в строке не более 20 чисел. Тогда можно попробовать разобрать на суммы перебором всех сочетаний этих чисел.
Вообще задача новая, интересная и, самое главное, ее могут дать в ЕГЭ. Решений я не нашел, предлагаю посмотреть мое.

Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 21
ссылка на сообщение  Отправлено: 20.06.21 16:52. Заголовок: var summax, m..


 

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.



Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 22
ссылка на сообщение  Отправлено: 20.06.21 17:00. Заголовок: Этот код печатает ..


Этот код печатает
=== 134271400 === 204
ответ 134271196
5.829
За 5 секунд 100000 наборов это вроде нормально.
Идея известная, находим максимальную сумму и, если надо, вычитаем d_min. Само решение получилось длинное, и еще и с полным перебором, но как сократить не знаю.
Если кто поправит, буду благодарен
ЗЫ. вот тут "findSubSum(Copy(valueString,2,length(..." пробовал срезом передавать, выдает ошибку почему-то.
ЗЗЫ. Задание 67 из сборника. Можно было обойтись анализом четных -нечетных.

Спасибо: 0 
ПрофильЦитата Ответить
Ответ:
1 2 3 4 5 6 7 8 9
видео с youtube.com картинка из интернета картинка с компьютера ссылка файл с компьютера русская клавиатура транслитератор  цитата  кавычки оффтопик свернутый текст

показывать это сообщение только модераторам
не делать ссылки активными
Имя, пароль:      зарегистрироваться    
Тему читают:
- участник сейчас на форуме
- участник вне форума
Все даты в формате GMT  3 час. Хитов сегодня: 1970
Права: смайлы да, картинки да, шрифты нет, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет