Simulate how much change you receive in each transaction.

The minimum number of \(1000\)-yen bill to pay for \(A\)-yen purchase is \(\left\lceil\frac{A}{1000}\right\rceil\), so the change will be \(1000\times \left\lceil\frac{A}{1000}\right\rceil -A\).

When the change is \(X\) yen (\(X<1000\)), the change contains \(\left\lfloor\frac{X}{100}\right\rfloor\) \(100\)-yen coins, \(\left\lfloor\frac{X}{10}\right\rfloor\bmod 10\) \(10\)-yen coins, and \((X \bmod 10)\) \(1\)-yen coins.

Sample code (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n;
  cin >> n;

  int c1=0,c10=0,c100=0;
  for(int i=0;i<n;i++){
    int a;
    cin >> a;
    int x=(a+999)/1000*1000-a;
    c100+=x/100;
    c10+=x/10%10;
    c1+=x%10;
  }
  cout << c1 << ' ' << c10 << ' ' << c100 << endl;
}

In Python, the remainder is always non-negative, so we can find the change as (-a)%1000.

Sample code (Python)

N=int(input())
A=list(map(int,input().split()))
c100,c10,c1=0,0,0
for a in A:
  x=(-a)%1000
  c100+=x//100
  c10+=x//10%10
  c1+=x%10

print(c1,c10,c100)