JWorld@TW the best professional Java site in Taiwan
      註冊 | 登入 | 全文檢索 | 排行榜  

» JWorld@TW » Java 技巧文件 » UVA(ACM)討論  

按列印兼容模式列印這個話題 列印話題    把這個話題寄給朋友 寄給朋友    訂閱主題
reply to topicthreaded modego to previous topicgo to next topic
本主題所含的標籤
無標籤
作者 UVA 10298 Power Strings TLE / RE
likecoding





發文: 4
積分: 0
於 2014-12-16 07:36 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
source : http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1239

以下是我一開始寫的程式,但是上傳UVA 一直Time limit exceeded
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.*;
 
public class Main{    
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    
    while( sc.hasNext() ){
      String inputStr = sc.nextLine();
      if( inputStr.matches("."))
        break;
      int maxLen = inputStr.length();
      String matchStr = "";
      int count = 1;
      //boolean noAnswer = true;
      
      for( int i=1 ; i<=maxLen/2 ; i++ ){
        if( maxLen%i != 0 ){
          matchStr += inputStr.charAt(i-1); 
          continue;
        }
        //System.out.println("i:"+i);
        matchStr += inputStr.charAt(i-1); 
        int len = matchStr.length();
        //System.out.println("len:"+len);
        int startIndex = len;
        int endIndex = startIndex+len;
        while( endIndex<=maxLen && matchStr.equals( inputStr.substring(startIndex,endIndex) ) ){
          startIndex += len;
          endIndex += len;
          count++;
        }
        if( startIndex == maxLen ){
          break;
        }
        else{
          count=1;
        }
      }
      System.out.println(count);
      
    }
  }
 
}


後來我看到秒殺大大的 "用 Java 參加 UVa Online Judge 必備程式 [精華] " ,想說可能是因為做 java 做I/O時太慢,
所以每次都超過時間,於是改用大大提供的方法而不用 java 的 Scanner ,以下是我修改後的版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
public class Main{
  public static byte[] cinbuf = new byte[1024];
   
   
    public static String readToken() {
      int offset = 0;
      int bytedata = -1;
      
      try {
        
        bytedata = System.in.read();
        while(bytedata==9||bytedata==10||bytedata==13||bytedata==32) {
          bytedata = System.in.read();
        }
   
        
        while(bytedata!=-1) {
          if(bytedata==9||bytedata==10||bytedata==13||bytedata==32) {
            break;
          } else {
            cinbuf[offset++] = (byte)bytedata;
          }
          bytedata = System.in.read();
        }
      } catch(Exception e) {}
      
      if(offset+bytedata==-1) return null;
      return new String(cinbuf,0,offset);
    }
    
    
    public static String readLine() {
      int offset = 0;
      int bytedata = -1;
      
      try {
        
        bytedata = System.in.read();
        while(bytedata!=-1) {
          if(bytedata==10) {
            break;
          } else {
            cinbuf[offset++] = (byte)bytedata;
          }
          bytedata = System.in.read();
        }
      } catch(Exception e) {}
   
      if(offset+bytedata==-1) return null; 
      if(cinbuf[offset-1]=='\r') offset--; 
      return new String(cinbuf,0,offset);
    }
    
    
    public static int parseInt(String s) {
      int i;
      int mul = 10;
      int value = s.charAt(s.length()-1)-48;
      
      for(i=s.length()-2;i>=0;i--) {
        value += (s.charAt(i)-48)*mul;
        mul *= 10;
      }
      
      return value;
    }
    public static void main(String[] args) {
      
      String inputStr;
      while( ( inputStr=readLine() ) != null ){
        
        if( inputStr.matches("."))
          break;
        int maxLen = inputStr.length();
        String matchStr = "";
        int count = 1;
        
        for( int i=1 ; i<=maxLen/2 ; i++ ){
          if( maxLen%i != 0 ){
            matchStr += inputStr.charAt(i-1); 
            continue;
          }
  
          matchStr += inputStr.charAt(i-1); 
          int len = matchStr.length();
          int startIndex = len;
          int endIndex = startIndex+len;
          while( endIndex<=maxLen && matchStr.equals( inputStr.substring(startIndex,endIndex) ) ){
            startIndex += len;
            endIndex += len;
            count++;
          }
          if( startIndex == maxLen ){
            break;
          }
          else{
            count=1;
          }
        }
        System.out.println(count);
        
      }
    }
}


可是這次上傳UVA卻一直 Runtime error ,完全搞不懂為什麼。

我自己在eclipse上測試時以上兩個都可以執行,
第一個程式還可以推測可能是因為Scanner做I/O太慢的關係,
第二個程式就真的看不出哪裡有問題,連推測都想不出來。

想知道我到底是因為邏輯哪裡有問題,或是演算法不夠好 ,
還是因為還有什麼我不知道的事才過不了UVA,請大大幫忙。


likecoding edited on 2014-12-16 07:46
reply to postreply to post
作者 Re:UVA 10298 Power Strings TLE / RE [Re:likecoding]
roysiu





發文: 236
積分: 0
於 2014-12-16 08:46 user profilesend a private message to usersend email to roysiureply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
likecoding wrote:
source : http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1239

以下是我一開始寫的程式,但是上傳UVA 一直Time limit exceeded
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.*;
 
public class Main{    
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    
    while( sc.hasNext() ){
      String inputStr = sc.nextLine();
      if( inputStr.matches("."))
        break;
      int maxLen = inputStr.length();
      String matchStr = "";
      int count = 1;
      //boolean noAnswer = true;
      
      for( int i=1 ; i<=maxLen/2 ; i++ ){
        if( maxLen%i != 0 ){
          matchStr += inputStr.charAt(i-1); 
          continue;
        }
        //System.out.println("i:"+i);
        matchStr += inputStr.charAt(i-1); 
        int len = matchStr.length();
        //System.out.println("len:"+len);
        int startIndex = len;
        int endIndex = startIndex+len;
        while( endIndex<=maxLen && matchStr.equals( inputStr.substring(startIndex,endIndex) ) ){
          startIndex += len;
          endIndex += len;
          count++;
        }
        if( startIndex == maxLen ){
          break;
        }
        else{
          count=1;
        }
      }
      System.out.println(count);
      
    }
  }
 
}


後來我看到秒殺大大的 "用 Java 參加 UVa Online Judge 必備程式 [精華] " ,想說可能是因為做 java 做I/O時太慢,
所以每次都超過時間,於是改用大大提供的方法而不用 java 的 Scanner ,以下是我修改後的版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
public class Main{
  public static byte[] cinbuf = new byte[1024];
   
   
    public static String readToken() {
      int offset = 0;
      int bytedata = -1;
      
      try {
        
        bytedata = System.in.read();
        while(bytedata==9||bytedata==10||bytedata==13||bytedata==32) {
          bytedata = System.in.read();
        }
   
        
        while(bytedata!=-1) {
          if(bytedata==9||bytedata==10||bytedata==13||bytedata==32) {
            break;
          } else {
            cinbuf[offset++] = (byte)bytedata;
          }
          bytedata = System.in.read();
        }
      } catch(Exception e) {}
      
      if(offset+bytedata==-1) return null;
      return new String(cinbuf,0,offset);
    }
    
    
    public static String readLine() {
      int offset = 0;
      int bytedata = -1;
      
      try {
        
        bytedata = System.in.read();
        while(bytedata!=-1) {
          if(bytedata==10) {
            break;
          } else {
            cinbuf[offset++] = (byte)bytedata;
          }
          bytedata = System.in.read();
        }
      } catch(Exception e) {}
   
      if(offset+bytedata==-1) return null; 
      if(cinbuf[offset-1]=='\r') offset--; 
      return new String(cinbuf,0,offset);
    }
    
    
    public static int parseInt(String s) {
      int i;
      int mul = 10;
      int value = s.charAt(s.length()-1)-48;
      
      for(i=s.length()-2;i>=0;i--) {
        value += (s.charAt(i)-48)*mul;
        mul *= 10;
      }
      
      return value;
    }
    public static void main(String[] args) {
      
      String inputStr;
      while( ( inputStr=readLine() ) != null ){
        
        if( inputStr.matches("."))
          break;
        int maxLen = inputStr.length();
        String matchStr = "";
        int count = 1;
        
        for( int i=1 ; i<=maxLen/2 ; i++ ){
          if( maxLen%i != 0 ){
            matchStr += inputStr.charAt(i-1); 
            continue;
          }
  
          matchStr += inputStr.charAt(i-1); 
          int len = matchStr.length();
          int startIndex = len;
          int endIndex = startIndex+len;
          while( endIndex<=maxLen && matchStr.equals( inputStr.substring(startIndex,endIndex) ) ){
            startIndex += len;
            endIndex += len;
            count++;
          }
          if( startIndex == maxLen ){
            break;
          }
          else{
            count=1;
          }
        }
        System.out.println(count);
        
      }
    }
}


可是這次上傳UVA卻一直 Runtime error ,完全搞不懂為什麼。

我自己在eclipse上測試時以上兩個都可以執行,
第一個程式還可以推測可能是因為Scanner做I/O太慢的關係,
第二個程式就真的看不出哪裡有問題,連推測都想不出來。

想知道我到底是因為邏輯哪裡有問題,或是演算法不夠好 ,
還是因為還有什麼我不知道的事才過不了UVA,請大大幫忙。


To write a complicate algorithm, you choose the worst and most annoyed way. Your program skill is quite bad actually.

By simple judge, your way on simply mixing up I/O procedures and algorithm codes in single function is the worst and you simply don't know how to analyse problem and even don't know how to divide and quer.

Firstly, you would better define well your algorithm functions. It may be some prototype interface like this:
1
public int countPeriodicString(String inputString);


And then, you should define well your test cases like
1
2
3
4
5
String[][] testcases = new String[][]{
  {"abcd","1"},
  {"aaaa","4"},
 {"ababab",3}
};


By following, your testing procedures will be just:
1
2
3
4
5
  for (int i=0; i<testcases.length; i++){
      int result = countPeriodicString(testcases[i][0]);
      bool match = Integer.parseInt(testcases[i][1]) == result;
       System.out.println("test for string '" + testcases[i][0] + "', expected: " + testcases[i][1] + ", actual: " + result + "("+ match+")");
}


For the algorithm, your logic is simple wrong. But one thing good is that you have intention to define right variables.

Here, I will not write down the codes for you. But I can tell your thinking on defining variables is simple head and just not enough. Can you think more variables? My hint is to use string buffer to store the string segment just match.

Just like that.

In serious talk, you would be better to think if programmer is your dream job...

For me, if I need to mark the code, I will simple mark 1 to 2 out of 10 for your code as you have intention to find some I/O routines, quite bad you know?


roysiu edited on 2014-12-16 08:55
reply to postreply to post
作者 Re:UVA 10298 Power Strings TLE / RE [Re:roysiu]
likecoding





發文: 4
積分: 0
於 2014-12-16 20:52 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
謝謝大大的指教,我會好好想想怎麼把I/O和演算法分開還有使用buffer來減少I/O的時間

reply to postreply to post
» JWorld@TW »  Java 技巧文件 » UVA(ACM)討論

reply to topicthreaded modego to previous topicgo to next topic
  已讀文章
  新的文章
  被刪除的文章
Jump to the top of page

JWorld@TW 本站商標資訊

Powered by Powerful JuteForum® Version Jute 1.5.8