Монеты - 2

Посчитаем количество монет, которые взял волшебник. Это значение равно 1+2+3+...+(n-2)+(n-1)=(1+n-1)*(n-1)/2=n*(n-1)/2. Здесь мы использовали формулу суммы элементов арифметической прогрессии: s = (a₁+a_n)*n/2, где a₁ и a_n - первый и последний элементы прогрессии, а n - количество элементов. Поскольку все нефальшивые монеты весят w граммов, то в том случае, когда фальшивых монет нет, общий вес составил бы w*n*(n-1)/2 граммов. Отнимем теперь от этого веса значение p суммарного веса монет, которые взял волшебник. Тогда у нас получится значение k=w*n*(n-1)/2-p. Если это значение равно нулю, то среди отобранных монет нет фальшивых (т.е. фальшивые в n-й корзине), в противном случае мы получим положительное число, превосходящее в d раз количество фальшивых монет среди отобранных. Мы знаем, что количество фальшивых монет равно номеру корзины с фальшивыми монетами, поэтому этот номер равен k/d, что и требовалось определить.

Алгоритм, реализующий вышеизложенные идеи, можно представить следующим образом:

  read(n,w,d,p)
  k = w*n*(n-1)/2-p
  if(k>0) write(k/d) else write(n)

[Обсуждение] [Все попытки] [Задача]