Đề thi quốc gia

[G.Perelman]

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.

[thansautk]

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++

[6220119]

1.sắp xếp hai day tăng dần

cái độ phức tạp được đánh giá từ đây đấy. :-"

[linkinsteps]

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á.

[tuan1010]

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

[nthung]

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

// 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();
}

[darkan]

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.

[nthung]

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

[halohcm]

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

[granjota]

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

#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);
}