列表

详情


OR2. Numeric Keypad

描述

The numberic keypad on your mobile phone looks like below:
123
456
789
0
suppose you are holding your mobile phone with single hand. Your thumb points at digit 1. Each time you can 1)press the digit your thumb pointing at.2)moveyour thumb right,3)move your thumb down. Moving your thumb left or up is not allowed.
By using the numeric keypad under above constrains, you can produce some numbers like 177 or 480 while producing other numbers like 590 or 52 is impossible.
Given a number K, find out the maximum number less than or equal to K that can be produced.

输入描述

the first line contains an integer T, the number of testcases.
Each testcase occupies a single line with an integer K.

For 50%of the data ,1<=K<=999.
For 100% of the data, 1<=K<=10^500,t<=20.

输出描述

for each testcase output one line, the maximum number less than or equal to the corresponding K that can be produced.

示例1

输入:

3
25
83
131

输出:

25
80
129

原站题解

C 解法, 执行用时: 2ms, 内存消耗: 200KB, 提交时间: 2019-11-30

#include<stdio.h>

int T,x[10],y[10];
char c[503],d[503];

void getxy()
{	int i;
	y[0]=4;
	for(i=1;i<=9;i++)y[i]=(i+2)/3;
	x[0]=2;
	for(i=1;i<=9;i++)x[i]=(i+2)%3+1;
}

int cango(char i,char j)
{	if(x[i-'0']<=x[j-'0']&&y[i-'0']<=y[j-'0'])return 1;
	else return 0;
}

int fun(int i,char pre)//i表示插入位置
{	char j,k;
	if(!c[i]){
		d[i]=0;
		return 1;
	}
	for(j=c[i];j>='0'&&!cango(pre,j);j--);
	if(j==c[i]){
		d[i]=j;
		if(fun(i+1,j))return 1;
		while(--j>='0'&&!cango(pre,j));
	}
	if(j<'0')return 0;
	d[i]=j;
	k=j=='0'?'0':'9';
	while(c[++i])d[i]=k;
	d[i]=0;
	return 1;
}

int main()
{
	int i;
	getxy();
	scanf("%d",&T);
	getchar();
	for(i=0;i<T;i++){
		c[0]='1';
		gets(c+1);
		fun(0,'1');
		printf("%s\n",d+1);
	}
}

C 解法, 执行用时: 2ms, 内存消耗: 280KB, 提交时间: 2022-01-28

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

int s[10][10] = {
    {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
    {9,8,7,6,5,4,3,2,1,0},
    {9,8,6,5,3,0,-1,-1,-1,-1},
    {9,6,-1,-1,-1,-1,-1,-1,-1,-1},
    {9,8,7,6,5,0,-1,-1,-1,-1},
    {9,8,6,0,-1,-1,-1,-1,-1,-1},
    {9,-1,-1,-1,-1,-1,-1,-1,-1,-1},
    {9,8,0,-1,-1,-1,-1,-1,-1,-1},
    {9,0,-1,-1,-1,-1,-1,-1,-1,-1},
    {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}
};

int count = 0;

bool cango(int i, int j){
    if (i == j) return true;
    bool flag = false;
    for(int k = 0; k < 10; k++) {
        if (s[i][k] == j) {
            flag = true;
            break;
        }
    }
    return flag;
}

void fill(char * c, int j) {
                    for(int l = j; l < 503; l++) {
                        if (c[l] == 0) {
                            break;
                        }
                        if (s[c[l]-'0'][0] != -1) {
                            if (c[l+1] != 0) {
                                c[l+1] = s[c[l]-'0'][0] + '0';
                            }
                        } else {
                            if (c[l+1] !=0) {
                                c[l+1] = c[l];
                            }
                        }
                    }
}

bool helper(char * c, int j) {
            //printf("!cnago==%s--,%d\n",c,j);
            c[j]--;
            bool flag = false;
            while(j == 0 || cango(c[j-1]-'0', c[j]-'0')) {
                if(s[c[j]-'0'][0] != -1) {
                    c[j+1] = s[c[j]-'0'][0] + '0';
                    fill(c,j+1);
                    flag = true;
                    break;
                } 
                c[j]--;
            }
            if (flag) {
                return true;
            }
            c[j]++;
            return false;
}

void deal(char c[]) {
    int j = 0;
    bool flag = true;
    for(int i = 1; i < 503; i++) {
        if (c[i] == 0) {
            break;
        }
        if (!cango(c[i-1]-'0',c[i]-'0')) {
            //printf("cnago==%s--,%d\n",c,i);
            flag = false;
            break;

        }
        j++;
    }
    if (flag) {
       printf("%s\n",c);
    } else {
        int t = 0;
        int flag = false;
        //return;
        while(s[c[j]-'0'][t] != -1) {
            if (s[c[j]-'0'+t] < c[j+1]){
                flag = true;
                break;
            }
            t++;
        }
        bool res_f = false;
        if (flag) {
            c[j+1] = s[c[j]-'0'+t] + '0';
            res_f = true;
        } else if (c[j] < c[j+1]){
            c[j+1] = c[j];
            res_f = true;
        }
        //printf("before fill:%s,j=%d\n",c,j);
        if (res_f) {
            fill(c,j+1);
            printf("%s\n",c);
            return;
        }
        if (cango(c[j]-'0', 0)) {
            for(int k = j + 1; k < 503; k++) {
                if (c[k] == 0) {
                    break;
                }
                c[k] = '0';
            }
        } else {
            //printf("jjj===%d",j);
            while (j >= 0) {
                if(helper(c, j)) {
                    break;
                }
                j--;
            }
        }
        printf("%s\n",c);
    }

}

int main()
{
    int n;
    char * data[21];
    scanf("%d",&n);
    getchar();
    for(int i = 0; i < n; i++) {
        char c[503] = {0};
        gets(c);
        deal(c);
    }
    
}

C++ 解法, 执行用时: 2ms, 内存消耗: 284KB, 提交时间: 2021-12-17

#include<bits/stdc++.h>
using namespace std;
#define debug printf("%d %s\n",__LINE__,__FUNCTION__);fflush(stdout)
using ll=long long;using i64=long long;using db=double;
using u32=unsigned int;using u64=unsigned long long;using db=double;
using pii=pair<int,int>;using vi=vector<int>;
using qi=queue<int>;using pqi=priority_queue<int>;using si=set<int>;
#define pb push_back
#define mk make_pair
#define ins insert
#define era erase
#define fi first
#define se second
#define lowbit(x) x&-x
#define ALL(a) a.begin(),a.end()
const int INF=0x3f3f3f3f;
const ll INFLL=0x3f3f3f3f3f3f3f3f;
const double PI=acos(-1.0);
template<class T>inline bool chkmin(T&a,T b){return b<a?a=b,true:false;}
template<class T>inline bool chkmax(T&a,T b){return a<b?a=b,true:false;}
int _w,_t;FILE* _f;
#define MULTI_CASES

const int N=502;
char s[N],ans[N];
bool G[12][12];
int n;

void init(){
    G[1][1]=G[1][2]=G[1][3]=G[1][4]=G[1][5]=G[1][6]=G[1][7]=G[1][8]=G[1][9]=G[1][0]=1;
    G[2][2]=G[2][3]=G[2][5]=G[2][6]=G[2][8]=G[2][9]=G[2][0]=1;
    G[3][3]=G[3][6]=G[3][9]=1;
    G[4][4]=G[4][5]=G[4][6]=G[4][7]=G[4][8]=G[4][9]=G[4][0]=1;
    G[5][5]=G[5][6]=G[5][8]=G[5][9]=G[5][0]=1;
    G[6][6]=G[6][9]=1;
    G[7][7]=G[7][8]=G[7][9]=G[7][0]=1;
    G[8][8]=G[8][9]=G[8][0]=1;
    G[9][9]=1;
    G[0][0]=1;
    ans[0]='1';
}

int can(){
    for(int i=1;i<n;i++){
        if(!G[s[i]-'0'][s[i+1]-'0']){
            return i;
        }
    }
    return n;
}

bool work(int u){
    // printf("work %d\n",u);
    for(int i=1;i<=u;i++){
        ans[i]=s[i];
    }
    if(u==n) return 1;
    ans[u+1]=0;
    // printf("ans=%s\n",ans+1);
    // printf("%d\n",s[u+1]-'0'-1);
    for(int d=s[u+1]-'0'-1;d>=0;d--){
        if(G[ans[u]-'0'][d]){
            ans[u+1]='0'+d;
            break;
        }
    }
    if(!ans[u+1]) return 0;
    for(int i=u+2;i<=n;i++){
        for(int d=9;d>=0;d--){
            if(G[ans[i-1]-'0'][d]){
                ans[i]='0'+d;
                break;
            }
        }
    }
    return 1;
}

void solve(){
    scanf("%s",s+1);
    n=strlen(s+1);
    ans[n+1]=0;
    int pos=can();
    for(int i=pos;i>=0;i--){
        if(work(i)){
            printf("%s\n",ans+1);return;
        }
    }
}

int main(){
    init();
    #ifdef MULTI_CASES
    _w=scanf("%d",&_t);while(_t--)
    #endif
    solve();
    return 0;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 308KB, 提交时间: 2022-07-08

#include<iostream>
#include<vector>
#include<cstring>
#include<string>

using namespace std;

int allc[4][3]={1,2,3,4,5,6,7,8,9,10,0,10};
int allmat[16][16];
void fillmat()
{
    memset(allmat,0,256*sizeof(int));
    for(int i1=0;i1<4;++i1)
        for(int j1=0;j1<3;++j1)
            for(int i2=i1;i2<4;++i2)
                for(int j2=j1;j2<3;++j2)
                    allmat[allc[i1][j1]][allc[i2][j2]]=1;
    return ;
}
void calStr(string oristr)
{
    int slen=oristr.size();
    char cstr[512];
    memset(cstr,'9',sizeof(char)*512);
    cstr[slen]='\0';
    int prem=0;
    int t=0;
    int pren=1;
    for(;t<slen;++t)
    {
        int ttd=oristr[t]-'0';
        prem=-1;
        for(int i=ttd;i>=0;--i)
        {
            if(allmat[pren][i])
            {
                prem=i;
                break;
            }
        }
        if(prem==-1)
            break;
        if(prem!=ttd)
        {
            cstr[t]=prem+'0';
            break;
        }
        pren=prem;
        cstr[t]=prem+'0';
    }
    if(prem==-1)
    {
        for(--t;t>=0;--t)
        {
            int ttd=cstr[t]-'0';
            prem=-1;
            if(t==0)
                pren=1;
            else
                pren=cstr[t-1]-'0';
            for(int i=ttd-1;i>=0;--i)
            {
                if(allmat[pren][i])
                {
                    cstr[t]=i+'0';
                    prem=i;
                    break;
                }
            }
            if(prem==-1)
                cstr[t]='9';
            else
            {
                cstr[t]=prem+'0';
                break;
            }
        }
    }
    else if(prem==0)
    {
        for(++t;t<slen;++t)
            cstr[t]='0';
    }
    if(cstr[0]=='0')
        printf("%s\n",cstr+1);
    else
        printf("%s\n",cstr);
    return ;
}
int main()
{
    //caldps();
    int T=0;
    fillmat();
    scanf("%d",&T);
    for(int i=0;i<T;++i)
    {
        string ts;
        cin>>ts;
        if(ts.size()==1)
            cout<<ts;
        else
            calStr(ts);
    }
    return 0;
}

C++14 解法, 执行用时: 2ms, 内存消耗: 348KB, 提交时间: 2020-08-08

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1005;
const int MAXM = 10;

int len_k = 0;
int k[MAXN], ans[MAXN];
int mx[10] = {0,9,9,9,9,9,9,9,9,9};

void read() {
    char ch = getchar();
    while(ch == '\n' || ch == ' ')  ch = getchar();
    len_k = 0;
    k[len_k] = 1;
    while(ch != '\n' && ch != EOF) {
        k[++len_k] = ch - '0';
        ch = getchar();
    }
}

int judge(int x, int y) {
    if(x == 0) {
        return y == 0;
    }
    if(y == 0) {
        return x == 0 || x%3 != 0;
    }
    int t = x%3, s = y%3;
    t = t==0 ? 3 : t;
    s = s==0 ? 3 : s;
    return (x<=y && t<=s);
}

// y >= x
int find(int x, int y) {
    if(x == 0) {
        return 0;
    }
    int ans = 0;
    int res = 10;
    int t = x%3 == 0 ? 3 : x%3;
    for(int i = 1; i < MAXM; ++i) {
        int j = i%3 == 0 ? 3 : i%3;
        if(i >= x && j >= t && i <= y) {
            if(y-i < res) {
                res = y - i;
                ans = i;
            }
        }
    }
    return ans;
}

void answer() {
    ans[0] = k[0];
    ans[1] = k[1];
    int i;
    for(i = 2; i <= len_k; ++i) {
        if(judge(k[i-1], k[i])) {
            ans[i] = k[i];
        } else {
            if(k[i] > k[i-1]) {
                ans[i] = find(k[i-1], k[i]);
            } else {
                if(k[i-1]%3 == 1 || k[i-1]%3 == 2) {
                    ans[i] = 0;
                } else {
                    ans[i] = ans[i-1];
                    while(ans[i-1] == ans[i])   --i;
                    ans[i] -= 1; 
                }
            }
            break;
        }
    }
    ++i;
    for(; i <= len_k; ++i) {
        ans[i] = mx[ans[i-1]];
    }
    for(int i = 1; i <= len_k; ++i) {
        putchar(ans[i]+'0');
    }
    putchar('\n');
}

int main() 
{
    int t;
    scanf("%d", &t);
    for(int i = t; i; --i) {
        read();
        answer();
    }
    return 0;
}

上一题