## 10176 - Ocean Deep ! - Make it shallow !!

Moderator: Board moderators

Wei
New poster
Posts: 23
Joined: Sat Jul 24, 2004 5:37 pm
Contact:
THX~~~ I got an AC~~~

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

### 10176 & 10551 - pls help

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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

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
New poster
Posts: 2
Joined: Tue Feb 14, 2006 9:29 am

### 10176 ocean deep

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#``````

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
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Hi,

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

anaconda1
New poster
Posts: 1
Joined: Tue Aug 29, 2006 7:43 pm

### 10176 TLE Ocean Deep!

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
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Re: 10176 TLE Ocean Deep!

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)
forum 'Volume CI' description wrote: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
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Contact:

### Re: 10176 ocean deep

code deleted AC now.
Last edited by kbr_iut on Tue Apr 22, 2008 1:54 pm, edited 1 time in total.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

### Re: 10176 ocean deep

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.
Ami ekhono shopno dekhi...
HomePage

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Contact:

### Re: 10176 ocean deep(got AC now)

jan vi thanx,I got AC now...actually shortage of a space gives me wrong answer but I dont understand it.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

rajib_sust
New poster
Posts: 16
Joined: Sun Mar 02, 2008 10:34 am

### Re: 10176 - Ocean Deep! Make it shallow!!

you can try to continuous input with continuous mod . it is good runtime take.
life is beautiful like coding

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

### Re: 10176 - Ocean Deep! Make it shallow!!

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.

Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

### Re: 10176 - Ocean Deep! Make it shallow!!

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..``
Last edited by Jehad Uddin on Thu Oct 08, 2009 10:01 am, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

### Re: 10176 - Ocean Deep! Make it shallow!!

Use long long.
Ami ekhono shopno dekhi...
HomePage