Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 12 kết quả

Đề tài: Đề thi quốc gia

  1. #1
    Ngày gia nhập
    04 2008
    Nơi ở
    Bốn bề là nhà
    Bài viết
    703

    Mặc định Đề thi quốc gia

    Mình post đề số 1 của đề thi tin học quốc gia 2008 để mọi người làm cho vui nhá.
    Cho 2 dãy
    b1 b2...bn
    c1 c2...cn
    tìm min(|bi+cj|)?
    input:là 1 số n duy nhất (n<=10^5)
    output:giá trị nhỏ nhất tìm được.

    lưu ý:các thuật toán độ phức tạp O(n^2) là không khả thi.

  2. #2
    Ngày gia nhập
    10 2008
    Bài viết
    258

    hướng giải
    1.sắp xếp hai day tăng dần
    2.cho i=0 đến cuối dãy b
    j=n-1 đến đầu dãy c
    nếu b[i]+c[j]>0
    j--;
    else
    i++

  3. #3
    Ngày gia nhập
    04 2008
    Bài viết
    336

    1.sắp xếp hai day tăng dần
    cái độ phức tạp được đánh giá từ đây đấy. :-"
    code ra gió bão

  4. #4
    Ngày gia nhập
    11 2008
    Bài viết
    10

    Bài này các bạn chú ý một tẹo là giải rất dễ dàng
    Với a thuộc dãy 1, b thuộc dãy 2 ta thấy |a+b| bằng một trong các giá trị sau:
    1. -a-b
    2. -a+b
    3. a-b
    4. a+b
    TH1 và 4: tìm 2 số âm nhỏ nhất hoặc 2 số dương lớn nhất (mỗi số thuộc 1 dãy)
    TH2 và 3: tìm a dương lớn nhất, b âm nhỏ nhất hoặc a âm nhỏ nhất b dương lớn nhất.
    Giải thuật này có độ phức tạp O(n), mình vừa đọc qua nên giải thuật có khi còn thiếu sót, các bạn bỏ quá.

  5. #5
    Ngày gia nhập
    09 2008
    Bài viết
    5

    Trích dẫn Nguyên bản được gửi bởi linkinsteps Xem bài viết
    Bài này các bạn chú ý một tẹo là giải rất dễ dàng
    Với a thuộc dãy 1, b thuộc dãy 2 ta thấy |a+b| bằng một trong các giá trị sau:
    1. -a-b
    2. -a+b
    3. a-b
    4. a+b
    TH1 và 4: tìm 2 số âm nhỏ nhất hoặc 2 số dương lớn nhất (mỗi số thuộc 1 dãy)
    TH2 và 3: tìm a dương lớn nhất, b âm nhỏ nhất hoặc a âm nhỏ nhất b dương lớn nhất.
    Giải thuật này có độ phức tạp O(n), mình vừa đọc qua nên giải thuật có khi còn thiếu sót, các bạn bỏ quá.
    ?
    sai lầm chăng?
    |a+b| có bao h bằng -a+b hay a-b đâu.
    |a+b| chỉ có thể có a+b hoặc a+b.
    Mà thuật toán cũng sai. Bạn nên kiểm tra lại.

    Thuật toán của mình là áp dụng con trỏ với cây nhị phân tìm kiếm.
    -Chọn dãy B là dãy tìm kiếm:
    +ta duyệt dãy để tạo cây nhịn phân tìm kiếm.
    *độ phức tạp < O(n^2)
    - Duyệt dãy A.
    +với phần tử A[i] đc duyệt.
    + chú ý |a+b| ( a là hằng số ) nhỏ nhất khi b gần -a nhất.
    + Tìm trong cây nhị phân tìm kiếm giá trị gần -A[i] nhất.
    + tính |a+b| và so sánh với min và cập nhật giá trị Min.
    *độ phức tạp < O(n^2)
    -> In ra min
    hok bít thế này có đc hok

  6. #6
    Ngày gia nhập
    01 2008
    Bài viết
    240

    Mặc định Đề thi quốc gia

    Trích dẫn Nguyên bản được gửi bởi tanglung117 Xem bài viết
    Mình post đề số 1 của đề thi tin học quốc gia 2008 để mọi người làm cho vui nhá.
    Cho 2 dãy
    b1 b2...bn
    c1 c2...cn
    tìm min(|bi+cj|)?
    input:là 1 số n duy nhất (n<=10^5)
    output:giá trị nhỏ nhất tìm được.

    lưu ý:các thuật toán độ phức tạp O(n^2) là không khả thi.
    không biết mình có hiểu sai không nhỉ, bài này cứ duyệt cả 2 dãy từ đầu đến cuối cộng chúng lại với nhau rồi chọn thằng nhỏ nhất là OK mà độ phức tạp của nó n*n như code của mình, anh em xem có sai không hộ cái
    thanks
    Code:
    // Test1.cpp : Defines the entry point for the console application.
    //
    
    #include "stdafx.h"
    #include<stdio.h>
    #include<conio.h>
    #include<math.h>
    #define MAX 100000
    long n,I,J;
    float a[MAX],b[MAX],result;
    float A,B;
    //-----------------------
    void Input(){
    	long i;
    	for(i=0;i<MAX;i++){
    		a[i]=0;
    		b[i]=0;
    	}
    	printf("N=");
    	scanf("%d",&n);
    	result=0;
    	for(i=0;i<n;i++){
    	printf("a[%d]",i);
    	scanf("%f",&a[i]);
    	}
    	printf("------------------------\n");
    	for(i=0;i<n;i++){
    	printf("b[%d]",i);
    	scanf("%f",&b[i]);
    	}
    result=abs(a[0]+b[0]);
    A=a[0];
    I=0;
    B=b[0];
    J=0;
    }
    //--------------------------
    float GetResult(){
    
    	long i,j;
    	for(i=0;i<n;i++)
    		for(j=0;j<n;j++){
    			if(abs(a[i]+b[j])<result){
    			result=abs(a[i]+b[j]);
    			A=a[i];
    			I=i;
    			B=b[i];
    			J=j;
    			}
    		}
    	return result;
    }
    void main()
    {
    Input();
    float result=GetResult();
    printf("%f+ %f =%f",A,B,result);
    printf("\n");
    printf("a[%d]+ b[%d]",I,J);
    getch();
    }
    Time

  7. #7
    Ngày gia nhập
    11 2007
    Bài viết
    294

    Vấn đề ở đây là độ phức tạp phải nhỏ hơn n^2, chứ làm thế kia thì chắc chắn được 0 điểm :P.
    Is the moon rising...

  8. #8
    Ngày gia nhập
    01 2008
    Bài viết
    240

    Trích dẫn Nguyên bản được gửi bởi darkan Xem bài viết
    Vấn đề ở đây là độ phức tạp phải nhỏ hơn n^2, chứ làm thế kia thì chắc chắn được 0 điểm :P.
    Ồ thế hả tưởng
    Đã được chỉnh sửa lần cuối bởi nthung : 04-11-2008 lúc 06:08 PM.
    Time

  9. #9
    Ngày gia nhập
    10 2007
    Nơi ở
    HCM
    Bài viết
    46

    Trích dẫn Nguyên bản được gửi bởi darkan Xem bài viết
    Vấn đề ở đây là độ phức tạp phải nhỏ hơn n^2, chứ làm thế kia thì chắc chắn được 0 điểm :P.
    đi thi hơn nhau cái chỗ này đấy, chính giới hạn này làm cho bài toán trở nên khó nuốt hơn

  10. #10
    Ngày gia nhập
    05 2008
    Bài viết
    6

    Bài này làm chỉ O(nlogn) thôi. Em mang đi chấm trên vn.spoj.pl accept đc 100% test. Code hơi xấu tẹo tại em gõ ẩu :P
    Code:
    #include<stdio.h>
    #include<stdlib.h>
    
    long n, b[100100],c[100100];
    
    void nhap();
    void sort_b(long l,long r);
    void sort_c(long l,long r);
    
    int main()
    {
    	nhap();
    	sort_b(0,n-1);
    	sort_c(0,n-1);
    
    	//xu ly
    	long kq,i,j;
    	kq=abs(b[0]+c[0]);
    	i=0; j=n-1;
    	while(i<=(n-1) && j>=0)
    	{
    		if(kq>abs(b[i]+c[j]))
    			kq=abs(b[i]+c[j]);
    		if((b[i]+c[j])>=0)
    			j--;
    		else
    			i++;
    	}
    	printf("%ld\n",kq);
    
    	return 0;
    }
    
    void nhap()
    {
    	long i;
    	
    	scanf("%ld",&n);
    	
    	for(i=0;i<n;i++)
    		scanf("%ld",&b[i]);
    	for(i=0;i<n;i++)
    		scanf("%ld",&c[i]);
    }
    
    void sort_b(long l,long r)
    {
    	long i,j,x,tmp;
    	i=l; j=r; x=b[(l+r)/2];
    	do
    	{
    		while(b[i]<x)
    			i++;
    		while(x<b[j])
    			j--;
    		if(i<=j)
    		{
    			tmp=b[i]; b[i]=b[j]; b[j]=tmp;
    			i++;j--;
    		}
    	} while(i<=j);
    	if(i<r)
    		sort_b(i,r);
    	if(l<j)
    		sort_b(l,j);
    }
    
    void sort_c(long l,long r)
    {
    	long i,j,x,tmp;
    	i=l;j=r; x=c[(l+r)/2];
    	do
    	{
    		while(c[i]<x)
    			i++;
    		while(x<c[j])
    			j--;
    		if(i<=j)
    		{
    			tmp=c[i];c[i]=c[j];c[j]=tmp;
    			i++;j--;
    		}
    	} while(i<=j);
    	if(l<j)
    		sort_c(l,j);
    	if(i<r)
    		sort_c(i,r);
    }
    Đã được chỉnh sửa lần cuối bởi granjota : 04-11-2008 lúc 09:23 PM.

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn