|
|
Here are some tests that helped me figure out what was wrong with my program: 316496 out => 317559 317560 318533 out => 318659 318660 945999 out => 950509 950510 055099 out => 055109 055110 00510059 out => 00504999 00505000 00450010 out => 00460019 00460020 00504010 out => 00504999 00505000 0019 out => 4509 4510 00510059 out => 00510059 00510060 945999 out => 950509 950510 008359 out => 009449 009450 3000 out => 4509 4510 4509 out => 4509 4510 4099 out => 4509 4510 9999 out => No solution 373730020389 out => 373730021389 373730021390 373730030290 out => 373730031289 373730031290 373730030289 out => 373730031289 373730031290 Good luck! If anybody knows O(n) solution, please, send it to sk1@hotbox.ru PS: My solution is O(n^2) Can you tell me your O(n^2) solution? My email: compileme@gmail.com Thank you:) Could you tell me your O(N^2) algorithm? Thanks. My email is temptempttt@126.com Could you tell me your O(N^2) algorithm? Thanks. my e-mail kostan3@spaces.ru Could anyone give me some test cases? Thanks. Edited by author 07.03.2013 11:16 Edited by author 07.03.2013 11:16 Edited by author 07.03.2013 11:17 Edited by author 07.03.2013 11:17 Give me more examples to test, pls. import java.util.Scanner; import java.util.Scanner; public class DoubleHappiness1432 { private static String number; private static int[] ticket; private static int[] ticket2; private static boolean flug = true; private static int sum1 = 0; private static int sum2 = 0; private static boolean pr = false; private static int sum12 = 0; private static int sum22 = 0; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); number = scanner.nextLine(); if(number.length()%2==0 && number.length()>=4 && number.length()<=1500){ toInt(); stop:while (flug) { flug=false; start:for (int j = number.length()-1; j >= 0; j--) { if (ticket[j] < 9) { ticket[j]+=1; if(summary() || summary1()){ pr = true; break stop; }else toNull(j); flug=true; break start; } } } if(!pr) System.out.print("No solution"); } } private static void toInt(){ ticket = new int[number.length()]; ticket2 = new int[number.length()]; for (int i = 0; i < number.length(); i++) { ticket[i] = Character.digit(number.charAt(i), 10); } } private static void toNull(int i){ for (int j = i+1; j < number.length(); j++) { ticket[j]=0; } } private static boolean summary(){ for (int i = 0; i < number.length()/2; i++) { sum1 += ticket[i]; } for (int i = number.length()/2; i < number.length(); i++) { sum2 += ticket[i]; } if (sum1==sum2) { System.arraycopy(ticket, 0, ticket2, 0, ticket.length); for (int i = number.length()-1; i >=0; i--) { if (ticket[i] < 9) { ticket[i]+=1; flug=true; toNull(i); break; } } if (flug) { for (int i = 1; i < ticket.length; i+=2) { sum12 +=ticket[i]; sum22 +=ticket[i-1]; } }else{return false;} if(sum12==sum22){ for (int i = 0; i < number.length(); i++) { System.out.print(ticket2[i]); } System.out.print(" "); for (int i = 0; i < number.length(); i++) { System.out.print(ticket[i]); } return true; }else{sum12=0;sum22=0;return false;} }else{sum1=0;sum2=0;return false;} }
private static boolean summary1(){ for (int i = 1; i < ticket.length; i+=2) { sum12 +=ticket[i]; sum22 +=ticket[i-1]; } if(sum12==sum22){ System.arraycopy(ticket, 0, ticket2, 0, ticket.length); for (int i = number.length()-1; i >=0; i--) { if (ticket[i] < 9) { ticket[i]+=1; flug=true; toNull(i); break; } } if (flug) { for (int i = 0; i < number.length()/2; i++) { sum1 += ticket[i]; } for (int i = number.length()/2; i < number.length(); i++) { sum2 += ticket[i]; } if (sum1==sum2) { for (int i = 0; i < number.length(); i++) { System.out.print(ticket2[i]); } System.out.print(" "); for (int i = 0; i < number.length(); i++) { System.out.print(ticket[i]); } return true; }else{return false;} }else{sum1=0;sum2=0;return false;} }else{sum12=0;sum22=0;return false;} } } Edited by author 06.07.2011 03:58 Try this test: 316496 My program returns: 317559 317560 and yours: 318659 318660 I am getting WA at #23. Could someone give tricky test case or test case 23 :) ? Thank you Yes , nobody can be faster than you. Yes! Finally after 121(64 of them got AC) submissions you got 0.001!!! I wish you to be the fastest with your 1438 problem, you submitted it only 140 times, may be after 100 or 200 submissions more you will get 0.1 sec and be the fastest. Good Luck!!! If author achieved 0.001c on this problem then he is'n maniac but reserch man! I have 75 submissions on this problem and 0.14c only but has great pleasure because the problem has so many trics as no other in timus. It was helpfull training. When I see on final variant of my program it is evident that strong solver could solve this problem in 1 hour. Edited by author 15.12.2007 11:09 I got AC with 0.001 too!!! *YAHOO* AnUs, thanks a lot for this subject!!! code: ... while ((n&1) == 1) {}; n2 = n; n = n/2; ... receive TLE, but code: ... n = n/2; n2 = n*2; ... have AC How do solve it faster, any suggestions? Try this test 318533 correct answer: 318659 318660 Problem statement has been updated. Now your program gets TLE. Sorry but statements has been updated once again. If there are no answer print "No solution". (But no "No Solution") Edited by author 01.03.2006 18:05 if it TLE again, i shall optimize it once more. but i don't think i need it. ... Edited by author 01.03.2006 18:15 a small bug. modified again and submitted again. Edited by author 01.03.2006 18:28 I'll check it on random tests and then unlock problem. PS. Change "No Solution" to "No solution" BTW, if you need(my program TLE), i could make it much faster. we're always using emails or forum to discuss. why not gtalk/icq/aim/msn or something else? Yeah, the problem seems uncompleted. Maybe that's the reason why it's locked?.. sample incorrect is the reason I suppose Люди, а почему при попытке отправить задачку №2 выдается Problem Locked? Задачу сняли с соревнований, поэтому и Problem Locked. |
|
|