Connection Status:
Competition Arena > Make737Hard

Make737Hard

TCO19 SRM 737 · 2018-09-18 · by Blue.Mary

TCO19 SRM 737 · 2018-09-18 · by Blue.Mary · Dynamic Programming, Math
Class Name: Make737Hard
Return Type: String
Method Name: make
Arg Types: (int)
Problem Statement

Problem Statement

Given a string S, a 737-triple in S is a triple (i,j,k) such that:

  • i, j, k are valid indices into S such that i < j < k
  • S[i] = '7', S[j] = '3', and S[k] = '7'.

You are given an int X. Your task is to generate and return any string S such that:

  • The length of S is between 1 and 373, inclusive.
  • The string S contains only characters '3' and '7'.
  • The number of 737-triples in S is exactly X.

You may assume that for the given constraints a solution always exists.

Constraints

  • X will be between 0 and 1,737,373, inclusive.
Examples
0)
1
Returns: "737"
1)
8
Returns: "773377"
2)
0
Returns: "777333"
3)
4
Returns: "73737"
4)
0
Returns: "777333"

Submissions are judged against all 109 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Make737Hard with a public method string make(int X) · 109 test cases · 2 s / 256 MB per case

Submitting as anonymous