Форум » Обработка числовых последовательностей » 27 задание 77 номер » Ответить

27 задание 77 номер

m0rk0vka: (Е. Драчева) Набор данных состоит из групп натуральных чисел, каждая группа записана в отдельной строке. В любой группе содержится не менее двух чисел. Из каждой группы выбрали два числа и нашли их наименьшее общее краткое (НОК). Затем все полученные таким образом значения НОК сложили. Определите наибольшую сумму, кратную числу 5 или 7 (но не одновременно двум этим числам), которая может быть получена таким образом. Входные данные: Даны два входных файла: файл A (27-77a.txt) и файл B (27-77b.txt), каждый из которых содержит в первой строке количество чисел N (2 ≤ N ≤ 100000). В каждой из следующих N строк файлов записан сначала размер группы K (N <= 10), а затем – K натуральных чисел, не превышающих 500. Пример входного файла: 4 2 8 6 3 2 7 8 2 6 5 4 7 3 8 6 Для указанных входных данных значения НОК для первой группы – 24; для второй группы – 14, 8, 56; для третьей группы – 30, для четвёртой группы – 6, 21, 24, 24, 42, 56. Значением искомой суммы должно быть число 110 (24+14+30+42). Задача 77 из файла ege27 Поясните, пожалуйста, пример: Из первой группы берем числа 2 и 8: НОК(2,8) = 8 Из 2-й: НОК(7,8) = 56 Из 3-й: НОК(6,5) = 30 Из 4-й: НОК(7,8) = 56 8 + 56 + 30 + 56 = 150 делится на 5 и не делится на 7. Почему тут ответ 110 и по-какому принципу выписывается кол-во НОК в примере, для первой группы одно число - 24, для второй группы 3 числа, для третьей опять одно, я предполагаю, что это просто для примера, но тогда остается вопрос про ответ 110

Ответов - 9

Поляков: m0rk0vka пишет: Из первой группы берем числа 2 и 8: НОК(2,8) = 8 Первое число в каждой строке - это количество чисел в группе. А дальше идут сами числа, входящие в группу.

ivackov.sergey: Протестировал свое решение на примере из задания и файле "27-77a.txt" все совпало. А для файла "27-77b.txt" получился ответ 1254402250 вместо 1254402115. В чем может быть ошибка не могу понять? [pre2] ## uses school; {Функция попарных сум из двух списков} function DvaLista(X1, X2: list<integer>): List<integer>; begin var G := new List<integer>; for var i := 0 to X1.Count - 1 do for var j := 0 to X2.Count - 1 do G.Add(X1[ i] + X2[j]); result := G; end; Assign(input, '27-77b.txt'); var n := ReadlnInteger; var L := new List<List<integer>>; //В каждой строке набор НОКов var L2 := new List<integer>; {Формируем для каждой стоки НОКи} for var i := 1 to n do begin var s := ReadlnString; var a := s.ToWords; for var x := 1 to a.Length - 2 do for var y := x + 1 to a.Length - 1 do L2.Add(LCM(a[x].ToInteger, a[y].ToInteger)); L.Add(L2[:]); L2.Clear; end; //L.Println; {Обнуляем словарь} var base := 35; var D := new Dictionary<integer, integer>; for var i := 0 to base - 1 do D.Add(i, 0); L2 := L[0][:]; for var i := 1 to L.Count - 1 do begin L2 := DvaLista(L2, L[ i][:]); for var j := 0 to L2.Count - 1 do begin var key := L2[j] mod base; if not D.ContainsKey(key) then begin D.Add(key, L2[j]) end else begin if D[key] <= L2[j] then begin D.Remove(key); D.Add(key, L2[j]); end; end; end; //Из Словаря в список обновляем L2.clear; for var k := 0 to D.Count - 1 do L2.Add(D[k]); //L2.Println; end; var mx := -1; for var k := 0 to D.Count - 1 do if (d[k] mod 5 = 0) xor (d[k] mod 7 = 0) then mx := max(d[k], mx); mx.Println; [/pre2]

Поляков: Первое замечание по чтению - вы считаете первое число в строке одним из чисел массива. А это количество следующих далее чисел массива.


ivackov.sergey: "количество следующих" - это '0' элемент массива, а он у меня исключается из расчетов. НОКи - алгоритм рассчитывает корректно!

Поляков: ivackov.sergey пишет: а он у меня исключается из расчетов. НОКи - алгоритм рассчитывает корректно! Согласен. Вот правильное решение (только цикл):[pre2] for var i := 1 to L.Count - 1 do begin L2 := DvaLista(L2, L[ i][:]); L2.Sort; D.Clear; for var j := 0 to L2.Count - 1 do begin var key := L2[j] mod base; D[key] := L2[j]; end; //Из Словаря в список обновляем L2.Clear; for var k := 0 to D.Count - 1 do if D.ContainsKey(k) then L2.Add(D[k]); //L2.Println; end; [/pre2]

Поляков: Вот более аккуратная версия:[pre2] ## uses school; {Вычисление попарных сум из двух списков} function CombineLists(L1, L2: list<integer>): List<integer>; begin var Res := new List<integer>; foreach var i in L1 do foreach var j in L2 do Res.Add(i + j); Result := Res; end; Assign(input, '27-77b.txt'); var N := ReadlnInteger; var base := 35; var D := new Dictionary<integer, integer>; var L := new List<integer>; L.Add(0); var HOK := new List<integer>; for var i := 1 to N do begin var data := ReadlnString.ToIntegers[1:]; HOK.Clear; for var j := 0 to data.Length - 2 do for var k := j + 1 to data.Length - 1 do HOK.Add( LCM(data[j], data[k]) ); L := CombineLists( L, HOK ); L.Sort; D.Clear; foreach var x in L do D[x mod base] := x; L.Clear; foreach var p in D do L.Add( p.Value ); end; L.Where( x -> (x mod 5 = 0) xor (x mod 7 = 0) ).Max.Println; [/pre2]

ivackov.sergey: Спасибо за красивое и более компактное решение!

Герман: Здравствуйте, Константин Юрьевич. Я понимаю, что вы уже опубликовали хорошее и красивое решение, но еще до того, как его увидел, пришло другое решение, как по мне чуть более понятное школьникам. [pre2] type arr=array[1..10] of integer; arr1=array[1..45] of integer; arr2=array[1..10000] of arr1; var i,j,k,x,y,sum,max,max2,min,maxi,maxj:integer; a:arr; b:arr2; c:arr1; f:text; function nok(n,m:integer):integer; var o:integer; begin o:=n*m; while n <> m do if n > m then n:=n-m else m:=m-n; nok:=round(o/n); end; begin assign (f, 'C:\Users\e.kochura\Desktop\27-77b.txt'); reset(f); for i:=1 to 10000 do begin read(f,x); max:=0; for j:=1 to x do read(f,a[j]); for y:=1 to 45 do c[y]:=0; y:=1; for j:=1 to x do for k:=j+1 to x do begin c[y] := nok(a[j],a[k]); y:=y+1; end; b[ i]:=c; end; sum:=0; for i:=1 to 10000 do begin max:=0; for j:=1 to 45 do if b[ i][j] > max then max:=b[ i][j]; sum:=sum+max; end; writeln(sum); while not (((sum mod 5 = 0) and (sum mod 7 <> 0)) or ((sum mod 5 <> 0) and (sum mod 7 = 0))) do begin sum:=0; min:=maxint; for i:=1 to 10000 do begin max:=0; max2:=0; for j:=1 to 45 do if b[ i][j] > max then begin max2:=max; max:=b[ i][j]; maxj:=j; end; if (max-max2)<min then begin min:=max-max2; maxi:=i; end; sum:=sum+max; end; sum:=sum-min; b[maxi][maxj]:=0; end; writeln(sum); end.[/pre2]И проблема такая же, файл А решает, а в файле В 1254402250. Не могли бы вы подсказать, что не так?

Поляков: Мне не совсем ясно, как работает последний цикл while, что там происходит (вернее, зачем). Как вы доказываете, что искомая комбинация НОД не будет пропущена?



полная версия страницы