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

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

10176 - Ocean Deep ! - Make it shallow !!

Post by yatsen » Tue Sep 10, 2002 9:45 am

Can anyone tell me how to solve this problem?

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

Post by Yarin » Tue Sep 10, 2002 5:40 pm

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

Post by lowai » Wed Jun 11, 2003 8:38 am

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
New poster
Posts: 4
Joined: Mon Mar 22, 2004 11:30 pm
Location: /dev/null

Post by graz » Tue Mar 23, 2004 12:09 am

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?

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Tue Mar 23, 2004 1:57 am

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

Post by graz » Tue Mar 23, 2004 10:56 pm

i think i found the property :D

graz
New poster
Posts: 4
Joined: Mon Mar 22, 2004 11:30 pm
Location: /dev/null

Post by graz » Sun Mar 28, 2004 5:25 pm

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:

Post by Dominik Michniewski » Sun Mar 28, 2004 10:07 pm

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)

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Mon Mar 29, 2004 5:05 am

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:

Post by Dominik Michniewski » Mon Mar 29, 2004 9:15 am

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

Post by graz » Thu Apr 01, 2004 8:48 pm

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

Post by oulongbin » Sun Sep 05, 2004 9:53 am

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
New poster
Posts: 23
Joined: Sat Jul 24, 2004 5:37 pm
Contact:

10176

Post by Wei » Sat Feb 26, 2005 1:58 pm

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;
}

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Fri Apr 29, 2005 3:58 pm

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.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Fri Apr 29, 2005 5:13 pm

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.

Post Reply

Return to “Volume 101 (10100-10199)”