10176 - Ocean Deep ! - Make it shallow !!

[yatsen]

Can anyone tell me how to solve this problem?

[Yarin]

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]

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
read(ch);
x := 0;
l := 0;
while ch <> '#' do
begin
if (ch = '0') or (ch = '1') then
begin
inc(l);
a[l] := ord(ch) - 48;
end;
read(ch);
end;
readln;

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]

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]

101111111111111111 has 17 1's [base 10 196607] but is not divisible by 131071. Think about the hint again.

[graz]

i think i found the property

[graz]

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]

I use Finite State Automaton to solve this problem.

Best regards
DM

[sohel]

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]

My automaton works in this manner (number division) ...

Best regards
DM

[graz]

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]

please help me ,thanx;
[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]

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]

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]

I compiled and ran your program.

Your algorithm is OK but your program always prints
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
that your program prints 8 answers.

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.