10176 - Ocean Deep ! - Make it shallow !!

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

Moderator: Board moderators

Wei
New poster
Posts: 23
Joined: Sat Jul 24, 2004 5:37 pm
Contact:

Post by Wei » Sat Apr 30, 2005 3:19 pm

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

Post by sunny » Mon Nov 28, 2005 6:45 am

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

Post by helloneo » Mon Nov 28, 2005 2:09 pm

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

10176 ocean deep

Post by yukisama » Thu Aug 10, 2006 5:08 pm

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

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

Post by daveon » Sat Aug 19, 2006 2:16 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!

Post by anaconda1 » Tue Aug 29, 2006 7:49 pm

I cannot believe that there can be a TLE on this probem! However, I am getting it all the time with my code :o 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! :wink:

User avatar
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!

Post by Martin Macko » Wed Aug 30, 2006 12:09 am

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.

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 10176 ocean deep

Post by kbr_iut » Mon Apr 21, 2008 1:59 am

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
Location: Dhaka, Bangladesh
Contact:

Re: 10176 ocean deep

Post by Jan » Mon Apr 21, 2008 5:53 am

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

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 10176 ocean deep(got AC now)

Post by kbr_iut » Tue Apr 22, 2008 1:53 pm

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
Location: SUST , Sylhet, Bangladesh

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

Post by rajib_sust » Fri Aug 15, 2008 11:27 am

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!!

Post by stcheung » Sun Oct 05, 2008 8:02 am

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
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

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

Post by Jehad Uddin » Fri May 08, 2009 6:07 pm

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
Location: Dhaka, Bangladesh
Contact:

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

Post by Jan » Sun May 17, 2009 12:30 am

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

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

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

Post by Jehad Uddin » Sun May 17, 2009 1:26 am

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

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest