This test contain such string that answer (minimal integer number) is more than 99999. I created array p[1..10000000] of boolean; p[i]=true when exist i in input. But i can t prove that if length of input <=100000 then absent numb <=10000000 because if you will write all numbers from 1 to 10000000. string length will be more than 10^5 I'm laughing now .... I've spent about 3 hours for this problem. First off, I used Z-function and I tried to treat problem as a string problem. I generated new string and tried to find it. If there is no, that's the answer. It became not so slow as can seems to be. But TLE#6 got me! Then I tried to store positions for each digit(0-9) and than tried to search target number using binary search for every digit. It works, but not good enough to pass test#6. Then I decided to use the straight approach using bool exists[1000000] that indicates whether n is substring. It approach can be done since total length is 10^5, so 10^6 is free for sure. Since we know several approaches sometimes we use more complex first :) if you have WA 43 and 51, check this tests 0 00 000 0000 00000 1 01 001 0001 00001 answers is primitive - 1,1,1,1,1,2,2,2,2,2 My programm works on my computer. Timus gives me this verdict. Why it may be?I write on C++ in Dev. May be I cannot use strings? Edited by author 16.03.2011 20:11 for string you should write #include<string> Dear colleagues, Can anybody, please, explain me the condition of the problem with simple tests? I didn’t understand given sample. Monks were told to write all the integers starting from the smallest integer that was not a substring of that string. If 11 was the initial string. Assuming integers with leading zeroes are not accepted, monks would start from 0, then 2 (since 1 is a substring of 11) That’s why, if the initial string was 11, monks would have written 02345678910, am I wrong? Could anybody please explain me the condition of the problems? Thanks, The string carved on the stone is 10123456789 and the monks begin writing positive integers that are not a substring of 10123456789. The first string that is not a substring of 10123456789 is 11. The english in the problem is strange.. for i = 1.. for j = 0..n-i; atoi() strings str[j...j+i] to num[j] sort(num, num + n - i + 1) find num[j] + 1 < num[j+1] and output num[j]+1 There is a solution O(N) without sorting: check numbers that has length at most 6 digits... Read buffer size is 100002(10^5 + 2 (13 and 10 bytes)). Zero is ignored. Test: 140051715416348726920797036492488196690846913267128596190521765523258272915411326652499477662321559400240243025385922325531607435354460224854854789172790422082699161691921215211265020255276693637323390308581372719218697573705167311948170669560826796977119144439062473865548749290708026898940249352335596346960246701868163284769923581208100816278539874491366451178190245275148804575563207864980035188533495461464611182224503481318194894795899530095304225848561075258515826860807569347989563418218033315611641070515265583012032542413165442672199224236732385640080346148119744715525729217641134438620386384432175780764936419909263251871198373431970336511517512266991527494812295417761157131887516459605130273324209494428321604165936938643665167653110211999342131767863138213646183859400125439119368195023609875655725280252737388791975472393751757033734680275509267474303064517420298692106780786877121279815728529858832327428129275374458515191749482035839501623872449096899866212891307052433946175414882278474151155821260423095562697365713627951905205742993551837625497997687297678831484749676852899652616262745850146376974301305739477333447537362098526698167264924433959529878595635057196124356987016104438328205463212317524467228318050292845259203847171121402877003559921334843495859744812824961906330368111989214639069827401863561498684778734857131993979393179662557307601727640348561292235624615896745387290681716022726412811677020534337915714243873582584292162935131606847752537458166128916158211672513434883362277575137165381164377333050964107617571273569634163708364280245862434984938247227643998381181561255115197885772436648111386912364484076663846882710610574937181889724440263401262491510372354546523897322834076792858754892459033892893415378010753519255568675536682574837388991979158380757221808884121654323289756031354326924996020549630918886449816631013177950243583302651313968901941388546092694699169623039374195249873494704816778006496358707175931610138636441755335987526935511649196111767478998567978390545708854447325722602785228930291070742237303953635923758990854576306769236873778514591636087351666613173824714971418584238149942583566867751130449641452214078667591916847978250486137577695471025057149805045105002141257367453386625768201855725648984138453395388674327116782331666736198524359191124365681528402097502409546683398024922568207114638816155565658683581554959453928226685584754235386929381406434641844288712029945097695387943988541364148817994126492284674591494312399867899630474089786533842979677444252416920658768272981555798318568123184846109218242071122425858958913775563868252731796764376983312944032169999089764297155467858249445004100853652880834020635936460923537002526451094115605265145595301730162842368158258747510324692844060724379263261581929789186627749024264607634393031485217722547512810346197813341575443927696840903803318451283794109721440464219891997242932058539687955292724736028299424255868867208280436690345986909483548314890853905407059274943621286285642225243373714057910951435168651420867476571835382212444179524625898513369969097185140724351987213301548423922426157306439130236264606352160264757296700215299689290543672834157605315556299271366580103761959192790250853638053301393053884984126221191753952756428691739972924169588189222958677808099802376796306460453022271394636905099975310531232910060654748567949204822949656047178478216822283114516207272940195881195320962398301183392164044808522940151504769236467044801611307057810660833264392493192487502143812911497362789762973364932378325801917410896482458911224435268226253194364006108926194049046816563219567382012799938268382246120746284318425568753709407318997729961008506640332290576230087242548402270127428289777095609465678957736537455917277343141882664049504597699031267977758995330574904612158839915137799862389397804648398923769964487635930208280953973250614940625256581326859073 Answer: 147 Any suggestions ? Edited by author 01.11.2011 23:52 get AC. make sure that ALL your variables can contain 100000 bytes (even counters) ;) Edited by author 01.11.2011 23:53 package Oct_24; import java.io.IOException; import java.io.InputStreamReader; public class T_1769 { public static void main(String[] args) throws IOException { InputStreamReader is = new InputStreamReader(System.in); char c[] = new char[(int) 4e+5 + 1]; int k = 0; c[k] = (char)is.read(); while(is.ready()){ k++; c[k] = (char) is.read(); } k--; int t = 0; int [] a = new int [100001]; for (int i = 1; i <=4; i++) { for (int j = 0; j+i <= k; j++) { String s = (new String(c,j,i)); a[t] = Integer.parseInt(s); t++; } } boolean f[] = new boolean [400001]; for (int i = 0; i < t; i++) { f[a[i]]= true; } for (int i = 1; i < f.length; i++) { if(!f[i]){ System.out.println(i); return; } } } } Edited by author 24.10.2011 19:29 Edited by author 24.10.2011 19:29 Do you have any ideas? Edited by author 13.04.2010 04:02 Edited by author 13.04.2010 04:02 check 100000-999999 numbers too I changed: char ch[100001]; fgets(ch,100000,stdin); to char ch[1000001]; fgets(ch,1000000,stdin); and got AC! Now AC!I have found my mistake. check this testcase in: 5 out: 1 (not 6) Edited by author 08.07.2011 19:24 I have WA39 too, but my solution pass your test correct... any ideas why? I checked my code several times, it works fine... :S Exact same problem for me :S. fixed, make sure the array size is 100000, not 10000 :P Can't get past test #6 (Time limit exceeded) and I have no idea how could I improve/change the algorithm, looking for suggestions ;P. Thanks. Here's the code (with comments ^^): #include <cstdlib> #include <iostream> #include <string> using namespace std; int powering(int n){ int r = 1; for (int i = 0; i<n; i++){ r = r*10;} return r; } int main(int argc, char *argv[]) { std::string inputNumber; std::cin >> inputNumber; int length = inputNumber.length(); char digits[100001]; int num[100001];
for (int i=0; i<length; i++){ //reading input digits[i] = inputNumber[i]; num[i] = digits[i] - '0';}
for (int i=0; i<length; i++) // starting cycle for all n { int q = powering(i); int n = q; // n = 10^i bool unique; for(int m = 0; m<(q*10); m++){ // running through every number in 10^i to 10^(i+1)-1
unique = true; for(int j = 0; j<(length-i); j++) //with a given number, checking if it's in the string; { int temp = n; for(int x = j+i; x>=j; x--){ // checking if the number is unique in given position // x = current digit, i = number of digits (zero based) temp = temp - num[x]; if(temp == 0){unique = false; break;} if(temp % 10 != 0){break;}else{temp = (int)(temp/10);} } if(unique == false){break;} // if given number is not unique, breaks the cycle } if(unique == true){std::cout << n << endl; return 1; } // checks if the number checked was unique (add pause here if you want to test) if(n<((q*10)-1)){n++;}else{break;} // checks if 10^(i+1)-1 is reached, if not, then n++; } } return EXIT_SUCCESS; } Edited by author 25.09.2011 22:01 Edited by author 25.09.2011 22:01 Edited by author 25.09.2011 22:01 The program works for me perfectly, passes all tests, for specified time, but here, constantly deduces an error of excess of time, why? Not to make second thread, how much is the time limit for this problem since I've got the same problem? Time Limit: 1.0 second Memory Limit: 64 MB You say that it passes all tests for you... Did you make your own tests, or the tests can be found somewhere because I have WA#17, to see what's wrong... This test is 1|2|3|4|5|....and you continue this until it excedes 10^5 characters. Memory VS time? Which one is critical resource here? ;) Time is critical. Memory is rarely exceeded :P P.s. I get TLE on test #6 too. Edited by author 25.09.2011 21:45 how to input without length Read all as one string. x) I checked the code, and all the test given here, and it gives true answers, but I don't know why I get WA on 17... Can you give some more tests that are similar to 17 so I can see where is my mistake? My program works well, but I have WA on test 6 please give some tests This test may help~ 0001002003004005006007008009011012013014015016017018019021022023024025026027028029031032033034035036037038039041042043044045046047048049051052053054055056057058059061062063064065066067068069071072073074075076077078079081082083084085086087088089091092093094095096097098099111211311411511611711811912212312412512612712812913213313413513613713813914214314414514614714814915215315415515615715815916216316416516616716816917217317417517617717817918218318418518618718818919219319419519619719819922232242252262272282292332342352362372382392432442452462472482492532542552562572582592632642652662672682692732742752762772782792832842852862872882892932942952962972982993334335336337338339344345346347348349354355356357358359364365366367368369374375376377378379384385386387388389394395396397398399444544644744844945545645745845946546646746846947547647747847948548648748848949549649749849955565575585595665675685695765775785795865875885895965975985996667668669677678679687688689697698699777877978878979879988898999001000100100210031004100510061007100810091010110121013 the answer should be 1014 you may get 300 if you keep getting wrong on the test 6 good luck~ thanks ) sorry I had another problem, now it works right, but I have TLE, my algo is not fast ( my program gives 1014 on this test, but I have WA#2 ( I have right answer on this test, but WA#6. WTF? Edited by author 17.04.2010 10:19 0 is not positive integer! So if ur output is 0 its wrong answer... That might cause u a problem on test 2 Edited by author 07.04.2011 19:50 #include <iostream> #include <algorithm> #include <string> #include <cctype> #include <iomanip> #include <cmath> using namespace std; #define MaxN 500000 #define f0(i,n) for(i=0;i<n;i++) #define f1(i,n) for(i=1;i<n;i++) char x[MaxN]; int main() { int i=0; char c; while((c=getchar())!='\n') { x[i]=c; i++; } long int total=0,t=1; int j,k,l,m; m=i; int count=0; int counter; f1(i,MaxN) { if(i<10 && i>=0)t=1; if(i<100 && i>=10)t=2; if(i<1000 && i>=100)t=3; if(i<10000 && i>=1000)t=4; if(i<100000 && i>=10000)t=5; f0(j,m) { total=0; counter=1; for(k=j;k<j+t;k++) { l=x[k]-48; total+=pow(10,t-counter)*l; counter++; } if(total==i) { count++; break; } } if(count==0) { cout<<i<<endl; break; } count=0; } return 0; } Thanks!!! |
|