SPOJ Corner

[MrPaint]

Đang ngồi làm tí Nghịch con PNUMBER mà submit lên toàn bị kết quả sai mới láo

Thuật toán dùng linked list để lưu các số nguyên tố tìm được rồi chạy lần lượt từ 1 ~> b, hàm isPrime có trách nhiệm kiểm tra:

• nếu là 1 ~> false luôn khỏi xét
• nếu là 2 ~> true luôn khỏi nghĩ
• nếu chia hết cho 2 ~> false luôn
• nếu không phải các trường hợp trên thì thử chia lần lượt cho các số nguyên tố đã tìm được (nhưng chỉ xét các số < căn của số cần kiểm tra thôi), nếu tìm thấy thằng nào chia hết ~> false
• ra được đến đây thì true

Có tí buồn nhé

Code nè:

[highlight=cpp]#include <cstdlib>
#include <stdio.h>
#include <math.h>

typedef unsigned long int USLI;

class Prime
{
public:
Prime(USLI number): itsNumber(number), itsNext(0) {};
void setNext(Prime * next) {itsNext = next;};
USLI getNumber() const {return itsNumber;};
Prime * getNext() const {return itsNext;};
private:
USLI itsNumber;
Prime * itsNext;
};

bool isPrime(USLI);
Prime * pHead, * pLast;

int main()
{
Prime * pNode;
USLI a,b;

scanf("%lu %lu",&a,&b);

for(USLI i = 1; i < b; i++)
{
if (isPrime(i) == true)
{
pNode = new Prime(i);
if (!pHead) pHead = pNode;
if (pLast) pLast->setNext(pNode);
pLast = pNode;
if (i >= a && a <= b) printf("%lu\n",i);
}
}
return 0;
}

bool isPrime(USLI number)
{
Prime * pNode;

if (number == 1) return false;
if (number == 2) return true;
if (number % 2 == 0) return false;

if (!pHead) return false;

USLI limit = (USLI)sqrt(number);

pNode = pHead;
while (pNode->getNumber() <= limit)
{

if (number % pNode->getNumber() == 0) return false;
pNode = pNode->getNext();
}
return true;
}
[/highlight]

[haqduong]

Cái này for là được anh ạ . Đây là code pascal. (thời đấy em chưa code C++ nhiều)

[highlight=pascal]var p:array[1..20000] of longint;
np2,i:longint;
a,b:longint;

Function prime(c:longint):boolean;
var j:longint;
begin
if c<=1 then exit(false);
j:=1;
while ((j<=np2) and (p[j]<=sqrt(c))) do
begin
if ((c mod p[j])=0) then exit(false);
inc(j);
end;
exit(true);
end;


BEGIN
read(a,b);
np2:=0;
for i:=2 to a-1 do
if prime(i) then
begin
inc(np2);
p[np2]:=i;
end;
for i:=a to b do
begin
if prime(i) then
begin
inc (np2);
p[np2]:=i;
writeln(i);
end;
end;
END.[/highlight]

Nếu cần trao đổi code có 2 phương án: 1 là vào hskl.net; 2 là vào vnoi.info (diễn đàn của nó).

PS: Nên include cstdio, cmath,... hay thì stdio.h. Không nên lạm dụng class (làm chậm tốc độ chạy).
Bài này int là đủ, cần gì cái chữ long nhỉ , mà C++ là long long chứ không phải long int.
Còn long = int.

@robin: C++ dễ đọc hơn chứ.

[haqduong]

Đề bài này:

1783. Tìm số nguyên tố
Mã bài: PNUMBER

Hãy tìm tất cả các số nguyên tố trong đoạn [A,B] .

Input
Gồm 2 số nguyên A và B cách nhau bởi 1 dấu cách ( 1 ≤ A ≤ B ≤ 200000 ) .

Output
Ghi ra tất cả các số nguyên tố trong khoảng [A,B]. Mỗi số trên 1 dòng.

Ví dụ

Input:
1 10

Output:
2
3
5
7

Code C++ này:
[highlight=cpp]#include <cstdio>

int a,b;
int np2 = 0;
int pr [20000];

void readData() {
scanf("%d %d", &a, &b);
}

bool isPrime(int s) {
if (s <= 1) return false;
for (int j = 0; (j < np2) && (pr[j]*pr[j] <= s); j++) {
if (s % pr[j] == 0) return false;
}
return true;
}

void solve() {
for (int i = 2; i <= a - 1; i++){
if (isPrime(i)) {
pr[np2++] = i;
}
}
for (int i = a; i <= b; i++) {
if (isPrime(i)) {
pr[np2++] = i;
printf("%d\n",i);
}
}
}

int main() {
readData();
solve();
}
[/highlight]

Kết quả này:

2154470 2009-02-22 04:51:31 Tìm số nguyên tố Đạt yêu cầu 0.59 2.6M C++
1999274 2008-12-30 12:25:56 Tìm số nguyên tố Đạt yêu cầu 1.34 632k PAS fpc

PS: Các bạn vào spoj chơi đi, trường mình thiếu mỗi người, đủ người là cũng có hạng đấy.

[MrPaint]

Dùng for thì nói làm ji
Dùng linked list + long mới mở rộng ra sau này được mờ Cho chạy đến vài triệu, đợi mốc mép Rồi đi so sánh với bảng prime number thấy khớp nhá, thế mờ...

Trước anh cũng không dùng class mà dùng struct nhưng giờ lười, dùng class cho tiện. Tóm lại là hem hiểu sao lại sai nhá

PS: Mà các chú dùng highlighter đi nhá, cú pháp [highlight=pascal] hoặc [highlight=cpp], ngoài ra còn nhiều cái khác tự khám phá

[haqduong]

Originally Posted by MrPaint

Dùng for thì nói làm ji
Dùng linked list + long mới mở rộng ra sau này được mờ Cho chạy đến vài triệu, đợi mốc mép Rồi đi so sánh với bảng prime number thấy khớp nhá, thế mờ...

Trước anh cũng không dùng class mà dùng struct nhưng giờ lười, dùng class cho tiện. Tóm lại là hem hiểu sao lại sai nhá

PS: Mà các chú dùng highlighter đi nhá, cú pháp [highlight=pascal] hoặc [highlight=cpp], ngoài ra còn nhiều cái khác tự khám phá

Em chạy 1 đến 1000000000 (1 tỉ) vẫn nhanh như thường Giải thuật khác gì đâu.

PS: Các bạn thử làm bài này nhé: link
Đề bài:

3202. Quay bánh xe
Mã bài: ROTATION

Nông dân John có một cái máy gặt đập cũ, máy này yêu cầu một số dây curoa được đặt trên các bánh xe khác nhau để quay các bộ phận. Động cơ sẽ làm quay bánh xe 1 theo chiều kim đồng hồ, bánh xe 1 lại được gắn kèm 1 dây curoa với bánh xe 2. Bánh xe 2 lại được gắn kèm 1 dây curoa với bánh xe 3 , v.v.. và cứ như vậy có tổng cộng N (1 <= N <= 1,000) bánh xe (và N-1 dây curoa).

Hình ở trên minh họa 2 cách đặt dây curoa giữa 2 bánh xe. Trong hình minh họa, dây curoa của bánh xe 1 đã trực tiếp làm bánh xe 2 chuyển động và quay cùng chiều với bánh xe 1 (gọi là dây curoa thẳng - straight belt). Bánh xe 3 quay kéo theo bánh xe 4 cũng quay nhờ vào dây curoa chéo (crossed belt) khiến cho bánh xe 4 chuyển động ngược chiều so với bánh xe 3 => Đảo ngược chiều chuyển động.

Cho danh sách các dạng của curoa nối các bánh xe với nhau. Biết rằng bánh xe 1 được động cơ quay theo chiều kim đồng hồ. Hãy xác định chiều quay của bánh xe N. Mỗi dây curoa được mô tả bởi 3 số nguyên:

* S_i -- bánh xe tác động (nguồn)
* D_i -- bánh xe bị tác động (đích)
* C_i -- dạng của dây curoa (0=dây thẳng, 1=dây chéo)

Thật không may, FJ lại đưa ra danh sách các dây curoa theo 1 thứ tự ngẫu nhiên.

Dưới đây là 1 ví dụ với N=4, bánh xe 1 quay theo chiều kim đồng hồ.

Dây curoa thẳng được nối tới bánh xe 2 và 3 bởi vậy mà chúng cũng chuyển động cùng chiều kim đồng hồ. Còn lại dây curoa chéo đảo ngược chuyển động vì vậy bánh xe 4 (bánh xe N) chuyển động ngược chiều kim đồng hồ.
DỮ LIỆU

* Dòng 1: Một số nguyên duy nhất: N
* Dòng 2..N: Mỗi dòng mô tả 1 dây curoa với 3 số nguyên: S_i, D_i, và C_i

KẾT QUẢ

* Dòng 1: Một số nguyên duy nhất là chiều quay của bánh xe N. (0=cùng chiều kim đồng hồ, 1=ngược chiều kim đồng hồ)

VÍ DỤ

Dữ liệu
4
2 3 0
3 4 1
1 2 0

Kết quả
1

[MrPaint]

Phát hiện ra rồi
Ngu si ở dòng này:

[highlight=cpp]for(USLI i = 1; i < b; i++)[/highlight]

Phải là

[highlight=cpp]for(USLI i = 1; i <= b; i++)[/highlight]

Buồn man mác

2154543 2009-02-22 05:58:37 Tìm số nguyên tố Đạt yêu cầu 0.68 2.9M C++

[haqduong]

Cái highlighter làm hỏng hết code của em rồi

PS: Bạn nào giải được bài ROTATION sẽ có award (bao nhiêu thì tùy time với dùng ngôn ngữ gì), chỉ người đầu tiên làm được mới có thưởng, những người sau nếu xét thấy làm tốt hơn cũng thưởng.

[MrPaint]

ROTATION cũng đơn giản Quyết tâm code theo OOP

[highlight=cpp]#include <cstdlib>
#include <stdio.h>

#define MAX_WHEEL 1000
#define DEBUG
#undef DEBUG

class Wheel
{
public:
Wheel() {};
void setInfo(int id,Wheel * next,int type) {itsID = id; itsNext = next; itsType = type; itsDirection = 0;};
void roll(int direction) {
itsDirection = direction;
int nextDirection = direction-itsType;
nextDirection = (nextDirection < 0?(-1)*nextDirection:nextDirection);
#ifdef DEBUG
printf("Wheel #%d direction = %d. Belt type = %d ~> Next wheel direction = %d\n",itsID,itsDirection,itsType,nextDirection);
if (itsNext)
{
printf("Wheel #%d's next is #%d\n",itsID,itsNext->getID());
} else {
printf("Wheel #%d has no next!\n",itsID);
}
#endif
if (itsNext) itsNext->roll(nextDirection);
};
int getDirection() {return itsDirection;};
int getID() {return itsID;};
#ifdef DEBUG
void selfIdentify() {
printf("I'm wheel #%d, my type is %d",itsID,itsType);
if (itsNext)
{
printf(", my next is #%d\n",itsNext->getID());
} else {
printf(", I have no next!\n");
}
};
#endif
private:
int itsID;
Wheel * itsNext;
int itsType;
int itsDirection;
};

//Variables
int n,i,tmp_id,tmp_next,tmp_type;
Wheel theWheel[MAX_WHEEL];

void getInput()
{
#ifdef DEBUG
printf("Input N: ");
#endif
scanf("%d",&n);
for (i = 0; i < n-1; i++)
{
#ifdef DEBUG
printf("Input ID,TARGET,TYPE (#%d): ",i+1);
#endif
scanf("%d %d %d",&tmp_id,&tmp_next,&tmp_type);
theWheel[tmp_id-1].setInfo(tmp_id,&theWheel[tmp_next-1],tmp_type);
}
#ifdef DEBUG
theWheel[n-1].setInfo(n,0,0);
for (i = 0; i < n; i++)
theWheel[i].selfIdentify();
#endif
}

void work()
{
theWheel[0].roll(0);
}

int printOutput()
{
#ifdef DEBUG
printf("Final Direction = %d\n",theWheel[n-1].getDirection());
system("pause");
#else
printf("%d",theWheel[n-1].getDirection());
#endif
return 0;
}

int main()
{
getInput();
work();
return printOutput();
}
[/highlight]

[MrPaint]

Chả hiểu sao code của chú thì lỗi còn của anh không sao nhỉ

Post lại rotation không có debug (SPOJ: 0.07 2.6MB C++)

[highlight=cpp]#include <cstdlib>
#include <stdio.h>

#define MAX_WHEEL 1000

class Wheel
{
public:
Wheel() {};
void setInfo(int id,Wheel * next,int type) {itsID = id; itsNext = next; itsType = type; itsDirection = 0;};
void roll(int direction) {
itsDirection = direction;
int nextDirection = direction-itsType;
nextDirection = (nextDirection < 0?(-1)*nextDirection:nextDirection);
if (itsNext) itsNext->roll(nextDirection);
};
int getDirection() {return itsDirection;};
int getID() {return itsID;};
private:
int itsID;
Wheel * itsNext;
int itsType;
int itsDirection;
};

//Variables
int n,i,tmp_id,tmp_next,tmp_type;
Wheel theWheel[MAX_WHEEL];

void getInput()
{
#ifdef DEBUG
printf("Input N: ");
#endif
scanf("%d",&n);
for (i = 0; i < n-1; i++)
{
scanf("%d %d %d",&tmp_id,&tmp_next,&tmp_type);
theWheel[tmp_id-1].setInfo(tmp_id,&theWheel[tmp_next-1],tmp_type);
}
}

void work()
{
theWheel[0].roll(0);
}

int printOutput()
{
printf("%d",theWheel[n-1].getDirection());
return 0;
}

int main()
{
getInput();
work();
return printOutput();
}
[/highlight]

PS: Đã fix lỗi highlighter

[haqduong]

Vâng, đã có 1 người AC ROTATION, các bạn cho anh mrpaint 1 tràng pháo tay

Còn đây là solution của tớ:

[highlight=cpp]#include<cstdio>

int readAndSolve() {
int n,re,s,c,d;
scanf("%d",&n);
re = 0;
for (int i = 2; i<=n; i++) {
scanf("%d%d%d",&s,&c,&d);
if (d==1)
re++;
}
return re;
}

void writeData(int count) {
printf("%i",count);
}

int main() {
int count = readAndSolve();
writeData(count % 2);
}
[/highlight]

[highlight=pascal]Var n,count,i,c:longint;

BEGIN
readln(n);
count:=0;
for i:=1 to n-1 do
begin
readln(c,c,c);
count:=count xor c;
end;
write(count);
END.
[/highlight]

Time:

2119807 2009-02-10 15:35:43 Quay bánh xe 100 0.00 552k PAS fpc
2119571 2009-02-10 14:02:36 Quay bánh xe 100 0.07 2.5M C++

Bài tiếp này:

2782. Đường đi có tổng lớn nhất
Mã bài: QBMAX

Cho một bảng A kích thước m x n (1 <= m, n <= 100), trên đó ghi các số nguyên aij (|aij| <= 100). Một người xuất phát tại ô nào đó của cột 1, cần sang cột n (tại ô nào cũng được).

Quy tắc đi: Từ ô (i, j) chỉ được quyền sang một trong 3 ô (i, j + 1); (i - 1, j + 1); (i + 1, j + 1)
Input

Dòng 1: Ghi hai số m, n là số hàng và số cột của bảng.

M dòng tiếp theo, dòng thứ i ghi đủ n số trên hàng i của bảng theo đúng thứ tự từ trái qua phải
Output

Gồm 1 dòng duy nhất ghi tổng lớn nhất tìm được
Example

Input:
5 7
9 -2 6 2 1 3 4
0 -1 6 7 1 3 3
8 -2 8 2 5 3 2
1 -1 6 2 1 6 1
7 -2 6 2 1 3 7

Output:
41

Bài này gần giống đề vòng 1 Hà Nội năm nay (hay có thể nói là giống hệt)

[MrPaint]

QBMAX mình dính wrong answer mới ghét chứ Bài này cơ bản quy hoạch động + hình như là ví dụ để dạy quy hoạch động thì phải. Mà còn đơn giản hơn vì không bắt tìm đường. Chậc. Sao lại wrong answer được nhờ

Chú haqduong ngó hộ cái code đê

[highlight=cpp]#include <cstdlib>
#include <stdio.h>

#define MAX 100

int m,n;
int a[MAX][MAX];
long int q[MAX][MAX]; //q[i][j] store highest value to lead to a[i][j]
const int VERYLOW = -255;

void getInput()
{
#ifdef DEBUG
printf("Nhap M & N: ");
#endif
scanf("%d %d",&m,&n);
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
{
#ifdef DEBUG
printf("Nhap a[%d][%d]: ",i,j);
#endif
scanf("%d",&a[i][j]);
}
}

long int max(int a,int b,int c)
{
if (a > b && a > c) return a;
if (b > c) return b;
return c;
}

long int qCalc(int row,int column)
{
if (row < 0 || row >= m) return VERYLOW; //return 0 value for invalid row request

if (q[row][column] != 0) return q[row][column];

if (column == 0)
{
//no where to trace back, so... just return the value at a[row][column]
q[row][column] = a[row][column];
return q[row][column];
}

//get the highest value from 3-posible-cell that can lead to this cell
long int highest = max( qCalc(row,column - 1) , qCalc(row-1,column-1) , qCalc(row+1,column-1) );

//the cost to go to this cell = the highest cost (above) plus this cell value
q[row][column] = highest + a[row][column];
return q[row][column];
}

void work()
{
int i,j;

for (i = 0; i < m; i++)
{
q[i][n-1] = qCalc(i,n-1);
}
}

int printOutput()
{
int i,highest;
for (i = 0; i < m; i++)
if (q[i][n-1] > highest)
highest = q[i][n-1];
#ifdef DEBUG
printf("Highest = ");
printf("q array\n");
for (i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
printf("%3ld",q[i][j]);
}
printf("\n");
}
#endif
printf("%ld",highest);
return 0;
}



int main()
{
getInput();
work();
int result = printOutput();
#ifdef DEBUG
printf("\n");
system("pause");
#endif
return result;
}[/highlight]

[haqduong]

Originally Posted by MrPaint

[highlight=cpp]#define MAX 100
[/highlight]

Anh thử để cái này là MAX 101 đi, mà dùng const chứ dùng define làm gì ạ?

PS: anh cài đệ quy làm gì
hay anh attach cái file vào đi, em debug cho tiện.

[haqduong]

Originally Posted by MrPaint

[highlight=cpp]#include <cstdlib>
#include <stdio.h>

#define MAX 100

int m,n;
int a[MAX][MAX];
long int q[MAX][MAX]; //q[i][j] store highest value to lead to a[i][j]
const int VERYLOW = -255;

void getInput()
{
#ifdef DEBUG
printf("Nhap M & N: ");
#endif
scanf("%d %d",&m,&n);
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
{
#ifdef DEBUG
printf("Nhap a[%d][%d]: ",i,j);
#endif
scanf("%d",&a[i][j]);
}
}

long int max(int a,int b,int c)
{
if (a > b && a > c) return a;
if (b > c) return b;
return c;
}

long int qCalc(int row,int column)
{
if (row < 0 || row >= m) return VERYLOW; //return 0 value for invalid row request

if (q[row][column] != 0) return q[row][column];

if (column == 0)
{
//no where to trace back, so... just return the value at a[row][column]
q[row][column] = a[row][column];
return q[row][column];
}

//get the highest value from 3-posible-cell that can lead to this cell
long int highest = max( qCalc(row,column - 1) , qCalc(row-1,column-1) , qCalc(row+1,column-1) );

//the cost to go to this cell = the highest cost (above) plus this cell value
q[row][column] = highest + a[row][column];
return q[row][column];
}

void work()
{
int i,j;

for (i = 0; i < m; i++)
{
q[i][n-1] = qCalc(i,n-1);
}
}

int printOutput()
{
int i,highest;
for (i = 0; i < m; i++)
if (q[i][n-1] > highest)
highest = q[i][n-1];
#ifdef DEBUG
printf("Highest = ");
printf("q arrayn");
for (i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
printf("%3ld",q[i][j]);
}
printf("n");
}
#endif
printf("%ld",highest);
return 0;
}



int main()
{
getInput();
work();
int result = printOutput();
#ifdef DEBUG
printf("n");
system("pause");
#endif
return result;
}[/highlight]

Có vài cái sai:
- const int VERYLOW = -255; -> Đặt thành INT_MIN (include climits)
- if (q[row][column] != 0) return q[row][column]; -> điều kiện sai.

Tạm thời thế

[MrPaint]

Cái VERYLOW có thể dùng -255 được vì đề bài có |aij| < 100 mà chú
Còn cái điều kiện chỉ để cải thiện tốc độ thôi mà (bỏ đi vẫn chạy nhưng chậm vì có những q nó sẽ tính đi tính lại, còn kiểm tra != 0 thì sẽ giảm một cách đáng kể việc tính toán)

[haqduong]

Originally Posted by MrPaint

Cái VERYLOW có thể dùng -255 được vì đề bài có |aij| < 100 mà chú
Còn cái điều kiện chỉ để cải thiện tốc độ thôi mà (bỏ đi vẫn chạy nhưng chậm vì có những q nó sẽ tính đi tính lại, còn kiểm tra != 0 thì sẽ giảm một cách đáng kể việc tính toán)

Kích thước bảng nó 100x100 -> 100*(-100) = -10000 << -255;

Thế nhỡ cái ô đó nó tính ra là 0 thì vẫn phải tính lại còn gì.

[MrPaint]

Originally Posted by haqduong

Kích thước bảng nó 100x100 -> 100*(-100) = -10000 << -255;

Thế nhỡ cái ô đó nó tính ra là 0 thì vẫn phải tính lại còn gì.

2158384 2009-02-23 15:17:35 Đường đi có tổng lớn nhất Đạt yêu cầu 0.08 2.6M C++

Damn it

[highlight=cpp]#include <cstdlib>
#include <stdio.h>

#define MAX 100

int m,n;
int a[MAX][MAX];
long int q[MAX][MAX]; //q[i][j] store highest value to lead to a[i][j]
const long int VERYLOW = -1*MAX*MAX - 1;

void getInput()
{
#ifdef DEBUG
printf("Nhap M & N: ");
#endif
scanf("%d %d",&m,&n);
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
{
#ifdef DEBUG
printf("Nhap a[%d][%d]: ",i,j);
#endif
scanf("%d",&a[i][j]);
}
}

long int max(int a,int b,int c)
{
if (a > b && a > c) return a;
if (b > c) return b;
return c;
}

long int qCalc(int row,int column)
{
if (row < 0 || row >= m) return VERYLOW; //return 0 value for invalid row request

if (q[row][column] != VERYLOW) return q[row][column]; //just return value for calculated cell

if (column == 0)
{
//no where to trace back, so... just return the value at a[row][column]
q[row][column] = a[row][column];
return q[row][column];
}

//get the highest value from 3-posible-cell that can lead to this cell
long int highest = max( qCalc(row,column - 1) , qCalc(row-1,column-1) , qCalc(row+1,column-1) );

//the cost to go to this cell = the highest cost (above) plus this cell value
q[row][column] = highest + a[row][column];
return q[row][column];
}

void work()
{
int i,j;

for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
q[i][j] = VERYLOW;
for (i = 0; i < m; i++)
{
q[i][n-1] = qCalc(i,n-1);
}
}

int printOutput()
{
int i,highest;
for (i = 0; i < m; i++)
if (q[i][n-1] > highest)
highest = q[i][n-1];
#ifdef DEBUG
printf("Highest = ");
printf("q array\n");
for (i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
printf("%3ld",q[i][j]);
}
printf("\n");
}
#endif
printf("%ld",highest);
return 0;
}


int main()
{
getInput();
work();
int result = printOutput();
#ifdef DEBUG
printf("\n");
system("pause");
#endif
return result;
}[/highlight]

[haqduong]

Tiếp này:

Đề bài: LIQ

1779. Dãy con tăng dài nhất ( bản dễ )
Mã bài: LIQ

Cho một dãy số nguyên gồm N phần tử A[1], A[2], ... A[N].
Biết rằng dãy con tăng đơn điệu là 1 dãy A[i1],... A[ik] thỏa mãn
i1 < i2 < ... < ik và A[i1] < A[i2] < .. < A[ik]. Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử?

Input

* Dòng 1 gồm 1 số nguyên là số N (1 ≤ N ≤ 1000).
* Dòng thứ 2 ghi N số nguyên A[1], A[2], .. A[N] (1 ≤ A[i] ≤ 10000).

Output

Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.
Ví dụ

Input:
6
1 2 5 4 6 2

Output:
4

Giải thích test ví dụ: Dãy con dài nhất là dãy A[1] = 1 < A[2] = 2 < A[4] = 4 < A[5] = 6, độ dài dãy này là 4.

Gợi ý: Sử dụng phương pháp Quy Hoạch Động. F[i]: Độ dài dãy con đơn điệu tăng dài nhất mà phần tử cuối cùng là số A[i] này.

Lưu ý: Không down test và solution.

Bài 2:
Đề bài: LIS

1781. Dãy con tăng dài nhất (bản khó)
Mã bài: LIS

(Giống bài LIQ) Cho một dãy gồm N số nguyên (1 ≤ N ≤ 30000). Hãy tìm dãy con tăng dài nhất trong dãy đó. In ra số lượng phần tử của dãy con. Các số trong phạm vi longint.
Input

* Dòng đầu tiên gồm số nguyên N.
* Dòng thứ hai gồm N số mô tả dãy.

Output

Gồm một số nguyên duy nhất là đáp số của bài toán
Example

Input:
5
2 1 4 3 5

Output:
3

Giải được LIQ: 10KL$, cả 2: 30KL$

PS: Lưu ý: nếu copy code thì để vào hide.

[MrPaint]

Cần làm rõ

Cho các số:

19 3 14 9 7 20 7 13 15 23 25 15 14 22 3 24 3 11 5 11

Chuỗi con tăng dài nhất là gì? Có phải là chuỗi này không?

3 5 11 14 22 24

(Ngoài ra còn 1 chuỗi nữa là "3 7 13 15 23 25" cũng có độ dài = 6)

Thế mà không hiểu sao bộ test (bài LIQ) lại như thế này nhỉ?

Originally Posted by LIQ.IN3

20
19 3 14 9 7 20 7 13 15 23 25 15 14 22 3 24 3 11 5 11

Originally Posted by LIQ.AN3

8

Tại sao lại thế?

PS: Dùng quy hoạch động chấm bài LIQ thì AC. Dùng cách O(nlogn) chấm LIS thì TLE, bê sang LIQ thì WA. Dùng bộ test thì thấy thế. Vậy là sao nhờ

Code LIQ (Quy hoạch động)

[hide]
[highlight=cpp]#include <cstdlib>
#include <stdio.h>

#define MAXN 1000

typedef int atype;
typedef int ntype;
ntype n;
atype a[MAXN];
ntype q[MAXN];

void getInput()
{
#ifdef DEBUG
printf("Nhap N: ");
#endif
scanf("%d",&n);
for (ntype i = 0; i < n; i++)
{
#ifdef DEBUG
printf("Nhap a[%d]: ",i);
#endif
scanf("%d",&a[i]);
}
}

ntype qCalc(ntype i)
{
if (q[i] > -1) return q[i];

ntype longest_before = 0;
ntype tmp;
for (ntype j = 0; j < i; j++)
{
if (a[j] < a[i])
{
tmp = qCalc(j);
if (tmp > longest_before) longest_before = tmp;
}
}

q[i] = longest_before + 1;
return q[i];
}

void work()
{
ntype i;
for (i = 0; i < n; i++)
{
q[i] = -1;
}
for (i = 0; i < n; i++)
{
qCalc(n-i-1);
}
}

int printOutput()
{
ntype longest = 0;
for (ntype i = 0; i < n; i++)
{
if (q[i] > longest) longest = q[i];
}
#ifdef DEBUG
printf("a array:\n");
for (ntype i = 0; i < n; i++)
{
printf("%3ld",a[i]);
}
printf("\n");
printf("q array:\n");
for (ntype i = 0; i < n; i++)
{
printf("%3ld",q[i]);
}
printf("\n");
printf("Longest = ");
#endif
printf("%ld",longest);
return 0;
}


int main()
{
getInput();
work();
int result = printOutput();
#ifdef DEBUG
printf("\n");
system("pause");
#endif
return result;
}[/highlight][/hide]

[MrPaint]

Vừa lôi source quy hoạch động (ở trên) ra test lại với LIQ.IN3, kết quả = 6 Mà source này AC rồi nhá ~> bộ test bị sai àh?

PS: Bài trên dài quá, lười edit

PS: AC cả 2 bài rồi

[haqduong]

3 bài thi năm ngoái này:

1. VOI08 Trò chơi với dãy số
Đề bài:

2401. VOI08 Trò chơi với dãy số
Mã bài: NKSGAME

Hai bạn học sinh trong lúc nhàn rỗi nghĩ ra trò chơi sau đây. Mỗi bạn chọn trước một dãy số gồm n số nguyên. Giả sử dãy số mà bạn thứ nhất chọn là:

b1, b2, ..., bn

còn dãy số mà bạn thứ hai chọn là

c1, c2, ..., cn

Mỗi lượt chơi mỗi bạn đưa ra một số hạng trong dãy số của mình. Nếu bạn thứ nhất đưa ra số hạng bi (1 ≤ i ≤ n), còn bạn thứ hai đưa ra số hạng cj (1 ≤ j ≤ n) thì giá của lượt chơi đó sẽ là |bi+cj|.

Ví dụ: Giả sử dãy số bạn thứ nhất chọn là 1, -2; còn dãy số mà bạn thứ hai chọn là 2, 3. Khi đó các khả năng có thể của một lượt chơi là (1, 2), (1, 3), (-2, 2), (-2, 3). Như vậy, giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể là 0 tương ứng với giá của lượt chơi (-2, 2).
Yêu cầu

Hãy xác định giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể.
Dữ liệu

* Dòng đầu tiên chứa số nguyên dương n (n ≤ 105)
* Dòng thứ hai chứa dãy số nguyên b1, b2, ..., bn (|bi| ≤ 109, i=1, 2, ..., n)
* Dòng thứ hai chứa dãy số nguyên c1, c2, ..., cn (|ci| ≤ 109, i=1, 2, ..., n)

Hai số liên tiếp trên một dòng được ghi cách nhau bởi dấu cách.
Kết quả

Ghi ra giá nhỏ nhất tìm được.
Ràng buộc

* 60% số tests ứng với 60% số điểm của bài có 1 ≤ n ≤ 1000.

Ví dụ

Dữ liệu:
2
1 -2
2 3

Kết qủa
0

Bài này 10KL$

2. VOI08 Lò cò

2402. VOI08 Lò cò
Mã bài: NKJUMP

Nhảy lò cò là trò chơi dân gian của Việt Nam. Người trên hành tinh X cũng rất thích trò chơi này và họ đã cải biên trò chơi này như sau: Trên mặt phẳng vẽ n vòng tròn được đánh số từ 1 đến n. Tại vòng tròn i người ta điền số nguyên dương ai. Hai số trên hai vòng tròn tùy ý không nhất thiết phải khác nhau. Tiếp đến người ta vẽ các mũi tên, mỗi mũi tên hướng từ một vòng tròn đến một vòng tròn khác. Quy tắc vẽ mũi tên là: Nếu có ba số ai, aj, ak thỏa mãn ak = ai + aj thì vẽ mũi tên hướng từ vòng tròn i đến vòng tròn k và mũi tên hướng từ vòng tròn j đến vòng tròn k. Người chơi chỉ được di chuyển từ một vòng tròn đến một vòng tròn khác nếu có mũi tên xuất phát từ một trong số các vòng tròn, di chyển theo cách mũi tên đã vẽ để đi đến các vòng tròn khác. Người thắng cuộc sẽ là người tìm được cách di chuyển qua nhiều vòng tròn nhất.

Ví dụ: Với 5 vòng tròn và các số trong vòng tròn là 1, 2, 8, 3, 5, trò chơi được trình bày trong hình dưới đây:

Khi đó có thể di chuyển được nhiều nhất qua 4 vòng tròn (tương ứng với đường di chuyển được tô đậm trên hình vẽ).
Yêu cầu

Hãy xác định xem trong trò chơi mô tả ở trên, nhiều nhất có thể di chuyển được qua bao nhiêu vòng tròn.
Dữ liệu

* Dòng đầu chứa số nguyên n (3 ≤ n ≤ 1000);
* Dòng thứ hai chứa dãy số nguyên dương a1, a2, ..., an (ai ≤ 109, i=1, 2,..., n).

Hai số liên tiếp trên một dòng được ghi cách nhau bởi dấu cách.
Kết quả

Ghi ra số lượng vòng tròn trên đường di chuyển tìm được.
Ràng buộc

* 60% số tests ứng với 60% số điểm của bài có 3 ≤ n ≤ 100.

Ví dụ

Dữ liệu:
5
1 2 8 3 5

Kết qủa
4

Bài này 12KL$

3. VOI08 Quà tết

2403. VOI08 Quà tết
Mã bài: NKGIFTS

Chuẩn bị đón năm mới. Công ty bánh kẹo Hương Dứa đã làm một tấm sôcôla cực lớn với mục đích ghi tên mình vào sách kỷ lục Ghi-nét đồng thời quảng bá thương hiệu trước công chúng. Tấm sôcôla có hình vuông kích thước 2kx2k, tạo thành lưới ô vuông 2k hàng và 2k cột. Các hàng được đánh số từ 0 đến 2k-1 từ trên xuống dưới, các cột được đánh số từ 0 đến 2k-1 từ trái sang phải. Ô nằm ở hàng i và cột j được gọi là ô (i, j). Sau buổi trưng bày giới thiệu sản phẩm, tấm sôcôla được cắt nhỏ, chia cho mọi người, mỗi người được một ô của chiếc bánh kỷ lục. Bộ phận tiếp thị đã ấn vào hai ô khác nhau (p, q) và (u, v) mỗi ô một đồng xu. Vị khách nào may mắn nhận được ô sôcôla có đồng xu sẽ được tặng rất nhiều sản phẩm độc đáo của công ty.

Vì chiếc bánh rất lớn nên công ty đã thiết kế một máy cắt bánh. Máy thực hiện dãy các thao tác cắt, bắt đầu từ chồng bánh chỉ gồm 1 tấm sôcôla ban đầu, mỗi thao tác gồm hai bước sau:

* Bước 1: Cắt ngang song song với cạnh chồng bánh chia chồng sôcôla thành hai phần bằng nhau, úp chồng bánh bên dưới lên chồng bánh bên trên sao cho mép dưới đè lên mép trên.
* Bước 2: Cắt dọc song song với cạnh chồng bánh chia chồng sôcôla thành hai phần bằng nhau, úp chồng bánh bên trái lên chồng bánh bên phải sao cho mép trái đè lên mép phải.

Như vậy sau mỗi lần thực hiện thao tác cắt, chiều dài và chiều rộng của các tấm sôcôla giảm đi một nửa. Sau k lần thực hiện thao tác cắt, các ô của tấm sôcôla sẽ được xếp thành một cột. Khách nhận bánh xếp hàng một và được đánh số từ 1 trở đi, người thứ m sẽ nhận được miếng sôcôla thứ m từ trên xuống dưới. (1 ≤ m ≤ 2k x 2k).

Ví dụ, với k=1 và đồng xu được ấn vào các ô (0,0), (1,1), việc thực hiện các thao tác cắt sẽ được trình bày trên hình vẽ minh họa ở trên. Trong ví dụ này, vị khách thứ nhất và thứ ba sẽ là những người nhận được tặng phẩm của công ty.
Yêu cầu

Cho biết các số nguyên k, p, q, u, v. Hãy xác định số thứ tự của hai vị khách may mắn nhận được quà.
Dữ liệu

Gồm một dòng chứa 5 số nguyên k, p, q, u, v, các số cách nhau bởi dấu cách.
Kết quả

Một dòng chứa hai số nguyên là số thứ tự các vị khách may mắn. Hai số phải cách nhau đúng một dấu cách.
Ràng buộc

* 1 ≤ k ≤ 40, 0 ≤ p, q, u, v ≤ 2k - 1.
* 60% số tests ứng với 60% số điểm của bài có 1 ≤ k ≤ 5.

Ví dụ

Dữ liệu:
1 0 0 1 1

Kết qủa
1 3

Bài này 15KL$