SPOJ.com - Problem NKPALIN

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

NKPALIN - Chuỗi đối xứng

Một chuỗi được gọi là đối xứng (palindrome) nếu như khi đọc chuỗi này từ phải sang trái cũng thu được chuỗi ban đầu.

Yêu cầu: tìm một chuỗi con đối xứng dài nhất của một chuỗi s cho trước. Chuỗi con là chuỗi thu được khi xóa đi một số ký tự từ chuỗi ban đầu.

Dữ liệu vào

Gồm một dòng duy nhất chứa chuỗi s, chỉ gồm những chữ cái in thường.

Kết qủa

Gồm một dòng duy nhất là một xâu con đối xứng dài nhất của xâu s. Nếu có nhiều kết quả, chỉ cần in ra một kết quả bất kỳ.

Giới hạn

Chuỗi s có độ dài không vượt quá 2000.

Ví dụ

Dữ liệu mẫu
lmevxeyzl

Kết qủa
level

Submit solution!

Được gửi lên bởi:	Jimmy
Ngày:	2007-11-30
Thời gian chạy:	1s
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:	VNOI Marathon '08 - Practice Round Problem Setter: Ngô Minh Đức

hide comments

2022-09-29 05:09:24
https://oj.vnoi.info/problem/nkpalin
bài này đã có trên VNOJ

2021-11-12 03:53:27
package subset;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {

static int data[]=new int [15];
static int visit[]=new int [15];
static int N;
static int K;
static int a[]=new int [15];

public static void solve(int x) {
if(x>K) {
int S=data[a[1]];
for(int i=2; i<=K; i++) {
S=S+data[a[i]];
}
if(S==0) {
for(int i=1;i<=K;i++) {
System.out.print(data[a[i]]+" ");
}
System.out.println();
}
return ;
}

for(int i=a[x-1]+1;i<=N;i++) {
if(visit[i]==0) {
a[x]=i;
visit[i]=1;
solve(x+1);
a[x]=0;
visit[i]=0;
}
}
}
public static void main(String[] args) throws FileNotFoundException {
Scanner sc =new Scanner(new FileInputStream("D:\\trung.txt"));
//Scanner sc =new Scanner(System.in);
// int n;
N=sc.nextInt();
// K=3;
for(int i=1;i<=N;i++) {
data[i]=sc.nextInt();

}

for( K=1;K<=N;K++) {
solve(1);
}

}

}

2021-11-12 03:30:05
10
-1 2 -9 6 7 -6 1 5 4 -2

2021-11-12 03:29:54
package subset;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {

static int data[]=new int [15];
static int visit[]=new int [15];
static int N;
static int K;
static int a[]=new int [15];

public static void solve(int x) {
if(x>K) {
int S=a[1];
for(int i=2; i<=K; i++) {
S+=data[a[i]];
}
if(S==0) {
for(int i=1;i<=K;i++) {
System.out.println(data[a[i]]);
}
}
return ;
}

for(int i=a[x-1]+1;i<=N;i++) {
if(visit[i]==0) {
a[x]=i;
visit[i]=1;
solve(x+1);
a[x]=0;
visit[i]=0;
}
}
}
public static void main(String[] args) throws FileNotFoundException {
Scanner sc =new Scanner(new FileInputStream("D:\\trung.txt"));
//Scanner sc =new Scanner(System.in);
int n;
N=sc.nextInt();
// K=3;
for(int i=1;i<=N;i++) {
a[i]=sc.nextInt();

}

for(int K=1;K<=N;K++) {
solve(1);
}

}

}

2021-11-11 02:04:13
package fly;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
static boolean check;

static int ketqua;
static int n;
static int map[][]=new int [13][5];
public static void backtrack(int vang, int hang, int cot, boolean nobom) {
if(vang<0) {
return;
}
if(hang==0) {
check=true;
if(ketqua<vang)
{ketqua=vang;
}
return;
}

for(int i=1;i<=4;i++) {
if(i==1) {

if(cot>0) {
int tempvang=0;
if(map[hang-1][cot-1]==1) {
tempvang=1;
}
else if (map[hang-1][cot-1]==2) {
tempvang=-1;
}
backtrack(vang+tempvang, hang-1, cot-1, nobom);
}
}

else if (i==2) {

int tempvang=0;
if(map[hang-1][cot]==1) {
tempvang=1;
}
else if (map[hang-1][cot]==2) {
tempvang=-1;
}
backtrack(vang+tempvang, hang-1, cot, nobom);
}

else if(i==3) {
if(cot<4) {
int tempvang=0;
if(map[hang-1][cot+1]==1) {
tempvang=1;
}
else if (map[hang-1][cot+1]==2) {
tempvang=-1;
}
backtrack(vang+tempvang, hang-1, cot+1, nobom);

}
}
else {
if(nobom==false) {
int temp[][]=new int [5][5];
for(int p=0;p<5;p++) {
for(int q=0;q<5;q++) {
if(hang-p>0) {
temp[p][q]=map[hang-p-1][q];

if(map[hang-p-1][q]==2)
map[hang-p-1][q]=0;
}
}
}
nobom=true;
backtrack(vang, hang, cot, nobom);
nobom=false;
for(int p=0;p<5;p++) {
for(int q=0;q<5;q++) {
if(hang-p>0) {
map[hang-p-1][q]=temp[p][q];}
}
}

}

}
}

}

public static void main(String[] args) throws FileNotFoundException {
Scanner sc =new Scanner(new FileInputStream("D:\\trung.txt"));
// Scanner sc =new Scanner(System.in);

int T;
T=sc.nextInt();
for(int test=1;test<=T;test++) {
n=sc.nextInt();
for(int i=0;i<n;i++) {
for(int j=0;j<5;j++) {
map[i][j]=sc.nextInt();
}
}

ketqua=0;
boolean nobom=false;
check =false;
backtrack(0, n, 2, nobom);
System.out.println("Case"+" #"+test);
if(check) {
System.out.println(ketqua);
}
else
{
System.out.println(-1);
}

}
}

}

2021-11-10 11:30:36
2

5

1 1 0 0 0

1 2 2 2 1

1 1 2 2 1

2 2 2 1 2

2 2 0 2 0

8

2 0 2 0 2

1 0 1 2 0

0 0 0 2 1

2 0 2 0 1

1 2 1 2 0

0 2 2 0 2

2 1 1 2 2

0 2 1 2 0

Output

Case #1

3

Case #2

4

2021-11-10 11:30:23
package fly;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
static boolean check;

static int ketqua;
static int n;
static int map[][]=new int [13][5];
public static void backtrack(int vang, int hang, int cot, boolean nobom) {
if(vang<0) {
return;
}
if(hang==0) {
check=true;
if(ketqua<vang)
{ketqua=vang;
}
return;
}

for(int i=1;i<=4;i++) {
if(i==1) {

if(cot>0) {
int tempvang=0;
if(map[hang-1][cot-1]==1) {
tempvang=1;
}
else if (map[hang-1][cot-1]==2) {
tempvang=-1;
}
backtrack(vang+tempvang, hang-1, cot-1, nobom);
}
}

else if (i==2) {

int tempvang=0;
if(map[hang-1][cot]==1) {
tempvang=1;
}
else if (map[hang-1][cot]==2) {
tempvang=-1;
}
backtrack(vang+tempvang, hang-1, cot, nobom);
}

else if(i==3) {
if(cot<4) {
int tempvang=0;
if(map[hang-1][cot+1]==1) {
tempvang=1;
}
else if (map[hang-1][cot+1]==2) {
tempvang=-1;
}
backtrack(vang+tempvang, hang-1, cot+1, nobom);

}
}
else {
if(nobom==false) {
int temp[][]=new int [5][5];
for(int p=0;p<5;p++) {
for(int q=0;q<5;q++) {
temp[p][q]=map[hang-p-1][q];
if(map[hang-p-1][q]==2) {
map[hang-p-1][q]=0;
}
}
}
nobom=true;
backtrack(vang, hang, cot, nobom);
nobom=false;
for(int p=0;p<5;p++) {
for(int q=0;q<5;q++) {
map[hang-p-1][q]=temp[p][q];
}
}

}

}
}

}

public static void main(String[] args) throws FileNotFoundException {
Scanner sc =new Scanner(new FileInputStream("D:\\trung.txt"));
// Scanner sc =new Scanner(System.in);

int T;
T=sc.nextInt();
for(int test=1;test<=T;test++) {
n=sc.nextInt();
for(int i=0;i<n;i++) {
for(int j=0;j<5;j++) {
map[i][j]=sc.nextInt();
}
}

ketqua=0;
boolean nobom=false;
check =false;
backtrack(0, n, 2, nobom);
System.out.println("Case"+" #"+test);
if(check) {
System.out.println(ketqua);
}
else
{
System.out.println(-1);
}

}
}

}

2021-11-10 11:25:34
package fly;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
static boolean check;

static int ketqua;
static int n;
static int map[][]=new int [13][5];
public static void backtrack(int vang, int hang, int cot, boolean nobom) {
if(vang<0) {
return;
}
if(hang==0) {
check=true;
if(ketqua<vang)
{ketqua=vang;
}
return;
}

for(int i=1;i<=4;i++) {
if(i==1) {

if(cot>0) {
int tempvang=0;
if(map[hang-1][cot-1]==1) {
tempvang=1;
}
else if (map[hang-1][cot-1]==2) {
tempvang=-1;
}
backtrack(vang+tempvang, hang-1, cot-1, nobom);
}
}

else if (i==2) {

int tempvang=0;
if(map[hang-1][cot]==1) {
tempvang=1;
}
else if (map[hang-1][cot]==2) {
tempvang=-1;
}
backtrack(vang+tempvang, hang-1, cot, nobom);
}

else if(i==3) {
if(cot<4) {
int tempvang=0;
if(map[hang-1][cot+1]==1) {
tempvang=1;
}
else if (map[hang-1][cot+1]==2) {
tempvang=-1;
}
backtrack(vang+tempvang, hang-1, cot+1, nobom);

}
}
else {
if(nobom==false) {
int temp[][]=new int [5][5];
for(int p=0;p<5;p++) {
for(int q=0;q<5;q++) {
temp[p][q]=map[hang-p-1][q];
if(map[hang-p-1][q]==2) {
map[hang-p-1][q]=0;
}
}
}
nobom=true;
backtrack(vang, hang, cot, nobom);
nobom=false;
for(int p=0;p<5;p++) {
for(int q=0;q<5;q++) {
map[hang-p-1][q]=temp[p][q];
}
}

}

}
}

}

public static void main(String[] args) throws FileNotFoundException {
Scanner sc =new Scanner(new FileInputStream("D:\\trung.txt"));
// Scanner sc =new Scanner(System.in);

int T;
T=sc.nextInt();
for(int test=1;test<=T;test++) {
n=sc.nextInt();
for(int i=0;i<n;i++) {
for(int j=0;j<5;j++) {
map[i][j]=sc.nextInt();
}
}

ketqua=0;
boolean nobom=false;
check =false;
backtrack(0, n, 2, nobom);
System.out.println("Case"+" #"+test);
if(check) {
System.out.println(ketqua);
}
else
{
System.out.println(-1);
}

}
}

}

2021-11-10 09:30:45
Fishing
There are N spots for fishing in the fishing center.

The center has 3 gates, and a number of customers standing before each gate.

2021-11-09 11:38:46
package Fishing;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
static int vt[]=new int [10000];
public static void xetvt(int cong, int nguoi) {
int dodai=0;
while(nguoi>0) {
int min=99999;
int vitri=0;
for(int i=1;i<=10;i++) {
if(vt[i]!=1) {
if(min>Math.abs(cong-i)) {
min=Math.abs(cong-i);
vitri=i;
}
}
}
// vt=
nguoi=nguoi-1;

}
}

public static void main(String[] args) throws FileNotFoundException {
Scanner sc =new Scanner(new FileInputStream("D:\\trung.txt"));
// Scanner sc =new Scanner(System.in);
int T;
T=sc.nextInt();
for(int test=1;test<=1;test++) {
int N;
int g1;
int n1;
int g2;
int n2;
int g3;
int n3;
N=sc.nextInt();
g1=sc.nextInt();
n1=sc.nextInt();
g2=sc.nextInt();
n2=sc.nextInt();
g3=sc.nextInt();
n3=sc.nextInt();

}
}

}

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

NKPALIN - Chuỗi đối xứng

Dữ liệu vào

Kết qủa

Giới hạn

Ví dụ