D2208
unknown
plain_text
20 days ago
12 kB
1
Indexable
Never
////////////////////////////////////
package d2208;
import java.util.Scanner;
public class BanBongBay {
static int t, n;
static int[] bong = new int[n];
static int res = 0;
static boolean[] visit = new boolean[n];
public static int b3() {
int max = 0;
int[] a = new int[2];
int dem = 0;
for (int i = 0; i < n; i++) {
if (visit[i] == false) {
a[dem] = i;
dem++;
}
}
max = Math.max(bong[a[0]]*2, bong[a[1]]*2);
return max;
}
public static void Try(int k, int sum) {
if (k == n - 2) {
if (res < sum + b3()) {
res = sum + b3();
}
return;
}
for (int i = 0; i < n; i++) {
if (visit[i] == false) {
if (i == 0) {
visit[i] = true;
int check = 0;
for (int j = 1; j < n; j++) {
if (visit[j] == false) {
check = j;
break;
}
}
if (check == 0) {
Try(k + 1, sum + bong[i]);
} else {
Try(k + 1, sum + bong[check]);
}
visit[i] = false;
} else if (i == n - 1) {
visit[i] = true;
int check = n - 1;
for (int j = n - 2; j >= 0; j--) {
if (visit[j] == false) {
check = j;
break;
}
}
if (check == n - 1) {
Try(k + 1, sum + bong[i]);
} else {
Try(k + 1, sum + bong[check]);
}
visit[i] = false;
} else {
visit[i] = true;
int left = i;
int right = i;
for (int j = left - 1; j >= 0; j--) {
if (visit[j] == false) {
left = j;
break;
}
}
for (int j = right + 1; j < n; j++) {
if (visit[j] == false) {
right = j;
break;
}
}
if (left == i && right == i) {
Try(k + 1, sum + bong[i]);
}
if (left != i && right != i) {
Try(k + 1, sum + bong[left] * bong[right]);
}
if (left != i && right == i) {
Try(k + 1, sum + bong[left]);
}
if (left == i && right != i) {
Try(k + 1, sum + bong[right]);
}
visit[i] = false;
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
t = sc.nextInt();
for (int tc = 1; tc <= t; tc++) {
n = sc.nextInt();
bong = new int[n];
visit = new boolean[n];
for (int i = 0; i < n; i++) {
bong[i] = sc.nextInt();
}
res = 0;
Try(0, 0);
System.out.println("Case #" + tc);
System.out.println(res);
}
}
}
//////////////////////////////////////
package d2208;
import java.util.Scanner;
public class BieuThucZero {
static int t,n;
static int[] a = new int[n];
static int[] dau = new int[n];
static int res2 = 0;
public static boolean check(){
int res= 0, trangthai = 0;
int tmp = a[0];
for(int i = 0 ; i < n - 1 ; i++){
if(dau[i] == 1){
tmp = tmp*10+a[i+1];
}
if(dau[i] == 2){
if(trangthai == 0){
res = tmp;
tmp = a[i+1];
trangthai = 1;
}
else if(trangthai == 1){
res = res + tmp;
tmp = a[i+1];
trangthai = 1;
}
else if(trangthai == 2){
res = res - tmp;
tmp = a[i+1];
trangthai = 1;
}
}
if(dau[i] == 3){
if(trangthai == 0){
res = tmp;
tmp = a[i+1];
trangthai = 2;
}
else if(trangthai == 1){
res = res + tmp;
tmp = a[i+1];
trangthai = 2;
}
else if(trangthai == 2){
res = res - tmp;
tmp = a[i+1];
trangthai = 2;
}
}
}
if(trangthai == 1){
res = res + tmp;
}
else if(trangthai == 2){
res = res - tmp;
}
else{
res = tmp;
}
if(res == 0){
return true;
}
return false;
}
public static void Try(int k){
if(k == n - 1){
if(check()){
res2++;
}
return;
}
for(int i = 0 ; i < 3 ; i++){
if(i == 0){
dau[k] = 1;
Try(k+1);
dau[k] = 0;
}
else if(i == 1){
dau[k] = 2;
Try(k+1);
dau[k] = 0;
}
else if(i == 2){
dau[k] = 3;
Try(k+1);
dau[k] = 0;
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
t = sc.nextInt();
for(int tc = 1 ;tc <= t ; tc++){
n = sc.nextInt();
a = new int[n];
for(int i = 0 ; i < n ; i++){
a[i] = i +1 ;
}
dau = new int[n-1];
res2 = 0;
Try(0);
System.out.println("#"+tc+" "+res2);
}
}
}
/////////////////////////////////
package d2208;
import java.util.Scanner;
public class HeThongDien {
static int t,n,m,h;
static int oo = 99999999;
static int[][] a = new int[n][n];
static int[] tram = new int[m];
static int[] visitDao = new int[n];
static class Queue {
int front, rear;
int[] data = new int[90001];
public Queue() {
front = rear = 0;
}
public void enQ(int n) {
data[rear++] = n;
}
public int deQ() {
return data[front++];
}
public int qPeek() {
return data[front];
}
public boolean isEmpty() {
if (front == rear) {
return true;
}
return false;
}
}
public static void bfs(int u){
Queue q = new Queue();
q.enQ(u);
while(!q.isEmpty()){
int nx = q.deQ();
for(int i = 0 ; i < n ; i++){
if(a[nx][i] == 1 && visitDao[i] > visitDao[nx]+1){
visitDao[i] = visitDao[nx]+1;
q.enQ(i);
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
t = sc.nextInt();
for(int tc = 1 ; tc <= t ;tc++){
n = sc.nextInt();
m = sc.nextInt();
h = sc.nextInt();
a = new int[n][n];
tram = new int[m];
visitDao = new int[n];
for(int i = 0 ; i < n ; i++){
visitDao[i] = oo;
}
for(int i = 0 ; i < m ; i++){
tram[i] = sc.nextInt();
visitDao[tram[i]] = 0;
}
for(int i = 0 ; i < h ; i++){
int x = sc.nextInt();
int y = sc.nextInt();
a[x][y] = 1;
a[y][x] = 1;
}
for(int i = 0 ; i < m ; i++){
bfs(tram[i]);
}
int res = -1,id = -1;
for(int i = 0 ; i < n ; i++){
if(visitDao[i] > res ){
res = visitDao[i];
id = i;
}
}
System.out.println(id);
}
}
}
/////////////////////////
package d2208;
import java.util.Scanner;
public class LadderGame {
static int t,n,b,m;
static int[][] a = new int[n+1][n+1];
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
for(int tc = 1 ; tc <= 10 ;tc++){
n = sc.nextInt();
b = sc.nextInt();
m = sc.nextInt();
a = new int[n+1][n+1];
int dem = 1;
for(int i = 0 ; i < m ; i++){
int x = sc.nextInt();
int y = sc.nextInt();
int z = sc.nextInt();
int u = sc.nextInt();
for(int j = y ; j <= u ; j++){
a[x][j] = dem;
}
dem++;
}
for(int i = 1 ; i <= n ; i++){
int r = 1 , c = i;
while(r <= n){
if(a[r][c] == 0){
r++;
}
else{
if(c == 1){
if(c+1 <= n && a[r][c+1]==a[r][c] ){
int x = a[r][c];
while(a[r][c] == x && c >= 1 && c <= n){
c++;
}
c--;
r++;
}
}
else if(c == n){
if(c-1 >= 1 && a[r][c-1] == a[r][c]){
int x = a[r][c];
while(a[r][c] == x && c >= 1 && c <= n){
c--;
}
c++;
r++;
}
}
else if(c-1 >= 1 && c+1 <= n && a[r][c-1] == a[r][c] && a[r][c+1]==a[r][c] ){
r++;
}
else if(c-1 >= 1 && c+1 <= n && a[r][c-1] != a[r][c] && a[r][c+1]==a[r][c]){
int x = a[r][c];
while(c >= 1 && c <= n && a[r][c] == x ){
c++;
}
c--;
r++;
}
else if(c-1 >= 1 && c+1 <= n && a[r][c-1] == a[r][c] && a[r][c+1]!=a[r][c]){
int x = a[r][c];
while(a[r][c] == x && c >= 1 && c <= n){
c--;
}
c++;
r++;
}
}
}
if(c == b){
System.out.println("#"+tc+" "+i);
break;
}
}
}
}
}
////////////////////////
package d2208;
import java.util.Scanner;
public class PhaHuyHeThongDien {
static int t,n;
static int[][] a = new int[n][n];
static int[] visit = new int[n];
static class Queue {
int front, rear;
int[] data = new int[90001];
public Queue() {
front = rear = 0;
}
public void enQ(int n) {
data[rear++] = n;
}
public int deQ() {
return data[front++];
}
public int qPeek() {
return data[front];
}
public boolean isEmpty() {
if (front == rear) {
return true;
}
return false;
}
}
public static void bfs(int u){
Queue q= new Queue();
q.enQ(u);
visit[u] = 1;
while(!q.isEmpty()){
int nx = q.deQ();
for(int i = 0 ; i < n ; i++){
if(a[nx][i] == 1 && visit[i] == 0){
visit[i] = 1;
q.enQ(i);
}
}
}
}
public static void xoa(int u){
for(int i = 0 ; i < n ; i++){
if(a[u][i] == 1){
a[u][i] = 2;
a[i][u] = 2;
}
}
}
public static void quay(int u){
for(int i = 0 ; i < n ; i++){
if(a[u][i] == 2){
a[u][i] = 1;
a[i][u] = 1;
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc= new Scanner(System.in);
t = sc.nextInt();
for(int tc = 1 ; tc <= t ; tc++){
n = sc.nextInt();
a = new int[n][n];
visit = new int[n];
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < n ; j++){
a[i][j]= sc.nextInt();
}
}
int max = 0;
for(int i = 0 ; i < n ; i++){
if(visit[i] == 0){
bfs(i);
max++;
}
}
int id = -1;
for(int i = 0 ; i < n ; i++){
xoa(i);
int dem = -1;
visit = new int[n];
for(int j = 0 ; j < n ; j++){
if(visit[j] == 0){
bfs(j);
dem++;
}
}
if(dem > max ){
max = dem;
id = i;
}
quay(i);
}
if(id == -1){
System.out.println(0);
}
else{
System.out.println(id+1);
}
}
}
}
/////////////////////////
package luyentap2307;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class visitdepartment {
static int N, E, K, T;
static int len = 3000;
static float[][] arr = new float[len][len];
static float[][] timeXacSuat = new float[len][len];
public static void reset() {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
arr[i][j] = 0;
timeXacSuat[i][j] = 0;
}
}
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("src/luyentap2307/inputvisitdepartment.txt"));
Scanner scanner = new Scanner(System.in);
for (int tc = 1; tc <= 10; tc++) {
N = scanner.nextInt();
E = scanner.nextInt();
K = scanner.nextInt();
T = scanner.nextInt();
reset();
for (int i = 0; i < E; i++) {
int dinh1 = scanner.nextInt();
int dinh2 = scanner.nextInt();
arr[dinh1][dinh2] = scanner.nextFloat();
}
//node
timeXacSuat[1][0] = 1;
for (int t = 1; t <= T; t++) {
for (int i = 1; i <= N; i++) {
if (timeXacSuat[i][t-1] != 0) {
for (int j = 1; j <= N; j++) {
timeXacSuat[j][t] += timeXacSuat[i][t-1]*arr[i][j];
}
}
}
}
//Jang start tai 0, Kang tai K
//10p di chuyen 1 lan
int jangTime = T/10, kangTime = (T-K)/10;
int jangD = 0, kangD = 0;
float jangXS = 0, kangXS = 0;
for (int i = 1; i <= N; i++) {
if (timeXacSuat[i][jangTime] > jangXS) {
jangXS = (float)timeXacSuat[i][jangTime];
jangD = i;
}
if (timeXacSuat[i][kangTime] > kangXS) {
kangXS = (float)timeXacSuat[i][kangTime];
kangD = i;
}
}
System.out.print("#" + tc + " ");
System.out.println(String.format("%d %.6f %d %.6f", jangD, jangXS, kangD, kangXS));
}
}
}
Leave a Comment