dp greedy implementation *1400

Please click on ads to support us..

Python Code:

length, num = [int(x) for x in input().split()]

if length == 1 and num == 0:
    print(0,0)

elif num == 0 or num > length * 9:
    print(-1,-1)
else:
    
    dp = [0] * (length - 1) + [1]
    for x in range(len(dp)):
        dp[x] += min(9,num - sum(dp))
    
    a = int("".join(list(reversed([str(x) for x in dp]))))
    
    dp = [0] * length
    for x in range(len(dp)):
        dp[x] += min(9,num - sum(dp))
    
    b = "".join([str(x) for x in dp])
    
    print(a,b)

C++ Code:

#include<bits/stdc++.h>
using namespace std;
int a[105];
int b[105];
int main(){
	int m , s , x;
	cin>>m>>s;
	x = s;
	if(m == 1 && s == 0){
		cout<<0<<" "<<0;
		return 0;
	}
	if(s == 0||s > m * 9){
		cout<<-1<<" "<<-1;
		return 0;
	}
	while(s != 0){
		if(a[1] == 0){
			a[1] = 1;
			s--;
			continue;
		}
		for(int i = m ; i >= 1 ;){
			if(a[i] != 9){
				a[i] ++ ;
				s--;
				break;
			}else{
				i--;
			}
		}
	}
	for(int i = 1 ; i <= m ; i++) cout<<a[i];
	cout<<" ";
	while(x != 0){
		for(int i = 1 ; i <= m ;){
			if(b[i] != 9){
				b[i] ++ ;
				x--;
				break;
			}else{
				i++;
			}
		}
	}
	for(int i = 1 ; i <= m ; i++) cout<<b[i];
}


Comments

Submit
0 Comments
More Questions

1302. Deepest Leaves Sum
1209. Remove All Adjacent Duplicates in String II
994. Rotting Oranges
983. Minimum Cost For Tickets
973. K Closest Points to Origin
969. Pancake Sorting
967. Numbers With Same Consecutive Differences
957. Prison Cells After N Days
946. Validate Stack Sequences
921. Minimum Add to Make Parentheses Valid
881. Boats to Save People
497. Random Point in Non-overlapping Rectangles
528. Random Pick with Weight
470. Implement Rand10() Using Rand7()
866. Prime Palindrome
1516A - Tit for Tat
622. Design Circular Queue
814. Binary Tree Pruning
791. Custom Sort String
787. Cheapest Flights Within K Stops
779. K-th Symbol in Grammar
701. Insert into a Binary Search Tree
429. N-ary Tree Level Order Traversal
739. Daily Temperatures
647. Palindromic Substrings
583. Delete Operation for Two Strings
518. Coin Change 2
516. Longest Palindromic Subsequence
468. Validate IP Address
450. Delete Node in a BST