657 - The die is cast

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

Moderator: Board moderators

faiem
New poster
Posts: 14
Joined: Fri Aug 13, 2010 12:22 pm

WA: 657 - The die is cast

Post by faiem » Sun Feb 27, 2011 10:53 pm


I dnt know why i getting WA...I passed all I/O in boards...Help me pls..Here is my code.. :cry:

Code: Select all

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
long t=0;
class Die{

    private:
    char cast[60][60],ch;
    vector<long> v,x,s,sorting;
    long I,J;

    public:
    bool Input(long R,long C)
    {
        for(I=0;I<R;I++)
        {
            for(J=0;J<C;J++)
                {
                cast[I][J]=getchar();
                    }
            getchar();
            }
        return 1;
        }

    bool print(long R,long C)
    {

        for(I=0;I<R;I++){
            for(J=0;J<C;J++)
                printf("%c",cast[I][J]);
        printf("\n");
        }
    return 0;
    }
    
//(if DFS find any ' * ' make it 'S' )and (if find ' X ' makes it 'Y') 

    bool X_MAN(long x,long y,long R,long C)  //find 'X'
    {
        long a,b;
        a=x+1;b=y;
        if(a>=0&&a<R&&b>=0&&b<C)
        {
            if(cast[a][b]=='X')
            {
                cast[a][b]='Y';
                v.push_back(a);
                v.push_back(b);
                return 1;
                }
            else if(cast[a][b]=='*')
            {
                s.push_back(a);
                s.push_back(b);
                return 0;
                }

            }
        a=x-1;b=y;
        if(a>=0&&a<R&&b>=0&&b<C)
        {
            if(cast[a][b]=='X')
            {
                cast[a][b]='Y';
                v.push_back(a);
                v.push_back(b);
                return 1;
                }
            else if(cast[a][b]=='*')
            {
                s.push_back(a);
                s.push_back(b);
                return 0;
                }

            }
        a=x;b=y+1;
        if(a>=0&&a<R&&b>=0&&b<C)
        {
            if(cast[a][b]=='X')
            {
                cast[a][b]='Y';
                v.push_back(a);
                v.push_back(b);
                return 1;
                }
            else if(cast[a][b]=='*')
            {
                s.push_back(a);
                s.push_back(b);
                return 0;
                }

            }
        a=x;b=y-1;
        if(a>=0&&a<R&&b>=0&&b<C)
        {
            if(cast[a][b]=='X')
            {
                cast[a][b]='Y';
                v.push_back(a);
                v.push_back(b);
                return 1;
                }
            else if(cast[a][b]=='*')
            {
                s.push_back(a);
                s.push_back(b);
                return 0;
                }

            }
        return 0;
        }

    bool star_Man(long x,long y,long R,long C) //find '*'
    {
        long a,b;
        a=x+1;b=y;
        if(a>=0&&a<R&&b>=0&&b<C)
        {
            if(cast[a][b]=='*')
            {
                cast[a][b]='S';
                s.push_back(a);
                s.push_back(b);
                return 1;
                }
            else if(cast[a][b]=='X')
                {
                    t++;
                    v.push_back(a);
                    v.push_back(b);
                    X_DFS(R,C);
                    return 1;
                    }
            }
        a=x-1;b=y;
        if(a>=0&&a<R&&b>=0&&b<C)
        {
            if(cast[a][b]=='*')
            {
                cast[a][b]='S';
                s.push_back(a);
                s.push_back(b);
                return 1;
                }
            else if(cast[a][b]=='X')
                {
                    t++;
                    v.push_back(a);
                    v.push_back(b);
                    X_DFS(R,C);
                    return 1;
                    }
            }

        a=x;b=y+1;
        if(a>=0&&a<R&&b>=0&&b<C)
        {
            if(cast[a][b]=='*')
            {

                cast[a][b]='S';
                s.push_back(a);
                s.push_back(b);
                return 1;
                }
            else if(cast[a][b]=='X')
                {
                    t++;
                    v.push_back(a);
                    v.push_back(b);
                    X_DFS(R,C);
                    return 1;
                    }
            }

        a=x;b=y-1;
        if(a>=0&&a<R&&b>=0&&b<C)
        {
            if(cast[a][b]=='*')
            {
                cast[a][b]='S';
                s.push_back(a);
                s.push_back(b);
                return 1;
                }
            else if(cast[a][b]=='X')
                {
                    t++;
                    v.push_back(a);
                    v.push_back(b);
                    X_DFS(R,C);
                    return 1;
                    }
            }

        return 0;
        }

    bool X_DFS(long R,long C) // 'X' DfS 
    {
        long X,Y;
        X=v[v.size()-2];
        Y=v[v.size()-1];
        cast[X][Y]='Y';

        while(!v.empty())
        {
            X=v[v.size()-2];
            Y=v[v.size()-1];
            while(X_MAN(X,Y,R,C))
            {
                X=v[v.size()-2];
                Y=v[v.size()-1];
                }
            v.pop_back();
            v.pop_back();
            }
        return 0;
        }
//if DFS find any ' * ' make it 'S' and if find ' X ' makes it 'Y' 
    bool S_DFS(long R,long C)  // '*' dfs
    {
        long X,Y;
        X=s[s.size()-2];
        Y=s[s.size()-1];
        cast[X][Y]='S';
        while(star_Man(X,Y,R,C))
        {
            X=s[s.size()-2];
            Y=s[s.size()-1];
            }
        s.pop_back();
        s.pop_back();

        return 0;
        }
    bool scan(long R,long C) //scan the whole matrix
    {

        for(I=0;I<R;I++)
            for(J=0;J<C;J++)
                if(cast[I][J]=='X')
                {
                    t=1;              //counter to count how many 'X' on a single dice.
                    v.push_back(I);
                    v.push_back(J);
                    X_DFS(R,C);
                    if( !s.empty() )    //if input ....X.... i mean only X then 'vector s'  is empty so not need another DFS
                        S_DFS(R,C);
                    sorting.push_back(t);//total 'X' count for a single dice.
                    }

        sort(sorting.begin(),sorting.end());
        
        if( ! sorting.empty() )  //Print the Sorting Result here...
        {
            for(I=0;I<sorting.size()-1;I++)
                printf("%ld ",sorting[I]);
             printf("%ld",sorting.back());
                }
        else
            printf("0");  //I submit without this condition but still WA.
        printf("\n");
        return 1;
        }


    };


int main()
{
    long R,C,I,J,count=1;
/*
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
*/
    while(scanf("%ld %ld",&C,&R)==2)
    {
        getchar();
        if(R==0&&C==0)
            break;
        Die hard;  //creating obj.
        hard.Input(R,C); //taking input...
        printf("Throw %ld\n",count);
        hard.scan(R,C);  //scan the matrix...
        printf("\n");
        count++;
        }
    return 0;
    }


mostafa_angel
New poster
Posts: 23
Joined: Sun Oct 04, 2009 12:03 pm

Re: 657 - The die is cast

Post by mostafa_angel » Mon May 16, 2011 1:59 am

I got WA...
please Help me :(
by the way, all the available test cases in this site are have right output...

Code: Select all

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

int p[4][2]={{0,-1}, {1,0}, {0,1}, {-1,0}};

vector < string > grid;
bool mark[51][51];
vector < int > res;
int n , m , cnt;

void dfs(int row , int col);

void dfs2(int row , int col)
{
	//cout << "dfs2  x = " << row << "  y = " << col << endl; 
	mark[row][col] = true;
	for(int i=0 ; i < 4 ; i++)
	{
		int rt = row + p[i][0];
		int ct = col + p[i][1];
		if(rt >= 0 && rt < m && ct >= 0 && ct < n)
		{
			if(mark[rt][ct] ==  false)
			{
				if(grid[rt][ct] == 'X')
					dfs2(rt , ct);
			}
		}
	}
	for(int i=0 ; i < 4 ; i++)
	{
		int rt = row + p[i][0];
		int ct = col + p[i][1];
		if(rt >= 0 && rt < m && ct >= 0 && ct < n)
		{
			if(mark[rt][ct] ==  false)
			{
				if(grid[rt][ct] == '*')
					dfs(rt , ct);
			}
		}
	}
}

void dfs(int row , int col)
{
	mark[row][col] = true;
	for(int i=0 ; i < 4 ; i++)
	{
		int rt = row + p[i][0];
		int ct = col + p[i][1];
		if(rt >= 0 && rt < m && ct >= 0 && ct < n)
		{
			if(mark[rt][ct] ==  false)
			{
				if(grid[rt][ct] == 'X')
				{
					cnt++;
					dfs2(rt , ct);
				}
				if(grid[rt][ct] == '*')
					dfs(rt , ct);
			}
		}
	}
}

int main()
{
	string tmp;
	int ncase = 1;
	while(cin >> n >> m , n || m)
	{
		cnt = 0;
		getline(cin , tmp);
		grid.clear();
		res.clear();
		memset(mark , false, sizeof mark);
		for( int i=0 ; i < m ; i++)
		{
			getline(cin , tmp);
			grid.push_back(tmp);
		}

		for(int i = 0 ; i < m ; i++)
		{
			for(int j = 0 ; j < n ; j++)
			{
				if(mark[i][j] == false)
				{
					if(grid[i][j] == '*')
					{
						res.push_back(cnt);
						cnt = 0;
						dfs(i , j);
					}
					if(grid[i][j] == 'X')
					{
						res.push_back(cnt);
						cnt = 1;
						dfs2(i , j);
					}
				}
			}
		}
		if (cnt > 0)
			res.push_back(cnt);

		printf("Throw %d\n",ncase++);
		sort(res.begin()+1 , res.end());
		for(int i = 1 ; i < res.size() ; i++)
		{
			if(i > 1)
				cout << " ";
			cout << res[i];
		}
		cout << endl << endl;
	}
	return 0;
}

Ahmad
New poster
Posts: 16
Joined: Thu Apr 28, 2011 10:48 pm

Re: 657 - The die is cast

Post by Ahmad » Tue Aug 16, 2011 11:30 pm

for people who's still getting WA even with the previous I/O is OK
try this case ...

Code: Select all

10 2
..X**X***X
..XXXX....

ur output may be
1 1
but the right answer is
2

hope this helps ;)

torryton
New poster
Posts: 3
Joined: Thu Nov 10, 2011 12:45 pm

Re: 657 - The die is cast

Post by torryton » Mon Nov 14, 2011 12:09 pm

Many thanks!!! Just what i needed!! Nice that the problem was finally solved and i can start doing something else :D

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

Re: 657 - The die is cast

Post by outsbook » Sat Nov 19, 2011 6:41 pm

try this

Input:

Code: Select all

2 2
XX
XX
2 2
..
**
2 2
..
..
5 5
XX**X
XX**X
.....
.....
XX**X
Output:

Code: Select all

Throw 1
1

Throw 2
0

Throw 3
0

Throw 4
2 2

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

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 657 - The die is cast

Post by Scarecrow » Mon Apr 16, 2012 4:10 pm

i passed al the sample I/Os here, and my logic seems quite ok. but dont know, why am getiing WA. can any1 help,plz?

Code: Select all

AC
Last edited by Scarecrow on Tue Apr 17, 2012 8:21 pm, edited 1 time in total.
Do or do not. There is no try.

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

Re: 657 - The die is cast

Post by brianfry713 » Tue Apr 17, 2012 12:52 am

Input:

Code: Select all

3 2
XX*
X..
0 0
AC Output:

Code: Select all

Throw 1
1

Check input and AC output for thousands of problems on uDebug!

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 657 - The die is cast

Post by Scarecrow » Tue Apr 17, 2012 8:23 pm

thnx brianfry713 :D got AC with ur help
Do or do not. There is no try.

mostafiz93
New poster
Posts: 31
Joined: Thu Nov 24, 2011 12:08 am

Re: 657 - The die is cast

Post by mostafiz93 » Wed May 02, 2012 12:51 am

The picture will contain at least one die

so there is no input for which 0 comes!

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

Re: 657 - The die is cast

Post by brianfry713 » Wed May 02, 2012 11:16 pm

The picture will contain at least one die, and the numbers of dots per die is between 1 and 6, inclusive.
Check input and AC output for thousands of problems on uDebug!

Ronok1307
New poster
Posts: 8
Joined: Tue May 29, 2012 7:37 pm

Re: 657 - The die is cast

Post by Ronok1307 » Tue May 29, 2012 7:44 pm

Removed
Last edited by Ronok1307 on Mon Jun 04, 2012 9:31 pm, edited 1 time in total.

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

Re: 657 - The die is cast

Post by brianfry713 » Fri Jun 01, 2012 12:46 am

Don't use getchar() and count on it to be a newline. That won't work if there are extra spaces in the input file.
Check input and AC output for thousands of problems on uDebug!

SyFyKid
New poster
Posts: 26
Joined: Tue May 08, 2012 9:47 am

Re: 657 - The die is cast

Post by SyFyKid » Mon Jun 04, 2012 6:02 pm

I am getting crazy solving this problem... :evil:

here is my code: http://paste.ubuntu.com/1023130/
I have tested ALL data that I found here... I have checked my algo with all possible and impossible test cases... works OK... but system shows me WA.
Really need help.

Thx.

Code: Select all

import java.io.*;
//import java.math.BigInteger;
import java.util.*;
//import java.awt.geom.*;
//import java.util.regex.*;
import java.util.StringTokenizer;

public class Main implements Runnable {
    int throwCount = 1;
    ArrayList<String> output = new ArrayList<String>();

    void solve(){
        console(System.getProperty("ONLINE_JUDGE") != null);

        while(true){
            int y = RI(), x = RI();
            if(x==0 && y==0) break;

            char[][] image = new char[x][y];
            for(int i=0; i<x; i++){
                String line = RLine().trim();

                for(int j=0; j<y; j++){
                    image[i][j] = line.charAt(j);
                }
            }

            solve(x, y, image);

            ++throwCount;
        }

        for(int i=0; i<output.size()-1; i+=2){
            out.println(output.get(i));
            out.print(output.get(i+1));

            if(i == output.size() - 2){ out.println(); } else out.println("\n");
        }
    }

    void solve(int height, int width, char[][] image){
        HashSet<Integer> used = new HashSet<Integer>();
        ArrayList<Integer> points = new ArrayList<Integer>();
        HashSet<Integer> component;
        boolean flag = false;

        for(int i=0; i<height; i++){
            for(int j=0; j<width; j++){
                if(!used.contains(encode(i, j)) && (image[i][j] == 'X' || image[i][j] == '*')){
                    flag = true;
                    component = getFullComponent(i, j, used, image);

                    int dots = countDots(component, image);
                    points.add(dots);
                }
            }
        }

        if(!flag){
            points.add(0);
        }

        Collections.sort(points);

        // generating output
        StringBuilder sb = new StringBuilder("");

        output.add("Throw "+throwCount);
        for(int v:points) sb.append(Integer.toString(v)+" ");
        output.add(sb.toString().trim());
    }

    HashSet<Integer> getFullComponent(int x, int y, HashSet<Integer> used, char[][] image){
        HashSet<Integer> component = new HashSet<Integer>();
        Queue<Integer> q = new LinkedList<Integer>();

        q.add(encode(x, y));
        used.add(encode(x, y));
        component.add(encode(x, y));

        while(!q.isEmpty()){
            int encodedValue = q.poll();
            int curX = encodedValue/PRIME, curY = encodedValue%PRIME;

            for(int i=0; i<DX4.length; i++){
                int newX = curX + DX4[i], newY = curY + DY4[i];

                if(newX>=0 && newX<image.length && newY>=0 && newY<image[0].length && !used.contains(encode(newX, newY)) && image[newX][newY]!='.'){
                    int newEncodedValue = encode(newX, newY);

                    used.add(newEncodedValue);
                    q.add(newEncodedValue);
                    component.add(newEncodedValue);
                }
            }
        }

        return component;
    }

    int countDots(HashSet<Integer> component, char[][] image){
        int dots = 0;
        HashSet<Integer> localUsed = new HashSet<Integer>();
        Queue<Integer> q = new LinkedList<Integer>();

        for(int encodedValue:component){
            int x = encodedValue/PRIME, y = encodedValue%PRIME;

            if(image[x][y] == '*' || localUsed.contains(encodedValue)) continue;

            dots++;

            localUsed.add(encodedValue);
            q.add(encodedValue);

            while(!q.isEmpty()){
                int curEncodedValue = q.poll();
                int curX = curEncodedValue/PRIME, curY = curEncodedValue%PRIME;

                for(int i=0; i<DX4.length; i++){
                    int newX = curX + DX4[i], newY = curY + DY4[i];
                    int newEncodedValue = encode(newX, newY);

                    if(!localUsed.contains(newEncodedValue) && newX>=0 && newX<image.length && newY>=0 && newY<image[0].length && image[newX][newY]=='X'){
                        q.add(newEncodedValue);
                        localUsed.add(newEncodedValue);
                    }
                }
            }
        }

        return dots;
    }

    int encode(int a, int b){
        return PRIME*a + b;
    }

    // ---------------------------------------------------------- TEMPLATE ----------------------------------------------
    final int PRIME = 107;
    final int[] DX4 = new int[]{-1, 0, +1, 0}, DY4 = new int[]{0, +1, 0, -1};
    final int[] DX8 = new int[]{-1, -1, -1, 0, +1, +1, +1, 0}, DY8 = new int[]{-1, 0, +1, +1, +1, 0, -1, -1};

    StringTokenizer st;
    PrintWriter out;
    BufferedReader br;
    boolean eof = false;

    public static void main(String[] args) {
        new Thread(new Main()).start();
    }

    String nextToken(){
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }

    String RLine() {
        String ret;
        try {
            ret = br.readLine();
        } catch (Exception e) {
            ret = "";
        }
        if (ret == null) {
            eof = true;
            return null;
        }
        return ret;
    }

    int RC() {
        try {
            return br.read();
        } catch (Exception e) {
            return -1;
        }
    }

    String RS() {
        return nextToken();
    }

    int RI() {
        return Integer.parseInt(nextToken());
    }

    long RL() {
        return Long.parseLong(nextToken());
    }

    double RD() {
        return Double.parseDouble(nextToken());
    }

    void raiseError(){
        int k = 10/0;
    }

    void console(boolean f) {
        if (f) {
            br = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(new OutputStreamWriter(System.out));
        } else {
            try {
                File input = new File("input.txt");
                if (!input.exists()) {
                    input.createNewFile();
                }

                br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
                out = new PrintWriter(new OutputStreamWriter(new FileOutputStream("output.txt")));
            } catch (Exception e) {
                e.printStackTrace();
                System.exit(111);
            }
        }
    }

    @Override
    public void run() {
        solve();
        out.close();
    }
}

Ronok1307
New poster
Posts: 8
Joined: Tue May 29, 2012 7:37 pm

Re: 657 - The die is cast

Post by Ronok1307 » Mon Jun 04, 2012 9:32 pm

brianfry713 wrote:Don't use getchar() and count on it to be a newline. That won't work if there are extra spaces in the input file.
Thanks a lot. I changed the scanf-getchar to a gets-sscanf and got AC. :D

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

Re: 657 - The die is cast

Post by brianfry713 » Mon Jun 04, 2012 10:55 pm

SyFyKid wrote:I am getting crazy solving this problem... :evil:
Don't read and write to a file.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 6 (600-699)”