10176 - Ocean Deep ! - Make it shallow !!

[Wei]

THX~~~ I got an AC~~~

[sunny]

how 2 solve the prob 10176 & 10551 . i tried by converting the whole number into decimal & then doing the modulas. but i got TLE on both of the prob.but my bigint code is not so slow.

is there any other approaches?
any1 pls help me...

[helloneo]

about 10551

you're not supposed to get TLE for this problem..
and you don't need to use "big int" ..
because it's modulor operation..

just remember that..

(a+b) mod m = ((a mod m) + (b mod m) ) mod m

[yukisama]

hi all, i try this question because i really love the song
however i cannot solve the problem (WA)

could anyone help and give me some critical test data? thanks a lot
i don't post my problem as i simply use the hints from the old posts (hope i understand the hint correctly)

here are the data sets that i had used:

Code: Select all

100000000000000001111111111110111111111111111111000#

101111111111111111#

1#

010101#

11111111111111100#



1011111111111111101#

11111111111111111#

111111111111111110000000000000000000000000000000000#

1 00000000000000000 11111111111111110#

1 00000000000000001 11111111111111101#

1 00000000000000010 11111111111111100#

1 00000000000000011 11111111111111011#

1 00000000000000100 11111111111111010#

1 00000000000000101 11111111111111001#

1 00000000000000110 11111111111111000#

1 00000000000000111 11111111111110111#

1 00000000000001000 11111111111110110#

1 00000000000001001 11111111111110101#

1100111111111111100 11000000000000000#

1111110000000000000 00001111111111100#

11111111111111111

11111111111111111

11111111111111111

00000000000000000

00000000000000000#

110011111111111110011#

11111111111111111

11111111111111111

11111111111111111#



00000000000000001

00000000000000010

00000000000000100

00000000000001000

00000000000010000

00000000000100000

00000000001000000

00000000010000000

00000000100000000

00000001000000000

00000010000000000

00000100000000000

00001000000000000

00010000000000000

00100000000000000

01000000000000000

10000000000000000#



11111111111111110

00000000000000001

11111111111111111#



10101010101010101

01010101010101010#

answers from my program:

Code: Select all

NO
NO
NO
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES

[daveon]

Hi,

Your output is correct. There is no trick and all you do is check a remainder.

[anaconda1]

I cannot believe that there can be a TLE on this probem! However, I am getting it all the time with my code Could someone plz tell me where I went wrong ?

Here is the code:

#include<iostream>
#include<string>

using namespace std;

long long int square (long long int x)
{
return x*x;
}

long long int bigmod(long int n, int p, int m)
{
if(p==0)
return 1;
else if(p%2==0)
return square(bigmod(n, p/2, m))%m;
else
return ((n%m)*(bigmod(n, p-1, m)))%m;

}

void handle()
{
string num="";
char digit;
int div = 131071;
while(cin>>digit and digit!='#')
num+=digit;

int power = 0;
long long int result = 0;
for(int i=num.size()-1; i>=0; i--)
{
long int n = (num-'0')*2;
if(power!=0 or n!=0)
result+= bigmod(n,power, div);
power++;
}
result=result%div;
if(result==0)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;

}


int main()
{
while(EOF)
handle();
}

Thanx!

[Martin Macko]

There is already a thread on this problem. If there is a thread on a particular problem, please, use it to post your question and do not create a new one. (see http://online-judge.uva.es/board/viewtopic.php?t=1306)

All about problems in Volume CI. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

[kbr_iut]

code deleted AC now.

[Jan]

Why max is so high? The problem states that the number can have at most 10000 digits.

Replace this part

Code: Select all

if(base[0]=='#')continue;
      if(base[0]=='0'||base[0]=='1')i=1;
      else i=0;

with

Code: Select all

i=0;

And use

Code: Select all

while(scanf(" %c",&base[0])==1)// There is a space before %c and it is important

Hope these help.

[kbr_iut]

jan vi thanx,I got AC now...actually shortage of a space gives me wrong answer but I dont understand it.

[rajib_sust]

you can try to continuous input with continuous mod . it is good runtime take.

[stcheung]

Even after reading the hints I still got stuck for long. Now that I understand the pattern, let me throw another hint out. Basically you want to break down the binary input into groups of 17 consecutive digits (because 131071 is 17 consecutive ones as someone pointed out) and do something with them. By breaking down the input I mean if you have 123456789 as input, and you want to break them into groups of 3 consecutive digits, you would end up with 123, 456, 789.

[Jehad Uddin]

This is my code,can any one tell me the process of taking inputs in this prob,...advanced thank to the helpers...

Code: Select all

removed after acc..

[Jan]

Use long long.

[Jehad Uddin]

though i use long long it gives WA,is there any critical input,pls help me....thanks for ur eagerness to help, thanks a lot