## 10067 - Playing with Wheels

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

Moderator: Board moderators

Try the cases...

Input:
Code: Select all
`21 7 4 09 4 8 824 5 5 17 1 1 53 4 8 49 9 2 553 3 3 74 3 8 08 8 0 68 1 9 89 7 2 2`

Output:
Code: Select all
`1114`

Hope these help.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

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
`21 7 4 09 4 8 824 5 5 17 1 1 53 4 8 49 9 2 553 3 3 74 3 8 08 8 0 68 1 9 89 7 2 2`

Output:
Code: Select all
`1114`

Hope these help.
cs_lyxaa
New poster

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

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

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

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.
Learning poster

Posts: 76
Joined: Tue Apr 16, 2002 10:07 am
Location: Mauritius

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
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 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   1int 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;}`
Learning poster

Posts: 76
Joined: Tue Apr 16, 2002 10:07 am
Location: Mauritius

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
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

I haven't tried yet.

Will try and let you know..

Thanks for the help.
Learning poster

Posts: 76
Joined: Tue Apr 16, 2002 10:07 am
Location: Mauritius

Jan wrote:Try the cases...

Input:
Code: Select all
`21 7 4 09 4 8 824 5 5 17 1 1 53 4 8 49 9 2 553 3 3 74 3 8 08 8 0 68 1 9 89 7 2 2`

Output:
Code: Select all
`1114`

Hope these help.

Thanks for your test data!
barry800414
New poster

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

### Re: 10067 - Playing with Wheels

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[i] != b[i]){
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[i]-b[i]);
if(d>5){
if(a[i]<b[i]){
sum += a[i] + (9-b[i])+1;
}else{
sum += b[i] + (9-a[i]) +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;
}
ary
New poster

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

### Re: 10067 - Playing with Wheels

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

There is a test case where the starting sequence is in the forbidden list. I got some WA for that reason. Try out this input:
Code: Select all
`18 0 5 66 5 0 818 0 5 6`

Output:
Code: Select all
`-1`
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

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?
erkape
New poster

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

### Re: 10067 - Playing with Wheels

bfs
Shafaet_du
Experienced poster

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

### Re: 10067 - Playing with Wheels

Tried every test case in this thread and I pass all of them, still I keep getting WA.. Not sure what else to do, I made sure I handled cases where the start is the target, the target is in the forbidden list, 9+1 goes to 0, 0-1 goes to 9. Are there any other elementary cases I could be tripping up on? Thanks

10 Cases:

Code: Select all
`109 9 9 99 9 9 919 9 9 99 9 9 90 0 0 010 0 0 09 9 9 90 0 0 019 9 9 93 3 4 21 2 0 913 4 4 29 9 9 90 0 0 138 9 0 76 5 4 22 3 4 59 9 9 90 0 1 138 9 0 76 5 4 22 3 4 50 0 0 00 0 0 138 9 0 76 5 4 22 3 4 51 5 7 97 4 3 168 9 0 76 5 4 22 3 4 54 4 4 46 5 7 98 5 7 91 5 7 97 4 3 168 9 0 76 5 4 22 3 4 54 4 4 40 0 0 08 5 7 91 7 1 07 0 0 061 9 0 71 4 2 21 3 4 54 4 4 42 5 0 91 1 7 9`

My Output:
Code: Select all
`0-141056111118`
Monty
New poster

Posts: 7
Joined: Fri Feb 17, 2012 10:24 am

PreviousNext