mickypinata

USACO-T002: Greedy Gift Givers

Sep 19th, 2021
828
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: gift1
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. typedef long long lli;
  11.  
  12. const int N = 10;
  13. const int L = 14;
  14. const int PB = 1e9 + 7;
  15.  
  16. map<lli, int> mp;
  17. int money[N + 1];
  18. char str[L + 1], name[N + 1][L + 1];
  19.  
  20. lli strHash(char *str){
  21.     int len = strlen(str);
  22.     lli hsh = 0;
  23.     for(int i = 0; i < len; ++i){
  24.         hsh *= PB;
  25.         hsh += str[i];
  26.     }
  27.     return hsh;
  28. }
  29.  
  30. int main(){
  31.  
  32.     freopen("gift1.in", "r", stdin);
  33.     freopen("gift1.out", "w", stdout);
  34.  
  35.     int n;
  36.     scanf("%d", &n);
  37.     for(int i = 1; i <= n; ++i){
  38.         scanf(" %s", name[i]);
  39.         mp[strHash(name[i])] = i;
  40.     }
  41.     for(int i = 1; i <= n; ++i){
  42.         int dv, nRe;
  43.         scanf(" %s%d%d", str, &dv, &nRe);
  44.         int giverIdx = mp[strHash(str)];
  45.         if(nRe == 0){
  46.             money[giverIdx] += dv;
  47.             continue;
  48.         }
  49.         int give = dv / nRe;
  50.         int remain = dv % nRe;
  51.         money[giverIdx] -= dv - remain;
  52.         for(int j = 1; j <= nRe; ++j){
  53.             scanf(" %s", str);
  54.             int reIdx = mp[strHash(str)];
  55.             money[reIdx] += give;
  56.         }
  57.     }
  58.     for(int i = 1; i <= n; ++i){
  59.         printf("%s %d\n", name[i], money[i]);
  60.     }
  61.  
  62.     fclose(stdin);
  63.     fclose(stdout);
  64.  
  65.     return 0;
  66. }
  67.  
RAW Paste Data