11995 - I Can Guess the Data Structure!

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

Moderator: Board moderators

sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

11995 - I Can Guess the Data Structure!

Post by sith » Wed Jun 20, 2012 11:14 am

Hello guys!
I've got runtime error
What is wrong with my solution (java)

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) {                
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String line;
        try {
            while ((line = reader.readLine()) != null) {
                int actionCount = Integer.parseInt(line.trim());
                List<DataStructure> dataStructures = new ArrayList<DataStructure>();
                dataStructures.add(new PriorityQueueDataStructure());
                dataStructures.add(new QueueDataStructure());
                dataStructures.add(new StackDataStructure());

                for (int i = 0; i < actionCount; i++) {
                    StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

                    int action = Integer.parseInt(tokenizer.nextToken());
                    int value = Integer.parseInt(tokenizer.nextToken());


                    switch (action) {
                        case 1:
                            for (DataStructure dataStructure : dataStructures) {
                                dataStructure.add(value);
                            }
                            break;
                        case 2:
                            for (Iterator<DataStructure> iterator = dataStructures.iterator(); iterator.hasNext(); ) {
                                final DataStructure dataStructure = iterator.next();
                                if (dataStructure.take() != value) {
                                    iterator.remove();
                                }
                            }
                            break;
                    }
                }
                if (dataStructures.isEmpty()) {
                    System.out.println("impossible");
                }
                else if (dataStructures.size() > 1) {
                    System.out.println("not sure");
                }
                else {
                    System.out.println(dataStructures.iterator().next().name());
                }
            }
        }
        catch (IOException e) {
        }
    }


    static interface DataStructure {
        int take();

        void add(int value);

        String name();
    }

    static class StackDataStructure implements DataStructure {

        private Stack<Integer> stack = new Stack<Integer>();

        public int take() {
            return stack.pop();
        }

        public void add(final int value) {
            stack.add(value);
        }

        public String name() {
            return "stack";
        }
    }

    static class QueueDataStructure implements DataStructure {

        private Queue<Integer> queue = new LinkedList<Integer>();

        public int take() {
            return queue.poll();
        }

        public void add(final int value) {
            queue.add(value);
        }

        public String name() {
            return "queue";
        }
    }

    static class PriorityQueueDataStructure implements DataStructure {

        private PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(256,new Comparator<Integer>() {
            public int compare(final Integer o1, final Integer o2) {
                return o2.compareTo(o1);
            }
        });

        public int take() {
            return priorityQueue.poll();
        }

        public void add(final int value) {
            priorityQueue.add(value);
        }

        public String name() {
            return "priority queue"; 
        }
    }
}

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

Re: 11995 - I Can Guess the Data Structure!

Post by brianfry713 » Wed Jun 20, 2012 10:46 pm

Check if the data structure is empty before you remove an element.
Check input and AC output for thousands of problems on uDebug!

sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

Re: 11995 - I Can Guess the Data Structure!

Post by sith » Thu Jun 21, 2012 1:21 am

Thanks
But now I've got WA

Code: Select all

AC
Last edited by sith on Thu Jun 21, 2012 10:23 pm, edited 1 time in total.

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

Re: 11995 - I Can Guess the Data Structure!

Post by brianfry713 » Thu Jun 21, 2012 8:22 pm

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

Re: 11995 - I Can Guess the Data Structure!

Post by sith » Thu Jun 21, 2012 10:23 pm

Thanks it works!

naved92
New poster
Posts: 3
Joined: Thu Jul 05, 2012 1:10 pm

Re: 11995 - I Can Guess the Data Structure!

Post by naved92 » Thu Jul 05, 2012 1:15 pm

Can anyone help me?I m continuously getting runtime error...:(

Code: Select all

removed after AC

ramoto
New poster
Posts: 1
Joined: Sun Aug 26, 2012 8:15 pm

Re: 11995 - I Can Guess the Data Structure!

Post by ramoto » Sun Aug 26, 2012 8:18 pm

Hello guys!
I've got wrong answer
What is wrong with my java solution?

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {
	public static void main(String[] args) throws IOException
	{
			
		int qtd;
		
		boolean isStack = true;
		boolean isQueue = true;
		boolean isQueueP = true;
		
		String temp;
			
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer stringtoken;
		
		String linha;
		
		linha = br.readLine();
		
		qtd = Integer.parseInt(linha);
		
		
		while(qtd > 0)
		{	
			qtd = Integer.parseInt(linha);
			
			int[] stack = new int[qtd];
			int[] queue = new int[qtd];
			int[] queuep = new int[qtd];
				
			int last = -1;
			int first = 0;
			int max = 0;
			
			int istack = 0;
			int iqueue = 0;
			int iqueuep = 0;
			
				
			for(int i = 0; i < qtd; i++)
			{
				temp = br.readLine();
				stringtoken = new StringTokenizer(temp);
				int op = Integer.parseInt(stringtoken.nextToken());
				int el = Integer.parseInt(stringtoken.nextToken());
				if (el < 0) {
					el = el * -1;
				}
				
				if(isStack)
				{
					if(op == 1)
					{
						stack[istack] = el;
						last++;
						istack++;
					}
					else
					{
						if (last == -1) {
							isStack = false;
						}
						else if(el == stack[last] && istack != 0)
						{
							last--;
						}
						else
						{
							isStack = false;
						}
						
					}
				}
				if(isQueue)
				{
					if(op == 1)
					{
						queue[iqueue] = el;
						iqueue++;
					}
					else
					{
						if(el == queue[first] && iqueue != 0)
						{
							first++;
						}
						else
						{
							isQueue = false;
						}
						
					}
				}
				if(isQueueP)
				{
					if(op == 1)
					{
						queuep[iqueuep] = el;
						iqueuep++;
						
						if(el > max)
						{
							max = el;
						}
					}
					else
					{	
						if(el == max && iqueuep != 0)
						{					
							int max_temp = max;
							
							max = 0;
							
							for(int j = 0; j < iqueuep; j++)
							{
								if(queuep[j] > max && queuep[j] != max_temp)
								{
									max = queuep[j]; 
								}
								
								if(queuep[j] == max_temp)
								{
									queuep[j] = -1;
								}
							}
							
						}
						else
						{
							isQueueP = false;
						}
						
					}
				}
			}
	        if((isStack && isQueue) || (isStack && isQueueP) || (isQueue && isQueueP))  
	        {
	        	System.out.println("not sure");
	        }
	        else if(isStack)  
			{
	            System.out.println("stack");
			}
	        else if(isQueue) 
	        { 
	            System.out.println("queue");
	        }
	        else if(isQueueP) 
	        {
	        	System.out.println("priority queue");  
	        }
	        else  
	        {
	        	System.out.println("impossible");  
	        }
			
			isStack = true;
			isQueue = true;
			isQueueP = true;
			
			if(!br.ready())
			{
				qtd = -1;
			}
			else
			{
				linha = br.readLine();
			}
			
		}
			
	}
}

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

Re: 11995 - I Can Guess the Data Structure!

Post by brianfry713 » Mon Aug 27, 2012 8:40 pm

Input:

Code: Select all

8
1 3
1 2
2 2
2 3
1 1
1 4
2 4
2 1
stack
Check input and AC output for thousands of problems on uDebug!

mohsen1373
New poster
Posts: 1
Joined: Fri Nov 30, 2012 1:10 pm

Re: 11995 - I Can Guess the Data Structure!

Post by mohsen1373 » Fri Nov 30, 2012 1:15 pm

Hi all, here is my code and it works for sample inputs and every other input I've made, but I get wrong answer !
Can anyone help me with that ?

Code: Select all

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
int main()
{
    int n,N;
    while( cin >> n )
    {
        N = n ;
        vector <int> v;
        int qu,st,ps;
        qu = st = ps =  0 ;
        int Max = -1 ;
        int twoCounter = 0 ;
        while( n-- )
        {
            int o, x;
            cin >> o >> x ;



            if( o == 1 )
            {
                v.push_back(x);
                if( x > Max )
                    Max = x ;

            }
            else
            {
                twoCounter++ ;
                for( int i = 0 ; i < v.size() ; i++ )
                {
                    if( v[i] == x )
                    {
                        if( i == v.size()-1 )
                            st++ ;

                        if( i == 0 )
                            qu++ ;

                        if( x == Max )
                            ps++ ;

                        v.erase(v.begin()+i,v.begin()+i+1);
                        if( ps == twoCounter )
                        {
                            Max = -1 ;
                            for( int j = 0 ; j < v.size() ; j++ )
                            {
                                if( v[j] > Max )
                                    Max = v[j];
                            }
                        }
                        break;
                    }
                }
            }
        }

        if( st == twoCounter && qu != twoCounter && ps != twoCounter )
            cout << "stack" << endl ;
        else if( st != twoCounter && qu == twoCounter && ps != twoCounter )
            cout << "queue" << endl ;
        else if( st != twoCounter && qu != twoCounter && ps == twoCounter )
            cout << "priority queue" << endl ;
        else if( st != twoCounter && qu != twoCounter && ps != twoCounter )
            cout << "impossible" << endl ;
        else
            cout << "not sure" << endl ;
    }
    return 0;
}


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

Re: 11995 - I Can Guess the Data Structure!

Post by brianfry713 » Sat Dec 08, 2012 6:46 am

Input:

Code: Select all

4
1 1
1 2
1 2
2 2
AC output:
not sure
Check input and AC output for thousands of problems on uDebug!

zlshang
New poster
Posts: 4
Joined: Wed Jan 02, 2013 8:51 pm

Re: 11995 - I Can Guess the Data Structure!

Post by zlshang » Wed Jan 02, 2013 9:08 pm


hello guys!
I'v got wrong answer! :cry:
what's wrong with my codes(c++) PLZZZZ...

Code: Select all

#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#include <string.h>
#include <iostream>
#include <cmath>
using namespace std;
int n,m,a[1000001],b[1000001],c[1000000],k,v;
bool  cmp(int x,int y)
{
	return a[x]<a[y];	
} 

int find( )
{
	int left=0,right=n-1,mid;
	while(left<right)
		{
			mid=(left+right)/2;	
			if(a[b[c[mid]]]<v) left=mid+1;
			else right=mid;	
		}	
	return left;
}
int main()
{
	while(scanf("%d%d",&n,&m)==2)
		{
			memset(a,1,sizeof(a));
			for(int i=1;i<=n;i++)
				{
					scanf("%d",&a[i]);
					b[i]=c[i]=i;
				}
			sort(b+1,b+n+1,cmp);
			for(int i=0;i<m;i++)
				{
					int p;
					scanf("%d%d",&k,&v);
					p=find();			
					if(p==0) 
						{
							if(a[b[0]]==v) printf("%d\n",a[b[k-1]]==v? b[k-1]:0);
							else if(a[b[1]]==v) printf("%d\n",a[b[k]]==v? b[k]:0);
							else printf("0\n");				
						}
					else 
						{
					
							if(a[b[p-1]]==v) printf("%d\n",a[b[p+k-2]]==v? b[p+k-2]:0);
							else if(a[b[p]]==v) printf("%d\n",a[b[p+k-1]]==v? b[p+k-1]:0);
							else if(a[b[p+1]]==v) printf("%d\n",a[b[p+k]]==v? b[p+k]:0);
							else printf("0\n");					
						}
				}
		}
		return 0;
  
}
/*
8 9
1 3 2 2 4 3 2 1
1 3
2 4
3 2
4 2

8 4
1 3 4 5 6 7 8 9
*/

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

Re: 11995 - I Can Guess the Data Structure!

Post by brianfry713 » Wed Jan 02, 2013 9:33 pm

Doesn't match the sample I/O. Is this code for problem #11995?
Check input and AC output for thousands of problems on uDebug!

zlshang
New poster
Posts: 4
Joined: Wed Jan 02, 2013 8:51 pm

Re: 11995 - I Can Guess the Data Structure!

Post by zlshang » Thu Jan 03, 2013 9:34 am

brianfry713 wrote:Doesn't match the sample I/O. Is this code for problem #11995?
I so sorry! I forget that this problem #11995 I have solved. And this question is for the problem #11991. SORRY!! Thank you all the same :D

ajmer
New poster
Posts: 7
Joined: Thu Mar 07, 2013 2:16 am

Re: 11995 - I Can Guess the Data Structure!

Post by ajmer » Thu Mar 07, 2013 2:17 am

Why do I get wrong answer? Seems to work on every sample input:

(C)

Code: Select all

AC
Last edited by ajmer on Fri Mar 08, 2013 2:21 am, edited 1 time in total.

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

Re: 11995 - I Can Guess the Data Structure!

Post by brianfry713 » Fri Mar 08, 2013 12:55 am

Here is the gift I/O from:
http://uva.onlinejudge.org/index.php?op ... ontest=278
Input:

Code: Select all

8
1 36
1 65
2 65
1 75
1 62
1 42
1 58
2 75
10
1 84
1 59
1 51
2 51
1 41
1 59
2 59
1 70
1 67
2 67
10
1 24
1 37
1 87
1 25
1 74
1 9
2 87
1 64
1 49
2 74
7
1 84
1 36
1 61
1 4
2 4
1 61
2 61
8
1 76
1 83
1 22
1 11
1 8
1 48
2 83
1 90
9
1 1
2 1
1 36
1 85
1 4
2 4
1 51
1 15
2 15
9
1 64
1 85
1 33
1 34
1 58
1 70
2 85
2 69
2 64
9
1 72
1 20
2 72
2 20
1 89
1 60
1 39
2 89
1 77
5
1 63
2 63
1 57
1 66
1 73
2
1 49
2 49
10
1 48
1 90
1 81
2 48
1 42
2 90
2 81
2 42
1 44
1 63
7
1 88
1 63
2 88
1 90
2 63
1 73
1 15
3
1 86
1 64
2 86
7
1 38
1 68
1 14
2 38
1 27
1 83
2 68
Output:

Code: Select all

priority queue
stack
priority queue
stack
priority queue
stack
impossible
not sure
not sure
not sure
queue
queue
not sure
queue
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 119 (11900-11999)”