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

Moderator: Board moderators

yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan

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

Can anyone tell me how to solve this problem?

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
Notice that 131071 is 11111111111111111 in binary? Try multiplicate that binary number with other binary numbers and hopefully you'll see some pattern. The same trick can be used (I think) to check whether a number is divisble with 9, 99, 999 etc in the decimal system.

lowai
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm
i use that method but got WA. what's wrong with my code?
[pascal]
var
ch : char;
x : longint;
a : array[-17..10000]of shortint;
b : array[0..1, 1..600]of shortint;
l, lb, ll, i : longint;
p, q : integer;
p0, p1 : integer;
begin
l := 0;
while not eof do
begin
x := 0;
l := 0;
while ch <> '#' do
begin
if (ch = '0') or (ch = '1') then
begin
inc(l);
a[l] := ord(ch) - 48;
end;
end;

p0 := 0; p1 := 1;
lb := 17;
fillchar(b[p0], sizeof(b[p0]), 0);
while l > 0 do
begin
q := 0;
for i := 1 to 17 do
begin
b[p0, i] := b[p0, i] + a[l - i + 1] + q;
q := b[p0, i] div 2;
b[p0, i] := b[p0, i] mod 2;
end;
i := 17;
while q > 0 do
begin
inc(i);
b[p0, i] := b[p0, i] + q mod 2;
q := b[p0, i] div 2;
b[p0, i] := b[p0, i] mod 2;
end;
if i > lb then lb := i;
dec(l, 17);
end;
while (b[p0, lb] = 0) and (lb > 1) do dec(lb);
l := lb;

while true do
begin
if (l <= 17) then break;

lb := 17;
fillchar(b[p1], sizeof(b[p1]), 0);
ll := l;
l := 0;
while l <= ll do
begin
q := 0;
for i := 1 to 17 do
begin
b[p1, i] := b[p1, i] + b[p0, l + i] + q;
q := b[p1, i] div 2;
b[p1, i] := b[p1, i] mod 2;
end;
i := 17;
while q > 0 do
begin
inc(i);
b[p0, i] := b[p0, i] + q mod 2;
q := b[p0, i] div 2;
b[p0, i] := b[p0, i] mod 2;
end;
if i > lb then lb := i;
inc(l, 17);
end;

while (b[p1, lb] = 0) and (lb > 1) do dec(lb);
l := lb;
p0 := p1;
p1 := 1 - p1;
end;

if l = 1 then
if b[p0, 1] = 0 then
writeln('YES')
else
writeln('NO')
else
if l = 17 then
begin
p := 1;
for i := 1 to 17 do
if b[p0, i] = 0 then
begin p := 0; break; end;
if p = 1 then writeln('YES') else writeln('NO');
end
else writeln('NO');
end;
end.
[/pascal]

graz
New poster
Posts: 4
Joined: Mon Mar 22, 2004 11:30 pm
Location: /dev/null
i try with this..

Code: Select all

``````count = "number of 1's in a line";
if (count%17==0) cout << "YES" << endl;
else cout << "NO" << endl;
``````
but get WA, any idea?

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
101111111111111111 has 17 1's [base 10 196607] but is not divisible by 131071. Think about the hint again.

graz
New poster
Posts: 4
Joined: Mon Mar 22, 2004 11:30 pm
Location: /dev/null
i think i found the property

graz
New poster
Posts: 4
Joined: Mon Mar 22, 2004 11:30 pm
Location: /dev/null
I try with the numbers from 0 to 500000000000 and my program works well, but i get WA in JudgeOnline.
The property i found i a partial sum of groups 17 digits.

anyone solve the problem like me?

graz.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
I use Finite State Automaton to solve this problem.

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
Isn't it simply string division.....

I mean convert the binary to decimal and at each stage divide it by 131071 and see if the final remainder is 0.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
My automaton works in this manner (number division) ...

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

graz
New poster
Posts: 4
Joined: Mon Mar 22, 2004 11:30 pm
Location: /dev/null
Can anyone paste me a very large example?
All test i made in my computer are correct but I have WA over and over.

graz

oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

### 10176 WA???

[cpp]
#include <iostream>
using namespace std;
#include <cmath>
#include <cstdio>
#include <cstring>
int main()
{
int s;
int b=2;
char c;
int p=131071;
while(cin.get(c))
{
s=0;
do
{
if(c=='1'||c=='0')
{
s *= b;
s += int(c)-48;
s %= p;
}
}while(cin.get(c)&&c!='#');
if(s==0)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
[/cpp]

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

### 10176

I got a WA in "10176"...and I have tried a lot of test data...but...I still don't know where the wrong was~~
Can someone help???

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>

int main(void)
{
unsigned int ans,n;
char c;
while(scanf("%c",&c)!=EOF)
{
ans=0;
while(c!='#')
{
n=c-48;
n=2*ans+n;
ans=n%131071;
scanf("%c",&c);
}
scanf("%c",&c);
if(ans==0)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
``````

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Hi, Wei !

The input number can be very large - it could have 10000 binary
digits. Which means that in the worst case it could have a
magnitude of about 2 ^ 10000.

This won't fit into an unsigned int variable.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
I compiled and ran your program.

and additional unnecessary YES as last line in
the output. Your program won't print this YES only
if before the EOF there's no EOL.
If the input file ends with the sequence EOL EOF
then you print this additional YES.

Try with 7 input numbers for example and you will see

If you don't see this effect on your machine then
I guess it is due to some portability issues
with the method cin.get() which you're using.
By portabily issues I mean it probably behaves differently
on different platforms ( could be OS dependent ?! , compiler
dependent ?! , stuff like that ).

On my machine I see an additional unnecessary YES, as I said.
I used the Borland C++ Builder 6 to compile your program
on a machine with the Windows 2000 OS.

Maybe you should try to just use Stadard C I/O functions.
For this problem using scanf will be enough and
will work fine. You just have to slightly modify the way you
handle the input.