11795 - Mega Man's Mission

All about problems in Volume 117. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
yan yan
New poster
Posts: 13
Joined: Thu May 13, 2010 4:16 pm
Location: Viet Nam
Contact:

11795 - Mega Man's Mission

Post by yan yan »

is it backtracking problem? ....i got TLE when i used backtracking :roll: . Please tell me some hint! :oops:
Thanks advance!

lgarcia
New poster
Posts: 16
Joined: Mon Sep 14, 2009 7:49 pm
Location: Venezuela

Re: 11795 - Mega Man's Mission

Post by lgarcia »

It's more like a DP problem, think about what states you have, a robot can be destroyed or not, and for any combination of destroyed robots you can destroy others (independently of the order they were destroyed). I hope it was helpful.

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

Re: 11795 - Mega Man's Mission

Post by suneast »

Hi,yan yan...
I solve it during the contest using simple DP... :wink:
using an integer to store all the data to compress status...
others called it bitset...

I use pair<int,int> to store current status
.fist------stands for the robots have already being killed
.second------stands for whether Mega Man can killed the robot...

check

Code: Select all

if( !(cur.first&(1<<i)) && cur.second&(1<<i) )
then transition status like

Code: Select all

pii tmp;
tmp.first=cur.first+(1<<i);
tmp.second=cur.second|robot[i];
if(!state[tmp.first])                //I used an array state[] to store the ans
	q.push(tmp);                //I used a queue to transition status
state[tmp.first]+=state[cur.first];
and finally state[ (1<<n)-1 ]is the correct ans
just output it and got ac...

hope I am help to U... :D

yan yan
New poster
Posts: 13
Joined: Thu May 13, 2010 4:16 pm
Location: Viet Nam
Contact:

Re: 11795 - Mega Man's Mission

Post by yan yan »

thanks everyone! i will try DP :D

tanmoy
New poster
Posts: 18
Joined: Wed Jun 25, 2008 2:25 pm

Re: 11795 - Mega Man's Mission

Post by tanmoy »

Can any one give me some critical cases , i'm getting WA

Li Yingwei
New poster
Posts: 1
Joined: Wed Oct 31, 2012 5:04 pm

Re: 11795 - Mega Man's Mission

Post by Li Yingwei »

Can any one give me some critical cases , i'm getting WA
DP:
d[S]=sum(d[S-{i}]) (i in S)
d[{i}]=1 (Mega Buster can destory i) or 0 (Mega Buster can not destory i)

Code: Select all

var t,i,n:longint;
    d:array[0..65536]of int64;
    g:array[0..16,1..16]of char;
function get_1(x:word):integer;
   begin
      x:=(x and $55555555)+((x shr 1)and $55555555);
      x:=(x and $33333333)+((x shr 1)and $33333333);
      x:=(x and $0f0f0f0f)+((x shr 1)and $0f0f0f0f);
      x:=(x and $00ff00ff)+((x shr 1)and $00ff00ff);
      //x:=(x and $0000ffff)+((x shr 1)and $0000ffff);
      exit(x);
   end;
function pd(x,i:word):boolean;
   var j:integer;
   begin
      if g[0,i]='1'then exit(true);
      for j:=1 to n do
         if x and(1 shl(j-1))>0then
            if g[j,i]='1'then exit(true);
      exit(false);
   end;
function dp(x:word):int64;
   var i:longint;
   begin
      if d[x]<>-1 then exit(d[x]);
      if get_1(x)=1 then
         begin
            for i:=1 to n do
               if x and(1 shl(i-1))>0 then break;
            if pd(x,i)then d[x]:=1 else d[x]:=0;
            exit(d[x]);
         end;
      dp:=0;
      for i:=1 to n do
         if x and(1 shl(i-1))>0then
            begin
               if pd(x,i) then inc(dp,dp(x xor (1 shl(i-1))));
            end;
      d[x]:=dp;
   end;
procedure work(k:longint);
   var i,j:longint;ans:int64;
   begin
      readln(n);
      for i:=0 to n do
         begin
            for j:=1 to n do
               read(g[i,j]);
            readln;
         end;
      fillchar(d,sizeof(d),$ff);
      ans:=dp(1 shl n-1);
      writeln('Case ',k,': ',ans);
   end;
begin
   readln(t);
   for i:=1 to t do
      work(i);
end.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11795 - Mega Man's Mission

Post by brianfry713 »

Input:

Code: Select all

50
7
0011101
1101110
0101001
1000011
0000010
1110011
1011101
1000001
12
001001011110
010110100111
110101001100
101010110111
101111100110
000110100110
101110000001
111101001010
111100110111
111011100100
000100111011
000011111110
001111111001
7
0110001
0010011
1001000
1011101
0010100
1011011
0001001
0110111
3
100
110
011
110
14
11001111100000
11100100010100
00110111011011
01100001101111
01100010011000
01111011010111
01100000100110
11000011001111
00111010000101
01100100110011
10010100100000
10101001001111
10000100000000
00110011110110
00100000101111
12
101011010000
011000000001
110001011110
000100100010
010110001001
101100100110
001010011000
000000101011
101101001100
100000001001
001100011011
111001111111
111010010110
15
101110001100011
100011101111000
000111101011010
100101111000011
011010100011110
110101010101100
001100011010001
010101000010100
110100101010010
011001101010001
100110001110011
010001111110101
011000100001001
100100000011001
110011001101001
110010010011000
4
1100
0101
0110
0011
1110
3
000
010
010
011
1
1
1
14
10110110101000
00010111111001
11000110100011
01111101110001
00011011011111
10111000000110
11011001110100
00110000110110
01110100101011
10110100110001
11110001101100
10110100010101
00011110011100
00000110010001
00000010100101
14
01101110011001
01111111110110
10111000011000
00111100011110
10001100101110
01000111010111
00110101000001
11110100010110
00100100000100
10101001100110
00000110011111
01111010011111
01111110100111
00001110110100
00111100010101
4
1010
1010
1000
0110
0101
15
110101100000101
110110101001100
111010100100110
110101111000010
010011001011100
111101111001000
101100000111000
011010101001111
000110011000000
001100100101000
000011010100100
100111111001101
101101010000000
010000101001011
100110011010110
111010010110011
4
1110
0001
1001
1111
0111
2
10
10
01
9
101011011
000100011
110001110
111101110
011101111
110111110
111100100
011111001
010111000
110101001
9
111100011
110110000
000010101
001010101
010100011
011001100
110110001
010111011
010111001
111101010
5
10000
01111
00110
01101
11001
01100
6
101101
100000
000010
101001
101001
001110
100110
9
100110011
111000101
100000100
111101101
000110000
010101001
001111001
111010111
111100110
011101110
15
101011111000110
010111000101011
001010101001011
010101000000100
010111101101000
111000100100011
010001011101111
100100100110011
110100000110001
100010000110111
101111011000001
001000000111111
001111010111001
101001000011100
010000111101001
011111111111011
14
10111100100001
10000011100110
01111110010111
10000000011001
11010100010111
00000001011101
10000010010011
10000001000011
10000100111111
00010010011001
11101110010011
10110110000000
10101001011011
00100010100110
01011010011010
16
0010110110010000
0111010111000110
1000001101001111
0001100000001110
0100011011100001
0001101100101001
0110000101001011
0101100000010010
1000111101101110
0010000000100010
1100011110101000
0000000000000101
1011000111100000
0010010010100111
0100111000100110
0000101110111001
1011101010010100
16
0011100111111011
0010111011011001
0100101010001101
1110010100010101
0110100110101110
0010110100001110
0001100010001110
1001100111000100
0011101001010111
1001010100000000
1110100110110001
0101010010011010
1001000101000100
0010100100010011
0101110001000010
1000001100000010
1011101111010111
2
11
01
11
8
11111011
01011110
01100011
11100011
00010101
00011110
00000001
11110000
00111000
5
01001
00101
00111
01001
00000
10010
11
11010000110
10110011001
00110100010
01011000010
00000100100
01101101100
01101111111
11110100000
10100001000
10001110010
00010010001
01101011101
4
1100
1011
0110
1010
0010
12
010101000111
101110010000
100111000010
110000110001
100101101111
001000001101
110100011101
011101011111
101011101111
010100001001
100000110101
011110011000
000100111111
6
101000
001011
001101
101110
001100
110011
111010
11
00110000111
11001000110
00111011011
10110100101
10011000100
01100001111
00011001111
00000010000
10011000101
10010110010
11111101111
01001110010
7
0011010
1000011
0011110
0101001
1010001
1100000
0110101
0100001
2
00
00
10
1
1
0
6
101101
111101
001011
000011
001101
011001
110000
9
011100101
010001101
010010100
001000110
110010010
010111110
100000100
110111110
101100111
000001001
15
101011100000001
100111110011010
100000110100100
010001001000100
110011000010100
110010110010101
100100000100110
011011000110100
010100110101110
011110001110100
111001010100000
001011001110100
111011000011111
111010100011011
101010010011100
010101011001000
2
10
00
11
9
010010010
010010100
110010100
111101000
001001000
000110111
111001101
001001000
110110100
101110011
16
1101110110111010
0010010100001100
0001000101010110
1001111111000010
0110111101001100
1101010100100001
1110011001110100
0010111101101111
0110010001011011
0001110101000110
0000101001111001
0001001011010111
0111101110000110
1101110000100010
1111110111100101
0010110110010110
0110011100101000
5
10000
11011
11011
10111
01010
00000
2
10
11
10
10
1000101001
0110011110
1000111100
0100010110
1100001110
1100101111
1101100101
0110110000
0011001110
0010101111
1100111011
9
111011101
101011000
011111100
110101011
101000001
111110101
011100110
011110110
110001100
111010101
14
10100111100110
11010011101110
10110110001110
00010000100001
11011100010010
10011011011111
00111101001111
11111100111011
10010110011100
01110100010000
01110110100111
01101101001010
00001101010110
10010101000000
10010001101111
4
0100
1101
1111
0000
1000
9
001100011
111100101
001001000
000001111
011110000
111001101
001001101
010111010
111100010
100010110
1
0
0
AC output:

Code: Select all

Case 1: 1960
Case 2: 163906512
Case 3: 1380
Case 4: 1
Case 5: 28758476880
Case 6: 77812524
Case 7: 417636021600
Case 8: 8
Case 9: 0
Case 10: 1
Case 11: 24956175168
Case 12: 23166218880
Case 13: 0
Case 14: 331368125760
Case 15: 18
Case 16: 0
Case 17: 216720
Case 18: 160704
Case 19: 24
Case 20: 0
Case 21: 143640
Case 22: 574475529600
Case 23: 22386643200
Case 24: 3239358687360
Case 25: 8988771916800
Case 26: 2
Case 27: 30240
Case 28: 28
Case 29: 8194668
Case 30: 9
Case 31: 135582096
Case 32: 98
Case 33: 9624384
Case 34: 1104
Case 35: 0
Case 36: 1
Case 37: 300
Case 38: 129342
Case 39: 221795845440
Case 40: 0
Case 41: 38364
Case 42: 10235689390080
Case 43: 0
Case 44: 1
Case 45: 705528
Case 46: 233280
Case 47: 30803868480
Case 48: 6
Case 49: 80196
Case 50: 0
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 117 (11700-11799)”