Vét Cạn | Lập Trình C/C++

Trang chủ » Hack Vét Cạn » Vét Cạn | Lập Trình C/C++

Có thể bạn quan tâm

Menu Bỏ qua nội dung

Số tự nhiên có rất nhiều tính chất thú vị. Ví dụ với số 23, số đảo ngược của nó là 32. Hai số này có ước chung lớn nhất là 1. Những số như thế được gọi là số thân thiện, tức là số 23 được gọi là số thân thiện, số 32 cũng được gọi là số thân thiện.

Hãy nhập vào 2 số nguyên a,b (10≤a≤b≤30000). Hãy đếm xem trong khoảng từ a đến b (kể cả a và b) có bao nhiêu số thân thiện. Dữ liệu

Bao gồm một dòng chứa 2 số a,b. Hai số được cách nhau bằng một khoảng trắng Kết quả

Bao gồm một dòng là kết quả của bài toán. Ví dụ

Dữ liệu 20 30

Kết quả 3

Hướng dẫn: Duyệt trâu vét cạn, để ý rằng số nào chia hết cho 3,9,11 thì lật lại nó cũng chia hết tương ứng cho 3,9,11 nên gặp những số này ta bỏ qua. Vấn đề còn lại là lật số và thuật chia Euclid tìm ước chung lớn nhất.

Nguồn : http://vn.spoj.com/problems/NKNUMFRE/

Code

#include<stdio.h> long lat(long n) { long k=0; while(n>0) {k=k*10+n%10;n/=10;} return k; } long gcd(long a,long b) { if(b) return gcd(b,a%b); return a; } int main() { long a,b,d=0,j; scanf("%ld%ld",&a,&b); for(long i=a;i<=b;i++) { if(i%3==0 || i%11==0) continue; j=lat(i); if(i%2==0 && j%2==0) continue; d+=gcd(i,j)==1; } printf("%ld",d); }

Chia sẻ ngay:

Thích Đang tải...

Đất nước Văn Lang thời cổ xưa đã có những hiểu biết tân tiến về số học. Tương truyền rằng, vua Hùng Vương thứ 17 cùng các trưởng lão trong triều đình đã phát minh ra các số huyền bí. Các số này giúp chỉ dẫn đường vào kho tàng của đất nước.

Theo các chứng tích khảo cổ, các nhà khoa học kết luận rằng số huyền bí cơ sở a bằng tích của (3d-1) với mọi ước số d > 0 của a.

Bờm thích số học đồng thời cũng rất thích tìm hiểu lịch sử đất nước. Bạn hãy giúp Bờm tính số huyền bí cơ sở a (1 ≤ a ≤ 109). Do kết quả có thể rất lớn, bạn chỉ cần in ra phần dư của số huyền bí cơ sở a khi chia cho 20122007. Dữ liệu

Gồm một số nguyên a duy nhất. Kết qủa

In ra số nguyên duy nhất là phần dư của số huyền bí cơ sở a khi chia cho 20122007. Ví dụ

Dữ liệu: 10

Kết qủa 7291779

Nguồn: http://vn.spoj.com/problems/MYSTERY/

Hướng dẫn: Bước 1. Dùng thuật toán đệ quy chia để trị tính a^n mod b bằng cách 1. Nếu n=0 thì trả về 1 2. Nếu n chẵn trả về ( a^(n/2) mod b )^2 mod b 3. Nếu n lẻ trả về (a * ( a^(n/2) mod b )^2) mod b

Bước 2. Vét cạn duyệt đến căn a để tìm ước cứ có một ước i thì có một ước a/i chú ý trường hợp a là số chính phương thì ước căn a chỉ tính 1 lần.

Code

#include<iostream> using namespace std; typedef unsigned long long ULong; ULong Base=20122007; ULong Mymod(ULong a,ULong n) { if(n==0) return 1; ULong t=Mymod(a,n/2); t=(t*t)%Base; return n%2?(t*a)%Base:t; } int main() { ULong a,i,T=1; cin>>a; for(i=1;i*i<a;i++) if(a%i==0) { T=(T*(Mymod(3,i)-1))%Base; T=(T*(Mymod(3,a/i)-1))%Base; } if(i*i==a)T=(T*(Mymod(3,i)-1))%Base; cout<<T; }

Chia sẻ ngay:

Thích Đang tải...

Kỳ thi ACM/ICPC được tổ chức giữa các trường đại học ở Việt Nam. Mỗi trường sẽ chọn ra một đội gồm 3 thí sinh để thi đấu. Để chuẩn bị tốt cho kỳ thi, trường XYZ đã có kế hoạch tập huấn cho sinh viên với chủ đề:

Lý thuyết độ phức tạp tính toán Tổ hợp và số học Sắp xếp, tìm kiếm nâng cao Xử lý xâu Quy hoạch động Duyệt toàn bộ và nhánh cận Các thuật toán đồ thị Các thuật toán xấp xỉ Các thuật toán hình học Lý thuyết trò chơi Một số cấu trúc dữ liệu nâng cao

Kết thúc khoá tập huấn, Ban giám hiệu đã thống kê khả năng của từng sinh viên và muốn chọn ra 3 sinh viên để lập thành đội đi thi với hi vọng đạt kết quả cao nhất. Giả sử s[i][j] là điểm đánh giá khả năng của sinh viên với chủ đề thì việc đánh giá khả năng đạt kết quả cao của đội gồm 3 thí sinh x, y, z bằng max(s[x][1], s[y][1], s[z][1]) + max(s[x][2], s[y][2], s[z][2]) + … + max(s[x][11], s[y][11], s[z][11]).

Yêu cầu: Cho n sinh viên và s[i][j] là khả năng của sinh viên i với chủ đề j, hãy giúp Ban giám hiệu trường chọn ra 3 sinh viên thành một đội thi đấu có khả năng đạt kết quả cao nhất. Input

Dòng đầu tiên chứa số nguyên n (n≤100). n dòng tiếp theo, mỗi dòng chứa 11 số nguyên không âm s_(i,j) (s_(i,j)≤〖10〗^9) Hai số liên tiếp trên cùng một dòng được ghi cách nhau bởi dấu cách. Dòng đầu tiên chứa số nguyên n (n≤100). n dòng tiếp theo, mỗi dòng chứa 11 số nguyên không âm s[i][j] (s[i][j] <= 10^9) Hai số liên tiếp trên cùng một dòng được ghi cách nhau bởi dấu cách.

Output

• Khả năng đạt kết quả cao nhất của đội có 3 thí sinh được chọn. Example

Input: 4 2 2 2 0 0 0 0 0 0 0 0 3 1 1 0 0 0 0 0 0 0 0 1 3 1 0 0 0 0 0 0 0 0 1 1 3 0 0 0 0 0 0 0 0

Output: 9

Nguồn: http://www.spoj.com/PTIT/problems/PTIT016E/

Ý tưởng: Vét cạn duyệt tất các bộ 3 sinh viên để tìm max

code

#include<stdio.h>

long long maxx(long long a,long long b,long long c) { return a>b&&a>c?a:(b>c?b:c); }

int main() { int N; long long s[105][12],M=0,k; scanf("%ld",&N); for(int i=1;i<=N;i++) for(int j=1;j<=11;j++)scanf("%lld",&s[i][j]); for(int x=1;x<=N;x++) for(int y=x+1;y<=N;y++) for(int z=y+1;z<=N;z++) { k=0; for(int i=1;i<=11;i++) k+=maxx(s[x][i], s[y][i], s[z][i]); if(M<k)M=k; } printf("%lld",M); }

Chia sẻ ngay:

Thích Đang tải...

Trong một hội thi Ballgame, ban tổ chức chuẩn bị một bàn lớn. Trên mặt bàn có n bi xanh đánh số từ 1 đến n và n bi đỏ đánh số từ n + 1 đến 2n. Mỗi trận đấu, các vận động viên sẽ chơi luân phiên nhau. Đến lượt chơi của mình, Hùng cần tìm 3 bi mà vị trí của chúng là thằng hàng hanu và sao cho trong số đó có hai bi đỏ và 1 bi xanh (khi đó ăn được một bi đỏ), hoặc là có hai bi xanh và 1 bi đỏ (khi đó được ăn 1 bi xanh). Yêu cầu

Cho biết tọa độ trên mặt phẳng tọa độ Đề-các của vị trí và màu của các bi hiện tại trên bàn, bạn hãy giúp Hùng chọn 3 bi để chơi. Input

Dòng đầu ghi số nguên dương n. Dòng thứ i trong số n dòng tiếp theo ghi hai số nguyên là hoành độ và tung độ trên mặt phẳng tọa độ Đề-các của vị trí đặt bi xanh với chỉ sô i. Dòng thứ i trong số n dòng cuối cùng ghi hai số nguyên là hoàng độ và tung độ trên mặt phẳng tọa độ Đề-các của vị trí đặt bi đỏ với chỉ số n + i. Hoàng độ và tung độ không vượt quá 10^6, vị trí các bi là đôi một phân biệt.

Giới hạn

30% số test có n <= 2; 30% số test khác có n <= 100. 40% số test còn lại có n <= 1000.

Output

Ghi ra 3 chỉ số của các viên bi mà Hùng cần chọn, nếu không thể chọn được 3 bi nào, ghi ra -1. Nếu có nhiều đáp án, ghi ra một đáp án bất kì. Example

Input: 3 1 1 2 2 4 9 3 3 6 20 8 100

Output: 1 2 4

Nguồn: http://vn.spoj.com/problems/BALLGMVN/

Hướng dẫn: Để có 3 viên thẳng hàng có 1 cặp khác màu ta xét 2 trường hợp gồm 1 viên đỏ và 2 viên xanh hoặc ngược lại 2 viên xanh và 2 viên đỏ.

Trường hợp 1. (1 viên đỏ và 2 viên xanh)

Với mỗi viên đỏ nằm trong [1..n] ta duyệt tất cả các viên xanh [n+1..2n] với mỗi cặp như vậy ta tính hệ số góc tạo bởi đường thẳng đi qua 2 bi và đường y=0 có tan alpha bằng (y[j]-y[i])/(x[j]-x[i]) chú ý nếu x[j]==x[i] coi hệ số góc này bằng vô cùng.

Tính hết tất cả các hệ số góc này kiểm tra có cặp nào bằng nhau chứng tỏ chúng là 1 đường thẳng vì cùng đi qua 1 điểm lại có hệ số góc bằng nhau. Thuật toán kiểm tra cặp bằng nhau ta dùng đệ quy chia để trị giống quicksort phân hoạch ra có bằng nhau thì lấy luôn không có thì gọi đệ quy 2 bên phải, trái.

Trường hợp 2. Chỉ cần làm tương tự

Code

#include<stdio.h> #include<algorithm> using namespace std; double vc=1000005; struct bi { int id; double h; //he so goc tan anpha };

bool Timcap(bi *B,int L,int R,int &p,int &q) //giong quicksort nhung de tim 2 cap giong nhau { if(L>=R) return false; swap(B[L],B[(L+R)/2]); int i=L; for(int j=L+1;j<=R;j++) { if(B[L].h==B[j].h) {p=L;q=j;return true;} if(B[j].h<B[L].h) {i++; swap(B[i],B[j]);} } if(Timcap(B,L+1,i,p,q)) return true; if(Timcap(B,i+1,R,p,q)) return true; return false; }

int main() { int n,k,p,q; long x[2005],y[2005]; bi B[2005]; scanf("%d",&n); k=2*n; for(int i=1;i<=k;i++) scanf("%ld%ld",&x[i],&y[i]); for(int i=1;i<=n;i++) { for(int j=n+1;j<=k;j++) { if(x[i]==x[j]) B[j].h=vc; else B[j].h=double(y[j]-y[i])/(x[j]-x[i]); B[j].id=j; } if(Timcap(B,n+1,k,p,q)) {printf("%d %d %d",i,B[p].id,B[q].id); return 0;} } for(int i=n+1;i<=k;i++) { for(int j=1;j<=n;j++) { if(x[i]==x[j]) B[j].h=vc; else B[j].h=double(y[j]-y[i])/(x[j]-x[i]); B[j].id=j; } if(Timcap(B,1,n,p,q)) {printf("%d %d %d",i,B[p].id,B[q].id); return 0;} } printf("-1"); }

Chia sẻ ngay:

Thích Đang tải...

Chế độ ăn kiêng của đàn bò khiến cho nông trang của nông dân John dôi ra 1 số lượng cỏ khô, vì vậy anh ta muốn bán đấu giá số cỏ khô này để trang trải phần nào chi phí chăn nuôi. Anh ta có N (1 <= N <= 1,000) bó cỏ khô giống nhau; khách hàng sẽ đấu giá để mua đống cỏ này là M (1 <= M <= 1,000) nông dân khác sống gần đó.

Mỗi một nông dân i sẽ cho nông dân John biết anh ta sẵn sàng trả P_i (1 <= P_i = mức giá đó, những người còn lại sẽ bị từ chối giao dịch.

Hãy giúp nông dân John tính xem đặt mức giá nhỏ nhất là bao nhiêu để thu được nhiều tiền nhất có thể. Dữ liệu

* Dòng 1: Hai số nguyên cách nhau bởi dấu cách: N và M

* Dòng 2..M+1: Dòng i+1 chứa 1 số nguyên duy nhất: P_i Kết quả

* Dòng 1: 2 số nguyên cách nhau bởi dấu cách: giá bán của John và số tiền mà John thu được Ví dụ

Dữ liệu: 5 4 2 8 10 7

Kết quả: 7 21

Nguồn: http://vn.spoj.com/problems/AUCTION/

Hướng dẫn: Thuật giải tham lam theo nguyên lý thứ tự vét cạn các khả năng 1. Bước 1 sắp xếp p1…pm giảm dần dùng hàm sort có sẵn chú ý phải viết thêm hàm so sánh để giảm dần 2. Số bó cỏ bán tối đa sẽ là min(n,m) nên nếu m>n thì m gán lại bằng n 3. Xét lần lượt số bỏ có được bán từ 1 đến m ta tìm max của i*p[i] chú ý bài toán tìm giá nhỏ nhất nên nếu có nhiều max thì ta chọn max có p[i] nhỏ nhất

code

#include<algorithm> #include<stdio.h> using namespace std; long ss(long x,long y) {return x>y;} int main() { int n,m,t=1; long p[1005]; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%ld",&p[i]); sort(p+1,p+1+m,ss); if(m>n) m=n; for(int i=2;i<=m;i++) if(i*p[i]>=t*p[t]) t=i; printf("%d %ld",p[t],t*p[t]); }

Chia sẻ ngay:

Thích Đang tải...

Khi còn bé, các bạn học sinh học được cách trừ phân số bằng cách quy đồng mẫu số, rồi mới thực hiện phép trừ.

Nhưng một lần, An tính thử hiệu hai phân số bằng cách lấy hiệu hai tử số và hiệu hai mẫu số và thấy thật ngạc nhiên là kết quả vẫn đúng.

Chẳng hạn 5/4-9/12 có (5-9)/(4-12) = -4/-8=1/2 đúng bằng5/4-9/12

An thấy tính chất này thật kỳ diệu và An muốn biết, với phân số b/n cho trước, có bao nhiêu cặp giá trị a>0 và m>0 sao cho a/m-b/n=(a-b)/(m-n) Input

Một dòng chứa hai số nguyên dương b và n cách nhau ít nhất một dấu cách (1 <= b, n <= 10^6; trong 50% số test b, n <= 1000). Output

một số nguyên duy nhất là số lượng cặp (a,m) tính được. Example

Input: 9 12

Output: 5

Nguồn: http://vn.spoj.com/problems/WCALC/

Ý tưởng: 1. Xét phương trình a/m-b/n=(a-b)/(m-n) a * n^2 + b*m^2 – 2bmn = 0 b(m-n)^2 = (b-a) * n^2

tương đương (b-a)/b = [(m-n)/n]^2 suy ra b(b-a) là số chính phương

m = n+ b/n * sqrt(b*(b-a)) hoặc m = n – b/n * sqrt(b*(b-a)) biểu thức 1 luôn dương ta tìm m dương nên chỉ cần xét biểu thức 2.

2. Vậy bài toán đi tìm những số b-a<b mà nhân với b thành số chính phương ta vét cạn bằng cách phân tích b thành nhân tử ta chọn những nhân tử có mũ lẻ nhân với nhau để nó nhân với b thành số chính phương, sau đó ta duyệt các số chính phương để nhân vào sao cho nó nhỏ hơn b và giải hai nghiệm kiểm tra nguyên và kiểm tra dương để có kết quả

Code:

#include<math.h> #include<stdio.h> int main() { long long b,n,a=1,k,dem=1; scanf("%lld%lld",&b,&n); k=b; for(long long i=2;i*i<=k;i++) if(k%i==0) { long d=0; while(k%i==0) {k/=i;d++;} if(d%2!=0) a*=i; } a*=k; long long x=round(sqrt(a*b)); for(long long i=1;i*i*a<b;i++) { long long p=x*i*n; if(p%b==0) { dem++; if(n>p/b) dem++; } } printf("%lld",dem); }

Chia sẻ ngay:

Thích Đang tải...

Cho hai số tự nhiên A và B. Bài toán đặt ra là xác định số nguyên dương N sao cho bội số chung nhỏ nhất của A+N và B+N đạt giá trị nhỏ nhất. Input

Chỉ gồm một dòng chứa hai số tự nhiên A,B. Cả hai giá trị không quá 109. Output

Ghi ra giá trị N tìm được. Nếu có nhiều giá trị N thỏa mãn thì ghi ra giá trị nhỏ nhất. Example

Input: 4 10

Output: 2

Nguồn : http://www.spoj.com/PTIT/problems/PTIT016A/

Hướng dẫn:

I. Cơ sở toán 1. Nhận thấy bội chung nhỏ nhất của a và b bằng tích hai số chia cho ước chung lớn nhất. Do đó để tối thiểu bội chung nhỏ nhất thì ta phải tối đa ước chung lớn nhất

2. Ước chung lớn nhất của A+N và B+N theo định lý Euclid thì nó cũng là ước của (A+N)-(B+N) = A-B.

II. Lập trình

Đặt d=A-B để tìm được N nhỏ nhất thì ta tìm các ước của A-B để làm ước chung lớn nhất của A+N và B+N với mỗi ước đó ta tìm ra N tìm min nhưng lớn hơn 0 của các N ta sẽ thu được kết quả

Code:

#include<iostream> using namespace std; typedef unsigned long long Long; Long gcd(Long a,Long b) { while(b) { Long r=a%b; a=b;b=r; } return a; } int main() { Long A,B,d,N,i,max,max1,N1; cin>>A>>B; if(A<B) {d=A;A=B;B=d;} if(A==B) {cout<<1;return 0;} d=A-B; N=(B/d+1)*d-B; max=(A+N)/gcd(A+N,B+N)*(B+N); for(Long x=2;x*x<=d;x++) if(d%x==0) { N1=(B/x+1)*x-B; if(N1<N) { max1=(A+N1)/gcd(A+N1,B+N1)*(B+N1); if(max>=max1) {max=max1;N=N1;} } Long y=d/x; N1=(B/y+1)*y-B; if(N1<N) { Long max1=(A+N1)/gcd(A+N1,B+N1)*(B+N1); if(max>=max1) {max=max1;N=N1;} } } cout<<N; }

Chia sẻ ngay:

Thích Đang tải...

Với 1 số tự nhiên N(1<= N <= 10^9) ta có thể phân tích nó thành tổng của một số số tự nhiên liên tiếp( tất nhiên những số này phải nhỏ hơn N). Ví dụ với N = 5 ta có duy nhất 1 cách phân tích là 5 = 2+3. Bài toán đặt ra là cho số tự nhiên N, hãy cho biết có bao nhiêu cách phân tích số tự nhiên N thành tổng của các số tự nhiên liên tiếp. Input

Gồm nhiều dòng, mỗi dòng chứa một số nguyên N. (Giới hạn : số dòng <= 100) Output

Mỗi dòng ghi một số nguyên là số cách phân tích số N đọc được ở dòng tương ứng trong input. Ví dụ

Input: 12 5 4 13 45 100 234 3 175

Output: 1 1 0 1 5 2 5 1 5

Nguồn

http://vn.spoj.com/problems/COUNTCBG/

Hướng dẫn: Ta thấy rằng các phần tử liên tiếp u,u+1,u+2…, v là một cấp số cộng có v-u+1 phần tử do đó nó có tổng là (u+v)*(v-u+1)/2

Như vậy để phân tích n thành tổng 1 dãy liên tiếp từ 2 phần tử trở lên thì 2n=(u+v)*(v-u+1) do v-u+1<u+v nên ta chỉ xét 1 ước nhỏ hơn căn hoặc bằng 2n cho v-u+1 và 1 ước lớn hơn hoặc bằng căn 2n cho u+v. Hơn nữa do u+v và u-v cùng tính chẵn lẻ nên do đó ta đi đếm những cặp ước không cùng tính chẵn lẻ cho 2 số này.

Code tham khảo

int main() { long long n; while(scanf(&quot;%lld&quot;,&amp;n)!=EOF) { n=2*n; long d=0; for(long long i=2;i*i&lt;=n;i++) if(n%i==0) d+=(i+n/i)%2; printf(&quot;%ld\n&quot;,d); } }

Chia sẻ ngay:

Thích Đang tải...

Cho 1 bàn cờ N×N ô vuông. Hai người chơi lần lượt điền chữ cái đầu tiên của tên mình vào 1 trong các ô còn trống trên bàn cờ. Người chơi sẽ dành chiến thẳng nếu điền được 3 ô liền nhau cùng 1 chữ theo chiều dọc, chiều ngang, hoặc đường chéo. Cho trạng thái của bàn cờ, xác định xem ai thẳng cuộc? Input

– Dòng 1: số N (1<=N<=30)

– N dòng, mỗi dòng N kí tự liên nhau mô tả trạng thái của bàn cờ:

– Dấu '.': nếu ô đó còn trống

– Chữ cái in hoa: các ô đã được người chơi đi, hai người chơi đại diện bằng hai chữ cái khác nhau.

Dữ liệu đảm bảo rằng có nhiều nhất 1 người chiến thắng. Output

Nếu trò chơi đã có người thắng cuộc, in ra kí tự đại diện của người đó. Ngược lại in ra "ongoing". Example

Input: 3

XOO

XOO

X..

Output: X

Input: 4

….

..A.

AAB.

.B.B

Output: ongoing

Input: 3

ABB

AAA

BBA

Output: A

Ý tưởng: Vét cạn duyệt toàn bộ ma trận để kiểm tra, xây dựng thêm hai hàng rào lính canh thêm hai cột cuối và hai hàng cuối toàn dấu ‘.’

Nguồn http://www.spoj.com/PTIT/problems/PTIT125J/ code http://ideone.com/41ufsN

Chia sẻ ngay:

Thích Đang tải... Điều hướng bài viết
  • Theo dõi Đã theo dõi
    • Lập trình C/C++
      • Đã có 26 người theo dõi Theo dõi ngay
    • Đã có tài khoản WordPress.com? Đăng nhập.
    • Lập trình C/C++
    • Theo dõi Đã theo dõi
    • Đăng ký
    • Đăng nhập
    • Báo cáo nội dung
    • Đọc trong WordPress
    • Quản lý theo dõi
    • Ẩn menu
%d Tạo trang giống vầy với WordPress.comHãy bắt đầu

Từ khóa » Hack Vét Cạn