SPOJ.com - Problem NKTEST

Problem hidden

|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NKTEST - Kiểm tra chương trình

Test tuy không phải là phương pháp để chứng minh tính đúng đắn của chương trình, nhưng vẫn được sử dụng rộng rãi để phát hiện lỗi sai và tăng độ tin cậy. Có nhiều phương pháp hiệu chỉnh chương trình, nhưng nội dung chủ yếu vẫn dựa trên cơ sở chọn các bộ tests để đi vào các nhánh khác nhau của chương trình.

Cho mô tả chương trình dưới dạng các dòng lệnh. Các lệnh tuyến tính được ký hiệu là S, lệnh rẽ nhánh không đầy đủ được xác định bởi 2 câu lệnh IF và END_IF, lệnh rẽ nhánh đầy đủ được xác định bởi 3 câu lệnh IF, ELSE, và END_IF. Điều kiện sau IF được bỏ qua trong mô tả. Chương trình kết thúc bằng lệnh ENDPROGRAM.

Yêu cầu: xác định số lượng tests cần thiết để kiểm tra tất cả các nhánh của chương trình.

Dữ liệu

Gồm nhiều dòng, mô tả một chương trình theo định dạng đã nêu.

Kết qủa

Gồm 1 dòng duy nhất, chứa số lượng tests cần thiết để kiểm tra tất cả các nhánh của chương trình.

Giới hạn

Kết quả không vượt quá 2³¹-1

Ví dụ

Dữ liệu:
S
IF
S
S
ELSE
IF
IF
S
ELSE
S
END_IF
S
ELSE
S
END_IF
END_IF
S
ENDPROGRAM

Kết qủa
4

Dữ liệu:
S
IF
END_IF
ENDPROGRAM

Kết qủa
2

Dữ liệu:
S
S
ENDPROGRAM

Kết qủa
1

Submit solution!

Được gửi lên bởi:	Jimmy
Ngày:	2007-12-01
Thời gian chạy:	0.100s
Giới hạn mã nguồn:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Ngôn ngữ cho phép:	Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:	UVA

hide comments

2021-11-15 03:02:24
www.spoj.com/problems/BOOKS1
www.spoj.com/problems/AGGRCOW
www.spoj.com/problems/INVCNT
http://www.spoj.com/problems/PT07Y/
http://www.spoj.com/problems/NAKANJ/
www.spoj.com/problems/BENEFACT
http://www.spoj.com/problems/MICEMAZE/
http://www.spoj.com/problems/BUGLIFE/
www.spoj.com/problems/GCPC11J
http://www.spoj.com/problems/ABCPATH/
http://www.spoj.com/problems/ALLIZWEL/
http://www.spoj.com/problems/TRAFFICN/
www.spoj.com/problems/EASUDOKU
http://www.spoj.com/problems/EZSUDOKU/
http://www.spoj.com/problems/MKJUMPS/
Local server
Local server
GSCS server (Vietnamese)
http://www.spoj.com/problems/HERDING/
http://www.spoj.com/problems/ELEVTRBL/
http://www.spoj.com/problems/LABYR1/
http://www.spoj.com/problems/SHOP/
http://www.spoj.com/problems/SERGRID/
http://www.spoj.com/problems/ONEZERO/

2021-11-12 10:28:19
3

3

3 3 3

4

2 2 2 2

7

4 1 0 1 1 0 1

Output

0

2

3

2021-11-12 10:28:01
#include <iostream>

using namespace std;

#define FOR(i,a,b) for(int i=(a); i<=(b); i++)
#define FORD(i,a,b) for(int i=(a); i>=(b); i--)
typedef long long LL;
const int MAXN = 20000;

int N;
LL a[MAXN+1];
LL SUM_LR[MAXN+2];
LL SUM_RL[MAXN+2];
int _maxCount;

void F();
void backtrack(const int& start, const int& end, int count);

int main()
{
freopen("ChiaDoi2_in.txt","r",stdin);
// freopen("ChiaDoi_out.txt","w",stdout);//

int T;
cin >> T;
FOR(i,1,T)
F();

return 0;
}

void F()
{
cin >> N;
FOR(i,1,N)
cin >> a[i];

SUM_LR[0] = 0;
FOR(i,1,N)
SUM_LR[i] = SUM_LR[i-1] + a[i];

SUM_RL[N+1] = 0;
FORD(i,N,1)
SUM_RL[i] = SUM_RL[i+1] + a[i];

if(SUM_LR[N] == 0)
cout << N-1 << endl;
else{

_maxCount = 0;
backtrack(1,N,0);
cout << _maxCount << endl;
}
}

void backtrack(const int& start, const int& end, int count)
{
if(start < end)
{
FOR(i,start,end-1)
{
// Chia doi duoc
LL L = SUM_LR[i] - SUM_LR[start-1];
LL R = SUM_RL[i+1] - SUM_RL[end+1];
if(L == R)
{
count++;
if(count > _maxCount)
_maxCount = count;
//cout << "Tach " << i << " - " << (i+1) << endl;
backtrack(start,i,count);
backtrack(i+1,end,count);
return; // Không có dòng return này sẽ bị TLE
count--; // Khi có return ở trên rồi thì cái này cũng vô ích
}
}
}
}

2021-11-11 02:46:27
2
3
7
2 1 5 1 2 2 2
4
10
10 2 1 5 1 2 2 2 9 11

Sample Output

#1 6
#2 12

2021-11-11 02:46:08
Level 4

Minimal Big Sum
Suppose 'A' is a non empty zero indexed array of 'N' integers and 'K' is another Integer.
Array 'A' needs to be divided into 'K' blocks of consecutive elements.

Size of the block is any integer such that , 0 <= size of block <= N. Every element of the array should belong to some block.

The sum of the block from X to Y equals A[X] + A[X + 1] + ... + A[Y]. The sum of empty block equals 0.

The big sum is defined as the maximal sum of any block.

For example, you are given integers 'K' = 3 and array A such that:
A[0] = 2
A[1] = 1
A[2] = 5
A[3] = 1
A[4] = 2
A[5] = 2
A[6] = 2

The array can be divided, for example, into the following blocks:

[2, 1, 5, 1, 2, 2, 2], [], [] with a big sum of 15;
[2], [1, 5, 1, 2], [2, 2] with a big sum of 9;
[2, 1, 5], [], [1, 2, 2, 2] with a big sum of 8;
[2, 1], [5, 1], [2, 2, 2] with a big sum of 6.

The goal is to minimize the big sum. In the above example, 6 is the minimal big sum.

2021-08-21 03:07:19
nxhieu Hai Phong vo doi

Last edit: 2021-08-21 03:10:50

2021-05-27 18:04:15
Tham khảo: https://vnspoj.github.io/problems/NKTEST

2018-02-01 17:06:54
ad cho bài giải đi k hiểu đề bài

2016-12-15 16:52:25
bài dễ 1 hit

2016-11-27 06:19:51 hồ vãn tuấn
de la the loai gi vay?

Giải bài trực tuyến

NKTEST - Kiểm tra chương trình

Dữ liệu

Kết qủa

Giới hạn

Ví dụ