SMILEY1807 - 1807
There is a SmileyLand of angels. The queen of all angels Smiley1807 loves the number 1807. She is so much obsessed with 1807 that she asked her programmer friend to write a program to find the length of the largest sub sequence having digits 1, 8, 0 and 7 in order. For example if given sequence is 1800777700088888000777 then one of the largest sub sequence satisfying the above condition is 1800000000777 (there is one more possibility of 1888888000777) and hence the length of largest sub sequence is 13.
Input
The input contains only one test case.
The test case consist of only one sequence which may be as long as 10^6. There are only 1, 8, 0 or 7 present in the input sequence.
Output
Output contains only one line containing the length of the largest sub-sequence.
Example
Input: 1800777700088888000777 Output: 13
Explanation
1800000000777 is the largest sub-sequence
hide comments
|
shrey_devep:
2021-02-12 10:51:41
Just to make problem statement clear.
|
|
kumar_anubhav:
2020-09-29 19:54:46
whether we have to tell the largest subsequence which may or may not contain all 1,8,0,7 but it order or largest subsequence having all digits 1,8,0,7 and in order as well ??
|
|
horro:
2020-07-02 12:44:22
simple recursion with memo!! |
|
mrdevesh_00:
2020-06-26 19:18:57
got tle in recursion!! |
|
nadstratosfer:
2019-07-25 19:00:26
Good constraints, optimized the hell of my DP solution but couldn't get 0.00s until I was forced to think of something better. Python passes with both methods as well. Nice problem. |
|
~:
2017-02-14 18:01:51
Not a DP Problem |
|
vengatesh15:
2017-01-27 16:04:25
AC in 1 go Think simple.... |
|
madhavgaba:
2017-01-03 10:03:10
O(n^2) won't pass Last edit: 2017-01-04 10:20:14 |
|
dwij28:
2016-10-05 22:53:53
I hate it when I write a beautiful recursion and it gives a TLE. I did it with DP but there should be some questions where recursion can pass too. Anyways it is a nice problem :) |
|
hash7:
2016-05-16 16:13:49
qsn is very simple .can use adhoc logic as well .. recursion causes tle Last edit: 2016-05-16 16:45:16 |
| Added by: | Amitayush Thakur |
| Date: | 2015-08-22 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | MAWK BC C NCSHARP CSHARP C++ 4.3.2 CPP CPP14 C99 COFFEE LISP sbcl LISP clisp DART FORTH HASK JAVA JULIA KTLN OCT PROLOG PYTHON PYPY3 PYTHON3 PY_NBC R RACKET SCALA SQLITE SWIFT UNLAMBDA |
| Resource: | Own problem made for college competition CodeNite-1 |
RSS