Количество "единичек"

[boomeer]

Ограничение по времени 2 секунды) мое решение вроде должно пройти... еще не закодил. Для меня решить математимически как то легче, чем закодить. Свое еще не знаю как закодится

[Obey-Kun]

i++ медленнеей, чем --i. А ещё, isOnes лучше сделать inline, не будет тратиться время на вызов функции.

[NiCola999]

при оптимизации компилятор сам решает ставить inline или нет, и если даже там оно стоит, компилятор его уберет, если посчитает его не нужным

[Obey-Kun]

Это разве не зависит от флагов оптимизации?

[NiCola999]

зависит, но зачем их трогать

[Акоб]

для автора- в 100 21 а не 20

[Obey-Kun]

Ты это ещё гентушникам скажи
Я к тому, что у кого-то он сам доставит, у кого-то нет, так что надёжней тут поставить.

[Serge_Bliznykov]

решение практически "в лоб"
полный перебор на моём древней компьютере ~3 с половиной минуты.
для N = 999999999
количество чисел с единичкой: 612 579 511
(правильно считает или нет - не могу сказать, вручную долго пересчитывать ))
вот собственно код перебора:

function OneInNumber(N : longint; var AddCount : longint) : boolean;
begin
  OneInNumber := false;
  AddCount := 1;
  while N > 0 do begin
    if (N mod 10 ) = 1 then begin
      OneInNumber := true;
      Exit
    end;
    AddCount := AddCount * 10;
    N := N div 10;
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var i,count, N, addCnt : longint;
begin
  N := 999999999;
  count := 0;
  i := 1;
  while i<=N do begin
    if OneInNumber(i, addCnt) then
       begin
         if (i+addCnt)<=N
            then inc(count, addCnt)
            else inc(count, N-i+1);
         inc(i, addCnt);
       end
       else inc(i);
  end;
  Edit1.Text := IntToStr(count);
end;

p.s. при N = 50 чисел с единичкой всё таки 14, а не 15, как тут предполагалось..


_______________
по хорошему, этот мой пост можно было удалить, т.к. ничего нового он не говорит,
да и тема C/C++ - чего я тут выперся со своим Паскалем, непонятно...
Ну ладно, пусть остаётся, может в толпе других его никто и не заметит..

[Smitt&Wesson]

Вот "лобовое" решение с использованием string.

int a = 100000000;
int s = 0;
AnsiString str;
for(int i=0; i<a; i++)
  {
  str = IntToStr(i);
  for(int j=1; j<=str.Length(); j++)
    {
    if(str[j] == '1') s++;
    }
  }
Button3->Caption = s;

Этот расчёт мой комп делает за 100 секунд.
Результат 80000000.

Для 100 - результат 20.
Для 200 - 140.
Для 1000 - 300.
Для 10000 - 4000.

[NiCola999]

при N = 50 чисел с единичкой всё таки 14, а не 15, как тут предполагалось...

если считать общее кол-во единиц от 1 до 50, то их 15. Но как оказалось надо считать числа в которых есть хотя бы одна 1. Тогда да их 14