Friday, January 6, 2012

Codeforces Beta Round #91 (Div. 2 Only) - B. Lucky Substring

problem statement
After reading the problem statement carefully and checking the sample test cases, I noticed this part of the problem "needs the lexicographically minimum one", and thought by myself if it is gonna be a substring of input and lucky and lexicographically minimum one, then it has to be "4" or "7" because other substrings that are lucky contain 4 and 7, and there is no lucky number other than "4" or "7" that is repeated more times than "4" or "7" because at least the lucky number is going to be "44", "77", "47", "74", and at this cases "4" and "7" are repeated more times than these substrings.
So I just iterated through input string and counted number of 4's and number of  7's, if there is no 4 or 7, then output -1, otherwise if cnt7 is less than cnt4 output 4 else output 7.

No comments:

Post a Comment

USACO - Prime Palindromes

I just skimmed the problem statement and panicked of the high boundary of the input, but something inside told me don't worry everyth...