Подсчитать элементы последовательности которые делятся на 3

[studentus1985]

Сообщение от min@y™

кокой-токой олгоритм-шмолгоритм?

Выше Рома][а наводил
вот он
Код:

r := 0;
cnt := 0;
for i := 1 to n do begin
Inc(r, i); r := r mod 3; if r = 0 then Inc(cnt)
end;
WriteLn(cnt)

[min@y™]

число делится на три если сумма цифр всех разрядов этого числа тоже делится на три

а, ну тогда всё просто. на каждом шаге сворачивать-считать сумму цифр числа, плюсовать к сумме от предыдущего шага и ещё раз свернуть до одной цифры и mod 3 её.

[studentus1985]

Сообщение от min@y™

а, ну тогда всё просто. на каждом шаге сворачивать-считать сумму цифр числа, плюсовать к сумме от предыдущего шага и ещё раз свернуть до одной цифры и mod 3 её.

да, согласен, но не уверен что весь интервал можно просчитать за 1 сек.(условия задачи)поэтому спрашиваю, может кто посоветует что нибудь побыстрее

[Poma][a]

Проверил, из 11 елементов последовательности которые есть в первом посте на 3 делятся только 4, но алгоритм говорит что их есть 7!

1(-),12(+),123(6)(+),1234(-),12345(15)(+),123456(+),1234567(-), 12345678(36+),123456789(45)(+),1234 5678910(-),1234 567891011(66)(+)...
Где ошибка?
Ответ 7

[Аватар]

Решатели, обратите внимание на последовательность. В каждой тройке элементов начиная с 1-го на 3 делится 2-ой и 3-ий элемент и есть длина последовательности. Сколько на три делится?

[studentus1985]

Сообщение от Poma][a

1(-),12(+),123(6)(+),1234(-),12345(15)(+),123456(+),1234567(-), 12345678(36+),123456789(45)(+),1234 5678910(-),1234 567891011(66)(+)...
Где ошибка?
Ответ 7

Прошу прощения, перепроверил, действительно работает, но пока не разобрался как именно, все таки я думал будет код пообьемней, большое вам спасибо

[Аватар]

А так

Count:=(n div 3)*2;
if n mod 3=2 then Inc(Count);

[Poma][a]

Решатели, обратите внимание на последовательность. В каждой тройке элементов начиная с 1-го на 3 делится 2-ой и 3-ий элемент и есть длина последовательности. Сколько на три делится?

Мда.. Не заметил.. Спасибо..
Тогда (n+1) div 3 + n div 3?

[studentus1985]

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

Решатели, обратите внимание на последовательность. В каждой тройке элементов начиная с 1-го на 3 делится 2-ой и 3-ий элемент и есть длина последовательности. Сколько на три делится?

наверное самый быстрый вариант, спасибо

[Аватар]

Тогда (n+1) div 3 + n div 3?

Оно, у тебя еще короче