fork download
copy 
  1. /*
  2.  * http://w...content-available-to-author-only...h.club/tasks.php?show_task=5000000355
  3.  */
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. int dest,n,k;
  9. vector<pair<int,int>> graph;
  10. int cache[60][4];
  11. string str="";
  12. int dp(int i, int source)
  13. {
  14. 	if(cache[i][source]!=-1)
  15. 	{
  16. 		return cache[i][source];
  17. 	}
  18. 	if(i==0)
  19. 	{
  20. 		if(source==dest)
  21. 		{
  22. 			return cache[i][source]=1;
  23. 		}
  24. 		return cache[i][source]=0;
  25. 	}
  26.  
  27.  
  28. 	cache[i][source]=dp(i-1,graph[source].first)+dp(i-1,graph[source].second);
  29. 	return cache[i][source];
  30. }
  31. void rec(int len, int num, int source)
  32. {
  33. 	if(len==0)
  34. 	{
  35. 		return;
  36. 	}
  37. 	bool flag=0;
  38. 	if(dp(len-1,graph[source].first)>=num)
  39. 	{
  40. 		str+='0';
  41. 		rec(len-1,num,graph[source].first);
  42. 	}
  43. 	else{
  44. 		str+='1';
  45. 		num-=dp(len-1,graph[source].first);
  46. 		rec(len-1,num,graph[source].second);
  47. 	}
  48. }
  49.  
  50.  
  51.  
  52. int main() {
  53. 	memset(cache,-1, sizeof(cache));
  54. 	graph.push_back({2,1});
  55. 	graph.push_back({3,0});
  56. 	graph.push_back({0,3});
  57. 	graph.push_back({1,2});
  58. 	char ch;
  59. 	cin>>ch;
  60. 	dest=ch-'A';
  61. 	cin>>n>>k;
  62. 	if(dp(n,0)<k)
  63. 	{
  64. 		cout<<"impossible\n";
  65. 	}else{
  66. 		rec(n,k,0);
  67. 		cout<<str<<"\n";
  68. 	}
  69. }
  70.  
  71.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
B 3 2
stdout
copy 
010
https://ideone.com/SgUPZk
language:
C++14 (gcc 8.3)
created:
5 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!