fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int lli;
  4. #define M 1000000007
  5. #define INF 1000000007
  6. typedef pair<lli,lli> ll;
  7. #define mem(a,x) memset(a,x,sizeof(a))
  8. lli n,k,m;
  9. lli vis[10007];
  10. lli dist[507][507];
  11. lli path[207][207];
  12. lli path1[207][207];
  13. vector<int> v2(1005,1);
  14. vector<vector<lli>> v;
  15. lli x,y,c,z;
  16. map<int,int> m1;
  17. struct edge
  18. {
  19.     lli a,b,cost;
  20. };
  21. /*void djkstra(int x,vector<ll> v[])
  22. {
  23.     mem(vis,0);
  24.     dist[x]=0;
  25.     s2.insert({0,x});
  26.     while(!s2.empty())
  27.     {
  28.         ll p=*s2.begin();
  29.         s2.erase(s2.begin());
  30.         x=p.second;
  31.         if(vis[x])
  32.         continue;
  33.         vis[x]=1;
  34.         for(int j=0;j<v[x].size();j++)
  35.         {
  36.             if(dist[v[x][j].second]>dist[x]+v[x][j].first)
  37.             {
  38.                 dist[v[x][j].second]=dist[x]+v[x][j].first;
  39.                 s2.insert({dist[v[x][j].second],v[x][j].second});
  40.                 a[v[x][j].second]=x;
  41.             }
  42.         }
  43.     }
  44. }*/
  45. lli parent[100007];
  46. lli find(lli a)
  47. {
  48.     return a==parent[a]?a:parent[a]=find(parent[a]);
  49. }
  50. void dset(lli n)
  51. {
  52.     for(int j=0;j<=n;j++)
  53.     parent[j]=j;
  54. }
  55. void unio(lli a,lli b,lli rank[])
  56. {
  57.     if(rank[find(a)]>rank[find(b)])
  58.     parent[find(b)]=find(a);
  59.     else if(rank[find(b)]>rank[find(a)])
  60.     parent[find(a)]=find(b);
  61.     else
  62.     {
  63.         parent[find(a)]=find(b);
  64.         rank[find(b)]++;
  65.     }
  66. }
  67. bool check(lli a,lli b)
  68. {
  69.     return find(a)==find(b);
  70. }
  71. lli vis1[31];
  72. lli q,u,v1,l,t;
  73. lli a[300007];
  74. /*bool valid(int i,int x)
  75. {
  76.     for(int j=1;j<x;j++)
  77.     {
  78.         if((abs(b[j-1]-i)==abs(j-x))||(i==b[j-1])||(j==x))
  79.         return false;
  80.     }
  81.     return true;
  82. }*/
  83. lli d,N,e;
  84. lli tot;
  85. lli m4=0;
  86. struct edge coins[41];
  87. lli dp[1001][1001];
  88. int f=0;
  89. lli dp1[100000];
  90. lli solve(lli x,lli y,lli e,lli w)
  91. {
  92.     if(dp[x][y]!=100000)
  93.     {
  94.  
  95.         return dp[x][y];
  96.     }
  97.     if((x*x+y*y)==e*e)
  98.     {
  99.      return 0;   
  100.     }
  101.     for(int i=1;i<=N;i++)
  102.     {
  103.         if(((x+coins[i].a)*(x+coins[i].a)+(y+coins[i].b)*(y+coins[i].b))<=e*e)
  104.         {
  105.             dp[x][y]=min(dp[x][y],(solve(x+coins[i].a,y+coins[i].b,e,i)+1));
  106.         }
  107.     }
  108.     return dp[x][y];
  109. }
  110. int main()
  111. {
  112. cin>>n;
  113. for(int i=1;i<=n;i++)
  114. {
  115.     f=0;
  116.     for(int j=0;j<1001;j++)
  117.     {
  118.         for(int k=0;k<1001;k++)
  119.         dp[j][k]=100000;
  120.     }
  121.     for(int i=0;i<100000;i++)
  122.     dp1[i]=100000;
  123.     cin>>N>>e;
  124.     for(int j=1;j<=N;j++)
  125.     {
  126.         cin>>x>>y;
  127.         coins[j].a=x;
  128.         coins[j].b=y;
  129.     }
  130.     lli d=solve(0,0,e,0);
  131.     if(d==100000)
  132.     cout<<"not possible"<<endl;
  133.     else
  134.     cout<<d<<endl;
  135. }
  136. }
Success #stdin #stdout 0s 4400KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/MuZCef
language:
C++14 (gcc 8.3)
created:
6 years 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!