| Show all threads Hide all threads Show all messages Hide all messages | | Optimal solution | ElPsyCongroo | 1209. 1, 10, 100, 1000... | 9 Mar 2024 14:26 | 15 | Ok, just posting this to help others understand few things here:
The sequence is 1101001000100000... If you see the locations of the digit 1, you can observe that it is at location 1,2,4,7...=> ( 1 + 0 ),( 1 + 1 ),( 1 + ( 1 + 2 )),( 1+(1+2+3 )..So, it is 1+sum_of_n_digits.
What we have now is below:
1 + n*( n+1 )/2 [ note that n*(n+1)/2 is the sum of first n natural numbers ].
Now, this value should be equal to the input value, say P.
1 + n*(n+1)/2 = p [ I/p P=7 => n should be 3, back track ].
2 + n^2 + n = 2p
n^2 + n = 2(p-1)
n^2 + n - 2 (p-1) = 0;
This is a quadratic equation in 'n'. The roots of a quadratic equation are
( -b +- sqrt( b^2 - 4ac ) )/2a
-1 +- sqrt( 8p-7 ) / 2;
But, for our example, if you do some analysis, if the value of 8p-7 is a perfect square, then the value at that position 'p' would be 1. Else the value would be 0.
So, check for 8p-7 to be a perfect square. This is the optimal solution. Got mine accepted.
BTW, if you face any difficulty at test 3, it means you have to upgrade your ints to doubles. Because 8p-7 can falll over the size of int [atleast in Java].
Thanks,
ElPsyCongroo.
Thanks for the hint. I tried a very similar algorithm but was still getting WA on Test 3 in Java. I finally switched over to Python, and got AC I tried hard with python but all I got was TLE, when I turn into c++ I got AC. У меня на эту задачу есть Accepted решение на Питоне, 499 мс How ( -b +- sqrt( b^2 - 4ac ) )/2a transforms into -1 +- sqrt( 8p-7 ) / 2 ? I do it like this:
the n-th '1'should be here: n(n-1)/2+1.So, we judge whether the input number(x) == (n(n-1)/2+1).
it could be transformed to 2*x-2 == n(n-1), and int(sqrt(2*x-2)) must be the number 'n' if 'n' exists!
sorry， int(sqrt(2*x-2)) == int(sqrt(n*(n-1))) == int(n-1) if 'n' exists How can i upgrade my ints to double ? Sorry for my ignorance.I'm a newbie... vi apnar analysis deikha chudna hoia gelam, airokom chinta kamne ashe mathai Edited by author 20.07.2018 22:26
Edited by author 20.07.2018 22:26
nice
Edited by author 20.07.2018 22:26 My initial approach was slightly different, but at the end, it gave the same result.
Here's the sequence ->
1 10 100 1000 10000 100000 ...
In that sequence, 1s are located at position ->
1, 2 ,4, 7, 11 , 16, 22 ...
Look at the 11th position in the sequence. There are total (1+2+3) zeros and (1 + 1 + 1 +1) ones before the 11th 1. So the position no 11 can be written as the sum:
(1+2+3) + 4 x 1 + 1.
Take another position as example, say 16. Before the 16th position, there are total (1+2+3+4) zeros, and (1+1+1+1+1) ones. And so 16 can be written as,
(1+ 2+3+4) + 5 x 1 + 1.
Now if you generalize this observation and formulate it, you'll get :
n(n+1)/2 + (n+1) x 1 + 1 = (position no containing 1)
After simplification, the equation stands:
n^2 + 3n + (4 - 2 x Position No) = 0
So for any INTEGER value of n, you'll get a Position No for 1 .
Now think the opposite of this . If the Position No contains 1, then n will must have an Integer value. Otherwise, the Position No will contains 0.
Solving that equation, you'll get:
n = ( -3 +- sqrt( 9 - 4 x 1 x (4 - 2 x Position No)) ) / 2
For n to be an Integer, the determinant (9 - 4x(4 - 2 x Position No)) or (8 x Position No - 7) must be a square number.
This an O(log n), because the sqrt function is O(log n) | | another hint | So Sui Ming | 1209. 1, 10, 100, 1000... | 16 Jan 2024 19:23 | 1 | Stack 1,10,100,1000,10000,100000,... vertically:
1
10
100
1000
10000
100000
...
the cumulative sums of digits from the top are:
1,3,6,10,15,21,... which are in the form of combination(N,2) = N*(N-1)/2
checking whether one is at Kth digit is the same as finding if there is integer solution to:
N*(N-1)/2 = K-1
one way is to solve the quadratic equation for N (in double) and cast N to integer and check the above relation.
regards,
So Sui Ming
Edited by author 16.01.2024 19:27
Edited by author 16.01.2024 19:27 | | Why this is wrong ans in visual C? | Iftekhar | 1209. 1, 10, 100, 1000... | 4 Mar 2023 19:16 | 1 | #include<stdio.h>
#include<math.h>
unsigned long a[70000];
int main()
{
unsigned long i,k,n;
long double l;
scanf("%lu\n",&n);
for(i=0;i<n;i++)
{
scanf("%lu",&a[i]);
}
for(i=0;i<n;i++)
{
l=((sqrt(-7+8*a[i])-1)/ 2);
k=l;
if(l==k)
printf("1 ");
else
printf("0 ");
}
return 0;
} | | Post the answer in java plz | Shemakin | 1209. 1, 10, 100, 1000... | 25 Jan 2023 13:16 | 1 | If my teacher is watching this post, sorry. | | 3-rd test time limit exceded, but why? Python 3.8 | Dmitry | 1209. 1, 10, 100, 1000... | 2 Dec 2022 09:50 | 2 | I have two solutions!
Time: 1.15 solution:
numbers = []
for i in range(int(input())):
numbers.append(int(input()))
print_s = ''
for n in numbers:
if len(print_s) > 0:
print_s += ' '
number = int((n * 2) ** 0.5)
y = (number * (number - 1)) // 2
y2 = y + number
y += 1
if n <= y2:
print_s += '1' if n == y else '0'
else:
print_s += '1' if n == y + number else '0'
print(print_s)
Time: 1.15 solution:
numbers = []
for i in range(int(input())):
numbers.append(int(input()))
print_s = ''
for n in numbers:
if len(print_s) > 0:
print_s += ' '
length = 1
while n > length:
n -= length
length += 1
print_s += '1' if n == 1 else '0'
print(print_s)
Help me pls!!
Edited by author 13.08.2022 10:14 n=int(input())
numbers=[]
for i in range(0,n):
numbers.append(int(input()))
print_s = ''
for n in numbers:
if len(print_s) > 0:
print_s += ' '
length = 1
while n > length:
n -= length
length += 1
print_s += '1' if n == 1 else '0'
print(print_s) | | Why I am getting Wrong Answer at test 3? | Md. Shadman Matin | 1209. 1, 10, 100, 1000... | 29 Oct 2022 00:27 | 2 | I had the same mistake. But I used long long and it went away | | WA on test 3, but I can't find why | grazier | 1209. 1, 10, 100, 1000... | 2 Sep 2022 10:46 | 1 | Firstly, I pre-calculate the index which carries 1, and store them on the map. then I take input and check the map if the map stored 1 for this input, then I printed 1, otherwise 0.
what is wrong here? | | Треугольное число | Senya0000 | 1209. 1, 10, 100, 1000... | 13 Sep 2021 18:30 | 1 | | | Frustrating beauvoir of the Judge -- data type limit issue with C++ -- | Nouaili | 1209. 1, 10, 100, 1000... | 11 May 2021 01:55 | 1 | | | Can't figure out the WA on test #3. Please, help | Nouaili | 1209. 1, 10, 100, 1000... | 10 May 2021 17:44 | 1 | I checked the output of my code for all K ( 1 <= k <= 65535), I think it gives the correct output. https://github.com/Mourad-NOUAILI/Timus-Online-Judge/blob/main/1209/WA%233 long long type is used. Code explanation: I use a(k) = 1, 2, 2, 4, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, 16, 32, 32, 32, 32, 32, 32, 64, 64, 64, 64, 64, 64, 64,... to compute a(k) https://oeis.org/search?q=1%2C2%2C2%2C4%2C4%2C4%2C8%2C8%2C8%2C8%2C16%2C16%2C16%2C16%2C16&sort=&language=english&go=Search the pos(k) in a(k) from 0, 1, 0, 2, 1, 0, 3, 2, 1, 0, 4, 3, 2, 1, 0, 5, 4, 3, 2, 1, 0, 6, 5, 4, 3, 2, 1, 0, 7, 6, 5, 4, 3, 2, 1, 0, 8, 7, 6, 5, 4, 3, 2, 1,.. https://oeis.org/search?q=1+0+2+1+0+3+2+1+0+4+3+2+1+0&sort=&language=english&go=Search sequences are 0-base indexing. example: k = 16 --> a(15) = 32 = (100000)2 pos(15) in 0, 1, 0, 2, 1, 0, 3, 2, 1, 0, 4, 3, 2, 1, 0, 5, 4,... is 5, which means we gonna pick the bit at the 5th position from the left in 100000 100000 543210 so, for k = 16, the answer is 1 Thanks. | | Tips | Ruhul Amin | 1209. 1, 10, 100, 1000... | 4 Feb 2021 05:02 | 1 | Tips Ruhul Amin 4 Feb 2021 05:02 The triangular sequence is behind the scene.
n belongs to triangular sequence if and only if (8n+1) is a square. | | 1s are located at (i-th Tri-angular number + 1)th position | A. A. Noman Ansary | 1209. 1, 10, 100, 1000... | 23 Dec 2020 01:12 | 1 | Number of zeros in bracket: 0 1 2 3 4
Sequence : (1) (10) (100) (1000) (10000)
1 is found at : T0+1 T1+1 T3+1 T4+1 T5+1
Value of Ti+1 : 0+1 1+1 3+1 6+1 10+1
The i-th triangular number is the sum of the i natural numbers from 1 to i.
Ti = i(i+1)/2
i-th '1' is located at (Ti+1)-th position.
Let, z = (Ti + 1) = (i(i+1)/2) + 1
-> z = (i^2 + i + 2)/2
-> 2z = i^2 + i + 2
-> (1)x(i^2) + (1)x(i^1) + (-2(z-1)x(i^0) = 0
So, now if we solve for i using quadratic formula,
i = (-1 +- squareRoot(8z-7))/2 [do calculation on your own]
z = {1,2,4,7,11,...}
plugin these values and you will find that squareRoot(8z-7) = an integersquare number for any z. So, a number belongs to z only and if only squareRoot(8z-7) can produce an integer. And here z is the position number where the digits are 1.
[code deleted]
Edited by author 24.12.2020 19:00
Edited by moderator 14.02.2021 18:16 | | Tips | roman velichkin | 1209. 1, 10, 100, 1000... | 4 Dec 2019 19:15 | 1 | Tips roman velichkin 4 Dec 2019 19:15 You need to find formula for progression - it is a square equation, and then just solve it. | | How to solve that problem #1209 | Rodion | 1209. 1, 10, 100, 1000... | 21 Sep 2019 09:54 | 1 | Hello, today i'm gonna tell ya how to solve this easy task!
We can notice: 1 has places 0,1,3,6,10 etc.
0*8+1 = 1; 1*8+1 = 9; 3*8+1 = 25; 6*8+1 = 49; 10*8+1 = 81; I gave you the advice!
So, it's easy! Good luck!
If i hepled you, you may subscribe to my VK, Facebook, Instagram, Odnoklassniks, Patreon, Twitter, Twitch, Steam, Battlenet, Goggle+ and Youtube channel, there you'll find more solutions for problems! "If there is a problem, we solve it!" (c). Every rights are reserved. | | Why i am getting WA at test 1 | Tazma | 1209. 1, 10, 100, 1000... | 21 Aug 2019 01:36 | 1 | #include<bits/stdc++.h>
using namespace std;
const long long size=65535;
long long ara[size];
long long b[size];
Find()
{
long long i, sum=1, j;
for(i=0, j=1; i<=size; i++, j++)
{
sum=sum+i;
ara[j]=sum;
}
}
int main()
{
long long i, n, a, r, j;
Find();
cin>>a;
for(i=1; i<=a; i++)
{
cin>>b[i];
}
for(i=1; i<=a; i++)
{
r=0;
for(j=1; j<=size; j++)
{
if(b[i]==ara[j])
{
r=1;
break;
}
}
if(r==1)
{
printf("1 ");
}
else
{
printf("0 ");
}
}
printf("\n");
return 0;
} | | wrong ans in case #3 | Mushfiq Talha | 1209. 1, 10, 100, 1000... | 20 Aug 2019 21:12 | 6 | Code removed
Edited by author 20.08.2019 21:12 8*n-7 <--- integer overflow Integer overflow. But why? And How?
Edited by author 17.08.2019 19:12 [code deleted]
This code gets wrong answer in case #3.
Edited by author 18.08.2019 20:49
Edited by author 18.08.2019 20:49
Edited by moderator 17.11.2019 18:48 On timus 'long int' is equal to 'int', to use 64-bit integers you need to write 'long long'.
Also, there is a precision error in your 'per_sq' function. This line:
return ((x-floor(x))?0:1);
must be written as
return (abs(x-floor(x)) > 1e-8 ? 0 : 1); Thanks. I didn't know about the bit size of long in Timus. And what you said about the function. I had problem in the argument. I used double instead of int then it got accepted. | | Why this is said "wrong" ? this is true. | Sadriddin | 1209. 1, 10, 100, 1000... | 10 Nov 2018 22:37 | 1 | #include <iostream>
#include <math.h>
using namespace std;
int main()
{ int n,k,i,a;float z;
cin>>n;
int *b;
b=new int [n];
for(i=1;i<=n;i++){cin>>k;z=sqrt((k-1)*8+1);a=z;if(a==z)b[i-1]=1;else b[i-1]=0;}
for(i=1;i<=n;i++)cout <<b[i-1]<<" ";
return 0;
} | | Runtime error (access violation) help pls! C | vicente coopman | 1209. 1, 10, 100, 1000... | 21 May 2018 22:04 | 1 | #include <stdio.h>
int main(){
int t=0,n=0,i=0,cont=0;
int a[65535];
for(i=0;i<1000;++i){
a[i]=1;
t=cont;
while(cont!=0){
a[i+cont]=0;
--cont;
}
cont=t;
i=i+cont;
++cont;
}
scanf("%d",&n);
while(n!=0){
scanf("%d",&t);
printf("%d\n",a[t-1]);
--n;
}
return(0);
} | | Hint for 1209 | Fast Bastards | 1209. 1, 10, 100, 1000... | 11 Dec 2017 20:04 | 2 | The last "1" is 65536 and it lies in 2147516417 and K <= (2^31-1 = 2147483647). So from 2147483648 to 2147516417 is "0" I think you are not right.
65536-th "1" is on the position number 2147450881. | | Time Limited | Shohruh_1999 | 1209. 1, 10, 100, 1000... | 26 Oct 2016 14:33 | 1 | |
|
|
