1511D - Min Cost String - CodeForces Solution


brute force constructive algorithms graphs greedy strings *1600

Please click on ads to support us..

Python Code:

from sys import stdin
from collections import defaultdict
import string
input = stdin.readline

class Solution:
    def dfs(self, u):
        while self.G[u]:
            v = self.G[u].pop()
            self.dfs(v)
        self.tour.append(u)

    def find_tour(self):
        self.n, self.k = map(int, input().split())
        letters = string.ascii_lowercase[:self.k]; self.tour = []

        self.G = defaultdict(list)
        for l1 in letters:
            for l2 in letters:
                self.G[l1].append(l2)

        self.dfs('a')
        self.tour.pop()

        ans = []
        for i in range(self.n):
            ans.append(self.tour[i % len(self.tour)])

        print(''.join(ans))


solution_obj = Solution()
solution_obj.find_tour()


        






C++ Code:

#include <bits/stdc++.h>
#include <unordered_set>
#include <iostream>
#include <string>
using namespace std;


typedef long long int ll;
const int mod = 1e9 + 7;
#define INF 1e9
#define CLR(a) memset(a, 0, sizeof(a))
#define SET(a, val) memset(a, val, sizeof(a))


#define N 200005
void solve(int round)
{
    int n, k;
    int last = 0;
    string s = "";

    cin >> n >> k;

    while (s.size() < n) {
        for (int j1 = 0; (j1 < k) && (s.size() < n); j1++) {
            s += ('a' + j1);
            for (int j2 = j1+1; (j2 < k) && (s.size() < n); j2++) {
                s += ('a' + j1);
                s += ('a' + j2);
            }
        }
    }
    if (s.size() > n) {
        s.pop_back();
    }
    
    printf("%s\n", s.c_str());
}

int main()
{
#if 1
    std::ifstream in("C:\\Users\\user\\source\\repos\\ConsoleApplication1\\ConsoleApplication1\\test.txt", ::std::ios::binary);
    std::streambuf* cinbuf = std::cin.rdbuf();//save old buf
    std::cin.rdbuf(in.rdbuf());//redirect std::cin to in.txt!
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1;
    int round = 1;
    //cin >> tc;
    while (tc--) {
        solve(round);
        round++;
    }
    return 0;

}


Comments

Submit
0 Comments
More Questions

1712A - Wonderful Permutation
1712D - Empty Graph
1712B - Woeful Permutation
1712C - Sort Zero
1028B - Unnatural Conditions
735B - Urbanization
746C - Tram
1278B - A and B
1353D - Constructing the Array
1269C - Long Beautiful Integer
1076A - Minimizing the String
913C - Party Lemonade
1313A - Fast Food Restaurant
681A - A Good Contest
1585F - Non-equal Neighbours
747A - Display Size
285A - Slightly Decreasing Permutations
515C - Drazil and Factorial
1151E - Number of Components
1151F - Sonya and Informatics
556A - Case of the Zeros and Ones
867A - Between the Offices
1569A - Balanced Substring
260A - Adding Digits
1698C - 3SUM Closure
1029B - Creating the Contest
1421A - XORwice
1029A - Many Equal Substrings
1675D - Vertical Paths
1271C - Shawarma Tent