お釣りをいくら受け取るかを順にシミュレーションします。

\(A\) 円の買い物に対して出す最小の \(1000\) 円紙幣の枚数は \(\left\lceil\frac{A}{1000}\right\rceil\) であるため、そのときのお釣りは\(1000\times \left\lceil\frac{A}{1000}\right\rceil -A\) 円になります。

お釣りが \(X\) 円(\(X<1000\))であるとき、お釣りに含まれる \(100\) 円硬貨の数は \(\left\lfloor\frac{X}{100}\right\rfloor\) 、\(10\) 円硬貨の数は \(\left\lfloor\frac{X}{10}\right\rfloor\bmod 10\)、\(1\) 円硬貨の数は \(X \bmod 10\) です。

実装例 (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;
}

pythonでは剰余が常に非負になることから、お釣りを (-a)%1000 により求めることができます。

実装例 (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)