首页 > 试题广场 >

数字构造

[编程题]数字构造

热度指数：1473 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

对于一个十进制数而言，它的数位和等于将它各位数字相加得到的和。比如 231 的数位和是 6，3179 的数位和是 20。

现在你知道某个十进制数的数位和等于 s，并且这个数不包含 0，且任意相邻的数位是不同的，比如 112 或者 102 都是不满足条件的。现在你想知道满足这样的条件的最大的数是多少?

数据范围： $1 \le s \le 42 \$

输入描述:

第一行包含一个整数𝑠

输出描述:

输出满足条件的最大整数。

示例1

输入

输出

示例2

输入

输出

算法知识视频讲解

wylu

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println(generate(Integer.parseInt(br.readLine())));
    }

    private static String generate(int s) {
        StringBuilder sb = new StringBuilder();
        if (s % 3 == 1) sb.append(1);
        for (int i = 0; i < s / 3; i++) sb.append("21");
        if (s % 3 == 2) sb.append(2);
        return sb.toString();
    }
}

发表于 2019-03-13 15:04:59 回复(1)

pein531

1和2是没有办法从1-9的数字中挑两个不一样的相加出来的，那么从3开始找规律：

对于3=1+2，要想数字尽可能的大，就要将大数放在前面，21是数位为3的最大数；

对于4=1+2+1（数位为4的数最大应该是三位数，而2放在前面会导致两个1相邻），同理得到最大的数为121；

对于5=2+1+2（从5开始基本就能发现，要想数字尽可能大，优先要保证数的位数尽可能多，那每一位上的数字就要尽可能小，而要保证相邻的数字不同，实际上只需要1和2两种数字就可以了），得到最大的数为212；

对于6=2+1+2+1，最大的数为2121；

对于7=1+2+1+2+1，最大的数为12121；

对于8=2+1+2+1+2，最大的数为21212；

……

当s%3=0时，最大数应该是s/3个21拼接而成；s%3=1时，最大数应该是s/3个12拼接而成再在末尾拼接个1；s%3=2时，最大数应该是s/3个21拼接而成再在末尾拼接个2。由于s=1或2时s/3=0，因此这个规律对1和2仍然成立。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int s = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        if(s % 3 == 1){
            for(int i = 0; i < s/3; i++) sb.append(12);
            sb.append(1);
        }else if(s % 3 == 2){
            for(int i = 0; i < s/3; i++) sb.append(21);
            sb.append(2);
        }else{
            for(int i = 0; i < s/3; i++) sb.append(21);
        }
        System.out.println(sb.toString());
    }
}

编辑于 2021-02-03 13:42:52 回复(1)

嘟嘟6668

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        while(scan.hasNext()) {
            int s=scan.nextInt();
            get(s);
        }
    }
    public static void get(int s){
        if(s==1){
            System.out.println(1);
        }else if(s==2){
            System.out.println(2);
        }else{
            if(s%3==0){
                for(int i=0;i<s/3;i++){
                    System.out.print("21");
                }
                System.out.println();
            }else if(s%3==1){
                for(int i=0;i<s/3;i++){
                    System.out.print("12");
                }
                System.out.println("1");
            }else{
                for(int i=0;i<s/3;i++){
                    System.out.print("21");
                }
                System.out.println("2");
            }
        }
    }
}

发表于 2019-05-08 21:59:52 回复(0)

黄宗文

def maxnum(n):
    if n%3 == 1:
        return "12"*(n//3)+"1"
    elif n%3 == 2:
        return "21"*(n//3)+"2"
    else:
        return "21"*(n//3)

if __name__ == "__main__":
    n = int(input())
    print(maxnum(n))

注意总结字符排列规律，以3为一个循环来看

发表于 2019-03-11 21:10:53 回复(0)

向宇回桌

import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n1 = sc.nextInt();int  n2 = n1;
        StringBuilder ans1 = new StringBuilder(), ans2 = new StringBuilder();
        boolean n1Flag = true;
        while (n1 > 0) {
            boolean upDateFlag1 = false;
            if (n1Flag) {
                if (n1 >= 2) { ans1.append(2); n1 -= 2;upDateFlag1 = true; }
            }
            else { ans1.append(1); n1-=1; upDateFlag1 = true;}
            n1Flag = !n1Flag;
            if (!upDateFlag1) {
                ans1 = new StringBuilder();
                ans1.append(-1);
                break;
            }
        }
        boolean n2Flag = true;
        while (n2 > 0) {
            boolean upDateFlag2 = false;
            if (n2Flag) { ans2.append(1); n2-=1; upDateFlag2 = true;}
            else {
                if (n2 >= 2){ ans2.append(2); n2-=2;upDateFlag2 = true;}
            }
            n2Flag = !n2Flag;
            if (!upDateFlag2) {
                ans2 = new StringBuilder();
                ans2.append(-1);
                break;
            }
        }
        BigInteger b1 = new BigInteger(ans1.toString());
        BigInteger b2 = new BigInteger(ans2.toString());
        System.out.println(b1.max(b2));
    }
}

发表于 2019-03-02 15:46:16 回复(0)

ChessC

//找规律的题，那么最好的情况就是拆成21这个没问题吧，我的目标就是21这个串尽可能的长
//那么其实就是观察被3除的余数，如果是1或者2，这个是没办法的，直接添加相应的1或2，剩下的是能够被3整除的，那么就全部变成21连续
//提交中看到的一位兄弟写的代码我觉得巧妙在于先放余数1的情况
//因为21是我的核心部分，肯定是以2开头，1结尾，那么我先解决余数1即可。
#include <iostream>
#include <string>
using namespace std;
int main(){
    int s;
    cin>>s;
    string res;
    if(s % 3 == 1) 
        res+="1";
    for(int i = 0; i < s/3; ++i){
        res += "21";
    }
    if(s % 3 == 2){
        res+="2";
    }
    cout << res << endl;
    return 0;
}

发表于 2019-02-28 23:11:10 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>

using namespace std;

int main()
{     int s;     while(cin>>s){         int n = s/3;         switch(s%3){             case 0:{                 for(int i=0;i<n;i++)                     cout<<"21";                 break;             }             case 1:{                 cout<<"1";                 for(int i=0;i<n;i++)                     cout<<"21";                 break;             }             case 2:{                 cout<<"2";                 for(int i=0;i<n;i++)                     cout<<"12";                 break;             }         }         cout<<endl;      }     return 0;
}

发表于 2019-01-27 01:55:11 回复(0)

C/C++

爬上♪键盘♬

#include<iostream>
#include<math.h>
using namespace std;
int main(){
    int s;
    while(cin>>s){
        int k = 0;
        int sum = 0;
        if(s==1||s==2){
            cout<<s<<endl;
            continue;
        }
        if(s%3==0){
            for(int i=0;i<s/3;++i)
                cout<<21;
            cout<<endl;
        }
        if(s%3==1){
            cout<<1;
            for(int i=0;i<s/3;++i)
                cout<<21;
            cout<<endl;
        }
        if(s%3==2){
            for(int i=0;i<s/3;++i)
                cout<<21;
            cout<<2<<endl;
        }
    }
    return 0;
}

发表于 2020-08-07 10:17:52 回复(0)

皮蛋秀柚秋

#include<bits/stdc++.h>
using namespace std;
int main(){
    int s;
    cin>>s;
    if(s==1) cout<<1;
    else if(s==2) cout<<2;
    // 贪心原则 所有数字都为1时整数最长也最大
    // 由于相邻的数字不能相同，就把不符合条件的相邻两个1转化成2，
    // 尽可能少的减少数字长度
    // 也即每有一个3就转换成字符串"12"
    else{
        string str = "";
        while(s>=3){
            str+="12";
            s-=3;
        }
        if(s==1) str+="1";
        else if(s==2) str = "2"+str;
        else reverse(str.begin(),str.end());
        cout<<str<<endl;
    }
}

发表于 2020-06-16 00:20:48 回复(0)

嘀嘀复嘀嘀

#include<bits/stdc++.h>
using namespace std;
int main()
{

	int n;
	cin >> n;
	int tmp = n;
	if (n % 3 == 1)
	{
		int flag = 1;
		while (tmp)
		{
			cout << flag;
			tmp -= flag;
			flag = 3 - flag;
		}
	}
	else
	{
		int flag = 2;
		while (tmp)
		{
			cout << flag;
			tmp -= flag;
			flag = 3 - flag;
		}
	}
}
/*

*/

发表于 2020-06-13 17:24:10 回复(0)

Shelven丶

#include<bits/stdc++.h>

using namespace std;

int main()
{
	int z;
	cin >> z;
	string s;
	while (z > 3)
	{
		z -= 3;
		s += "21";
	}
	switch (z % 3)
	{
	case 0:
		s += "21";
		break;
	case 1:
		s = "1" + s;
		break;
	case 2:
		s += "2";
		break;
	}
	cout << s;
}

发表于 2020-04-10 21:54:12 回复(0)

二手独轮车

#include <bits/stdc++.h>
using namespace std;
int main()
{
	string s;
	int a,m,n; cin >> a;
	m = a / 3;
	n = a % 3;
	if (a == 1)
		cout << "1" ;
	if (a == 2)
		cout << "2" ;
	if (a >= 3)
	{
		if (n == 0)
		{
			for (int i = 0; i < m; i++)
				s += "21";
		}
		if (n == 1)
		{
			for (int j = 0; j < m; j++)
				s += "12";
			s += "1";
		}
		if (n == 2)
		{
			for (int k = 0; k < m; k++)
				s += "21";
			s += "2";
		}
	}
	cout <<s;
	return 0;
}

发表于 2019-12-06 20:58:34 回复(0)

C/C++

海问香12138

#include <stdio.h>

int s;

int main()
{
	int t;
	scanf("%d",&s);
	if(s<3)
	{
		printf("%d\n",s);
		return 0;
	}
	t = s % 3;
	if(t==0)
	{
		for(t=0;t<s/3;t++)
		{
			putchar('2');
			putchar('1');
		}
		putchar('\n');
		return 0;
	}
	if(t==1)
	{
		putchar('1');
		for(t=0,s--;t<s/3;t++)
		{
			putchar('2');
			putchar('1');
		}
		putchar('\n');
		return 0;
	}
	for(t=0;t<s/3;t++)
	{
		putchar('2');
		putchar('1');
	}
	puts("2");
	return 0;
}

发表于 2019-08-19 17:13:32 回复(0)

Ladybug5

import java.util.Arrays;
import java.util.Scanner;

/**
* @author zcl
*/
public class Main {
    public static void deal(int i,int j)
    {
    if(i==j) {
        for(int k=0;k<i;k++) {
            System.out.print(2);
            System.out.print(1);
        }
    }
    else if(i-j==1) {
        System.out.print(2);
        for(int k=0;k<i-1;k++) {
            System.out.print(1);
            System.out.print(2);
        }
    }
    else {
        System.out.print(1);
        for(int k=0;k<j-1;k++) {
            System.out.print(2);
            System.out.print(1);
        }
    }
    }
        public static void main(String[] args) {

Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for(int i=0;i<=n;i++) {
    for(int j=0;j<=n;j++) {
        if(2*i+j==n) {
            if(i-j==0||Math.abs(i-j)==1) {
                deal(i,j);
                break;
            }
        }
    }
}

}
}

发表于 2019-07-14 15:58:18 回复(0)

C/C++

咸鱼儿

#include<stdio.h>
int main()
{
    int s = 0;
    int n = 0, m = 0;
    char str[50] = {0};
    
    scanf("%d",&s);
    n = s % 3;
    m = s / 3;
    
    if(1 == n)
    {
        while(m--)
        {
            strcat(str, "12");
        }
        strcat(str, "1");
    }
    else if(2 == n)
    {
        while(m--)
        {
            strcat(str, "21");
        }
         strcat(str, "2");
    }
    else
    {
        while(m--)
        {
            strcat(str, "21");
        }
    }
    printf("%s\n",str);
}

发表于 2019-05-05 21:35:34 回复(0)

Java小白..

import java.util.Scanner;
import java.math.BigInteger;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int s=sc.nextInt();
String A="21";
String B="1";
String C="2";
if(s%3==0){
int a=s/3;
//String A=null;
for(int i=1;i<a;i++){
A=A+"21";
}
System.out.println(new BigInteger(A));
}
if(s%3==1){
int b=s/3;
//String B="1";
for(int i=0;i<b;i++){
B=B+"21";
}
System.out.println(new BigInteger(B));
}
if(s%3==2){
int c=s/3;
//String C="2";
for(int i=0;i<c;i++){
C=C+"12";
}
System.out.println(new BigInteger(C));
}
}

}

发表于 2019-03-09 21:27:06 回复(0)

C/C++

watle自动机

DFS（可能我想多了TAT）

#include <stdio.h>
#include <string.h>
#define maxlen 30
int s;
char res[maxlen],maxres[maxlen];
void Dfs(int cur,int num){
    int i;
    if(num==0){
        res[cur]='\0';
        if((strcmp(res,"\0")==0) || (strcmp(res,maxres)>0))
            strcpy(maxres,res);
        return;
    }
    for(i=1;i<=2;i++){
        if(res[cur]=='0'){
            if(num-i<0 || res[cur-1]==i+'0')
                continue;
            res[cur]=i+'0';
            Dfs(cur+1,num-i);
            res[cur]='0';
        }
    }
}
int main()
{
    scanf("%d",&s);
    memset(res,'0',sizeof(res));
    memset(maxres,'\0',sizeof(maxres));
    Dfs(0,s);
    printf("%s\n",maxres);
    return 0;
}

发表于 2019-03-02 23:09:01 回复(0)