Lucky Long

Problem code: LUCKY5

All submissions for this problem are available.

Chef loves lucky numbers. Everybody knows that lucky numbers are positive integers whose decimal representation contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Chef has a positive integer N. He can apply any of the following operations as many times as he want in any order:

  • Add 1 to the number N.
  • Take some digit of N and replace it by any non-zero digit.
  • Add any non-zero leading digit to N.

Find the minimum number of operations that is needed for changing N to the lucky number.

Input

The first line contains a single positive integer T, the number of test cases. T test cases follow. The only line of each test case contains a positive integer N without leading zeros.

Output

For each T test cases print one integer, the minimum number of operations that is needed for changing N to the lucky number.

Constraints

1 ? T ? 10

1 ? N < 10100000

Example

Input:
3
25
46
99

Output:
2
1
2

Author: witua
Date Added: 5-12-2011
Time Limit: 2 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

I am little confused with the

s1a3 @ 1 Feb 2012 03:39 PM
I am little confused with the third operation: does it mean we can we can 10^x to N?

I cannot understand the 2nd

phantom11 @ 1 Feb 2012 04:29 PM
I cannot understand the 2nd opertation : Does it mean that I can replace all occurence of a digit in a single step.For eg.242 becomes 343 in 1 step???

phantom11: no, you choose

witua @ 1 Feb 2012 04:36 PM
phantom11: no, you choose just one occurrence and replace it.

I am not clear on the 3rd

l1ghth0use @ 1 Feb 2012 05:22 PM
I am not clear on the 3rd operation. Add any non-zero leading digit (of what?) to N.

I think so it means 10^x

s1a3 @ 1 Feb 2012 05:28 PM
I think so it means 10^x

can anyone help me about what

iamhashemi @ 1 Feb 2012 05:44 PM
can anyone help me about what third step says?

I think 3rd step means we can

abhi92 @ 1 Feb 2012 06:09 PM
I think 3rd step means we can add any digit to left of number?

Can anyone please elaborate

ritesh_gupta @ 1 Feb 2012 06:53 PM
Can anyone please elaborate "Take some digit of N and replace it by any non-zero digit."?.

Please re-stat this

dewarists @ 1 Feb 2012 07:44 PM
Please re-stat this problem, with good example, its very confusing...

To all: First operation: add

witaliy_adm @ 1 Feb 2012 08:23 PM
To all: First operation: add 1 to the number N; If N is 7, after that operation N becomes 8. If N is 999, after that operation it becomes 1000. Second operation: choose any occurrence of any digit and repcale it by another digit. (475->479, 101 -> 111, 299 -> 199 and so on) Third operation: add any non-zero digit to the left of the decimal representation of N: 47 -> 247, 9999 -> 49999, 2474 -> 72474 and so on).

@admin--please clarify the

psingh871 @ 1 Feb 2012 08:29 PM
@admin--please clarify the question, i tried 2 meanings of the 3rd statement....i am not getting whether error is in my code or understanding the question.....

@psingh871: Third operation

witaliy_adm @ 1 Feb 2012 08:36 PM
@psingh871: Third operation is adding some leading digit to N. This means that if N has some decimal representation S (some string of digits, like "475" for N = 475), then it becomes dS, where d is some non-zero digit (1..9). For example: 7 -> 47, 85 -> 985, 123 -> 9123, 78 -> 178, 555 -> 5555, 47 -> 747, 47 -> 447 and so on.

@admin Is it mandatory to use

vineetdeoraj87 @ 1 Feb 2012 09:27 PM
@admin Is it mandatory to use all the operations atleast once?

No, it's not.

witaliy_adm @ 1 Feb 2012 09:32 PM
No, it's not.

what do you mean by take some

login_test @ 1 Feb 2012 09:38 PM
what do you mean by take some digit of N and replace it by any Non-zero digit?? What is this "some digit" ?? Some can be all digits! In 7532 I can take all the digits and replace it by 7 in a single operation. Or you mean I can take only one digit at a time??

@login_test: Actually, digit

witaliy_adm @ 1 Feb 2012 09:55 PM
@login_test: Actually, digit is a single character of decimal representation of N. So, by "digit" you can't assume "digits", hence you can take only one digit in each turn.

@witally_adm: Thank You! I

login_test @ 1 Feb 2012 10:06 PM
@witally_adm: Thank You! I think the correct statement should be "Take ANY digit of N and replace it by any non-zero digit." instead of "Take some digit of N and replace it by any non-zero digit." :)

The changed number(which is

tru3liar @ 1 Feb 2012 10:14 PM
The changed number(which is now lucky) should be >N ?

does the first and last

prateekk91 @ 1 Feb 2012 10:31 PM
does the first and last operation have any significance? and what would be the answer for 025? 2 or 3

@tru3liar: no

witaliy_adm @ 1 Feb 2012 10:54 PM
@tru3liar: no

@prateekk91: Your test is

witaliy_adm @ 1 Feb 2012 10:57 PM
@prateekk91: Your test is incorrect, because N can not contain leading zeros.

could i have any test case

tutum @ 1 Feb 2012 11:00 PM
could i have any test case for which 1st or 3rd operation is required..

It is giving wrong answer,

prashant170392 @ 1 Feb 2012 11:15 PM
It is giving wrong answer, since i applied only 2nd test case.....please provide us with more test cases.

one of my comment here is

dewarists @ 1 Feb 2012 11:19 PM
one of my comment here is deleted.. !!! please admin atleast let me know if you are deleting my comment... can please give me the reason why you deleted it !!

Y U NO ACCEPT C/C++ SOLUTION?

scientist1642 @ 1 Feb 2012 11:37 PM
Y U NO ACCEPT C/C++ SOLUTION?

I do not find any test case

juahn31 @ 1 Feb 2012 11:59 PM
I do not find any test case for which first and third rules are necesary, if someone gives an example of using first or third rules thanks!

What is the minimum number of

marcusflint @ 2 Feb 2012 12:23 AM
What is the minimum number of operation if N is already a lucky number ?

@marcusflint: it is 0.

witaliy_adm @ 2 Feb 2012 12:57 AM
@marcusflint: it is 0.

@admin.. please give me one

dewarists @ 2 Feb 2012 01:08 AM
@admin.. please give me one example where first or/and third op needs to be use...

@admin It seems that some

fura2 @ 2 Feb 2012 02:23 AM
@admin It seems that some test cases include CR characters. Could you check it?

Awesome Q!!!!

cooltodinesh @ 2 Feb 2012 04:42 AM
Awesome Q!!!!

Please clearify "Take some

poojits @ 2 Feb 2012 06:50 AM
Please clearify "Take some digit of N and replace it by any non-zero digit". Will changing a particular digit, change all the occurences of that digit in the number? (Ex: 6646 --->7747. Only 6 is changed to 7) Is this one operation or three?

if n is 10^99999 then how am

daryllopes89 @ 2 Feb 2012 10:34 AM
if n is 10^99999 then how am i suppose to assign it to a variable

@prashant170392 Please don't

hiroto_adm @ 2 Feb 2012 01:52 PM
@prashant170392 Please don't require additional test cases.

@fura2 You CANNOT assume the

hiroto_adm @ 2 Feb 2012 01:54 PM
@fura2 You CANNOT assume the Linux-style new lines. This is written in FAQ http://www.codechef.com/wiki/faq#Other_common_mistakes

@poojits It counted as three

hiroto_adm @ 2 Feb 2012 01:59 PM
@poojits It counted as three operations. The 2nd operation can change only one digit, not one kind of digits.

@Tool Please don't write any

hiroto_adm @ 2 Feb 2012 02:02 PM
@Tool Please don't write any tips on this problem. It is prohibited. ("Rules" says: Please do not discuss strategy, suggestions or tips in the comments during a live contest. Posting questions clarifying the problem statement is ok.)

@daryllopes89 Please think it

hiroto_adm @ 2 Feb 2012 02:02 PM
@daryllopes89 Please think it by yourself.

@munzirbm About the 3rd

hiroto_adm @ 2 Feb 2012 02:07 PM
@munzirbm About the 3rd operation: see comment by "witaliy_adm @ 1 Feb 2012 08:23 PM". The 3rd operation can add any digit to left of number N. About the second comment: Don't require additional test cases. Finding bugs in your code is your task.

@rushilpaul Read Rules:

hiroto_adm @ 2 Feb 2012 02:08 PM
@rushilpaul Read Rules: Please do not discuss strategy, suggestions or tips in the comments during a live contest. Posting questions clarifying the problem statement is ok.

That definitely wasn't a tip.

Tool @ 2 Feb 2012 05:26 PM
That definitely wasn't a tip. More of a "the system likely has an issue" comment. Since python solutions seem to have succeeded, i won't press anymore.

is "400" a lucky number?

professor @ 2 Feb 2012 07:55 PM
is "400" a lucky number?

@professor: no, it is not.

witaliy_adm @ 2 Feb 2012 08:23 PM
@professor: no, it is not.

max N is 10^100000, is it

darkdiver @ 2 Feb 2012 08:26 PM
max N is 10^100000, is it correct? Can I do zero leading number? like 400 -> 000? if 000 lucky? Are 004 lucky?

in a turn, 3 operations(may

cxplorer @ 2 Feb 2012 08:57 PM
in a turn, 3 operations(may be used 1,2 or all) will be counted 1 or every operation is counted 1 individually?77 and 44 lucky...?

@darkdiver: no, 004 is not a

witaliy_adm @ 2 Feb 2012 11:45 PM
@darkdiver: no, 004 is not a lucky number.

@flareneos: I did the same

rushilpaul @ 3 Feb 2012 05:49 AM
@flareneos: I did the same thing and even I'm getting a WA. Looks like some weird quirk

Yes, there is definitely

neil_812 @ 3 Feb 2012 05:50 AM
Yes, there is definitely something with the newline. I've been having the same problem (always WA) until just now, and the only difference in my most recent submission is that I stripped off the whitespace.

@admin Can any operation be

arnab_das @ 3 Feb 2012 10:51 AM
@admin Can any operation be applied consecutively to N? e.g. N= 25 -->24 -->44 can be done?

004->lucky number 2 steps or

tru3liar @ 3 Feb 2012 11:44 AM
004->lucky number 2 steps or 3?

@rushilpaul Yeah, these tasks

flareneos @ 3 Feb 2012 01:02 PM
@rushilpaul Yeah, these tasks were made to simply annoy u.. I wonder if a story about new line is true. Then why on Earth I get different things with same compiler on Windows? Moving to Linux -.-

Something must be wrong with

flareneos @ 3 Feb 2012 01:24 PM
Something must be wrong with the input, no other explanation..

@admin I feel that these

aman05 @ 3 Feb 2012 02:07 PM
@admin I feel that these comments are conflicting: witaliy_adm @ 2 Feb 2012 11:45 PM says that 004 is not a lucky number witaliy_adm @ 1 Feb 2012 10:57 PM says leading zeros are not allowed may I know is 00000 a valid test input.

@admin... seriously there is

dewarists @ 3 Feb 2012 03:25 PM
@admin... seriously there is some problem with the testcases, i am writing my code in C, and i seriously feels that there is CR character problem.. this problem converted to parsing problem.. instead focusing on main problem...

neil_812: what did you do

rushilpaul @ 3 Feb 2012 03:49 PM
neil_812: what did you do exactly? I have continuously been getting a WA. There are no whitespaces anywhere in the output. I've printed output like this: printf("%dn",ans);

Easy and a good one!

umangkedia @ 3 Feb 2012 10:55 PM
Easy and a good one!

@rushilpaul I used Python and

neil_812 @ 4 Feb 2012 04:41 AM
@rushilpaul I used Python and I just did n = raw_input().strip(). Without the strip() it got WA.

@admin is there any special

ikercasillas @ 4 Feb 2012 11:17 AM
@admin is there any special way for input or output .i am continously getting WA .can please tell me what it is?

@admin code works well in my

kp25 @ 4 Feb 2012 07:30 PM
@admin code works well in my pc,even it is correct for large input,ex:10^1000000..... but codechef saying wrong continously,what to do..??

same problem as kp

pratikjain1993 @ 5 Feb 2012 02:32 AM
same problem as kp 25...please comment...

same as kp25.. :((

aayush123 @ 5 Feb 2012 02:55 AM
same as kp25.. :((

Is the range given for N with

codersrikant @ 5 Feb 2012 04:25 AM
Is the range given for N with max < 10^100000 correct?

if someone entered 004 do we

c2tarun @ 5 Feb 2012 09:32 AM
if someone entered 004 do we have to consider it as one digit number or three digit number?

@codechef this is very sad

aayush123 @ 6 Feb 2012 12:20 AM
@codechef this is very sad instead of focussing on programming knowlegde u r stressing on other things.. really its sad ... try to focus on main thing.. @all problem is with whitespaces..

@c2tarun a positive integer N

calc_saransh @ 6 Feb 2012 12:56 AM
@c2tarun a positive integer N without leading zeros.

can i use only one of those

seddik @ 6 Feb 2012 02:36 AM
can i use only one of those operation or i've to use all of them , ex. can i use the second operation 3 times without using the first and the third operations ?!

What are problems with

darkdiver @ 6 Feb 2012 09:00 AM
What are problems with whitespase? Are input - output in example correct? One test on one line with 1013 without space?

Problem with input.

darkdiver @ 6 Feb 2012 09:08 AM
Problem with input.

This was so irritating.

ingridmorstrad @ 6 Feb 2012 03:22 PM
This was so irritating. Thanks to the comments I finally solved it after wasting almost 30 attempts, more than 90% of which would have been right if the input was right. Remember to check for whitespace at every input. Irritating.

what is problem with

anuprathi321 @ 6 Feb 2012 04:12 PM
what is problem with whitespaces? It runs perfectly on my machine, after submitting it says wrong answer.

is the minimum count within

bodmas @ 7 Feb 2012 12:28 AM
is the minimum count within int range?

@admin : plz clarify 23 -->

deswal161990 @ 7 Feb 2012 09:01 AM
@admin : plz clarify 23 --> 24 acc to 1st operation -->> 44 acc to 2nd operation.............is that a single operation or 2 ?

@bodmas: yes, it is.

witaliy_adm @ 8 Feb 2012 03:34 AM
@bodmas: yes, it is.

i did the question with just

deswal161990 @ 8 Feb 2012 09:07 AM
i did the question with just the 2nd operation nd its givin WA . but there is not even a single case where 1st or 3rd are working.........plzzz reply someone

can anyone tell why i am

pprateek @ 8 Feb 2012 07:24 PM
can anyone tell why i am getting runtime error in the following code http://www.codechef.com/viewsolution/838505 ... i have been trying a lot but not able to get it .. please help me .

hi there..... can anyone

multimandy @ 8 Feb 2012 07:53 PM
hi there..... can anyone explain me detail of these examples....i did not get it....pls explain me in deatil....

How the minimum count be

sachin1984 @ 8 Feb 2012 08:21 PM
How the minimum count be under int limits? if N = 10^100000 - 1, basically all 9s, then i would need to change all 9s to 4s or 7s to get to the luck number and in that case min count will be greater than int limits?

@admin what if the number

abhipranay @ 8 Feb 2012 11:55 PM
@admin what if the number entered in already a lucky number?

@admin can we have test cases

sanjayk @ 9 Feb 2012 03:15 PM
@admin can we have test cases with N > 10100000?

i meant N > 100000

sanjayk @ 9 Feb 2012 03:15 PM
i meant N > 100000

can we enter numbers which

abhipranay @ 9 Feb 2012 04:20 PM
can we enter numbers which are already lucky like 47,444 etc what should be the output for that?

@admin, Thanks for the last

bodmas @ 9 Feb 2012 11:16 PM
@admin, Thanks for the last reply. I want to be sure you understand what I mean. I meant to ask whether the minimum count is <= (2^31) - 1 ?

@bodmas: Yes, I understand

witaliy_adm @ 9 Feb 2012 11:57 PM
@bodmas: Yes, I understand you correct. I do not know why this is so "popular" question. You see, number can not contain more than 100000 digits. In the statement there is the operation of changing digit. Hence, in worst case, you will not need more than 10^5 operations! And 10^5 < (2^31)-1 It's obviously.

@abhipranay: the output for

witaliy_adm @ 9 Feb 2012 11:58 PM
@abhipranay: the output for such cases is 0.

frnz solve it using java its

tj91 @ 10 Feb 2012 10:24 PM
frnz solve it using java its easier ........

Why do i get the Runtime

lojzezust @ 11 Feb 2012 12:43 AM
Why do i get the Runtime Error? It works perfectly on my computer. I'm using Python.

Admins, Your problem

krunalmodi @ 11 Feb 2012 05:17 PM
Admins, Your problem description is faulty. It says "The only line of each test case contains a positive integer N without leading zeros." That means N != 044 But, it seems in the input, this kind of case happens. If we check for leading zeroes and skip that digit, judge says "wrong answer" http://www.codechef.com/viewsolution/844974 [ Check line 37 ] {044 -> 0} If we don't check leading zero and convert it in lucky number, judge accepts it {044 -> 1} http://www.codechef.com/viewsolution/844967 Using simple method without checking "leading zeroes" solution got accepted http://www.codechef.com/viewsolution/844980 [ But, according to problem description there should not be ANY leading zeroes - & If we ignore it - judge should accept the solution which it doesn't - Admins, should have listened to what kids were saying in above mentioned comments ] I know the problem is very simple - But, can't make assumptions like "If someone is raising doubts for easy problems, they are always wrong !"

@krunalmodi: You are right. I

anton_adm @ 14 Feb 2012 10:29 AM
@krunalmodi: You are right. I checked this condition during testing process but accidentally wrote assert(s[0]>='0') instead of assert(s[0]>'0'). But I think that this goof is not so critical.

what r the 3 conditions mean

kkk_99 @ 20 Feb 2012 12:22 AM
what r the 3 conditions mean

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions