Posted:

**Mon Nov 07, 2005 9:15 pm**my AC program gives the same o/p as yours.

Page **2** of **3**

Posted: **Mon Nov 07, 2005 9:15 pm**

my AC program gives the same o/p as yours.

Posted: **Wed Jan 25, 2006 7:13 pm**

I use brute force method.

But I got TLE!!

Who can give me a hint.

Thanks in advanced!

But I got TLE!!

Who can give me a hint.

Thanks in advanced!

Posted: **Sat Feb 11, 2006 3:01 pm**

I use brute force method.

But I got TLE!!

Who can give me a hint.

Thanks in advanced!

But I got TLE!!

Who can give me a hint.

Thanks in advanced!

Posted: **Sat Feb 11, 2006 11:11 pm**

Please help me....Why WA!?

Or give me some input data and output data....

Thanks in advance!

Or give me some input data and output data....

Thanks in advance!

Code: Select all

`Acc......`

Code: Select all

```
my Input
18
8
3
80
546
23423
65753
2345
45645756
546454
6786797
131231
78934124
68904565
123487907
5655
778888
101011
2147483647
```

Code: Select all

```
my output
2
2
0
2
3
1
5
5
2
5
9
7
5
7
1
5
5
2
```

Posted: **Sun May 21, 2006 2:50 am**

The ouputs you've posted are correct.IRA wrote:Please help me....Why WA!?

Or give me some input data and output data....

Thanks in advance!

Posted: **Mon Jun 26, 2006 9:04 pm**

Salamo Aleko

This problem is not hard but need some work.Try to display the numbers in the sequence and thier digits and find any relation but you may not able to solve this problem without solving "10427 Naughty Sleepy Boys"

In problem 10706

All what we have to do is to reduce this problem input to

the number of digits in poblem 10427

And then applying its code

To do that we only remove previous digts of it

1 1

1 2

2 3

1 4

2 5

3 (6) largest possible number less than it in end

1 7

2 8

3 (9)

4 10

e.g if given input 9 all what i have to do is to remve it from

the largest possible number less than it [in end-1 of interval]

which is 6 so send to code_10427(9-6)

Let take another example : Look for the sequence 1121231234.. view it as

1 1

*********

1 2

2 3

*********

1 4

2 5

3 6

*********

1 7

2 8

3 9

4 10

*********

1 11

2 12

3 13

4 14

5 15

*********

1 16

2 17

3 18

4 19

5 20

6 21

*********

1 22

2 23

3 24

4 25

5 26

6 27

7 28

*********

1 29

2 30

3 31

4 32

5 33

6 34

7 35

8 36

*********

1 37

2 38

3 39

4 40

5 41

6 42

7 43

8 44

9 (45)

*********

1 46

2 47

3 48

4 49

5 50

6 51

7 52

8 53

9 54

10 (55) 56

//////////////////////////////////

Now assume input is (55) we know[By calculating and save in arr[32000]]

That previous interval end with 45 which is the sum of all prev digits

Now 55-45=10 send this output to code_10427(55-45) to get 10

Lastely assume it is 56 so code_10427(56-45=11)

I hope this is enough..If need more explantation or help.Just ask.

This problem is not hard but need some work.Try to display the numbers in the sequence and thier digits and find any relation but you may not able to solve this problem without solving "10427 Naughty Sleepy Boys"

In problem 10706

All what we have to do is to reduce this problem input to

the number of digits in poblem 10427

And then applying its code

To do that we only remove previous digts of it

1 1

1 2

2 3

1 4

2 5

3 (6) largest possible number less than it in end

1 7

2 8

3 (9)

4 10

e.g if given input 9 all what i have to do is to remve it from

the largest possible number less than it [in end-1 of interval]

which is 6 so send to code_10427(9-6)

Let take another example : Look for the sequence 1121231234.. view it as

1 1

*********

1 2

2 3

*********

1 4

2 5

3 6

*********

1 7

2 8

3 9

4 10

*********

1 11

2 12

3 13

4 14

5 15

*********

1 16

2 17

3 18

4 19

5 20

6 21

*********

1 22

2 23

3 24

4 25

5 26

6 27

7 28

*********

1 29

2 30

3 31

4 32

5 33

6 34

7 35

8 36

*********

1 37

2 38

3 39

4 40

5 41

6 42

7 43

8 44

9 (45)

*********

1 46

2 47

3 48

4 49

5 50

6 51

7 52

8 53

9 54

10 (55) 56

//////////////////////////////////

Now assume input is (55) we know[By calculating and save in arr[32000]]

That previous interval end with 45 which is the sum of all prev digits

Now 55-45=10 send this output to code_10427(55-45) to get 10

Lastely assume it is 56 so code_10427(56-45=11)

I hope this is enough..If need more explantation or help.Just ask.

Posted: **Mon Aug 07, 2006 10:04 pm**

My code passed all of these testcases and still WA! why? (

Posted: **Wed Aug 09, 2006 3:12 pm**

I got it at last. I test these samples in VC++ and it has some precision rounding. when i use log() to compute number`s length in gcc i should add 1e-8 to the result. what a silly mistake!

Posted: **Tue Oct 10, 2006 11:14 pm**

Do I need to store the sum of the groups as u mentioned ?????

Thanks In Advance

Thanks In Advance

Posted: **Tue Oct 10, 2006 11:27 pm**

In my program i save for efficency., i do not know if i will get tle excceed with out it or not.

I copy these pattern form my code, i do not know if it will be useful or not

I think i forget many detail of implentation.

Code: Select all

```
const int MAX = 12;
int nines [MAX]; //9,99,999,9999,99999,...
int tens [MAX]; //1,10,100,1000,10000....
int digits[MAX]; //9,180,2700...9*[interval num of digits=i+1]*10^i
unsigned long nums[32000];
void build_table();
int get_num_of_digits(int num);
void build_accum_digits();
void solve_with_code_10427(int num_digtit);
int getDigit(int num, int digtPos);
int main()
{
build_accum_digits();
build_table();
int num, cases;
cin>>cases;
while(cases--)
{
cin>>num;
solve_with_code_10427( get_num_of_digits(num) );
}
return 0;
}
```

I think i forget many detail of implentation.

Posted: **Wed Oct 11, 2006 9:14 pm**

Thanks for ur reply .. The whole idea is very clear to me..... But i am still confusing in this

Thanks in Advance

How can i get the sum of the previous interval without restoring it .... and if i store them it takes a very long time ...... How can i over come it ????Now assume input is (55) we know[By calculating and save in arr[32000]]

That previous interval end with 45 which is the sum of all prev digits

Thanks in Advance

Posted: **Thu Oct 12, 2006 12:36 am**

sorry i do not know how by nost saving

but as u see from my code these two first calls will be running on laa cases for efficeny(as i remember)

my code have good time

so it is ur implementation problem

try to find the function that take large time

and we may speak about it.

but as u see from my code these two first calls will be running on laa cases for efficeny(as i remember)

my code have good time

so it is ur implementation problem

try to find the function that take large time

and we may speak about it.

Posted: **Mon Jul 09, 2007 1:45 am**

are nt you just spoiling his fun? to be true?

Posted: **Sun Sep 26, 2010 8:36 pm**

Hi every body

i really need help

i write this code for this problem i checked it for about 100000 test cases in uvatoolkit.com and it work correctly but i got WA

#include <iostream>

#include <fstream>

#include <string>

#include <sstream>

#include <vector>

#include <algorithm>

#include <set>

#include <queue>

#include <stack>

#include <functional>

#include <cmath>

#include <map>

#include <iomanip>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

int a[60002];

int b[60002];

char s[2000000];

int len(int n)

{

return log10l(n)+1;

}

char *intTochar(int n)

{

char t[20];

int l=len(n);

t[l]=0;

int i=1;

while(n>0)

{

int x=n%10;

t[l-i]=x+'0';

i++;

n/=10;

}

return t;

}

void pre()

{

a[0]=0;

for(int i=1;i<=31500;i++)

a*=a[i-1]+len(i);*

for(int i=1;i<=31500;i++)

b*=b[i-1]+a**;*

s[0]=0;

for(int i=1;i<=31500;i++)

strcat(s,intTochar(i));

}

int binSearch(int x)

{

int low = 1;

int high = 31267;

//while(b[high]<0)high--;

while(low <= high)

{

int mid = (low+high)/2;

if(b[mid]==x)return mid;

else if ( b[mid] > x)

high = mid-1;

else low = mid+1;

}

return high;

}

int main()

{

int tnum;

int n;

pre();

for(cin>>tnum;tnum--;)

{

cin >> n;

int idx = binSearch(n);

int dif = n-b[idx]-1;

if(dif==-1)

dif = n-b[idx-1]-1;

cout << s[dif] << endl;

}

}

i really need help

i write this code for this problem i checked it for about 100000 test cases in uvatoolkit.com and it work correctly but i got WA

#include <iostream>

#include <fstream>

#include <string>

#include <sstream>

#include <vector>

#include <algorithm>

#include <set>

#include <queue>

#include <stack>

#include <functional>

#include <cmath>

#include <map>

#include <iomanip>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

int a[60002];

int b[60002];

char s[2000000];

int len(int n)

{

return log10l(n)+1;

}

char *intTochar(int n)

{

char t[20];

int l=len(n);

t[l]=0;

int i=1;

while(n>0)

{

int x=n%10;

t[l-i]=x+'0';

i++;

n/=10;

}

return t;

}

void pre()

{

a[0]=0;

for(int i=1;i<=31500;i++)

a

for(int i=1;i<=31500;i++)

b

s[0]=0;

for(int i=1;i<=31500;i++)

strcat(s,intTochar(i));

}

int binSearch(int x)

{

int low = 1;

int high = 31267;

//while(b[high]<0)high--;

while(low <= high)

{

int mid = (low+high)/2;

if(b[mid]==x)return mid;

else if ( b[mid] > x)

high = mid-1;

else low = mid+1;

}

return high;

}

int main()

{

int tnum;

int n;

pre();

for(cin>>tnum;tnum--;)

{

cin >> n;

int idx = binSearch(n);

int dif = n-b[idx]-1;

if(dif==-1)

dif = n-b[idx-1]-1;

cout << s[dif] << endl;

}

}

Posted: **Mon Sep 27, 2010 8:33 am**

i checked my code in iranian contest web site and worked correctly ???????????? but i got WA

http://sina.sharif.edu/~acmicpc/acmicpc ... probs.html

problem D

i'm confuse

http://sina.sharif.edu/~acmicpc/acmicpc ... probs.html

problem D

i'm confuse