Ciel and New Menu

Problem code: CIEL8STR

All submissions for this problem are available.

Chef Ciel likes 8. Ciel's restaurant has many menus whose prices are multiples of 8. Now, Ciel has some digits written on a wooden board, and she'd like to cut the board to display prices in a new menu. In how many ways can Ciel choose consecutive digits from the board which denote integer multiples of 8?

In this problem, an integer must not have leading zeros. For example, 0, 8, 48, 1000 are integer multiples of 8, but 00, 5, 58, 01000 are not.

Input

An input contains a string S, which denotes digits written on the wooden board.

Output

Print the number of ways in which Ciel can choose consecutive digits which denote integer multiples of 8.

Constraints

1 ? |S| ? 1000000 (106), where |S| means the length of S.
S doesn't contain non-digit charactors.

Sample Input

5858

Sample Output

2

Output details

Ciel can choose 5, 8, 5, 8, 58, 85, 58, 585, 858 and 5858. Here, only 8 and 8 are multiples of 8.

Author: laycurse
Date Added: 21-11-2011
Time Limit: 1 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

> an integer must not have

lyrically @ 18 Dec 2011 09:41 PM
> an integer must not have leading zeros this means "extra" leading zeros?

@lyrically Yes. As examples

hiroto_adm @ 18 Dec 2011 09:44 PM
@lyrically Yes. As examples say 0 is valid, 00 is not valid.

How many test cases?

neil_812 @ 18 Dec 2011 09:47 PM
How many test cases?

@neil_812 many inputs, each

jingbo_adm @ 18 Dec 2011 09:49 PM
@neil_812 many inputs, each input just contains one line.

But how do we know when to

neil_812 @ 18 Dec 2011 09:50 PM
But how do we know when to stop taking input?

@neil_812 they are diffirent

jingbo_adm @ 18 Dec 2011 09:52 PM
@neil_812 they are diffirent files. Just reading one line from the standard input will be fine :)

is the explanation wrong?

foofoo @ 18 Dec 2011 09:55 PM
is the explanation wrong? what about 88?

@foofoo read the statement

jingbo_adm @ 18 Dec 2011 09:56 PM
@foofoo read the statement carefully :)

I didn't get the problem.

logic_max @ 18 Dec 2011 09:59 PM
I didn't get the problem. Ceil can chose two 8, but what about the two 5 that are left, they are not multiple of 8. Can you please elaborate a little?

@logic_max read the statement

jingbo_adm @ 18 Dec 2011 10:00 PM
@logic_max read the statement carefully :)

what should be the answer for

casy @ 18 Dec 2011 10:14 PM
what should be the answer for 0000 ?? 4 or 1

@casy As examples say 0 is

jingbo_adm @ 18 Dec 2011 10:16 PM
@casy As examples say 0 is valid, 00 is not valid.

@casy, it should be 4, not

thomasahle @ 18 Dec 2011 10:17 PM
@casy, it should be 4, not 10.

We have to print "how many

tarun29061990 @ 18 Dec 2011 10:28 PM
We have to print "how many ways" or we have to just print the no. of integer multiple of 8?

@tarun29061990 how many

jingbo_adm @ 18 Dec 2011 10:33 PM
@tarun29061990 how many

I mean to say that we have

tarun29061990 @ 18 Dec 2011 10:35 PM
I mean to say that we have print the no. of ways(like n!) or we have to just print the no. of integer multiples??

@tarun29061990 how many ways

jingbo_adm @ 18 Dec 2011 10:38 PM
@tarun29061990 how many ways like the sample input.

for 564, answer would be 1 or

tushicomeng @ 18 Dec 2011 10:39 PM
for 564, answer would be 1 or 2? she can cut 56 and 64 but separately. so do we have to just tell this number which will give two OR how many boards can she obtain simultaneously?

@tushicomeng consider them

jingbo_adm @ 18 Dec 2011 10:41 PM
@tushicomeng consider them isolately

If the input is 000 what will

shankey_adi @ 18 Dec 2011 10:41 PM
If the input is 000 what will be the output?

i wanna ask the same thing as

randomusername @ 18 Dec 2011 10:42 PM
i wanna ask the same thing as @tushicomeng. So in his case the answer is 2?

@shankey_adi 3

jingbo_adm @ 18 Dec 2011 10:45 PM
@shankey_adi 3

@randomusername the ways do

jingbo_adm @ 18 Dec 2011 10:46 PM
@randomusername the ways do not interact each other. you may think there are infinity copies. so it is 2

Why is O(S) solution giving

phantom11 @ 18 Dec 2011 10:51 PM
Why is O(S) solution giving TLE???

is just 0 a multiple of 8

architkhosla @ 18 Dec 2011 10:52 PM
is just 0 a multiple of 8 according to the question

When you submit and get WA,

thomasahle @ 18 Dec 2011 10:52 PM
When you submit and get WA, is that only for the 5858 case, or for the entire test suite?

TLE makes no sense!! :(

mayank.punetha @ 18 Dec 2011 10:52 PM
TLE makes no sense!! :(

@thomasahle for the entire

jingbo_adm @ 18 Dec 2011 10:56 PM
@thomasahle for the entire

@mayank.punetha huge input,

jingbo_adm @ 18 Dec 2011 10:57 PM
@mayank.punetha huge input, be careful

@phantom11 huge input, be

jingbo_adm @ 18 Dec 2011 10:57 PM
@phantom11 huge input, be careful

@architkhosla 0 is multiple

jingbo_adm @ 18 Dec 2011 10:59 PM
@architkhosla 0 is multiple of 8

I guess the answer would be 2

atiprashant @ 18 Dec 2011 11:00 PM
I guess the answer would be 2 for 500 and 4 for 5000. Am i right ? Getting wrong answer for such a long time :( :(

if answer in test case is

theunforgiven @ 18 Dec 2011 11:01 PM
if answer in test case is just 2 or 2! (factorial) ??????

time limit exceeding :|

rmagon @ 18 Dec 2011 11:01 PM
time limit exceeding :|

I think the problem statement

login_test @ 18 Dec 2011 11:04 PM
I think the problem statement is not very clear! Its confusing about the "number of ways". Its definitely not the number of ways of obtaining multiples of 8, but its number of multiples of 8 you can obtain assuming to have many copies of the same string. Correct me if I am wrong.

@theunforgiven

jingbo_adm @ 18 Dec 2011 11:04 PM
@theunforgiven 2=2!(factorial) I think :)

i am getting run time error

bonami @ 18 Dec 2011 11:07 PM
i am getting run time error ,can any one explain what it is ?my coding is correct ,pleaszz help

@login_test statement says

jingbo_adm @ 18 Dec 2011 11:07 PM
@login_test statement says "In how many ways can Ciel choose consecutive digits from the board". read this sentence carefully

@atiprashant Yes

jingbo_adm @ 18 Dec 2011 11:07 PM
@atiprashant Yes

Awesome problem ! :)

logic_max @ 18 Dec 2011 11:13 PM
Awesome problem ! :)

im getting TLE but ans is

theslyguy @ 18 Dec 2011 11:16 PM
im getting TLE but ans is correct for all test cases i consider. any advice ?

Admin If i mouse hover i am

bonami @ 18 Dec 2011 11:21 PM
Admin If i mouse hover i am not getting any message for run time exception ,pleaszz help

@mayank.punetha ALSO TO ALL.

jingbo_adm @ 18 Dec 2011 11:22 PM
@mayank.punetha ALSO TO ALL. be careful about the huge input. try to not use cin for C++, and use speed input in you language.

@bonami check the program

jingbo_adm @ 18 Dec 2011 11:23 PM
@bonami check the program yourself

@theslyguy speed up your

jingbo_adm @ 18 Dec 2011 11:27 PM
@theslyguy speed up your program

@Admin.............clear the

satya_patel @ 18 Dec 2011 11:31 PM
@Admin.............clear the meaning of how many ways..............what should be ans for 840?????????

my code works absolutely fine

atiprashant @ 18 Dec 2011 11:32 PM
my code works absolutely fine for all the cases in c Free on windows 7. However, its giving runtime errpr on gcc3.4.2. I have used strlen etc, can anyone tell me the header files to be included. I included stdio, string, math

@satya_patel read the post

jingbo_adm @ 18 Dec 2011 11:33 PM
@satya_patel read the post before. I think it is very clear now

@jingo_adm : How can the o/p

crazysaikat @ 18 Dec 2011 11:33 PM
@jingo_adm : How can the o/p for 564 be 3?? It should be 2(56 & 64).

@atiprashant check yourself

jingbo_adm @ 18 Dec 2011 11:36 PM
@atiprashant check yourself

@crazysaikat I have not said

jingbo_adm @ 18 Dec 2011 11:38 PM
@crazysaikat I have not said that

i am coding in java.....have

abhi_iit_10691 @ 18 Dec 2011 11:43 PM
i am coding in java.....have an O(S) algo.....there is just 1 loop....still it shows TLE....any suggestions admn???

@abhi_iit_10691 try your

jingbo_adm @ 18 Dec 2011 11:44 PM
@abhi_iit_10691 try your best to make it faster

the output for 001000 is 6,4

akshit_g @ 18 Dec 2011 11:47 PM
the output for 001000 is 6,4 or 1 ? my answer is 6 but it is not submitting..

@akshit_g think yourself or

jingbo_adm @ 18 Dec 2011 11:50 PM
@akshit_g think yourself or read the post before. I think the statement is very clear now

I would want to see the

coolnirdh @ 18 Dec 2011 11:51 PM
I would want to see the solutions for this problem in Java after the competition ends. Even I have a solution in O(s) and have tried my best to make it work, yet it always gave TLE :( Is it possible to get a successful answer by changing language?

@coolnirdh try your best to

jingbo_adm @ 18 Dec 2011 11:52 PM
@coolnirdh try your best to make it more faster

what is output for input

goelrinku @ 19 Dec 2011 12:04 AM
what is output for input 10000

@goelrinku Think yourself.

hiroto_adm @ 19 Dec 2011 12:05 AM
@goelrinku Think yourself. The statement is clear

Is it possible to submit

urnieza @ 19 Dec 2011 12:51 AM
Is it possible to submit solutions after contest to test them?

Should be written

anector @ 19 Dec 2011 01:01 AM
Should be written "charactEr"... (when constraints describing)

I have a solution now. can i

sharmasahil @ 19 Dec 2011 01:18 AM
I have a solution now. can i check it somewhere now as u do in test duration.?

u dereeeee..........plz i

sharmasahil @ 19 Dec 2011 01:28 AM
u dereeeee..........plz i want help

@sharmasahil: you can submit

balajiganapath @ 21 Dec 2011 06:09 PM
@sharmasahil: you can submit your solution in the practice section. http://www.codechef.com/problems/CIEL8STR

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions