Benny And The Broken Odometer

Problem

One fine day, Benny decided to calculate the number of kilometers that she traveled by her bicycle. Therefore, she bought an odometer and installed it onto her bicycle. But the odometer was broken. It was not able to display the digit 3 . This would precisely mean, that the odometer won't be able to display the numbers having one of their digits as 3 .

For example, after the number 1299, the odometer will show 1400.

Benny was traveling a lot and now she wants to know the number of kilometers that she has traveled. You will be given only the number that Benny saw on the odometer. Your task is to determine the real distance.

Input format

The input consists of several test cases. The first line contains one integer T denoting the number of test cases. The next T lines contain a single integer N denoting the number that Benny saw on odometer.

Output format

For each test case, print the real distance in a single line.

Constraints

• 1 ≤ T ≤ 10^5^
• 0 ≤ N < 10^9^

Sample Input

5
5
14
76
67
40

Sample Output

4
12
59
51
27

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

• In the first sample test case, the odometer skipped the number 3 and displayed 4 after it. Hence, the numbers were displayed in the order of [ 1 , 2 , 4 , 5 ] accounting to distance of four kilometers travelled.
• In the second sample test case, the sequence in which odometer displayed numbers would be [ 1 , 2 , 4 , 5 , 6 , 7 , 8 , 9 , 10, 11, 12, 14] and it skipped [ 3 , 13]. Thus, a total of 12 kilometers were travelled.

#include <bits/stdc++.h>
using namespace std;
int dp[10][2][2];
int recursion(int index,bool tight,bool flag,string &s){
	if(index==s.size()) return flag;
	if(dp[index][tight][flag]!=-1) return dp[index][tight][flag];
	int limit=tight?s[index]-'0':9;
	int ans=0;
	for(int i=0;i<=limit;i++){
		bool updatedFlag=(flag | (i==3));
		// ans+=recursion(index+1,(tight & (i==s[index]-'0'),updatedFlag,s));
		ans += recursion(index + 1, (tight & (i == s[index] - '0')), updatedFlag, s);
	}
	return dp[index][tight][flag]=ans;
}
void solve(){
	int x;
	cin>>x;
	memset(dp,-1,sizeof dp);
	string s=to_string(x);
	cout<<x- recursion(0,1,0,s)<<"\n";
}
int main() {
	int t;
	cin>>t;
	while(t--){
       solve();
	}
	return 0;
}

Classy Numbers

Let's call some positive integer classy if its decimal representation contains no more than 33 non-zero digits. For example, numbers 44, 200000200000, 1020310203 are classy and numbers 42314231, 102306102306, 72774200007277420000 are not.

You are given a segment [𝐿;𝑅][L;R]. Count the number of classy integers 𝑥x such that 𝐿≤𝑥≤𝑅L≤x≤R.

Each testcase contains several segments, for each of them you are required to solve the problem separately.

Input

The first line contains a single integer 𝑇T (1≤𝑇≤1041≤T≤104) — the number of segments in a testcase.

Each of the next 𝑇T lines contains two integers 𝐿𝑖Li and 𝑅𝑖Ri (1≤𝐿𝑖≤𝑅𝑖≤10181≤Li≤Ri≤1018).

Output

Print 𝑇T lines — the 𝑖i-th line should contain the number of classy integers on a segment [𝐿𝑖;𝑅𝑖**]**[Li;Ri].

Example

InputCopy

4
1 1000
1024 1024
65536 65536
999999 1000001

OutputCopy

1000
1
0
2

#include <bits/stdc++.h>
using namespace std;
#define int long long int
int dp[20][2][4];
int recursion(int index, bool tight, int count, string &s)
{
  if (index == s.size())
    return 1;
  int limit = tight ? s[index] - '0' : 9;
  int ans = 0;
  if (dp[index][tight][count] != -1)
    return dp[index][tight][count];
  for (int i = 0; i <= limit; i++)
  {
    int updateCnt = count + (i != 0 ? 1 : 0);
    if (updateCnt <= 3)
    {
      ans += recursion(index + 1, (tight & (i == s[index] - '0')), updateCnt, s);
    }
  }
  return dp[index][tight][count] = ans;
}
void solve()
{
  int l, r;
  cin >> l >> r;
  // cout << l << r << "\n";
  string s1 = to_string(r);
  string s2 = to_string(l - 1);
  memset(dp, -1, sizeof dp);
  int x = recursion(0, 1, 0, s1);
  memset(dp, -1, sizeof dp);
  int y = recursion(0, 1, 0, s2);
  cout << x - y << "\n";
}
signed main()
{
  int t;
  cin >> t;
  while (t--)
  {
    solve();
  }
  return 0;
}

GONE - G-One Numbers

#dynamic-programming

The War of Evil vs Good continues and Ra-One and G-One continue to be on respective sides.

After saving all the cities with Ra-One Numbers G-One realised that some cities whose population is a "G-One Number" can be easy target for Ra-One.

A G-One number is a number sum of whose digits is a prime number

For example 12 .. sum = 1+2 = 3 ... 3 is a prime number.

G-One wants to find out all the populations which can be g-One numbers....

Can You help him.?

You will be given the range of population and you have to tell him how many in this range are G-One Numbers.

Input

first line has number 'c' indicating the number of ranges.

'c' lines follow and contain two numbers ... 'f' and 't' inclusive.

Output

Print a single line per case giving the number of populations which are G-One numbers.

Example

Input:
3
10 19
1 9
20 29

Output:
4
4
5

Note : c will be less than 100 t and f will be less than 10^8 inclusive

Submit solution!

#include <bits/stdc++.h>
#define int long long
#define PI 3.141592653589793238462
#define set_bits __builtin_popcount
const int mod = (1e9 + 7);
const int N = (1e5 + 5);
using namespace std;
int dp[20][2][80];
bool isPrime(int n)
{
  if (n == 1)
    return false;
  if (n == 2 || n == 3)
    return true;
  if (n % 2 == 0 || n % 3 == 0)
    return false;
  for (int i = 5; i * i <= n; i += 6)
  {
    if (n % i == 0 || n % (i + 2) == 0)
      return false;
  }
  return true;
}

int recursion(int index, bool tight, int sum, string s)
{
  if (index == s.length())
  {
    if (isPrime(sum))
      return 1;
    return 0;
  }
  if (dp[index][tight][sum] != -1)
    return dp[index][tight][sum];
  int ans = 0;
  int end = tight ? s[index] - '0' : 9;
  for (int i = 0; i <= end; i++)
  {
    int updatedSum = sum + i;
    bool updatedTight = tight & (i == s[index] - '0');
    ans += recursion(index + 1, updatedTight, updatedSum, s);
  }
  return dp[index][tight][sum] = ans;
}
void solve()
{
  int l, r;
  cin >> l >> r;
  string s1 = to_string(l - 1);
  string s2 = to_string(r);
  memset(dp, -1, sizeof(dp));
  int ans1 = recursion(0, 1, 0, s1);
  memset(dp, -1, sizeof(dp));
  int ans2 = recursion(0, 1, 0, s2);
  cout << ans2 - ans1 << endl;
}
signed main()
{
  int t = 1;
  cin >> t;
  while (t--)
  {
    solve();
  }
  return 0;
}

233. Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

Example 1:

Input: n = 13
Output: 6

Example 2:

Input: n = 0
Output: 0

Constraints:

• 0 <= n <= 10<sup>9</sup>

class Solution {
public:
    int dp[20][2][20];
    int recursion(string &s,int index,bool tight,int count){
        if(index==s.size()){
            return count;
        }
        if(dp[index][tight][count]!=-1) return dp[index][tight][count];
        int limit=tight?s[index]-'0':9;
        int ans=0;
        for(int i=0;i<=limit;i++){
          int updateCount= i==1? count+1:count;
          ans+=recursion(s,index+1,(tight & (i==s[index]-'0')),updateCount);
        }
        return dp[index][tight][count]=ans;

    }
    int countDigitOne(int n) {
        string s=to_string(n);
        memset(dp,-1,sizeof dp);
        return recursion(s,0,true,0);
    }
};

Digit Count

LOJ-1122Debug

Given a set of digits S , and an integer n , you have to find how many n -digit integers are there, which contain digits that belong to S and the difference between any two adjacent digits is not more than two.

Input

Input starts with an integer T (≤ 300) , denoting the number of test cases.

Each case contains two integers, m (1 ≤ m < 10) and n (1 ≤ n ≤ 10) . The next line will contain m integers (from 1 to 9) separated by spaces. These integers form the set S as described above. These integers will be distinct and given in ascending order.

Output

For each case, print the case number and the number of valid n -digit integers in a single line.

Sample

Notes

For the first case the valid integers are

1. 11
2. 13
3. 31
4. 33
5. 66

#include <bits/stdc++.h>
using namespace std;
int dp[12][100];
int recursion(vector<int> &arr, int index, int prev, int n)
{
  if (index == n)
    return 1;
  if (dp[index][prev] != -1)
    return dp[index][prev];
  int ans = 0;
  for (int i = 0; i < arr.size(); i++)
  {
    if (prev == 0 || abs(arr[i] - prev) <= 2)
    {
      ans += recursion(arr, index + 1, arr[i], n);
    }
  }
  return dp[index][prev] = ans;
}
void basicIO()
{
  int a, b;
  cin >> a >> b;
  cout << a + b << endl;
}
void solve(int a)
{
  int n, m;
  cin >> n >> m;
  vector<int> arr(n);
  for (int i = 0; i < n; i++)
  {
    cin >> arr[i];
  }
  memset(dp, -1, sizeof dp);
  cout << "Case " << a << ": ";
  cout << recursion(arr, 0, 0, m) << "\n";
}
int main()
{
  // basicIO();
  // Your cpp code here
  int t;
  cin >> t;
  int a = 1;
  while (t--)
  {
    solve(a++);
  }
  return 0;
}