Back Jun 17521 Byte Coin解答(JAVA)


質問リンク

質問する


国際資本不動産会社はByte Coinに投資している.ビットコインは金博士が作った仮想通貨だ.実際にバイトコードの価格を予測することはできないが,この問題ではバイトコードの価格上昇を事前に正確に予測できると仮定する.
1日からn日までのn日間、図1に示すように、バイトコードの上昇と下落を予め知ることができ、初期現金Wがあります.図1の赤いボックスは、その日付のバイトコード価格を示す.毎日ビットコインを買収したり売ったりすることができます.しかし、ビットコインを1つに分けて投げ売りや買収することはできません.私たちはn日に持っているすべての硬貨を販売する際に、持っている現金を最大化することを望んでいます.

例えば、図1に示すバイトコードの立ち上がり図を初日に知ることができ、私たちに与えられた初期現金は24であると仮定することができる.収益を最大限に高めるには、ビットコインを以下の方法で買収、販売することができます.初日に現金20元でコインを4個買いました.翌日、すべての硬貨を売って、28の現金を得て、全部で32の現金があります.5日目に32現金で16個の硬貨を買収した.7日目にすべてのコインを売って、全部で128ドルの現金を手に入れた.9日目には現金126で42個の硬貨を購入し、10日目にはすべての硬貨を販売した.では、10日の現金は170に達し、これが最大です.
曜日n、初期現金W、1日からn日まで毎週1バイト硬貨の価格、n日に持っているすべての硬貨を売る場合、持っている最終現金の最高値を書いてください.

入力


入力は標準入力です.第1行は、曜日を表す正の整数nおよび初期現金W(1≦n≦15、1≦W≦100000)を与える.次のn行では、iの1行目は、i日バイトコードの価格(1≦si≦50)を表す整数siを与える.

しゅつりょく


出力は標準出力を採用する.n日に所持している全ての硬貨を売る場合、現金の最高値を1行に印刷する.なお、初期現金Wはそれほど大きくないが、最終的には現金が大きくなる可能性がある.

に答える


わあ...私もその能力を望んでいますが...
思ったより簡単です.
次の日は餅を打って壊れて草を買って、餅を打って落ちて草を買います.
現金は整数型ではありません...うらやましいですね.
BigIntegerに収録
int変数に正の値が満ちているように、お金がほしいです.

ソースコード

import java.util.*;
import java.io.*;
import java.math.BigInteger;
public class Main{
    
    public static void main(String [] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        final int NUMBER_OF_DAY = Integer.parseInt(st.nextToken());   
        BigInteger cash = new BigInteger(st.nextToken());
        BigInteger coin = BigInteger.ZERO;
        
        int price[] = new int [NUMBER_OF_DAY];
        for(int i=0;i<NUMBER_OF_DAY;i++) {
            price[i] = Integer.parseInt(br.readLine());
        }
        
        for(int i=0;i<NUMBER_OF_DAY-1;i++) {
            if(price[i] <= price[i+1]) {
                coin = coin.add( cash.divide(BigInteger.valueOf(price[i])) );
                cash = cash.remainder(BigInteger.valueOf(price[i]));
            }else {
                cash = cash.add( coin.multiply(BigInteger.valueOf(price[i])));
                coin = BigInteger.ZERO;
            }
        }
        cash = cash.add( coin.multiply(BigInteger.valueOf(price[NUMBER_OF_DAY -1])));
        sb.append(cash.toString());
        sb.append("\n"); 
        
        bw.write(sb.toString());
        
        bw.flush();
        br.close();
        bw.close();
        
    }

    
}