10067 - Playing with Wheels

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

Moderator: Board moderators

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Oct 07, 2007 9:09 pm

Try the cases...

Input:

Code: Select all

2
1 7 4 0
9 4 8 8
2
4 5 5 1
7 1 1 5

3 4 8 4
9 9 2 5
5
3 3 3 7
4 3 8 0
8 8 0 6
8 1 9 8
9 7 2 2
Output:

Code: Select all

11
14
Hope these help.
Ami ekhono shopno dekhi...
HomePage

cs_lyxaa
New poster
Posts: 3
Joined: Thu Oct 04, 2007 6:50 am

Post by cs_lyxaa » Mon Oct 08, 2007 3:55 am

Thanks so much. I finally got AC in 0.67s!!~~~
Through your case, I found that the bug was the negative modular arithmetic. C++ gives me the result that (-1)%10=-1. No wonder I got WA before.
Jan wrote:Try the cases...

Input:

Code: Select all

2
1 7 4 0
9 4 8 8
2
4 5 5 1
7 1 1 5

3 4 8 4
9 9 2 5
5
3 3 3 7
4 3 8 0
8 8 0 6
8 1 9 8
9 7 2 2
Output:

Code: Select all

11
14
Hope these help.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Oct 08, 2007 10:01 am

You are welcome. Remove your old code please.
Ami ekhono shopno dekhi...
HomePage

Zyaad Jaunnoo
Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am

Post by Zyaad Jaunnoo » Sun Oct 14, 2007 10:35 am

I am getting wrong answer :(

I tried the test cases posted and I am getting the correct answer.

Any other tricky test cases?

Will appreciate your help.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Oct 14, 2007 6:54 pm

I think many tricky cases are posted already. You can post your code, cause then it would be easier to check..
Ami ekhono shopno dekhi...
HomePage

Zyaad Jaunnoo
Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am

Post by Zyaad Jaunnoo » Sun Oct 14, 2007 9:06 pm

Below is my code...

Code: Select all

#include <iostream>
#include <list>

using namespace std;

#define TRUE    1
#define FALSE   0
#define LEFT    0
#define RIGHT   1

int N;
int S1, S2, S3, S4, S;
int T1, T2, T3, T4, T;
int F1, F2, F3, F4, F;
int forbidden [10000];
int g[10000][8];
int steps[10000];


void cleanUp() {
    for (int i = 0; i < 10000; i++) {
        forbidden[i] = FALSE;
        steps[i] = -1;
    }
}

int nextConfig (int state, int button, int direction) {
    int digit, order, toAdd;

    if (button == 1) order = 1000;
    else if (button == 2) order = 100;
    else if (button == 3) order = 10;
    else if (button == 4) order = 1;

    digit = (state % (order * 10)) / order;

    if (direction == RIGHT) {
        toAdd = -1 * order;
        if (digit == 0) toAdd = 9 * order;
    }
    else {
        toAdd = 1 * order;
        if (digit == 9) toAdd = -9 * order;
    }

    return (state + toAdd);
}


void buildGraph() {
    for (int i = 0; i < 10000; i++) {
        g[i][0] = nextConfig(i, 1, LEFT);
        g[i][1] = nextConfig(i, 1, RIGHT);

        g[i][2] = nextConfig(i, 2, LEFT);
        g[i][3] = nextConfig(i, 2, RIGHT);

        g[i][4] = nextConfig(i, 3, LEFT);
        g[i][5] = nextConfig(i, 3, RIGHT);

        g[i][6] = nextConfig(i, 4, LEFT);
        g[i][7] = nextConfig(i, 4, RIGHT);
    }
}


void readData() {
    cin >> S1 >> S2 >> S3 >> S4;
    S = (S1 * 1000) + (S2 * 100) + (S3 * 10) + S4;

    cin >> T1 >> T2 >> T3 >> T4;
    T = (T1 * 1000) + (T2 * 100) + (T3 * 10) + T4;

    int n;  //  no of forbidden configurations

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> F1 >> F2 >> F3 >> F4;
        F = (F1 * 1000) + (F2 * 100) + (F3 * 10) + F4;
        forbidden[F] = TRUE;
    }
}

int traverseG() {
    list <int> L;   //  queue to hold configurations
    list <int> :: iterator i;
    int currentConfig, neighbour;

    if (forbidden[T] || forbidden[S]) return -1;
    if (S == T) return 0;

    L.push_back(S);
    steps[S] = 0;

    for (i = L.begin(); L.size() > 0; i++) {
        currentConfig = *i;
        L.pop_front();

        for (int j = 0; j < 8; j++) {
            neighbour = g[currentConfig][j];
            //if (neighbour == T)
            //    return steps[currentConfig] + 1;

            if (!forbidden [neighbour] && steps[neighbour] == -1) {
                steps[neighbour] = steps[currentConfig] + 1;
                if (neighbour == T) return steps[neighbour];

                L.push_back(neighbour);
            }
        }
    }

    //  not found
    return -1;
}


int main() {
    cin >> N;

    buildGraph();

    for (int i = 0; i < N; i++) {
        cleanUp();
        readData();
        cout << traverseG() << endl;
    }


    return 0;
}

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Oct 17, 2007 9:55 pm

Your code looks correct to me. But one question. You are using list. Is there any problem using stl queue?
Ami ekhono shopno dekhi...
HomePage

Zyaad Jaunnoo
Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am

Post by Zyaad Jaunnoo » Thu Oct 18, 2007 5:06 am

I haven't tried yet.

Will try and let you know..

Thanks for the help.

barry800414
New poster
Posts: 1
Joined: Wed Nov 28, 2007 5:45 am

Post by barry800414 » Wed Nov 28, 2007 5:48 am

Jan wrote:Try the cases...

Input:

Code: Select all

2
1 7 4 0
9 4 8 8
2
4 5 5 1
7 1 1 5

3 4 8 4
9 9 2 5
5
3 3 3 7
4 3 8 0
8 8 0 6
8 1 9 8
9 7 2 2
Output:

Code: Select all

11


14
Hope these help.
Thanks for your test data!

ary
New poster
Posts: 5
Joined: Mon Jan 05, 2009 2:43 pm

Re: 10067 - Playing with Wheels

Post by ary » Sun Jan 11, 2009 7:01 am

i got wa.. i dunt know whats wrong.. already consider forbidden equal to target, and everything.. plz help me geniuses.. @_@

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <fstream>
#include <cmath>
//#include <conio.h>
using namespace std;
typedef struct {
int f[4];
} forbidden;

bool cg[4];
int cur[4];
int target[4];
int counter;
bool cant,ok;
vector<forbidden> forbid,candi,visited;
forbidden forb;

bool compara(int a[], int b[]){

for(int i=0;i<4;i++){
if(a != b){
return false;
}
}
return true;
}

int calc(int a[],int b[]){
int sum=0,d,e;
for(int i=0;i<4;i++){
d = abs(a-b);
if(d>5){
if(a<b){
sum += a + (9-b)+1;
}else{
sum += b + (9-a) +1;
}
}else
sum += d;
}
return sum;
}

void choose(int a[]){
int p[9][4];
int max=0,temp,n;

p[3][0] = p[4][0] = p[5][0] = p[6][0] = p[7][0] = p[8][0] = a[0];
if(a[0]==9)
p[1][0] = 0;
else
p[1][0] = a[0] +1;
if(a[0]==0)
p[2][0] = 9;
else
p[2][0] = a[0] -1;

p[1][1] = p[2][1] = p[5][1] = p[6][1] = p[7][1] = p[8][1] = a[1];
if(a[1]==9)
p[3][1] = 0;
else
p[3][1] = a[1] +1;
if(a[1]==0)
p[4][1] = 9;
else
p[4][1] = a[1] -1;

p[3][2] = p[4][2] = p[1][2] = p[2][2] = p[7][2] = p[8][2] = a[2];
if(a[2] == 9)
p[5][2] = 0;
else
p[5][2] = a[2] +1;
if(a[2] == 0)
p[6][2] = 9;
else
p[6][2] = a[2] -1;

p[3][3] = p[4][3] = p[5][3] = p[6][3] = p[1][3] = p[2][3] = a[3];
if(a[3]==9)
p[7][3] = 0;
else
p[7][3] = a[3] +1;
if(a[3] ==0)
p[8][3] = 9;
else
p[8][3] = a[3] -1;

for(int i=1;i<9;i++){
for(int c=0;c<4;c++){
forb.f[c] = p[i][c];
}
candi.push_back(forb);
}

for(int z=0;z<forbid.size();z++){
for(int i=0;i<candi.size();i++){
ok = false;
for(int c=0;c<4;c++){
if(candi[i].f[c] != forbid[z].f[c])
ok=true;
}
if(!ok)
candi.erase(candi.begin()+i);
}
}

for(int z=0;z<visited.size();z++){
for(int i=0;i<candi.size();i++){
ok = false;
for(int c=0;c<4;c++){
if(candi[i].f[c] != visited[z].f[c])
ok=true;
}
if(!ok)
candi.erase(candi.begin()+i);
}
}

/*
for(int i=0;i<candi.size();i++){
for(int c=0;c<4;c++){
cout<<candi[i].f[c];
}
cout<<endl;
}
*/
if(!candi.empty()) {
max = calc(candi[0].f,target);
n=0;
for(int i=1;i<candi.size();i++){
temp = calc(candi[i].f,target);
if(temp<max){
max = temp;
n=i;
}
}
//cout<<"1"<<endl;
/*
for(int c=0;c<4;c++){
cout<<candi[n].f[c];
}
cout<<endl;
*/
for(int c=0;c<4;c++){
cur[c] = candi[n].f[c];
}
counter++;
}
else {
cant = true;
}

}


int main(){
freopen("10067.txt","r",stdin);
freopen("10067O.txt","w",stdout);
bool notre;
int current,targe,fn,ff,T;

cin>>T;

for(int z=0;z<T;z++){

cin>>cur[0];
cin>>cur[1];
cin>>cur[2];
cin>>cur[3];

cin>>target[0];
cin>>target[1];
cin>>target[2];
cin>>target[3];

cin>>fn;

for(int i=0;i<fn;i++){
cin>>forb.f[0];
cin>>forb.f[1];
cin>>forb.f[2];
cin>>forb.f[3];

forbid.push_back(forb);
}

cant = false;
counter = 0;
//cout<<calc(cur,target)<<endl;

for(int z=0;z<forbid.size();z++){
ok = false;
for(int c=0;c<4;c++){
if(target[c] != forbid[z].f[c])
ok=true;
}
if(!ok)
cant = true;
}

while(!compara(cur,target) && !cant){
choose(cur);
for(int i=0;i<4;i++){
forb.f[i] = cur[i];
}
visited.push_back(forb);
}
if(cant)
cout<<"-1"<<endl;
else
cout<<counter<<endl;

// getch();
forbid.clear();
candi.clear();
visited.clear();
}
//getch();
return 0;
}

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 10067 - Playing with Wheels

Post by Articuno » Wed Mar 25, 2009 10:05 pm

Problem fixed....

Code: Select all

AC
Last edited by Articuno on Fri Mar 27, 2009 4:03 pm, edited 1 time in total.
May be tomorrow is a better day............ :)

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 10067 - Playing with Wheels

Post by Articuno » Fri Mar 27, 2009 4:00 pm

There is a test case where the starting sequence is in the forbidden list. I got some WA for that reason. :cry: Try out this input:

Code: Select all

1
8 0 5 6
6 5 0 8
1
8 0 5 6
Output:

Code: Select all

-1
May be tomorrow is a better day............ :)

erkape
New poster
Posts: 1
Joined: Mon Oct 12, 2009 4:02 am

Re: 10067 - Playing with Wheels

Post by erkape » Mon Oct 12, 2009 4:08 am

still got a WA, i already checked all test cases in the post and it was right.. but still WA..
is there any other special test case?

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10067 - Playing with Wheels

Post by Shafaet_du » Tue Nov 09, 2010 12:00 am

bfs :)

User avatar
outsbook
New poster
Posts: 26
Joined: Fri Oct 28, 2011 2:42 am

10067 - Playing with Wheels

Post by outsbook » Mon Nov 28, 2011 11:37 pm

BFS Problem

I represent the 4 digit as integer i.e. if 4 digits are 0 2 0 1 then I represent is 201, or 1 2 3 1 represent 1231

At first pregenerate all adjacency for 0 to 9999
For each value you got 8 adjacency value

Example If the 4 digit are 0 1 0 0 so, the value is 100
---set n=value
---set m=n%10, so m=100%10=0
---set L=R=value-m*1 now L=R=100
---set L =L + (m+1)%10 * 1 and R = R+ (m+9)%10 * 1 so, L=101 and R=109 . (101 and 109 are adjacency of 100)

---set n=n/10=100/10=10
---set m=n%10, so m=10%10=0
---set L=R=value-m*10 now L=R=100
---set L =L + (m+1)%10 * 10 and R = R+ (m+9)%10 * 10 so, L=110 and R=190 . (110 and 190 are adjacency of 100)

---set n=n/10=10/10=1
---set m=n%10, so m=1%10=1
---set L=R=value-m*100 now L=R=0
---set L =L + (m+1)%10 * 100 and R = R+ (m+9)%10 * 100 so, L=200 and R=0 . (200 and 0 are adjacency of 100)

---set n=n/10=1/10=0
---set m=n%10, so m=0%10=0
---set L=R=value-m*1000 now L=R=100
---set L =L + (m+1)%10 * 1000 and R = R+ (m+9)%10 * 1000 so, L=1100 and R=9100 . (1100 and 9100 are adjacency of 100)

Finally you got all adjacency for 100 are 101,109,110,190,200,0,1100,9100

Now run BFS from initial configuration
If you reach to target configuration then print length of shortest path.
other wise print -1

try this
Input:

Code: Select all

4

1 7 4 0
9 4 8 8
2
4 5 5 1
7 1 1 5

3 4 8 4
9 9 2 5
5
3 3 3 7
4 3 8 0
8 8 0 6
8 1 9 8
9 7 2 2

8 0 5 6
6 5 0 8
1
8 0 5 6

8 0 5 6
6 5 0 8
1
6 5 0 8
Output:

Code: Select all

11
14
-1
-1
"Learning to love yourself is the greatest love of all" - Michael Masser and Linda Creed

Post Reply

Return to “Volume 100 (10000-10099)”