i couldn't find any algo

[Artikali]

below a problem which i took it from timus judge?
I couldn' t find any way to solve it, please help me.
1495//
One-two, one-two 2
Time Limit: 2.0 second
Memory Limit: 64 MB

A year ago the famous gangster Vito Maretti woke up in the morning and realized that he was bored of robbing banks of round sums. And for the last year he has been taking from banks sums that have only digits 1 and 2 in their decimal notation. After each robbery, Vito divides the money between N members of his gang. Your task is to determine the minimal stolen sum which is a multiple of N.

Input
The input contains the number N (1 ≤ N ≤ 1000000).

Output
Output the minimal number which is a multiple of N and whose decimal notation contains only digits 1 and 2. If it contains more than 30 digits or if there are no such numbers, then output the word "Impossible" (without quotation marks).

Sample Input
Sample input #1
5

Sample input #2
8

Sample Output
Sample output #1
Impossible

Sample output #2
112

---
THANKS

[marcadian]

I think recursion can work

Code: Select all

void generate(int num)
{		
	if (valid(num)) print num
	else
	generate(num*10 + 1);
	generate(num*10+2);


}

int main()
{
	generate(0);
}

for the valid function, you check if num is multiple of n by simulating long division you learn in elementary school. correct me if I'm wrong

[Giorgi]

marcadian
your solution is not very good. you have to find minimal number.
It will give TLE

Artikali

if you have number (for example 1232) and
you want to find 1232 % 7. you can do it such way:
1 % 7 = 1;
(1*10 + 2) % 7 = 5
(5*10 + 3) % 7 = 4
(4*10 + 2) % 7 = 0

it means that 1232 mod 7 = 0;

try to use this fact and BFS.

[marcadian]

oh yes, i'm sorry thank's 4 correct me.to find minimal number use BFS instead of DFS. @giorgi: could you explain this again?I'm not fully understand what you mean

[Giorgi]

oh yes, i'm sorry thank's 4 correct me.to find minimal number use BFS instead of DFS. @giorgi: could you explain this again?I'm not fully understand what you mean

for example if you want to find
189 % 17

1 (first digit) % 17 = 1
now we have 1
then
1*10 + 8(second digit) = 18. 18 & 17 = 1
1*10 + 9(third digit) = 19. 19 % 17 = 2

so 189 % 17 = 2

I used BFS such way:
we want to find number wich consists with '1' and '2' and is multiply of N

at first we have number 1 and 2.
from this numbers I can get
11
12
21
22
and I save
11 mod n
12 mod n
21 mod n
22 mod n
if one of the remainders is 0 then this number is multiply of N.
then from 11 you can get 112 and 111 and so on
simple BFS. here is my code :

Code: Select all

var
a,pas,fr,p,r : array[0..1000000] of longint;
x,i,j,k,st,fin,n : longint;

procedure rec(x : longint);
begin
  if fr[p[x]] <> 0 then rec(p[x]);
  write(pas[x]);

end;

procedure solve;
begin

 fr[1] := 0;

 p[1] := 0;
 p[2] := 0;
 st := 1;
 fin := 1;

 while st <= fin do
 begin

 if r[st] > 30 then break;
    k := fr[st];
    k := (10*k + 1) mod n;
    if a[k] = 0 then
    begin
      a[k] := 1;
      inc(fin);
      fr[fin] := k;
      p[fin] := st;
      pas [fin] := 1;
      r[fin] := r[st] + 1;
    end;

    if k = 0 then
    begin
      rec(fin); exit;
    end;


    k := fr[st];
    k := (10*k + 2) mod n;
    if a[k] = 0 then
    begin
      a[k] := 1;
      inc(fin);
      fr[fin] := k;
      p[fin] := st;
      pas[fin] := 2;
      r[fin] := r[st] + 1;
    end;

    if k = 0 then
    begin
      rec(fin); exit;
    end;
    inc(st);

 end;

     writeln('Impossible');
end;

begin
  assign(input,'input.txt'); reset(input);
  assign(output,'output.txt'); rewrite(output);
    read(n);
    solve;
  close(input); close(output);
end.

[Darko]

http://acmicpc-live-archive.uva.es/nuev ... php?p=2040
http://acm.uva.es/p/v109/10993.html

They are similar problems, a bit harder, I guess, but the idea is the same.

[Giorgi]

another "One-two, one-two" problem. I can't solve it.
have you any idea how to solve it?

-----------------------------------------------------------------------

One-two, one-two
Time Limit: 1.0 second
Memory Limit: 16 MB


Having been awaken today’s morning Vito Maretti has understood that it’s boring for him to rob banks. Now he is planning to take from banks only sums of money with decimal notations containing only digits 1 and 2. Since Vito is very honest gangster he hesitates if he can divide the loot between his gang in equal parts. For quite some time now (after one of such Vito’s insight) Vito’s gang has exactly 2N members. Vito will reward you generously if given an integer N you determine the sum which decimal notation consists only of ones and twos that Vito will be able to divide in equal parts between the members of his gang.
Input

an integer N (1 <= N <= 100).
Output

If exists a number which decimal notation consists only of the digits 1 and 2 that is divided by 2N and has no more than 10000 digits then output it without the leading zeros. If there are several suitable numbers, then output any one of them. If there is no such number the output should contain the line “No solution” (without the quotes).
Sample Input

2
Sample Output

12

[Giorgi]

I think this problem is easier than previous one. But I can't solve it.
Why nobody wants to help me?

[Darko]

It's the same thing as the others - you do BFS over remainders, looking for 0. You seem to know how to solve it (from your post above). It's maybe just an implementation problem? Note that if you've seen a remainder before, its successors are already in the queue, so you just skip it (not sure if you do that in the code you posted above, but didn't look too closely).