fork download 
  1. #include <bits/stdc++.h>
  2. #define all(vec) vec.begin(), vec.end()
  3. #define rall(vec) vec.rbegin(), vec.rend()
  4. #define sz(x) int(x.size())
  5. using namespace std;
  6. typedef long long ll;
  7. void Fast_IO()
  8. {
  9.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  10. #ifndef ONLINE_JUDGE
  11.     freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  12. #endif
  13. }
  14.  
  15. const ll N = 1e5;
  16. ll dp[N][7];
  17. ll n;
  18.  
  19. map<int, vector<int>> dice;
  20. ll go(ll curr, ll pre)
  21. {
  22.     if (curr == n)
  23.     {
  24.         return 0;
  25.     }
  26.     if (curr > n)
  27.     {
  28.         return 1e9;
  29.     }
  30.  
  31.     ll &ret = dp[curr][pre];
  32.  
  33.     if (ret != 1e9)
  34.     {
  35.         return ret;
  36.     }
  37.  
  38.     ll ans = 1e9;
  39.  
  40.     for (int i = 0; i <= 3; i++)
  41.     {
  42.         ans = min(ans, 1 + go(curr + dice[pre][i], dice[pre][i]));
  43.     }
  44.  
  45.     ret = ans;
  46.     return ret;
  47. }
  48. void solve()
  49. {
  50.     cin >> n;
  51.     ll ans = 1e9;
  52.     for(int i = 2; i <= 5; i++){
  53.         cout << go(i, i) << "\n";
  54.         ans = min(ans, go(i, i));
  55.     }
  56.     cout << ans << "\n";
  57. }
  58.  
  59. int main()
  60. {
  61.     Fast_IO();
  62.     memset(dp, 1e9, sizeof dp);
  63.     dice[1] = {2, 3, 4, 5};
  64.     dice[2] = {2, 3, 4, 6};
  65.     dice[3] = {1, 2, 5, 6};
  66.     dice[4] = {1, 2, 5, 6};
  67.     dice[5] = {1, 3, 4, 6};
  68.     dice[6] = {2, 3, 4, 5};
  69.     int T = 1;
  70.     cin >> T;
  71.     while (T--)
  72.     {
  73.         solve();
  74.     }
  75.     return 0;
  76. }
  77.  
Success #stdin #stdout 0.01s 9068KB
comments (?)
stdin 
Standard input is empty
stdout 
1000000000
1000000000
1000000000
1000000000
1000000000
https://ideone.com/T0qaBn
language:
C++ (gcc 8.3)
created:
14 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!