Page 7 Write down the sequence, on paper, by hand. Now, right down the index of each digit on the sequence. Do you know prefix sums and binary search? It's kinda useful for many problems btw... Edited by author 15.05.2024 05:54 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 Great solution, So Sui Ming, I did not think about that one in particular. I just use prefix sums and binary search. If you write down the sequence and it's index starting from 1. You will notice that if you do prefix sum ( half interval way , so starting from 0, the first element, first element + second element, etc. ) up till sum <= MAX ( 2^31 - 1 ), you will get 65535 numbers in a sorted way. In this way, notice, that the numbers in this prefix_sum array are all index s.t. digit = 1. You still need to +1 in every position of prefix_sum array, because of 1-index of input. Now you read input number K and do binary search on the prefix sum array. If you did find, great! It is 1. Otherwise, it is 0. #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; } If my teacher is watching this post, sorry. Page 6 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? 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) 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. The triangular sequence is behind the scene. n belongs to triangular sequence if and only if (8n+1) is a square. 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 You need to find formula for progression - it is a square equation, and then just solve it. 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. #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; } 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. #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; } #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); } Please anyone help I had the same mistake. But I used long long and it went away 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. Pages: 7 6 5 4 3 2 1 Previous |
|