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

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vm10hntw


Để 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 Hi phiến đá (Hi > 0, và do kích thước các phiến đá là như nhau nên cũng có thể coi Hi 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 Ri 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 Tv (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 đá Tv (Tv = 1..N).

Kết quả

  • Ghi ra trên K dòng, dòng thứ i (i = 1..K) ghi số nguyên Li (Li = 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ứ Li.

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


Đượ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 :((
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.