자바 제9 회 블 루 브리지 컵 3 체 공격 실현
2896 단어 알고리즘 연습 문제
[제목 설명] 세 사람 이 지 구 를 공격 할 것 이다.공격 을 막 기 위해 지구 인 들 은 A 를 보 냈 다.× B × C 척 의 전함 은 우주 에서 A 층 B 행 C 열의 입방체 로 배열 되 어 있다.그 중에서 i 층 j 행 k 열 전함 (전함 (i, j, k) 의 생명 치 는 d (i, j, k) 이다.
세 사람 은 지구 에 m 륜 '입방체 공격' 을 일 으 켜 매번 공격 할 때마다 작은 입방체 중의 모든 전함 에 똑 같은 피 해 를 입 힐 것 이다.구체 적 으로 t 라운드 공격 은 7 개의 매개 변수 lat, 전체 8198, rat, 전체 8198, lbt, 전체 8198, rbt, 전체 8198, lct, 전체 8198, rct, 전체 8198, ht 설명 을 사용 합 니 다.모든 만족 i * 8196 ° * 8712 ° * 8196 ° [lat, * 8198 ° rat], j * 8196 ° * 8712 ° * 8196 ° [lbt, * 8198 ° rbt], k * 8196 ° * 8712 ° * * 8196 ° [lct, * 8198 ° rct] 의 전함 (i, * 8198 ° j, * 8198 ° k) 은 ht 의 데 미 지 를 입 습 니 다.만약 한 전함 이 누적 받 은 총 데 미 지가 방 어 력 을 초과 한다 면 이 전함 은 폭발 할 것 이다.
지구 지휘관 은 그 에 게 첫 번 째 폭발 한 전함 이 어느 라운드 공격 후에 폭 발 했 는 지 알려 주 기 를 바란다.
[입력 형식] 표준 입력 에서 데 이 터 를 읽 습 니 다.첫 번 째 줄 은 4 개의 정수 A, 8198 ° B, 8198 ° C, 8198 ° m 를 포함한다.두 번 째 줄 은 A 를 포함 합 니 다.× B × C 개 정수, 그 중 제 (i − 1)×B + (j − 1)) × C + (k − 1) + 1 개 수 는 d (i, j, k) 이다.3 번 부터 m 번 째 줄 은 7 개의 정수 lat, 8198, rat, 8198, lbt, 8198, rbt, 8198, lct, 8198, rct, 8198, ht 를 포함한다.
[출력 형식] 표준 출력 으로 출력 합 니 다.첫 번 째 폭발 을 수출 한 전함 은 어느 라운드 공격 후 폭발 한 것 입 니까?반드시 이런 전함 이 존재 할 것 을 보증한다.
[샘플 입력] 2, 2, 3, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1,
[샘플 출력] 2
[사례 설명] 2 차 공격 후 전함 (1, 1, 1) 은 모두 2 데 미 지 를 입 었 고 방 어 력 을 초과 하여 폭발 했다.
【 데이터 약정 】 10% 의 데이터 에 대해 B = C = 1;20% 의 데이터 에 대해 C = 1;40% 의 데이터 에 대해 A * 8197× B × C, m ≤ 10, 000; 70% 의 데이터 에 대해 A, B, C ≤ 200;모든 데이터 에 대해 A × B × C ≤ 10^6, m ≤ 10^6, 0 ≤ d(i, j, k), ht ≤ 10^9。
자원 약정: 피크 메모리 소모 (가상 머 신 포함) < 256 M CPU 소모 < 3000 ms
import java.util.Scanner;
/**
* https://www.cnblogs.com/scx2015noip-as-php/p/2018_10_18.html
*
* @description TODO
* @author frontier
* @time 2019 3 13 8:34:15
*
*/
public class 7 {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int a, b, c, m;
a = input.nextInt();
b = input.nextInt();
c = input.nextInt();
m = input.nextInt();
int[][][] martix = new int[a + 1][b + 1][c + 1];
for (int i = 1; i <= a; ++i)
for (int j = 1; j <= b; ++j)
for (int k = 1; k <= c; ++k)
martix[i][j][k] = input.nextInt();
int lat, rat, lbt, rbt, lct, rct, ht;
int flag = 0;
for (int p = 1; p <= m; ++p) {
lat = input.nextInt();
rat = input.nextInt();
lbt = input.nextInt();
rbt = input.nextInt();
lct = input.nextInt();
rct = input.nextInt();
ht = input.nextInt();
for (int i = lat; i <= rat; ++i)
for (int j = lbt; j <= rbt; ++j)
for (int k = lct; k <= rct; ++k) {
martix[i][j][k] -= ht;
if (martix[i][j][k] < 0) {
flag = p;
break;
}
}
if (flag != 0)
break;
}
System.out.println(flag);
}
}