1. Cards

topic description

Xiaolan has a lot of number cards, and each card has the numbers 0 to 9 on it.

Xiaolan is going to use these cards to spell some numbers. He wants to spell positive integers starting from 1, and save each one. The cards cannot be used to spell other numbers.

Xiaolan wants to know how much she can spell from 1.

For example, when Xiaolan has 30 cards, including 3 cards from 0 to 9, Xiaolan can spell out 1 to 10, but when spelling 11, there is only one card 1, which is not enough to spell out 11.

Now Xiaolan has 2021 cards from 0 to 9 in his hand, a total of 20210 cards. How many cards can Xiaolan get from 1?

Tip: It is recommended to use computer programming to solve the problem.

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int s[10];
bool check(int x) {
  while (x) {
    int t = x % 10;
    x = x / 10;
    if (--s[t] < 0) return false;
  }
  return true;
}

int main() {
  for (int i = 0; i < 10; i++) s[i] = 2021;
  for (int i = 1;; i++) {
    if (!check(i)) {
      cout << i - 1 << endl;
      return 0;
    }
  }
}

2. straight line

topic description

In a plane Cartesian coordinate system, two points can define a straight line.

If there are multiple points on a straight line, then the straight line determined by any two of these points is the same.

Given 2 × 3 integer points on the plane {(x, y)|0 ≤ x < 2, 0 ≤ y < 3, x ∈ Z, y ∈ Z},

That is, a point whose abscissa is an integer between 0 and 1 (inclusive), and whose ordinate is an integer between 0 and 2 (inclusive).

A total of 11 different straight lines are determined by these points.

Given 20 × 21 integer points on the plane {(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z},

That is, a point whose abscissa is an integer between 0 and 19 (inclusive), and whose ordinate is an integer between 0 and 20 (inclusive).

May I ask how many different straight lines are determined by these points?

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<math.h>
using namespace std;
const int N=200000;
int n=0;
struct Line
{
    double k;
    double b;
    bool operator < (const Line& t) const  //copy over
    {
        // If k is different, the smaller k comes first
        if(k!=t.k) return k<t.k;
        // If k is the same, the smaller b comes first
        return b<t.b;
    }
}l[N];

int main()
{
    //enumerate all pairs
    for(int x1=0;x1<20;x1++)
    {
        for(int y1=0;y1<21;y1++)
        {
            for(int x2=0;x2<20;x2++)
            {
                for(int y2=0;y2<21;y2++)
                if(x1!=x2)
                {
                    double k=(double)(y2-y1)/(x2-x1);
                    double b=y2-k*x2;
                   
                    l[n++]={k,b};
                }
            }
        }
    }
    sort(l,l+n);
    int res=1;
    for(int i=1;i<n;i++)
    {
        if(fabs(l[i].k-l[i-1].k)>1e-8||fabs(l[i].b-l[i-1].b)>1e-8)
        res++;
    }
    cout<<res+20<<endl;//Consider the case where the slope does not exist
    return 0;
}

2. Cargo placement

topic description

Xiaolan has an oversized warehouse that can store a lot of goods.

Now, Xiaolan has n boxes of goods to be placed in the warehouse, and each box of goods is a regular cube.

Xiaolan stipulates three mutually perpendicular directions of length, width, and height. The sides of each box of goods must be strictly parallel to the length, width, and height.

Xiaolan hopes that all the goods will eventually be arranged in one big cube. That is, stack L, W, and H goods in the directions of length, width, and height, satisfying n = L × W × H.

Given n, how many schemes for stacking goods meet the requirements.

For example, when n = 4, there are the following 6 schemes: 1×1×4, 1×2×2, 1×4×1, 2×1×2, 2×2×1, 4×1×1.

Excuse me, when n = 2021041820210418 (note that there are 16 digits), how many kinds are there in total

plan?

Tip: It is recommended to use computer programming to solve the problem.

#include <bits/stdc++.h>
using namespace std;
long long int a[3031];
long long int n=2021041820210418;
long long int ans=0;
void fun()
{
    for(long long int i=1;i*i<=n;i++)
    {
        if(n%i==0)
        {
            a[ans++]=i;
            if(i*i!=n)
            a[ans++]=n/i;
        }
 
    }
}//store approximation
int main()
{
    fun();
    long long int sum=0;//enumerate
    for(long long int i=0;i<ans;i++)
    {
        for(long long int j=0;j<ans;j++)
        {
            for(long long int k=0;k<ans;k++)
            {
                if(a[i]*a[j]*a[k]==n)
                    sum++;
            }
        }
    }
    cout<<sum;
    return 0;
}

4. Path

topic description

Xiaolan was very happy after learning the shortest path. He defined a special graph and hoped to find the shortest path in the graph.

Xiaolan's graph consists of 2021 nodes, numbered 1 to 2021 in sequence.

For two different nodes a, b, if the absolute value of the difference between a and b is greater than 21, there is no edge connection between the two nodes;

If the absolute value of the difference between a and b is less than or equal to 21, there is an undirected edge whose length is the least common multiple of a and b between the two points.

For example: there is no edge connection between node 1 and node 23; there is an undirected edge between node 3 and node 24 with a length of 24;

There is an undirected edge between node 15 and node 25 with length 75.

Please calculate, what is the shortest path length between node 1 and node 2021.

Tip: It is recommended to use computer programming to solve the problem.

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=2200,M=N*50;

int n;
int h[N],e[M],w[M],ne[M],idx;
int q[N],dist[N];
bool st[N];

int gcd(int a,int b)//Euclidean Algorithm Rolling and dividing (recursive) to find the greatest common divisor
{
    return b ? gcd(b,a%b):a;
}

void add(int a,int b,int c)//Add an edge a->b with edge weight c
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

void spfa()//Find the shortest distance from point 1 to point n
{
    int hh=0,tt=0;
    memset(dist, 0x3f,sizeof dist);
    dist[1]=0;
    q[tt ++]=1;
    st[1]=true;

    while(hh!=tt)
    {
        int t=q[hh ++];
        if(hh==N) hh=0;
        st[t]=false;

        for(int i=h[t]; i!=-1; i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                if(!st[j])  //If j already exists in the queue, there is no need to insert j repeatedly
                {
                    q[tt++]=j;
                    if(tt==N) tt=0;
                    st[j]=true;
                }
            }
        }
    }
}

int main()
{
    n=2021;
    memset(h,-1,sizeof h);
    for(int i=1; i<=n; i++)
    {
        for(int j=max(1,i-21); j<=min(n,i+21); j++)
        {
            int d=gcd(i,j);
            // Least common multiple Two numbers multiply/greatest common divisor i*j/d
            add(i,j,i*j/d);
        }
    }
    spfa();
    printf("%d\n",dist[n]);
    return 0;
}

5. Space

topic description

Xiaolan is going to use 256MB of memory space to open an array, and each element of the array is a 32-bit binary integer.

How many 32-bit binary integers can be stored in 256MB if the space occupied by the program and the auxiliary space required for maintaining memory are not considered?

#include <stdio.h>
int main() {
    printf("%d", 256 >> 2 << 20);
}

6. Weight weighing

topic description

You have a balance and N weights, and the weights of these N weights are W1, W2, ... , WN in sequence.

Please calculate how many different weights you can weigh in total?

Note that weights can be placed on both sides of the balance.

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 110, M = 2e5 + 10;
int n,m;
int a[N];
bool dp[N][M];//dp[i][j] represents the first i weights, the set of j is weighed, the value is a bool value, and it is true if j can be weighed
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],m+=a[i];
    dp[0][0]=true;
    for (int i = 1; i <= n;i++)//the first i
        for (int j = 0; j <=m;j++)//Weigh out j
            dp[i][j]=dp[i-1][j]||dp[i-1][j+a[i]]||dp[i-1][abs(j-a[i])];
    int ans=0;
    for(int i=1;i<=m;i++)
        if(dp[n][i])
            ans++;
    cout<<ans;
    return 0;
}

7. Bracket sequence

topic description

Given a sequence of parentheses, it is required to add as few parentheses as possible to make the sequence of parentheses legal.

When the addition is completed, different addition results will be produced. How many essentially different addition results are there?

Two results are substantially different in the sense that there exists a position where one result is an opening parenthesis and the other is a closing parenthesis.

For example, for the parenthesis sequence ((()), you only need to add two parentheses to make it legal

There are several different addition results: ()()(), ()(()), (())(), (()()) and ((())).

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5052;
const long long int MOD = 1e9 + 7;

int dp[maxn][maxn];
bool vis[maxn][maxn];
char str[maxn];
int n;

long long int mod(long long int x) { return x % MOD; }

long long int GetAns() {
  memset(dp, 0, sizeof dp);
  memset(vis, 0, sizeof vis);
  dp[0][0] = 1;
  vis[0][0] = true;

  for (int i = 1; i <= n; i++) {
    if (str[i - 1] == '(') {
      for (int j = 1; j <= n; j++) {
        dp[i][j] = dp[i - 1][j - 1];
        vis[i][j] = vis[i - 1][j - 1];
      }
    } else {
      dp[i][0] = mod(dp[i - 1][0] + dp[i - 1][1]);
      vis[i][0] = vis[i-1][0] | vis[i-1][1];
      for (int j = 1; j <= n; j++) {
        dp[i][j] = mod(dp[i - 1][j + 1] + dp[i][j - 1]);
        vis[i][j] = vis[i - 1][j + 1] | vis[i][j - 1];
      }
    }
  }
  for (int i = 0; i <= n; i++) {
    if (vis[n][i] != 0) {
      return dp[n][i];
    }
  }
  return -1;
}
int main() {
  scanf("%s", str);
  n = strlen(str);

  long long int ansL = GetAns();

  reverse(str, str + n);
  for (int i = 0; i < n; i++) {
    if (str[i] == ')') {
      str[i] = '(';
    } else {
      str[i] = ')';
    }
  }
  long long int ansR = GetAns();

  printf("%lld\n", mod(ansL * ansR));
  return 0;
}

8. Time display

topic description

Xiaolan wants to cooperate with a friend to develop a time display website.

On the server, the friend has obtained the current time, represented by an integer.

The value is the number of milliseconds that have passed since January 1, 1970 00:00:00 to the current time.

Now, Xiaolan wants to display this time on the client.

Xiaolan does not need to display the year, month, and day, but only needs to display the hour, minute, and second, and does not need to display the millisecond, just discard it.

Given a time represented by an integer, please output the hours, minutes and seconds corresponding to this time.

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long LL;
int main()
{
    int t;
    cin>>t;
    while(t--){
        LL ss;
        scanf("%lld",&m);
        int h=ss/(3600*1000)%24;
        int m=ss/(60*1000)%60;
        int s=ss/(1000)%60;
        printf("%02d:%02d:%02d\n",h,m,s);
   }
    return 0;
}