10325  The Lottery
Moderator: Board moderators
10325  The Lottery
I had a solution but it's too slow.
If you don't mind, please help me....show me a better one ???
Thank you.
If you don't mind, please help me....show me a better one ???
Thank you.

 Learning poster
 Posts: 63
 Joined: Thu Apr 04, 2002 2:00 am
Hi,
I did it the following way:
 set the initial "result" value to n.
 compute the lcm of every subset of divisors (except the empty one)
 if the size of a subset it odd, subtract n/lcm from "result"
 if it is even, add n/lcm to "result"
Those operations can be done in an iteration loop, doing some bit manipulation and lcm(a,b)=a*b/gcd(a,b).
I got AC in 270ms, but I don't know how to reach 20ms. That seems incredible!
I did it the following way:
 set the initial "result" value to n.
 compute the lcm of every subset of divisors (except the empty one)
 if the size of a subset it odd, subtract n/lcm from "result"
 if it is even, add n/lcm to "result"
Those operations can be done in an iteration loop, doing some bit manipulation and lcm(a,b)=a*b/gcd(a,b).
I got AC in 270ms, but I don't know how to reach 20ms. That seems incredible!
WA...help me please !!!!!
I try to do this problem. I found a very special DP. I think that I was right.
Here's my program. It's really short. But I get WA. I cannot find what wrong. But I did test it carefully. Anyone help me ??
(I use TP7)
[pascal]
const fi = 'lottery.in';
fo = 'lottery.out';
type
tab1 = array [1..15] of longint;
var
S: tab1;
max, n, i: longint;
function UCLN(a, b: longint): longint;
begin
if a mod b = 0 then UCLN := b
else UCLN := UCLN(b, a mod b);
end;
function F(Num: tab1; n: byte; Max: longint): longint;
var
j, i, k: longint;
S: tab1;
begin
if n = 1 then F := Max div Num[1]
else
begin
j := 0;
for i := 1 to N1 do
begin
k := round(Num / UCLN(Num, Num[n]));
if (j = 0) or (S[j] <> k) then
begin
j := j + 1;
S[j] := k;
end;
end;
F := F(Num, n1, Max) + Max div Num[n]  F(S, n1, Max div Num[n]);
end;
end;
begin
assign(input, fi); reset(input);
assign(output, fo); rewrite(output);
read(max);
read(n);
for i := 1 to n do read(s);
writeln(Max  F(S, n, Max));
close(input); close(output);
end.[/pascal]
Here's my program. It's really short. But I get WA. I cannot find what wrong. But I did test it carefully. Anyone help me ??
(I use TP7)
[pascal]
const fi = 'lottery.in';
fo = 'lottery.out';
type
tab1 = array [1..15] of longint;
var
S: tab1;
max, n, i: longint;
function UCLN(a, b: longint): longint;
begin
if a mod b = 0 then UCLN := b
else UCLN := UCLN(b, a mod b);
end;
function F(Num: tab1; n: byte; Max: longint): longint;
var
j, i, k: longint;
S: tab1;
begin
if n = 1 then F := Max div Num[1]
else
begin
j := 0;
for i := 1 to N1 do
begin
k := round(Num / UCLN(Num, Num[n]));
if (j = 0) or (S[j] <> k) then
begin
j := j + 1;
S[j] := k;
end;
end;
F := F(Num, n1, Max) + Max div Num[n]  F(S, n1, Max div Num[n]);
end;
end;
begin
assign(input, fi); reset(input);
assign(output, fo); rewrite(output);
read(max);
read(n);
for i := 1 to n do read(s);
writeln(Max  F(S, n, Max));
close(input); close(output);
end.[/pascal]
WA...help me please !!!!!
I try to do this problem. I found a very special DP. I think that I was right.
Here's my program. It's really short. But I get WA. I cannot find what wrong. But I did test it carefully. Anyone help me ??
(I use TP7)
[pascal]
const fi = 'lottery.in';
fo = 'lottery.out';
type
tab1 = array [1..15] of longint;
var
S: tab1;
max, n, i: longint;
function UCLN(a, b: longint): longint;
begin
if a mod b = 0 then UCLN := b
else UCLN := UCLN(b, a mod b);
end;
function F(Num: tab1; n: byte; Max: longint): longint;
var
j, i, k: longint;
S: tab1;
begin
if n = 1 then F := Max div Num[1]
else
begin
j := 0;
for i := 1 to N1 do
begin
k := round(Num / UCLN(Num, Num[n]));
if (j = 0) or (S[j] <> k) then
begin
j := j + 1;
S[j] := k;
end;
end;
F := F(Num, n1, Max) + Max div Num[n]  F(S, n1, Max div Num[n]);
end;
end;
begin
assign(input, fi); reset(input);
assign(output, fo); rewrite(output);
read(max);
read(n);
for i := 1 to n do read(s);
writeln(Max  F(S, n, Max));
close(input); close(output);
end.[/pascal]
Here's my program. It's really short. But I get WA. I cannot find what wrong. But I did test it carefully. Anyone help me ??
(I use TP7)
[pascal]
const fi = 'lottery.in';
fo = 'lottery.out';
type
tab1 = array [1..15] of longint;
var
S: tab1;
max, n, i: longint;
function UCLN(a, b: longint): longint;
begin
if a mod b = 0 then UCLN := b
else UCLN := UCLN(b, a mod b);
end;
function F(Num: tab1; n: byte; Max: longint): longint;
var
j, i, k: longint;
S: tab1;
begin
if n = 1 then F := Max div Num[1]
else
begin
j := 0;
for i := 1 to N1 do
begin
k := round(Num / UCLN(Num, Num[n]));
if (j = 0) or (S[j] <> k) then
begin
j := j + 1;
S[j] := k;
end;
end;
F := F(Num, n1, Max) + Max div Num[n]  F(S, n1, Max div Num[n]);
end;
end;
begin
assign(input, fi); reset(input);
assign(output, fo); rewrite(output);
read(max);
read(n);
for i := 1 to n do read(s);
writeln(Max  F(S, n, Max));
close(input); close(output);
end.[/pascal]
A few things, dunno if these will help:
1. Shouldn't you be reading from stdin/stdout instead of those files? (I don't know, I don't use Pascal for my solutions.)
2. Your algorithm doesn't look correct to me, but I don't think I really understand what you're trying to do in it. There was a good hint above... if that doesn't help, here's the meat of my solution (in C):
[cpp]
int div(int sign, int m, long long val) {
if (val>N) return 0;
if (m==M) return sign*(N/val);
return div(sign,m+1,val) + div(1*sign,m+1,lcm(val,nums[m]));
}
[/cpp]
3. Watch out for integer overflow (each of the numbers can be up to 2^311).
1. Shouldn't you be reading from stdin/stdout instead of those files? (I don't know, I don't use Pascal for my solutions.)
2. Your algorithm doesn't look correct to me, but I don't think I really understand what you're trying to do in it. There was a good hint above... if that doesn't help, here's the meat of my solution (in C):
[cpp]
int div(int sign, int m, long long val) {
if (val>N) return 0;
if (m==M) return sign*(N/val);
return div(sign,m+1,val) + div(1*sign,m+1,lcm(val,nums[m]));
}
[/cpp]
3. Watch out for integer overflow (each of the numbers can be up to 2^311).
I did solve this problem. My program run in 0.13s.
But I see that someone can run in 0.02s.
That's great. Anyone know how ??
Ah.., here is my program.
I used Dynamic Programing. But, it's very special ???
[pascal]
type
tab1 = array [1..15] of integer;
var
S: tab1;
max, n, i: integer;
function UCLN(a, b: integer): integer;
begin
if a mod b = 0 then UCLN := b
else UCLN := UCLN(b, a mod b);
end;
function F(Num: tab1; n, Max: integer): integer;
var
j, i, k: integer;
S: tab1;
begin
if n = 1 then F := Max div Num[1]
else
begin
j := 0;
fillchar(S, sizeof(S), 0);
for i := 1 to N1 do
begin
k := Num div UCLN(Num, Num[n]);
if (j = 0) or (S[j] <> k) then
begin
j := j + 1;
S[j] := k;
end;
end;
F := F(Num, n1, Max) + Max div Num[n]  F(S, j, Max div Num[n]);
end;
end;
begin
while not Eof(input) do
begin
readln(max, n);
for i := 1 to n do read(s);
readln;
writeln(Max  F(S, n, Max));
end;
end.
[/pascal]
But I see that someone can run in 0.02s.
That's great. Anyone know how ??
Ah.., here is my program.
I used Dynamic Programing. But, it's very special ???
[pascal]
type
tab1 = array [1..15] of integer;
var
S: tab1;
max, n, i: integer;
function UCLN(a, b: integer): integer;
begin
if a mod b = 0 then UCLN := b
else UCLN := UCLN(b, a mod b);
end;
function F(Num: tab1; n, Max: integer): integer;
var
j, i, k: integer;
S: tab1;
begin
if n = 1 then F := Max div Num[1]
else
begin
j := 0;
fillchar(S, sizeof(S), 0);
for i := 1 to N1 do
begin
k := Num div UCLN(Num, Num[n]);
if (j = 0) or (S[j] <> k) then
begin
j := j + 1;
S[j] := k;
end;
end;
F := F(Num, n1, Max) + Max div Num[n]  F(S, j, Max div Num[n]);
end;
end;
begin
while not Eof(input) do
begin
readln(max, n);
for i := 1 to n do read(s);
readln;
writeln(Max  F(S, n, Max));
end;
end.
[/pascal]

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
10325 Lottery  W.A.
I am gonna go nuts because of this problem....
I got W.A 12 times.....
Can anyone give me some test cases to help me?
Thanks in advance.
I got W.A 12 times.....
Can anyone give me some test cases to help me?
Thanks in advance.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
Actually, my program produces the correct answer for the above test case. However, I still do not understand why my program could not get accepted. >_<
Here is my code:
[cpp]
#include <stdio.h>
#include <math.h>
long long int save[100],used[100],num[100];
long long int result,m,n;
long long int gcd(long long int a,long long int b)
{
if(a%b==0) return b;
else return gcd(b,a%b);
}
void DFS(int k,int depth,int next) // find subset...
{
int i;
if(depth==k) {
long long int g,l,tmp;
int j;
g = save[0];
l = save[0];
for(j=1;j<depth;j++) {
g = gcd(g,save[j]);
}
for(j=1;j<depth;j++) {
l*=save[j];
if(l/g > n) { break; }
}
l/=g;
if(k%2)
result = n/l;
else
result += n/l;
}
for(i=next;i<m;i++) {
if(!used) {
used=1;
save[depth] = num;
DFS(k,depth+1,i+1);
used=0;
}
}
}
void check()
{
int flag=1;
int i,j,mov;
while(flag) {
flag=0;
for(i=0;i<m;i++) {
for(j=i+1;j<m;j++) {
if(num%num[j]==0num[j]%num==0) {
if(num>num[j])
mov = i;
else
mov = j;
flag=1;
break;
}
}
if(flag) break;
}
next:
if(flag) {
for(i=mov;i<m;i++)
num = num[i+1];
m;
}
}
}
int main()
{
int k,i,j;
while(scanf("%lld %lld",&n,&m)!=EOF) {
for(i=0;i<m;i++) {
scanf("%lld",&num);
}
check(); // find if there exists a case such that 2,4,8,16....
for(k=0;k<=m;k++)
used[k]=0;
result = n;
for(k=0;k<m;k++)
result = n/num[k];
for(k=2;k<=m;k++)
DFS(k,0,0);
printf("%lld\n",result);
}
return 0;
}
[/cpp]
Here is my code:
[cpp]
#include <stdio.h>
#include <math.h>
long long int save[100],used[100],num[100];
long long int result,m,n;
long long int gcd(long long int a,long long int b)
{
if(a%b==0) return b;
else return gcd(b,a%b);
}
void DFS(int k,int depth,int next) // find subset...
{
int i;
if(depth==k) {
long long int g,l,tmp;
int j;
g = save[0];
l = save[0];
for(j=1;j<depth;j++) {
g = gcd(g,save[j]);
}
for(j=1;j<depth;j++) {
l*=save[j];
if(l/g > n) { break; }
}
l/=g;
if(k%2)
result = n/l;
else
result += n/l;
}
for(i=next;i<m;i++) {
if(!used) {
used=1;
save[depth] = num;
DFS(k,depth+1,i+1);
used=0;
}
}
}
void check()
{
int flag=1;
int i,j,mov;
while(flag) {
flag=0;
for(i=0;i<m;i++) {
for(j=i+1;j<m;j++) {
if(num%num[j]==0num[j]%num==0) {
if(num>num[j])
mov = i;
else
mov = j;
flag=1;
break;
}
}
if(flag) break;
}
next:
if(flag) {
for(i=mov;i<m;i++)
num = num[i+1];
m;
}
}
}
int main()
{
int k,i,j;
while(scanf("%lld %lld",&n,&m)!=EOF) {
for(i=0;i<m;i++) {
scanf("%lld",&num);
}
check(); // find if there exists a case such that 2,4,8,16....
for(k=0;k<=m;k++)
used[k]=0;
result = n;
for(k=0;k<m;k++)
result = n/num[k];
for(k=2;k<=m;k++)
DFS(k,0,0);
printf("%lld\n",result);
}
return 0;
}
[/cpp]

 Experienced poster
 Posts: 146
 Joined: Sat Apr 26, 2003 2:51 am
10325 why WA !!!
My program does passes all test cases in the forum and the test cases that AC program that is posted in the forum, but why WA?
Can anybody post some trick test cases?[/pascal][/code]
Can anybody post some trick test cases?[/pascal][/code]
Test these
Here is some test cases:
Input:
Input:
Output:100 4
2 3 5 7
20 2
4 6
100 6
2 5 8 30 101 7
2100000000 10
12345 54123 23425 20000 12312 22222 1234 2021 111111 12344321
2147483647 3
2147483647 2 128
If the above test cases are not enough, you can make your own test case for smaller input range (<1000000) and using ceiv approach you can get the correct solution. Good luck.22
13
34
2096573927
1073741823
Re: 10325  The Lottery
using sieve approach im getting tle.. can any one give me a good algo to do it..
#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
#define MAX 2147483647
unsigned mark[(MAX>>5)+2];
#define checkp(x,n) (x[n>>5]&(1<<(n&31)))
#define setp(x,n) (x[n>>5]=(1<<(n&31)))
#define resetp(x,n) (x[n>>5]&=~(1<<(n&31)))
int ar[20];
int p;
int n,m;
void sieve()
{
int i,j,k;
p=0;
memset(mark,0,(m/32)*sizeof(unsigned)+2);
for(i=1;i<=m;i++)
for(j=ar,k=ar;j<=n&&j>0;j=j+k)
if(!checkp(mark,j))
{
setp(mark,j);
p++;
}
}
int main()
{
int i;
freopen("1.txt","r",stdin);
while(scanf("%d %d",&n,&m)==2)
{
for(i=1;i<=m;i++)
scanf("%d",&ar);
sieve();
printf("%d\n",np);
}
return 0;
}
#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
#define MAX 2147483647
unsigned mark[(MAX>>5)+2];
#define checkp(x,n) (x[n>>5]&(1<<(n&31)))
#define setp(x,n) (x[n>>5]=(1<<(n&31)))
#define resetp(x,n) (x[n>>5]&=~(1<<(n&31)))
int ar[20];
int p;
int n,m;
void sieve()
{
int i,j,k;
p=0;
memset(mark,0,(m/32)*sizeof(unsigned)+2);
for(i=1;i<=m;i++)
for(j=ar,k=ar;j<=n&&j>0;j=j+k)
if(!checkp(mark,j))
{
setp(mark,j);
p++;
}
}
int main()
{
int i;
freopen("1.txt","r",stdin);
while(scanf("%d %d",&n,&m)==2)
{
for(i=1;i<=m;i++)
scanf("%d",&ar);
sieve();
printf("%d\n",np);
}
return 0;
}

 New poster
 Posts: 9
 Joined: Mon Jul 07, 2014 3:37 pm
 Contact:
Re: 10325  The Lottery
Hint:
You are given N and M and you have M selected tickets numbered
Tickets from 1 to N should not be divisible by any of the selected tickets
for example if we have a, b, c, ... selected tickets
then any ticket that is divisible by a or b or c or .... or LCM(a,b) or LCM(a,c) or ..... or LCM(a,b,c)
Lets Assume N = 10 and M = 2
Selected = 2 3
Then our numbers from 1 to N should not be divisible by
2
3
LCM(2,3) = 6
Lets see what number those selected numbers divides
List1 2 3 4 5 6 7 8 9 10
Divisible by:2 2 2 2 2We will exclude(2,4,6,8,10)
Divisible by:3 3 3We will exclude(3,6,9)
Divisible by: 6We will exclude(6)
Notice that we excluded "6" 3 times, we need to solve this problem
The solution for that is to determine the size of set of the selected number {2,3}
LCM(2,3) is the LCM of the set {2,3} the size = 2 which is even then we should subtract N/LCM(2,3) from
forbidden count, in case of LCM(2,3) = 6 >>> N/LCM(2,3) = 1 which is what we want to subtract.
In case of the size of the set is odd, we need to add N/LCM(a) to the forbidden count, if set is {2}
then it's size is 1 which is odd then add N/LCM(1,2) to the forbidden count.
The reason for that is, if you have an even set then the product of it's numbers is excluded previously
more than once, so we need to subtract it to avoid redundant so that we excluded it those numbers only once.
You are given N and M and you have M selected tickets numbered
Tickets from 1 to N should not be divisible by any of the selected tickets
for example if we have a, b, c, ... selected tickets
then any ticket that is divisible by a or b or c or .... or LCM(a,b) or LCM(a,c) or ..... or LCM(a,b,c)
Lets Assume N = 10 and M = 2
Selected = 2 3
Then our numbers from 1 to N should not be divisible by
2
3
LCM(2,3) = 6
Lets see what number those selected numbers divides
List1 2 3 4 5 6 7 8 9 10
Divisible by:2 2 2 2 2We will exclude(2,4,6,8,10)
Divisible by:3 3 3We will exclude(3,6,9)
Divisible by: 6We will exclude(6)
Notice that we excluded "6" 3 times, we need to solve this problem
The solution for that is to determine the size of set of the selected number {2,3}
LCM(2,3) is the LCM of the set {2,3} the size = 2 which is even then we should subtract N/LCM(2,3) from
forbidden count, in case of LCM(2,3) = 6 >>> N/LCM(2,3) = 1 which is what we want to subtract.
In case of the size of the set is odd, we need to add N/LCM(a) to the forbidden count, if set is {2}
then it's size is 1 which is odd then add N/LCM(1,2) to the forbidden count.
The reason for that is, if you have an even set then the product of it's numbers is excluded previously
more than once, so we need to subtract it to avoid redundant so that we excluded it those numbers only once.
Abdelrahman Ali (MaTrix)