The Fewest Coins [Carl Hultquist, 2006]

Farmer John has gone to town to buy some farm supplies. Being a very efficient man, he always pays for his goods in such a way that the smallest number of coins changes hands, i.e., the number of coins he uses to pay plus the number of coins he receives in change is minimized. Help him to determine what this minimum number is. FJ wants to buy T (1 <= T <= 10,000) cents of supplies. The currency system has N (1 <= N <= 100) different coins, with values V1, V2, ..., VN (1 <= Vi <= 120). Farmer John is carrying C1 coins of value V1, C2 coins of value V2, ...., and CN coins of value VN (0 <= Ci <= 10,000). The shopkeeper has an unlimited supply of all the coins, and always makes change in the most efficient manner (although Farmer John must be sure to pay in a way that makes it possible to make the correct change). PROBLEM NAME: fewcoins INPUT FORMAT: * Line 1: Two space-separated integers: N and T. * Line 2: N space-separated integers, respectively V1, V2, ..., VN coins (V1...VN). * Line 3: N space-separated integers, respectively C1, C2, ..., CN SAMPLE INPUT (file fewcoins.in): 3 70 5 25 50 5 2 1 INPUT DETAILS: Farmer John has 5x5 cent coins, 2x25 cent coins and 1x50 cent coin. His bill is 70 cents. OUTPUT FORMAT: * Line 1: A line containing a single integer, the minimum number of coins involved in a payment and change-making. If it is impossible for Farmer John to pay and receive exact change, output -1. SAMPLE OUTPUT (file fewcoins.out): 3 OUTPUT DETAILS: Farmer John pays 75 cents using a 50 cents and a 25 cents coin, and receives a 5 cents coin in change, for a total of 3 coins used in the transaction.

მონეტების უმცირესი რაოდენობა - მიხეილ მეტრეველის თარგმანი

ფერმერი ჯონი წავიდა ქალაქში მარაგის შესაძენად. ის ძალიან მარჯვე კაცია და ამიტომ ჯონი ყოველთვის იხდის გადასახადს ისე, რომ მონეტები რაც შეიძლება ნაკლები ადამიანის ხელში გადადის ანუ იმ მონეტების რაოდენობა რომელსაც ის გასცემს და რომელსაც ის ხურდად იღებს მინიმალურია. დაეხმარეთ მას ამ მინიმალური რიცხვის გამოთვლაში. ჯონს უნდა იყიდოს T(1 <= T <= 10,000) ცენტის ღირებულების მარაგი. ფულის სისტემას აქვს N (1 <= N <= 100) ცალი განსხვავებული მონეტა ღირებულებებით V1,V2…VN (1 <= Vi <= 120). ჯონს თან აქვს C1 ცალი მონეტა თითოეულის ღირებულება კი V1 არის, ასევე აქვს C2 ცალი მონეტა ღირებულებებით V2...და CN ცალი მონეტა ღირებულებებით VN (0 <= Ci <= 10,000). მაღაზიის მფლობელს აქვს ყველანაირი მონეტების უსასრულო რაოდენობა და ხურდას ყოველთვის ყველაზე ეფექტური გზით აბრუნებს (თუმცა ფერმერმა ჯონმა ისე უნდა გადაიხადოს ფული, რომ შესაძლო იყოს ხურდის დაბრუნება). ამოცანის სახელი: fewcoins ინფორმაციის შეტანის ფორმატი: ხაზი 1 : ორი ცალი მთელი რიცხვი(Integer) N და T გამოყოფილი ცარიელი ადგილით (space) ხაზი 2 : N ცალი ცარიელი ხაზით გამოყოფილი მთელი რიცხვი: V1, V2, ..., VN მონეტები (V1...VN). ხაზი 3 : N ცალი ცარიელი ხაზით გამოყოფილი მთელი რიცხვი C1, C2, ..., CN. ინფორმაციის შეყვანის ნიმუში: 3 70 5 25 50 5 2 1 ინფორმაციის შეყვანის დეტალები: ჯონს აქვს 5x5, 2x25 და 1x50 ცენტი. მან უნდა გადაიხადოს 70 ცენტი. ინფორმაციის გამოტანის ფორმატი: ხაზი 1: ერთი ცალი მთელი რიცხვი, რომელიც არის გადასახადის გადახდაში და ხურდის დაბრუნებაში გამოყენებული მონეტების უმცირესი რაოდენობა. თუ ხურდის ზუსტად დაბრუნება შეუძლებელია, პროგრამამ უნდა დააბრუნოს -1. ინფორმაციის გამოტანის ნიმუში(ფაილი fewcoins.out): 3 ინფორმაციის გამოტანის დეტალები: ფერმერმა ჯონმა გადაიხადა 75 ცენტი 50 ცენტიანის და 25 ცენტიანის გამოყენებით და მიიღო 5 ცენტიანი ხურდად. ანუ მიმოცვლაში გამოყენებული იყო 3 ცალი მონეტა.

fewcoins

Let's start by looking at just the problem of deciding how to make the change, given what Farmer John is going to pay. This is a fairly well-known dynamic programming problem, which can be solved by using the following recurrence: the best way to make amount C with coins 1..N is either to do it with coins 1..N-1, or to make change C-VN with coins 1..N and add a VN. Working out the most efficient way for FJ to pay an amount M is slightly trickier, because he has a limited number of each coin. Instead, we can use the following recurrence: the best way to make amount M with coins 1..N is to use 0<=k<=CN coins of VN plus C-k.VN with coins 1..N-1, taking the minimum over all k. Thus, once we know how much FJ is going to pay, we can compute the total number of coins required. Of course, we can run the DPs just once each (up to a maximum value) rather than for every amount that FJ might pay. The only catch is that we need to determine the maximum. Of course, FJ cannot pay more than all the coins in his possession, but it is possible to do better. Let V be the largest coin value, and call this type of coin silver and all other coins brass. It is not difficult to prove that for any change amount of at least V^2, it is possible to use at least one silver coin (hint: consider the partial sums modulo V), and hence that in making change of at least 2V^2 there can be at least V silver coins. Now if Farmer John pays at least 2V^2, and hence pays with V coins, then a similar argument shows that some set of them adds up to a multiple of V and at most V^2, which can be cancelled out with the silver coins in the change. So the change amount can never exceed 2V^2. In fact it is possible to show tighter bounds (such as V^2),but that is left as an exercise. If implemented directly, this gives an algorithm that is O((T+V^2)NC), which at ~10^9 operations will most likely be too slow. One area that can easily be optimised is the inner-most loop, which determines the optimum number of coins of each type for FJ to use. It looks for the minimum of old[t - k*v] + k, where i is the total under consideration, v is the value of the coin under consideration and k ranges from 0 to c inclusive (c being the number of v's). If we define tilted[i%v][i/v] = old[i]-i/v then the expression we seek becomes min(tilted[t % v][t / v - k]) + t / v. By moving the offset outside of the minimum and splitting up the cases by modulus, we reduce the problem to one of finding the minimum from a range of values. What is worth noting is that the ranges we will use the same array multiple times, and each time the range we seek is just shifted over by 1. There exist some extremely sophisticated algorithms that provide constant-time range-min queries, but they are overkill for this specialised situation. Instead, we can preprocess the array to determine, for each i, the smallest j > i such that arr[j] < arr[i]. We can do this by working through the array, keeping a stack of the i values for which we have not yet seen any such j. Each time we see a new value j, we can finalise stack entries for which arr[i] > arr[j], before pushing j onto the stack (a similar algorithm can be used to solve Empodia from IOI 2004). To determine the smallest value in each range as we proceed, we simply keep track of the smallest index. If the previous smallest drops out of the window, start from the left of the window and keep following the "next smaller" pointer until the new smallest is found. With this optimisation, the search becomes amortised constant time per query, so the efficiency is O((T+V^2)N). #include <fstream> #include <algorithm> #include <set> #include <stack> #include <iterator> #include <cassert> #include <complex> using namespace std; #define MAXN 100 #define MAXT 20000 #define MAXV 200 #define MAXC 1000000 #define BIG (INT_MAX / 4) typedef complex<int> addr; int main() { ifstream in("fewcoins.in"); ofstream out("fewcoins.out"); int N, T, M; set<int> seen; in >> N >> T; assert(1 <= N && N <= MAXN); assert(1 <= T && T <= MAXT); int V[N], C[N], ans[N]; for (int i = 0; i < N; i++) { in >> V[i]; assert(1 <= V[i] && V[i] <= MAXV); assert(!seen.count(V[i])); seen.insert(V[i]); } for (int i = 0; i < N; i++) { in >> C[i]; assert(0 <= C[i] && C[i] <= MAXC); } M = 0; for (int i = 0; i < N; i++) M += V[i] * C[i]; assert(M >= T); int maxV = *max_element(V, V + N); M = min(M, T + maxV * maxV); M++; int dpf[M]; int dpu[M], dpu_old[M]; addr next[M]; fill(dpf + 1, dpf + M, BIG); dpf[0] = 0; for (int i = 0; i < N; i++) for (int j = V[i]; j < M; j++) dpf[j] <?= dpf[j - V[i]] + 1; fill(dpu + 1, dpu + M, BIG); dpu[0] = 0; for (int i = 1; i <= N; i++) { copy(dpu, dpu + M, dpu_old); fill(next, next + M, addr(-1, -1)); int v = V[i - 1]; int c = C[i - 1]; addr step(v, 1); addr delta = step * c; for (int b = 0; b < v; b++) { stack<addr> nonext; addr lo(b, 0); for (addr cur = lo; cur.real() < M; cur += step) { while (!nonext.empty() && dpu_old[nonext.top().real()] - nonext.top().imag() > dpu_old[cur.real()] - cur.imag()) { next[nonext.top().real()] = cur; nonext.pop(); } nonext.push(cur); if (cur.real() - delta.real() > lo.real()) lo = cur - delta; while (next[lo.real()].real() != -1) lo = next[lo.real()]; dpu[cur.real()] = dpu_old[lo.real()] - lo.imag() + cur.imag(); } } } int bestc = BIG; for (int i = T; i < M; i++) bestc <?= dpu[i] + dpf[i - T]; out << (bestc < BIG ? bestc : -1) << "\n"; return 0; }

მიხეილ მეტრეველის თარგმანი

მოდით ჯერ დავიწყოთ ხურდის დაბრუნებით იმის გათვალისწინებით თუ რამდენი გადაიხადა ფერმერმა. ეს კარგად ცნობილი დინამიური პროგრამირების ტიპის ამოცანაა, რომლის ამოხსნაც შესაძლებელია შემდეგი რეკურსიით: საუკეთესო გზა რომ მივიღოთ C თანხა მონეტებით 1…N არის ამის გაკეთება 1…N-1 მონეტით ან „ხურდის შექმნა“ C-VN მონეტებით 1...N და დავუმატოთ VN. საუკეთესო გზის პოვნა ფერმერისთვის M თანხის გადახდის კი უფრო რთულია, რადგან მას ყოველი მონეტა შეზღუდული რაოდენობით აქვს. შეგვიძლია გამოვიყენოთ შემდეგი რეკურსია: საუკეთესო გზა რომ შევადგინოთ M თანხა მონეტებიდან 1...N არის VN-ს დამატებული C-k ღირებულების 0<=K<=CN ცალი მონეტის გამოყენება. ანუ თუ ვიცით ფერმერმა რამდენი უნდა გადაიხადოს მაშინ გავიგებთ საჭირო მონეტების რაოდენობასაც. რა თქმა უნდა შეგვიძლია ავამუშავოთ DP(დინამიური პროგრამირება) თითოეულ პირობაზე (მაქსიმალურ რაოდენობამდე) იმის მაგივრად რომ ფერმერისგან გადახდის ყველანაირი ვარიანტი განვიხილოთ. ჩვენი მიზანი არის მაქსიმუმის პოვნა. რა თქმა უნდა ჯონი ვერ გადაიხდის იმაზე მეტს რაც გააჩნია მაგრამ უკეთესი გზაც შეგვიძლია ვიპოვოთ. V იყოს უდიდესი ფასის მქონე მონეტა და ასეთ მონეტებს „ვერცხლის მონეტა“დავუძახოთ, ხოლო ყველა დანარჩენს „წვრილი მონეტები“. რთული არ არის იმის დამტკიცება რომ ნებისმიერი ხურდის ოდენობის დაბრუნებაში რომელიც V^2 მაინც არის, შესაძლებელია ერთი ვერცხლის მონეტის გამოყენება მაინც (მინიშნება: განიხილეთ ნაწილობრივი ჯამები V მოდულით)და შესაბამისად 2V^2 ხურდის შემთხვევაში შეიძლება V ცალი ვერცხლის მონეტა მაინც იყოს. თუ ფერმერი გადაიხდის 2V^2 თანხას მაინც და ანუ ამ გადასახადში იქნება V მონეტებიც, მაშინ ანალოგიური არგუმენტებით ვასკვნით რომ ამ მონეტების ზოგი სიმრავლის აჯამვით შეგვიძლია მივიღოთ V-ს რომელიმე ჯერადი, მაქსიმუმ V^2, რომელიც შეგვიძლია გავაბათილოთ ვერცხლის მონეტებით დაბრუნებულ ხურდაში. ანუ ხურდის რაოდენობა ვერ გადასცდება 2V^2-ს.შესაძლებელია უფრო მჭიდრო საძღვრების ჩვენებაც, (როგორიცაა V^2) მაგრამ ეს საკითხი უბრალო სავარჯიშოდ დავტოვოთ. თუ იმპლემენტაციას პირდაპირ გავაკეთებთ ჩამოყალიბებული პირობა მოგვცემს ალგორითმს რომელიც იმუშავებს O((T+V^2)NC) დროში, რაც მიახლოებით 10^9 ოპერაციაზე სავარაუდოდ იქნება საკმაოდ ნელი. ერთ ერთი არე რომელსაც ოპტიმიზაცია შეგვიძლია ადვილად გავუკეთოთ არის ყველაზე შიდა ციკლი, რომელიც განსაზღვრავს ყოველი ტიპის მონეტების ოპტიმალურ რაოდენობას რომელსაც ფერმერი გამოიყენებს. ეს ციკლი ეძებს [t - k*v] + k -ის მინიმუმს, სადაც i (აქ მგონი შეცდომა იყო) არის განხილულთა მთელი რაოდენობა, v არის ახლა განხილვის პროცესში მყოფი მონეტის ფასი ხოლო k არის 0 დან c მდე ,c-ს ჩათვლით (c არის v-ების რაოდენობა).თუ ჩვენ განვსაზღვრავთ tilted i%v][i/v] = old[i]-i/v მაშინ გამოსახულება იცვლება შემდეგნაირად : min(tilted[t % v][t / v - k]) + t / v . საფეხურის(შვერის) მინიმუმის გარეთ გატანით და მდგომარეობის რამდენიმე მოდულად დაყოფით ამოცანა დადის უფრო პატარა ამოცანაზე: უმცირესი მნიშვნელობის პოვნა გარკვეულ სიმრავლეში. აღსანიშნავია რომ სიმრავლე ერთი და იგივე მასივითაა რამდენჯერმე განსაზღვრული და ეს სიმრავლე ერთით იწევს ყოველ ჯერზე. არსებობს საკმაოდ რთული ალგორითმები, რომლებიც საშუალებას გვაძლევენ რომ ეს პრობლემა მუდმივ დროში გადაიჭრას, მაგრამ ამ კერძო ამოცანისთვის ეს არ იქნება საჭირო. ამის მაგივრად ჩვენ შეგვიძლია დავამუშავოთ მასივი ისე რომ ყოველი i სთვის გვქონდეს უმცირესი j>i ისე რომ arr[j] < arr[i]. ამის გაკეთება შეგვიძლია მასივზე გადაყოლით, თან ვიქონიოთ i მნიშვნელობების სტეკი რომელთათვისაც ჯერ არ გვიპოვია j. ყოველ ჯერზე როდესაც ვნახავთ ახალ j-ს, ჩვენ შეგვიძლია დავასრულოთ სტეკის წევრი, რომლისთვისაც arr[i] > arr[j], სანამ j-ს სტეკში ჩავსვამთ (ანალოგიური ალგორითმით შესაძლებელია ამოიხსნას Empodia, IOI 2004 -დან). უმცირესი მნიშვნელობის საპოვნელად ჩვენ უბრალოდ ვადევნებთ თვალს უმცირეს ინდექსს. თუ წინა უმცირესი ‘ფანჯრიდან გავარდება’ (გამოუსადეგარი გახდება) მაშინ დავიწყოთ ამ ფარჯნის მარცხნიდან და მოვძებნოთ ახალი უმცირესი მნიშვნელობა. ამ ოპტიმიზაციით ალგორითმი ხდება და ეფექტურობა ხდება O((T+V^2)N).

Below is Bruce's solution

#include <fstream>
#include <algorithm>
#include <set>
#include <stack>
#include <iterator>
#include <cassert>
#include <complex>

using namespace std;

#define MAXN 100
#define MAXT 20000
#define MAXV 200
#define MAXC 1000000

#define BIG (INT_MAX / 4)

typedef complex<int> addr;

int main() {
    ifstream in("fewcoins.in");
    ofstream out("fewcoins.out");
    int N, T, M;
    set<int> seen;

    in >> N >> T;
    assert(1 <= N && N <= MAXN);
    assert(1 <= T && T <= MAXT);

    int V[N], C[N], ans[N];
    for (int i = 0; i < N; i++) {
        in >> V[i];
        assert(1 <= V[i] && V[i] <= MAXV);
        assert(!seen.count(V[i]));
        seen.insert(V[i]);
    }
    for (int i = 0; i < N; i++) {
        in >> C[i];
        assert(0 <= C[i] && C[i] <= MAXC);
    }
    M = 0;
    for (int i = 0; i < N; i++)
        M += V[i] * C[i];
    assert(M >= T);
    int maxV = *max_element(V, V + N);
    M = min(M, T + maxV * maxV);
    M++;

    int dpf[M];
    int dpu[M], dpu_old[M];
    addr next[M];
    fill(dpf + 1, dpf + M, BIG);
    dpf[0] = 0;
    for (int i = 0; i < N; i++)
        for (int j = V[i]; j < M; j++)
            dpf[j] <?= dpf[j - V[i]] + 1;

    fill(dpu + 1, dpu + M, BIG);
    dpu[0] = 0;
    for (int i = 1; i <= N; i++) {
        copy(dpu, dpu + M, dpu_old);
        fill(next, next + M, addr(-1, -1));
        int v = V[i - 1];
        int c = C[i - 1];
        addr step(v, 1);
        addr delta = step * c;
        for (int b = 0; b < v; b++) {
            stack<addr> nonext;
            addr lo(b, 0);
            for (addr cur = lo; cur.real() < M; cur += step) {
                while (!nonext.empty()
                       && dpu_old[nonext.top().real()] - nonext.top().imag() >
                                         dpu_old[cur.real()] - cur.imag()) {
                    next[nonext.top().real()] = cur;
                    nonext.pop();
                }
                nonext.push(cur);
                if (cur.real() - delta.real() > lo.real())
                    lo = cur - delta;
                while (next[lo.real()].real() != -1) lo = next[lo.real()];

                dpu[cur.real()] = dpu_old[lo.real()] - lo.imag() + cur.imag();
            }
        }
    }

    int bestc = BIG;
    for (int i = T; i < M; i++)
        bestc <?= dpu[i] + dpf[i - T];
    out << (bestc < BIG ? bestc : -1) << "\n";

    return 0;
}