:V

ez

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

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

This test contain such string that answer (minimal integer number) is more than 99999.

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,

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 :)

Read buffer size is 100002(10^5 + 2 (13 and 10 bytes)). Zero is ignored.

Test:
140051715416348726920797036492488196690846913267128596190521765523258272915411326652499477662321559400240243025385922325531607435354460224854854789172790422082699161691921215211265020255276693637323390308581372719218697573705167311948170669560826796977119144439062473865548749290708026898940249352335596346960246701868163284769923581208100816278539874491366451178190245275148804575563207864980035188533495461464611182224503481318194894795899530095304225848561075258515826860807569347989563418218033315611641070515265583012032542413165442672199224236732385640080346148119744715525729217641134438620386384432175780764936419909263251871198373431970336511517512266991527494812295417761157131887516459605130273324209494428321604165936938643665167653110211999342131767863138213646183859400125439119368195023609875655725280252737388791975472393751757033734680275509267474303064517420298692106780786877121279815728529858832327428129275374458515191749482035839501623872449096899866212891307052433946175414882278474151155821260423095562697365713627951905205742993551837625497997687297678831484749676852899652616262745850146376974301305739477333447537362098526698167264924433959529878595635057196124356987016104438328205463212317524467228318050292845259203847171121402877003559921334843495859744812824961906330368111989214639069827401863561498684778734857131993979393179662557307601727640348561292235624615896745387290681716022726412811677020534337915714243873582584292162935131606847752537458166128916158211672513434883362277575137165381164377333050964107617571273569634163708364280245862434984938247227643998381181561255115197885772436648111386912364484076663846882710610574937181889724440263401262491510372354546523897322834076792858754892459033892893415378010753519255568675536682574837388991979158380757221808884121654323289756031354326924996020549630918886449816631013177950243583302651313968901941388546092694699169623039374195249873494704816778006496358707175931610138636441755335987526935511649196111767478998567978390545708854447325722602785228930291070742237303953635923758990854576306769236873778514591636087351666613173824714971418584238149942583566867751130449641452214078667591916847978250486137577695471025057149805045105002141257367453386625768201855725648984138453395388674327116782331666736198524359191124365681528402097502409546683398024922568207114638816155565658683581554959453928226685584754235386929381406434641844288712029945097695387943988541364148817994126492284674591494312399867899630474089786533842979677444252416920658768272981555798318568123184846109218242071122425858958913775563868252731796764376983312944032169999089764297155467858249445004100853652880834020635936460923537002526451094115605265145595301730162842368158258747510324692844060724379263261581929789186627749024264607634393031485217722547512810346197813341575443927696840903803318451283794109721440464219891997242932058539687955292724736028299424255868867208280436690345986909483548314890853905407059274943621286285642225243373714057910951435168651420867476571835382212444179524625898513369969097185140724351987213301548423922426157306439130236264606352160264757296700215299689290543672834157605315556299271366580103761959192790250853638053301393053884984126221191753952756428691739972924169588189222958677808099802376796306460453022271394636905099975310531232910060654748567949204822949656047178478216822283114516207272940195881195320962398301183392164044808522940151504769236467044801611307057810660833264392493192487502143812911497362789762973364932378325801917410896482458911224435268226253194364006108926194049046816563219567382012799938268382246120746284318425568753709407318997729961008506640332290576230087242548402270127428289777095609465678957736537455917277343141882664049504597699031267977758995330574904612158839915137799862389397804648398923769964487635930208280953973250614940625256581326859073

Answer:
147

Any suggestions ?

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

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

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

Now AC!I have found my mistake.

check this testcase

in: 5
out: 1 (not 6)

Edited by author 08.07.2011 19:24

how to input without length

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?

any ideas why?
I checked my code several times, it works fine... :S

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

#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!!!

The program works for me perfectly, passes all tests, for specified time, but here, constantly deduces an error of excess of time, why?

My program works well, but I have WA on test 6
please give some tests