KTLT12. Dãy số

Tiêu đề: KTLT12. Dãy số Thu May 12, 2022 8:05 pm

KTLT12. Dãy số
Xét dãy số nguyên a1, a2, . . ., an , . . ., trong đó a1 = 1, an được xác định như sau: đảo ngược thứ tự viết các chữ số của an-1 (trong hệ cơ số 10) và cộng thêm 2 vào số nhận được.
Phần đầu của dãy số này có giá trị như sau:
Chỉ số 1 2 3 4 5 6 7 8 9 10 11 12 . . .
Dãy a 1 3 5 7 9 11 13 33 35 55 57 77 . . .

Yêu cầu: Cho số nguyên dương n. Hãy xác định an (1 ≤ n ≤ 10^12).
Dữ liệu: Vào từ file văn bản SEQUENCE.INP gồm nhiều tests, mỗi test cho trên một dòng chứa một số nguyên n.
Kết quả: Đưa ra file văn bản SEQUENCE.OUT, kết quả mỗi test đưa ra trên một dòng.
Ví dụ:
SEQUENCE.INP
1
12
SEQUENCE.OUT
1
77

Tổng số bài gửi : 14 Join date : 10/05/2022

Code:: // Simple Anh Long <3

#include <bits/stdc++.h>

#define fast ios_base::sync_with_stdio(false);\
cin.tie(NULL);\
cout.tie(NULL);
#define io freopen("SEQUENCE.INP","r",stdin);\
freopen("SEQUENCE.OUT","w",stdout);
#define maxn 1000009
#define ll long long
#define vt vector
#define pb push_back

using namespace std;

int dp[100];
ll n;

int sdn(int n)
{
int daonguoc = 0;
while(n > 0)
{
daonguoc = (daonguoc + n%10) * 10;
n /= 10;
}
return daonguoc;
}

int main()
{
fast;
io;
while(cin >> n){
dp[1] = 1;
//cout << dp[1] << endl;
for(int i = 2;i <= 7; i++){
dp[i] = dp[i-1] + 2;
//cout << dp[i] << '\n';
}
//cout << endl;
for(int i = 8; i <= 82; i++)
{
dp[i] = sdn(dp[i-1])/10 + 2;
//cout << dp[i] << '\n';
}
cout<<dp[n-(n/81)*81];
return 0;
}

Tổng số bài gửi : 7 Join date : 10/05/2022

Code:: #include <bits/stdc++.h>
#define maxn 100000
using namespace std;
int dp[100];
long long n;
int sdn(int u){
int daonguoc = 0;
while(u > 0){
daonguoc=(daonguoc+u%10)*10;
u/=10;
}
return daonguoc;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
freopen("SEQUENCE.INP","r",stdin);
freopen("SEQUENCE.OUT","w",stdout);
while (cin>>n){
dp[1]=1;
for(int i=2;i<=82;i++)
dp[i]=dp[i-1]+2;
if (n<=82){
for(int i=8 ;i <= n; i++)
dp[i] = sdn(dp[i-1])/10+2;
}else{
for(int i=8 ;i <= 82; i++){
dp[i] = sdn(dp[i-1])/10+2;
}
}
cout<<dp[n-(n/81)*81];
}
}

Tổng số bài gửi : 71 Join date : 10/05/2022

Code:: #include<bits/stdc++.h>
using namespace std;
#define forl(i,a,b) for (int i=a; i<=b; i++)
#define forr(i,a,b) for (int i=a; i>=b; i--)
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))

int n,maxx,A[100001],N[100001],dem=0;

void nhap()
{
while (cin >> n)
{
maxx = max(maxx,n);
N[++dem] = n;
}
A[1] = 1;
}

int revers(int x)
{
int temp=0;
while (x>0)
{
temp *= 10;
temp += x%10;
x /= 10;
}
return temp;
}

int main ()
{
ios_base::sync_with_stdio(0); cin.tie(0);
nhap();
forl (i,2,maxx)
{
A[i] = revers(A[i-1]) + 2;
}
forl (i,1,dem) cout << A[N[i]] << "\n";
return 0;
}

Tổng số bài gửi : 16 Join date : 10/05/2022

Code:: #include <bits/stdc++.h>
using namespace std;
int n,a[100001];

long long sd(int x)
{
int sodao = 0;
while(x)
{
sodao = sodao*10 + (x % 10);
x = x/10;
}
return sodao;
}

void nhap()
{
cin>>n;
}
void sol()
{
a[1] = 1;
for(int i = 2; i<= n; i++)
a[i] = sd(a[i-1]) + 2;
cout<<a[n];
}
int main()
{
nhap();
sol();
}

Tổng số bài gửi : 71 Join date : 10/05/2022

Code:: #include<bits/stdc++.h>
using namespace std;
#define forl(i,a,b) for (int i=a; i<=b; i++)
#define forr(i,a,b) for (int i=a; i>=b; i--)
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))

int n,maxx,N[100001],dem=0;
int A[82] = {1,3,5,7,9,11,13,33,35,55,57,77,79,99,101,103,303,305,505,507,707,709,909,911,121,123,323,325,525,527,727,729,929,931,141,143,343,345,545,547,747,749,949,951,161,163,363,365,565,567,767,769,969,971,181,183,383,385,585,587,787,789,989,991,201,104,403,306,605,508,807,710,19,93,41,16,63,38,85,60,8,10};

void nhap()
{
while (cin >> n)
{
if (n==1) cout << 1 << "\n";
else if (n<=82) cout << A[n-1] << "\n";
else cout << A[n%82] << "\n";
}
}

int main ()
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
freopen ("xdd.inp","r",stdin);
freopen ("xdd.out","w",stdout);
nhap();
return 0;
}

Tổng số bài gửi : 16 Join date : 10/05/2022

Code:: #include <bits/stdc++.h>
using namespace std;
int n,a[100001];

int b[85] = {1, 3, 5, 7, 9, 11, 13, 33, 35, 55, 57, 77, 79, 99, 101, 103, 303, 305, 505, 507, 707, 709, 909, 911, 121, 123, 323, 325, 525, 527, 727, 729, 929, 931, 141, 143, 343, 345, 545, 547, 747, 749, 949, 951, 161, 163, 363, 365, 565, 567, 767, 769, 969, 971, 181, 183, 383, 385, 585, 587, 787, 789, 989, 991, 201, 104, 403, 306, 605, 508, 807, 710, 19, 93, 41, 16, 63, 38, 85, 60, 8, 10};
void nhap()
{
cin>>n;
}
void sol()
{
if(n % 83 == 0) cout<<b[1];
else
cout<<b[(n % 83) - 1];
}
int main()
{
freopen("s.inp","r",stdin);
freopen("s.out","w",stdout);
nhap();
sol();
}

Tiêu đề: Re: KTLT12. Dãy số Tue May 17, 2022 4:09 pm

Subtask1:
Khởi tạo a[1] = 1;
for (i,2,n) a[i] = sodao(a[i-1]) + 2; //viết thêm hàm sodao(int u) trả vể số đảo của u.
Độ phức tạp của thuật toán: O(N)
Subtask2:
Chỉnh sửa code cách 1 để thực hiện tính a[i] và đưa a[i] ra.
Chạy thử chương trình với N = 10; N = 100; N = 300,...
Kiểm tra tính chất của dãy a[i].
Nhận xét: Dãy số bị lặp đi lặp lại ở phần sau. Độ dài của đoạn lặp lại được gọi là chu kỳ lặp.
Với mỗi N, ta chỉ cần xác định vị trí của a[i] trong đoạn chu kì này.
Độ phức tạp của thuật toán: O(1).

Tổng số bài gửi : 27 Join date : 10/05/2022

Code:: #include <bits/stdc++.h>
#define maxn 100000
using namespace std;
int dp[100];
long long n;
int sdn(int u){
int daonguoc = 0;
while(u > 0){
daonguoc=(daonguoc+u%10)*10;
u/=10;
}
return daonguoc;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
freopen("SEQUENCE.INP","r",stdin);
freopen("SEQUENCE.OUT","w",stdout);
while (cin>>n){
dp[1]=1;
for(int i=2;i<=82;i++)
dp[i]=dp[i-1]+2;
if (n<=82){
for(int i=8 ;i <= n; i++)
dp[i] = sdn(dp[i-1])/10+2;
}else{
for(int i=8 ;i <= 82; i++){
dp[i] = sdn(dp[i-1])/10+2;
}
}
cout<<dp[n-(n/81)*81];
}
}

Tổng số bài gửi : 34 Join date : 13/06/2022

Code:: #include <bits/stdc++.h>
#define maxn 100000
using namespace std;
int dp[100];
long long n;
int sdn(int u){
int daonguoc = 0;
while(u > 0){
daonguoc=(daonguoc+u%10)*10;
u/=10;
}
return daonguoc;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
freopen("SEQUENCE.INP","r",stdin);
freopen("SEQUENCE.OUT","w",stdout);
while (cin>>n)
{
dp[1]=1;
for(int i=2;i<=82;i++)
dp[i]=dp[i-1]+2;
if (n<=82){
for(int i=8 ;i <= n; i++)
dp[i] = sdn(dp[i-1])/10+2;
}else{
for(int i=8 ;i <= 82; i++){
dp[i] = sdn(dp[i-1])/10+2;
}
}
cout<<dp[n-(n/81)*81];
}
}