fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int inf=1e9;
  5.  
  6. #define ll long long
  7.  
  8. int solve()
  9. {
  10. 	int n;
  11. 	cin >> n;
  12. 	vector<string>a(n);
  13. 	for(int i=0;i<n;i++)
  14. 		cin >> a[i];
  15. 	int ans=0;
  16. 	for(int i=1;i<n;i++)
  17. 	{
  18. 		if(a[i].length()<=a[i-1].length())
  19. 		{
  20. 			int flag=-1;
  21. 			int j=0;
  22. 			int x=a[i].length(),y=a[i-1].length();
  23. 			while(j<min(x,y))
  24. 			{
  25. 				if(a[i][j]-'0'<a[i-1][j]-'0')
  26. 				{
  27. 					// cerr << "1st\n";
  28. 					flag=1;
  29. 					break;
  30. 				}
  31. 				else if(a[i][j]-'0'>a[i-1][j]-'0')
  32. 				{
  33. 					flag=0;
  34. 					break;
  35. 				}
  36. 				j++;
  37. 			}
  38. 			if(flag==1){
  39. 				if(x==y)
  40. 				{
  41. 					a[i]=a[i]+"0";
  42. 					ans++;
  43. 				}
  44. 				else
  45. 				{
  46. 					string z="";
  47. 					for(int j=x+1;j<=y;j++)
  48. 						z+="0";
  49. 					z+="0";
  50. 					ans+=(y+1-x);
  51. 					a[i]=a[i]+z;
  52. 				}
  53. 			}
  54. 			else if(flag==0)
  55. 			{
  56. 				if(x<y)
  57. 				{
  58. 					string z="";
  59. 					for(int j=x+1;j<=y;j++)
  60. 						z+="0";
  61. 					a[i]=a[i]+z;
  62. 					ans+=(y-x);
  63. 				}
  64. 			}
  65. 			else
  66. 			{
  67. 				if(x<y)
  68. 				{
  69. 					string z="";
  70. 					for(int j=x;j<y-1;j++)
  71. 						z+=a[i-1][j];
  72. 					if(a[i-1][y-1]=='9')
  73. 					{
  74. 						z+="90";
  75. 						ans+=(y+1-x);
  76. 					}
  77. 					else
  78. 					{
  79. 						z+=(a[i-1][y-1]+1);
  80. 						ans+=(y-x);
  81. 					}
  82. 					a[i]+=z;
  83. 				}
  84. 				else
  85. 				{
  86. 					ans++;
  87. 					a[i]+="0";
  88. 				}
  89. 			}
  90. 		}
  91. 	}
  92. 	return ans;
  93. }
  94.  
  95. int main()
  96. {
  97. 	ios_base::sync_with_stdio(0);
  98.   cin.tie(0);
  99.   cout.tie(0);
  100. 	int t;
  101. 	cin >> t;
  102. 	for(int i=1;i<=t;i++){
  103. 		cout << "Case #" << i << ": ";
  104. 		cout << solve() << "\n";
  105. 	}
  106. 	return 0;
  107. }
Success #stdin #stdout 0s 5336KB
comments (?)
stdin
copy 
1
4
4 3 2 1
stdout
copy 
Case #1: 6
https://ideone.com/sBK3lw
language:
C++ (gcc 8.3)
created:
3 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!