A Stack of Gold

Question

https://open.kattis.com/problems/astackofgoldopen.kattis.com

Solution

Idea

This problem is a bit interesting. The solution is implemented in $O(N)$. Here we just assume all the stacks are tungsten. And then we loop through every stack (cuz we take different number of coins from every stack). And during each iteration, we add the number of coins times the difference between the weight of gold coins and tungsten coins. If the weight is equal to the input weight. Then this stack is what we want.

Code

https://github.com/mendax1234/Coding-Problems/blob/main/kattis/astackofgold/astackofgold.c

#include <stdio.h>

#define TUNGSTEN_W 29260
#define DIFF 110

int main()
{
  long w;
  long s;
  long c;
  long init_w;
  long tar = 0;

  scanf("%ld %ld", &w, &s);
  c = s * (s + 1) / 2;
  init_w = TUNGSTEN_W * c;
  
  for (long i = 1; i <= s; i += 1)
  {
    long cur_w = init_w + DIFF * i;
    if (cur_w == w)
    {
      tar = i;
      break;
    }
  }

  printf("%ld\n", tar);
}