Отправлено: 09.03.22 19:06. Заголовок: 27 задание 77 номер

(Е. Драчева) Набор данных состоит из групп натуральных чисел, каждая группа записана в отдельной строке. В любой группе содержится не менее двух чисел. Из каждой группы выбрали два числа и нашли их наименьшее общее краткое (НОК). Затем все полученные таким образом значения НОК сложили. Определите наибольшую сумму, кратную числу 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

 Отправлено: 24.03.22 19:53. Заголовок: m0rk0vka пишет: Из п..

m0rk0vka пишет:

цитата:

Из первой группы берем числа 2 и 8: НОК(2,8) = 8

Первое число в каждой строке - это количество чисел в группе. А дальше идут сами числа, входящие в группу.

 Отправлено: 15.04.22 16:23. Заголовок: Вопрос по ответу в файле 27-77b?

Протестировал свое решение на примере из задания и файле "27-77a.txt" все совпало.
А для файла "27-77b.txt" получился ответ 1254402250 вместо 1254402115.

В чем может быть ошибка не могу понять?

 
 ## 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; 
 

 Отправлено: 15.04.22 16:55. Заголовок: Первое замечание по ..

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

 Отправлено: 15.04.22 20:50. Заголовок: Ответ на замечание...

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

 Отправлено: 15.04.22 22:30. Заголовок: ivackov.sergey пишет..

ivackov.sergey пишет:

цитата:

а он у меня исключается из расчетов. НОКи - алгоритм рассчитывает корректно!

Согласен.
Вот правильное решение (только цикл):

  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;  
 

 Отправлено: 15.04.22 22:55. Заголовок: Вот более аккуратная..

Вот более аккуратная версия:

 ## 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; 
 

 Отправлено: 17.04.22 20:37. Заголовок: Новая версия...

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

 Отправлено: 21.04.22 13:31. Заголовок: Здравствуйте, Конста..

Здравствуйте, Константин Юрьевич. Я понимаю, что вы уже опубликовали хорошее и красивое решение, но еще до того, как его увидел, пришло другое решение, как по мне чуть более понятное школьникам.

 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.

И проблема такая же, файл А решает, а в файле В 1254402250. Не могли бы вы подсказать, что не так?

 Отправлено: 21.04.22 13:48. Заголовок: Мне не совсем ясно, ..

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