SPOJ.com - Problem VM10HNTW

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

VM10HNTW - Xây tháp Hà Nội

Để chào mừng đại lễ kỉ niệm 1000 năm Thăng Long Hà Nội, bạn bè trên khắp thế giới đã quyết định góp Q phiến đá quý (1 ≤ 30,000 ≤ Q) giúp thủ đô xây dựng một tòa tháp gồm K tầng (1 ≤ K ≤ Q), mỗi tầng làm từ một phiến đá quý. Những phiến đá này có hình dạng và kích thước giống hệt nhau, nhưng lại có “độ quý” C khác nhau (1 ≤ C ≤ 10,000).

Đá quý được tập kết về thủ đô thành M chồng xếp liền nhau theo một hàng dài, chồng đá thứ i gồm H_i phiến đá (H_i > 0, và do kích thước các phiến đá là như nhau nên cũng có thể coi H_i là “chiều cao” của chồng đá thứ i).

Sau đó các phiến đá lần lượt được “gắp” vào công trường để xây dựng tòa tháp (xây từ dưới lên trên) bằng một chiếc cần cẩu chuyên dụng (chiếc loại I). Chiếc ngoàm của cần cẩu được thiết kế chỉ có thể gắp mỗi lượt một phiến đá đang nằm trên cùng của một chồng đá bất kì, với điều kiện hai chồng đá liền kề phải có chiều cao nhỏ hơn chiều cao của chồng đó (nếu phía bên nào không có đá thì coi như chồng bên đó có chiều cao bằng 0). Để khắc phục nhược điểm đó, có một chiếc cần cẩu khác (chiếc loại II) được thiết kế đặc biệt có thể gắp bất kì phiến đá nào (tất nhiên phải là phiến đá nằm trên cùng của một chồng, và cũng chỉ có thể gắp mỗi lượt một phiến); tuy nhiên chiếc cần cẩu này lại làm “xước” phiến đá mà nó gắp, nên độ quý của phiến đá đó chỉ còn là C x P% (0 < P < 100).

Mặt khác, do các phiến đá cùng loại nếu được đặt chồng lên nhau sẽ tạo ra “hiệu ứng ánh sáng” rất đẹp mắt nên khi đó độ quý của phiến đá nằm trên sẽ tăng so với độ quý của phiến đá nằm dưới là D% (D > 0), nếu phiến đá nằm trên bị xước (do sử dụng cần cẩu loại II) thì độ quý của phiến đá sau khi tăng D% mới được nhân với P% để nhận được độ quý cần tính.

Tổng độ quý S của tòa tháp là tổng các độ quý của K phiến đá tạo nên tòa tháp theo cách tính nói trên. Vấn đề đặt ra là hãy lựa chọn một phương án xây tháp sao cho S càng lớn càng tốt!

Dữ liệu

Dòng đầu tiên chứa 5 số nguyên N, M, K, P, D trong đó N là số loại đá khác nhau (các loại đá được đánh số từ 1..N).
Dòng thứ hai chứa N số thực R_i là độ quý của loại đá thứ i (i = 1..N).
M dòng cuối cùng, dòng thứ j (j = 1..M) có định dạng:
- Bắt đầu bằng số nguyên H là số phiến đá ở chồng đá thứ j.
- Tiếp theo là H số nguyên T_v (v = 1..H) với ý nghĩa phiến đá thứ v (tính từ dưới lên) thuộc chồng đá thứ j là loại đá T_v (T_v = 1..N).

Kết quả

Ghi ra trên K dòng, dòng thứ i (i = 1..K) ghi số nguyên L_i (L_i = 1..M) thể hiện: lần gắp thứ i (theo thứ tự thời gian) chọn gắp phiến đá trên cùng của chồng đá thứ L_i.

Các cần cẩu sẽ được sử dụng theo nguyên tắc: ưu tiên sử dụng cần cẩu loại I, trong trường hợp một trong các điều kiện để sử dụng cần cẩu loại I không được thỏa mãn thì sẽ sử dụng đến chiếc cần cẩu loại II.

(Mỗi số trên cùng một dòng của input/output được/phải ghi cách nhau ít nhất một dấu cách trống)

Cách tính điểm

Số điểm bạn nhận được sẽ tỉ lệ với tổng độ quý S của tòa tháp bạn xây được.

Ví dụ

Dữ liệu:
13 7 7 70 30
1.7 2.3 3.4 5.5 7.8 1.0 4.6 6.1 9.9 1.3 7.3 8.2 2.5
2 1 1
5 2 3 3 3 2
4 4 4 4 5
7 6 7 7 8 7 9 9
6 10 10 11 11 11 10
1 12
3 13 13 13

Kết quả:
4
4
5
4
5
5
5

Giải thích

Như vậy với phương án xây tháp này bạn sẽ nhận được S = 43.41

Một phương án khác với thứ tự gắp lần lượt là 4, 4, 5, 4, 4, 5, 5 sẽ cho S = 44.49

Submit solution!

Được gửi lên bởi:	VOJ Team
Ngày:	2010-06-20
Thời gian chạy:	2s
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ừ: GOSU NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET
Nguồn bài:	VM10 - Tác giả: AnhDQ

hide comments



2020-02-20 05:16:18 1 1111111111111111 1210000000100011 1010101110101111 1000100010100011 1111111010101011 1000000010101011 1011111110111011 1010000010001011 1010101111101011 1010100010001011 1010111010111011 1010001000100011 1011101111101011 1000100000001311 1111111111111111 1111111111111111 2 1111111111111111 1200000010000011 1011111011111011 1000001010000011 1110101010111011 1010101010100011 1011111010111111 1000001010000011 1011101011111011 1010101010000011 1010101010111111 1010100000130011 1010111111111011 1000000000000011 1111111111111111 1111111111111111 3 1111111111111111 1210001000100011 1010101010101011 1000100010101011 1011111110101011 1000001010101011 1111101010101011 1010001000001011 1010111111111011 1010000000100011 1011111110101111 1000001010100011 1011101010111011 1000100000130011 1111111111111111 1111111111111111 4 1111111111111111 1200100000000011 1011101110111011 1000001010101011 1111111011101011 1000100010000011 1010101010111111 1010001010001011 1011111011101011 1000100010100011 1110101110111111 1010100000130011 1010111111111011 1000000000000011 1111111111111111 1111111111111111 5 1111111111111111 1210000000100011 1010111011101011 1010100010001011 1011101010111011 1000001010001011 1111111011111011 1000100010000011 1011101010111011 1010001000001011 1010101011111111 1010101000000011 1010101110111011 1000100010001311 1111111111111111 1111111111111111 6 1111111111111111 1210001010000011 1010101010111111 1010100000100011 1010111111101011 1000100000001011 1110101111111011 1000100000001011 1011101111101011 1000101000101011 1110101010111011 1010100010100011 1010111110101111 1000000000100311 1111111111111111 1111111111111111 7 1111111111111111 1210000000000011 1011101111111011 1000101010000011 1110101010111011 1000001000101011 1010111111101111 1010100000100011 1011101110101111 1000001000100011 1111111011111011 1000100010001011 1010101110111011 1010001300000011 1111111111111111 1111111111111111 8 1111111111111111 1200000010000011 1111111010111011 1000000010001011 1011111111111011 1010000000000011 1010111111101011 1010000000001011 1010111011111011 1000100010001011 1111111011101011 1000001000100011 1110111110101011 1000000000101311 1111111111111111 1111111111111111 9 1111111111111111 1200000000001011 1011111111101011 1000000010001011 1111111010111011 1000100010000011 1011101111111011 1010001000001011 1010111011101011 1010000010101311 1011111110101111 1000100000100011 1011101011111011 1000001000000011 1111111111111111 1111111111111111 10 1111111111111111 1200001000100011 1111101110101011 1000100010001011 1011101111101111 1000100000000011 1110111111101011 1000000010001011 1110111011101011 1010001000001011 1010101111111011 1000101010000011 1010101010101111 1010100000100311 1111111111111111 1111111111111111
2020-02-19 09:52:01 package stock; import java.io.File; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Stock { 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 = sc.nextInt(); for (int t = 1; t <= T; t++) { int n = sc.nextInt(); int[] a = new int[n]; int[] b = new int[100]; for (int i = 0; i < n; i++) { a[i] = sc.nextInt(); } int tong =0, lai =0, goc =0, tt=0,s=0; for (int i = 0; i < n; i++) { if (a[i]!=max(a)) { goc += a[i]; tt++; }else{ tong = tt*a[i]; lai = tong -goc; b[i]=lai; tong =0; lai =0; goc=0; tt=0; } a[i]=0; } for (int i = 0; i < b.length; i++) { s+=b[i]; } System.out.println("#" + t + " "+s ); } } public static int max(int[] a){ int max = 0; for (int i = 0; i < a.length; i++) { if(max<a[i]){ max=a[i]; } } return max; } }
2020-02-19 04:59:27 import java.io.FileInputStream; import java.util.Scanner; public class Solution { static String a; static char[] infix, postfix, stack1; static int[] stack2; public static void main(String[] args) throws Exception { // Scanner scanner = new Scanner(System.in); Scanner scanner =new Scanner(new FileInputStream("D:\\khongbiet.txt")); for (int test = 1; test <= 10; test++) { int L = scanner.nextInt(); a = scanner.next(); infix = new char[L]; int result = 0; for (int j = 0; j < L; j++) infix[j] = a.charAt(j); postfix = new char[200]; stack1 = new char[200]; int top = -1; int m = -1; char x; for (int k = 0; k < L; k++) { if (isNumber(infix[k])) { m++; postfix[m] = infix[k]; } else if (infix[k] == '(') { top++; stack1[top] = infix[k]; } else if (infix[k] == ')'){ while ((top>=0)&&(stack1[top] != '(')) { x = stack1[top]; top--; m++; postfix[m] = x; } top--;} else { while ((top >= 0) && Precedence(infix[k]) <= Precedence(stack1[top])) { x = stack1[top]; top--; m++; postfix[m] = x; } top++; stack1[top] = infix[k]; } } while (top >= 0) { x = stack1[top]; top--; m++; postfix[m] = x; } m++; postfix[m] = '\0'; stack2 = new int[500]; int top2 = -1; int a = 0; int num, op1, op2; while (postfix[a] != '\0') { if (isNumber(postfix[a])) { num = postfix[a] - '0'; top2++; stack2[top2] = num; } else { op1 = stack2[top2]; top2--; op2 = stack2[top2]; top2--; if (postfix[a] == '+') result = op1 + op2; if (postfix[a] == '') result = op1 op2; top2++; stack2[top2] = result; } a++; } result = stack2[top2]; System.out.println("#" + test + " " + result + "\n"); } } private static int Precedence(char c) { if (c == '(') return 0; if (c == '+') return 1; if (c == '*') return 2; return 3; } private static boolean isNumber(char c) { if (c == '0' \|\| c == '1' \|\| c == '2' \|\| c == '3' \|\| c == '4' \|\| c == '5' \|\| c == '6' \|\| c == '7' \|\| c == '8' \|\| c == '9') return true; return false; } }
2020-02-18 10:38:20 package b4; import java.io.File; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Ladder1 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); for (int t = 1; t <= 10; t++) { int T = sc.nextInt(); int a[][] = new int[100][100]; for (int i = 0; i < 100; i++) { for (int j = 0; j < 100; j++) { a[i][j] = sc.nextInt(); } } int x = 99, y = 0; for (int i = 0; i < 100; i++) { if (a[99][i] == 2) { y = i; } } while(x>0){ a[x][y]=0; if (y-1>=0&&a[x][y-1]==1) { y--; }else if (y+1<100&&a[x][y+1]==1) { y++; }else { x--; } } System.out.println("#" + t + " " + y); } } }
2017-06-29 05:44:47 so easy :3
2017-06-29 05:44:15 15 phút AC :))))
2011-07-04 14:41:29 trandatbav bài gì mà kinh khủng thế này :((

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