511 - Do You Know the Way to San Jose? - Do nothing AC

[Carlos]

solved.

[zobayer]

no newline at end??

[porker2008]

You must loss the endl at the end of the output.

However, I don't think your algorithm is good enough.

But it will be ok if the time limit is not exceeded.

[amir.shani]

Hi

I cannot understand why I got WA ...
does someone have some inputs so I can check my code

here is my code

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define LETTERS_NUM 26
#define TRUE 1
#define FALSE 0


typedef unsigned char BOOLEAN;
typedef unsigned char UINT8;
typedef struct word_t
{
    char str[20];
    struct word_t *next;
} word;

typedef struct graph_node_t
{
    UINT8 smalls_num;
    UINT8 bigs_num;
    BOOLEAN participates;
    BOOLEAN small[LETTERS_NUM];
    BOOLEAN big[LETTERS_NUM];    
} graph_node;



int main()

{
    // Declarations
    word *words_head,*words_tail,*tmp;
    graph_node order_graph[LETTERS_NUM];
    UINT8 letter_order[LETTERS_NUM];
    int word_count = 0;
    int index1,index2;
    int letter_count = 0;
    int letter_count1;
    int letter_rank = 1;
    
    
    // Input of words;
    tmp = (word*)malloc(sizeof(word));
    scanf("%s",tmp->str);
    words_head = tmp;
    words_tail = words_head;
    
    while (strcmp(words_tail->str , "#")!= 0)
    {
        word_count++;
        tmp = (word*)malloc(sizeof(word));
        scanf("%s",tmp->str);
        words_tail ->next = tmp;
        words_tail = words_tail->next;
    }
    if (word_count == 0)
        return 0;
    
    // fill in the order graph
    memset(order_graph,0,sizeof(order_graph));
    
    tmp = words_head;
    while (strcmp((tmp->next)->str , "#")!= 0)
    {
        char* str1 = tmp->str;
        char* str2 = (tmp->next)->str;
        
        while ((*str1 == *str2) && (*str1++ != '\0') && (*str2++ != '\0'));
        
        if ((*str1 != '\0') && (*str2 != '\0'))
        {
            if (FALSE == order_graph[*str1 - 'A'].participates)
            {
                order_graph[*str1 - 'A'].participates = TRUE;
                letter_count++;
            }
            order_graph[*str1 - 'A'].bigs_num++;
            order_graph[*str1 - 'A'].big[*str2 - 'A'] = TRUE;
            if (FALSE == order_graph[*str2 - 'A'].participates)
            {
                order_graph[*str2 - 'A'].participates = TRUE;
                letter_count++;
            }
            order_graph[*str2 - 'A'].smalls_num++;
            order_graph[*str2 - 'A'].small[*str1 - 'A'] = TRUE;        
        }
        
        tmp  = tmp->next;
        
        
    }
    
    memset ( letter_order,0,LETTERS_NUM);
    letter_count1 = letter_count;
    while (letter_count > 0)
    {
        index1 = 0;
        while ((FALSE == order_graph[index1].participates) || (TRUE == order_graph[index1].participates && order_graph[index1].smalls_num > 0))
            index1++;
        order_graph[index1].participates = FALSE;
        letter_order[index1] = letter_rank++;
        for (index2 = 0 ; index2 < LETTERS_NUM ; index2++)
        {
            if (TRUE == order_graph[index1].big[index2])
            {
                order_graph[index2].small[index1] = FALSE;
                order_graph[index2].smalls_num--;
            }
        
        }
        
        letter_count--;
    
    }
    
    index1 = 1;
    while (index1 <= letter_count1)
    {
        index2=0;
        while (letter_order[index2] != index1)
            index2++;
        
        printf("%c", index2 + 'A');
        
        
        index1++; 
    
    }
    
    printf("\n");
    

    return 0;
}

[Tausiq]

try to avoid pointers
not because of i don't understand pointer well
but it's not recommended

I haven't checked ur code
but did test some inputs-outputs
and a question arose in my mind
why this code getting wrong ans ??
it should get Runtime error !

try these inputs

Code: Select all

Input 1 : 
QEWR
YSFDG
IOU
BASERB
BKUI
LKJN
YHDF
EWRRW
BDQ
#

Output 1:
QYIBLESOAKHWDFUJRNG

Input 2 :
REFEW
EGBA
ILR
#

Output 2:
REIGLFBAW

[ADEEB1172]

ANY ONE HELP ME PLZ TO SOLVING THIS PROB
I CAN'T UNDSTD ITS OUTPUT

[sohel]

Search the board first using the 'search' button/text located at the top right corner.
There are plenty of discussions for your problem. Make you post on an existing thread.

[b821213]

Code: Select all

#include <cstdio>
#include <cstring>

bool m[26][26];
int ind[26];
bool used[26];

void cmp(char a[],char b[]){
	for(int i=0;a[i]&&b[i];++i)
		if( a[i] != b[i] ){
			int t1 = a[i]-'A';
			int t2 = b[i]-'A';
			m[t1][t2] = 1;
			used[t1] = used[t2] = 1;
			++ind[t2];
			return;
		}
}

int main(){
	
	char last[100];
	char now[100];
	bool only = 1;
	
	scanf("%s",last);
	
	while(1){	
		scanf("%s",now);		
		if( now[0] == '#' ) break;

		only = 0;
		cmp(last,now);
		strcpy(last,now);
	}
	
	int q[26];
	int qf = 0 , qn = 0;
	
	for(int i=0;i<26;++i)
		if( used[i] && ind[i]==0 )
			q[qn++] = i;
	
	while( qf < qn ){
		int f = q[qf++];
		printf("%c",'A'+f);
		for(int i=0;i<26;++i)
			if( m[f][i] ){
				--ind[i];
				if( ind[i] <= 0 ) q[qn++] = i;
			}
	}
	
	if( only ) printf("%c",last[0]);
	
	printf("\n");

	return 0;
}

my code is very short , but i can't find any bug in my code.....

is there anyone can help me?

[Mira13]

Code: Select all

#include <cstdio>
void cmp(char a[],char b[]){
	for(int i=0;a[i]&&b[i];++i)
		if( a[i] != b[i] ){
			int t1 = a[i]-'A';
			int t2 = b[i]-'A';
			m[t1][t2] = 1;
			used[t1] = used[t2] = 1;
			++ind[t2];
			return;
		}
}

at the first glance, ur cmp function is not correct.
it doesn't take in account previous letters in the words, only current.

[shtorm941]

This code got a WA.
I really don't understand why.

Code: Select all

import java.util.*;
import java.io.*;
 
class Stack<T> {
        private LinkedList<T> storage = new LinkedList<T>();
        public void push(T v) {storage.addFirst(v);}
        public T peek() {return storage.getFirst();}
        public T pop() {return storage.removeFirst();}
        public boolean isEmpty() {return storage.isEmpty();}
        public String toString() {return storage.toString();}
}
 
public class Main 
{
        static int[][]  a = new int[128][128];
        static boolean[] used = new boolean[128];
        static boolean[] exist = new boolean[128];
        static boolean[] letterUsed = new boolean[128];
        static Stack<Character> q = new Stack<Character>();
 
        static Scanner sc = new Scanner(System.in);
    static PrintWriter pw = new PrintWriter(System.out);
 
   /*
    * function for search in s1 and s2 first different characters
    * if s1 equals s2 then return -1
    * else first different character index
    */
   static void usingLetters(String s1) {
           for(int i = 0; i < s1.length(); i++) {
                   letterUsed[s1.charAt(i)] = true; 
           }
   }
   static int strcmp(String s1, String s2) {
           
           for(int i = 0; i < Math.min(s1.length(), s2.length()); i++)
                   if(s1.charAt(i) != s2.charAt(i)) {
                           return i;
                   }
           
           return -1;
   }
        
    static void dfs(int v) {
        used[v] = true; 
        for(int i = 0; i < 128; i++) 
                if (a[v][i] == 1 && !used[i]) {
                        dfs(i); 
                }
        q.push((char)v);
    }
    
    static void topSort() {
        for(int i = 127; i >= 0; i--)
        {
                if(!used[i] && letterUsed[i] && i != '#')
                        dfs(i);
        }
    }
    
    
    
        public static void main(String[] args) throws IOException {
       
        try
        {
                String s1,s2;
                s1 = sc.nextLine();
                if(s1.charAt(0) == '#')
                        return;
                usingLetters(s1);
                do {
                        
                        s2 = sc.nextLine();
                                if(s2.charAt(0) == '#')
                                        break;
                        usingLetters(s2);
                    int i = strcmp(s1,s2);
 
                        if(i != -1) 
                                a[s1.charAt(i)][s2.charAt(i)] = 1;
                        
                        s1 = s2;
                        
                } while(true);
                
 
                topSort();
                
                while(!q.isEmpty()) {
                        pw.print(q.pop());
                }
 
        }
        finally
        {
                pw.close();
        }
        }
        
}

[brianfry713]

This code gets a RE.
http://ideone.com/uqmIz

Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: -1
at java.lang.String.charAt(String.java:686)
at Main.main(Main.java:77)

[shtorm941]

This code gets a RE.
http://ideone.com/uqmIz

Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: -1
at java.lang.String.charAt(String.java:686)
at Main.main(Main.java:77)

Sorry, I copy-pasted the wrong code. Now it is the code, which give a WA.(http://ideone.com/B3Ftc)

P.S.: Also I have edited code in first message.
P.P.S.: Sorry for my bad English!

[brianfry713]

Did you look through these threads already?
http://acm.uva.es/board/search.php?keyw ... mit=Search

I'm seeing a runtime error on this input:
BC
CA
CB
#

Exception in thread "main" java.util.NoSuchElementException: No line found
at java.util.Scanner.nextLine(Scanner.java:1516)
at Main.main(Main.java:72)

Output should be ABC

[shtorm941]

Did you look through these threads already?
http://acm.uva.es/board/search.php?keyw ... mit=Search

I'm seeing a runtime error on this input:
BC
CA
CB
#

Exception in thread "main" java.util.NoSuchElementException: No line found
at java.util.Scanner.nextLine(Scanner.java:1516)
at Main.main(Main.java:72)

Output should be ABC

It happend becouse last string in your input was "# ", but correct is "#".

I fixed it(http://ideone.com/uo2sn) and this don't help.(WA)

[brianfry713]

Print a newline at the end.