Номер 27 из ЕГЭ по информатике 2017 года

Давайте сразу договоримся:

  1. На смысл программы (точнее на его отсутствие) не обращать внимания!
  2. Программа имеет только СТАНДАРТНЫЙ ввод/вывод (то есть в консоль).

Задание таково: Даётся последовательность из N (1 <= N <= 1000) различных чисел (0 <= a[i] <= 10000). Требуется написать программу, выводящую количество пар чисел в этой последовательности, произведение элементов которых делится на 38. Парами считаются НЕ только соседние числа. Например “Если a[5]*a[25] делится на 38, то к результирующей переменной прибавить 1”.

Балы начисляются так:

  1. 2 балла - Программа есть, и она работает.
  2. 3 балла - Пункт 1 + Оптимизация по времени (Не более 1 секунды)
  3. 4 балла - Пункт 2 + Оптимизация по памяти (На все переменные не более 1 Кбайт)

У меня такой вопрос. Как можно оптимизировать программу по памяти, если на каждое число будет минимум 2 байта, а это уже почти 2 Кбайт (На весь массив), и плюс ещё как минимум одна переменная под N (И она же для накопления результата).

P.S. Программу то я написал, и даже по времени оптимизировал, уж не знаю как, но вроде нормально):joy: /// program n27_1;

var
	a: array of word;
	n: cardinal;

begin

	ReadLn (n);
	a := new word[n];
	
	for var i := 0 to n - 1 do
		ReadLn (a[i]);
	
	Sort (a);
	
	n := 0;
	
	// Подсчёт количества.
	for var i := a.Length - 1 downto 1 do
		for var j := i - 1 downto 0 do
			if ((a[i] * a[j]) < 38) then break
				else if (((a[i] * a[j]) mod 38) = 0) then Inc (n);
				
	WriteLn (n);
	
	ReadLn ();

end.

///

Если что пар может быть 1000000, если N = 1000!

а на какой машине? :slight_smile:

На машине проверяльщика очевидно :smile:

Что Вам мешает в массиве хранить не сами элементы, а остатки от деления на 38?

2 лайка

Олимпиадные задачи для подготовки перед ЕГЭ не помешают. Eaa всё правильно говорит, сделайте массив на 38 элементов и сохраняйте число остатков от деления на 38, а дальше всё просто. Спокойно уложитесь в 1Кб.

Критерием эффективности по памяти является то, что мы не храним все данные в массиве, а последовательно считываем. Как только начинаем хранить - сразу -1 балл

Длина массива(38) будет одинаковой для любого количества входных данных. Это эффективно.

Да, мы же храним не все данные, а только 38

Да хрен его знает, на чём они там проверяют XD

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

Тут нужно использовать такое свойство: (ab)%38=((a%38)(b%38))%38.

да они ни на чем не проверяют)) просто если видят двойной цикл, в котором будут перебираться все пары - то балл снимут

Могу предложить такое решение данной задачи. 1 цикл, 4 переменных для вычислений (div1 на самом деле не нужна, для наглядности оставил)

[code]begin var n := readInteger; var res := 0; //результат var div38 := 0; //кол-во уже считанных элементов, которые делятся на 38 var div19 := 0; //кол-во уже считанных элементов, которые делятся на 19 var div2 := 0; //кол-во уже считанных элементов, которые делятся на 2 var div1 := 0; //кол-во уже считанных элементов (любых)

for var i := 1 to n do begin var el := readInteger; if el mod 38 = 0 then begin //если число делится на 38, то оно образует нужную пару со всеми числами res += div1; div1 += 1; div2 += 1; div19 += 1; div38 += 1; end else if el mod 19 = 0 then begin //если число делится на 19, то оно образует нужную пару со всеми четными числами res += div2; div1 += 1; div19 += 1; end else begin
res += div38; //другие числа образуют нужные пары с 38 if el mod 2 = 0 then begin //другие числа образуют нужные пары с 19, если они четные res += div19; div2 += 1; end; div1 += 1; end; end;

println(res); end.

{ 20 2 4 6 8 10 12 14 16 18 19 20 22 24 26 27 28 29 30 31 32 16 }[/code]

На эту тему, изрядно проще выглядит :slight_smile:Сначала написал, потом увидел, что уже что-то похожее есть, а выкидывать жалко =D Условия сохранены: функция использует каждый элемент последовательности только один раз. Так проще, ибо был написан затем тест с генерацией случайных наборов для тестирования полученной формулы. Не руками же тысячу значений 100000 раз вводить. Для тех, кто не умеет сие читать: операция % - это mod в Паскале, && - and, == - =. += тут не сильно тривиальное: используется автоматическое преобразование boolean -> integer (true->1, false->0)

function calc_count_optimized(<тут массив целых чисел> v, int div1, int div2): integer
// v - входной параметр алгоритма, а не место сбора элементов. не путаем.
{
    int div1_cnt = 0, div2_cnt = 0, div12_cnt = 0; //те самые три переменные с количеством
    for(int t: v) //заменить на ReadInteger, или кто там как хочет
    {
        div1_cnt += (t % div1 == 0);
        div2_cnt += (t % div2 == 0);
        div12_cnt += (t % div1 == 0) && (t % div2 == 0);
    }
    result = (div1_cnt - div12_cnt) * (div2_cnt - div12_cnt) + 
        div12_cnt * (v.size() - 1) - (div12_cnt * (div12_cnt - 1))/2;
    //v.size считать текущей длиной последовательности. Тут считается число пар, в 
    //которых нет самостоятельных делителей требуемого числа - до плюса, 
    //в которых есть - после плюса. Над второй формулой подумать придется =3
} 

Написано на дикой смазке из C-подобных языков и Pascal, т.к. Паскаль я уже не помню, а постить сюда С++ - моветон :slight_smile: Решение подходит для любого числа, имеющего ровно два простых делителя(т.е. 14, 21, 35, и т. д.)

Почему не использовать оператор ReadArrInteger для ввода одномерного массива? Это же возможности PascalABC.Net!

Потому что если мы будем сразу считывать все данные в массив, это будет неэффективно по памяти, и мы потеряем 1 балл. Нужно считывать поэлементно, чтобы не хранить сразу все в памяти

У меня стойкое ощущение, что эти задачи придумывают люди, застрявшие своим мышлением в 80-х годах прошлого века, когда байт был на вес золота. Уже в бытовых холодильниках чипы памяти имеют объёмы в десятки и сотни мегабайт, а они все пытаются приучить людей думать о том, как искорячившись, выгадать килобайт.

Сильное заявление.

1 лайк

Можно ReadSeqInteger.

У меня тоже. На мой взгляд, и решение этих задач только уродует стиль программирования