1. Uses the hashmap to map the character to its ink cost.
2. Store the ink cost for all bases of a certain number in array list.
3. Print out the minimum(s).
-----Sample input-----
2 // 2 test cases
10 8 12 13 15 13 13 16 9 // The 36 characters' ink cost
11 18 24 21 23 23 23 13 15
17 33 21 23 27 26 27 19 4
22 18 30 30 24 16 26 21 21
5 // 5 numbers
98329921 // The number. You should output what base to print out the number will cost the minimum ink.
12345
800348
14
873645
1 1 1 1 1 1 1 1 1 // The next case.
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
4
0
1
10
100
----
#include <stdio.h>
#include <stdlib.h>
/*
NOTE:
1.Pay attention to whether every array access invalid memory address.
*/
#define HIGHEST_BASE 36
#define LOWEST_BASE 2
void Cheapest_bases(const int ink_cost[], int num);
int main(int argc, char *argv[])
{
int cas_max, cas_cou; /* Test cases; cases count */
int ink_cost[36];
int i;
scanf("%d", &cas_max);
for(cas_cou = 1; cas_cou <= cas_max; cas_cou++)
{
printf("Case %d:\n", cas_cou);
for(i=0; i <= 35; i++)
scanf("%d", &ink_cost[i]);
int num_cas; /* Number cases */
scanf("%d", &num_cas);
while(num_cas--)
{
int num;
scanf("%d", &num);
printf("Cheapest base(s) for number %d:", num);
Cheapest_bases(ink_cost, num); /* Find and print the cheapest bases. */
}
if(cas_cou <= cas_max - 1)printf("\n"); /* Newline between cases. */
}
return 0;
}
void Cheapest_bases(const int ink_cost[], int num)
{
int price[37] = {0}; /* price:0~1, 2~36; 2 + 36-2+1 == 37 == size */
/* price[0], price[1] are unused */
int bases;
if(num == 0 || num == 1) /* When num == 0 or 1 the costs is equals to each other. */
{
for(bases = LOWEST_BASE; bases <= HIGHEST_BASE; bases++)
printf(" %d", bases);
printf("\n");
return;
}
/* From bases 2 to bases 36 */
for(bases = LOWEST_BASE; bases <= HIGHEST_BASE; bases++)
{
/* Compute how much it cost. */
int sum, num_temp = num;
for(sum=0; num_temp; num_temp /= bases)
sum += ink_cost[num_temp % bases]; /* Sum in this bases. */
price[bases] = sum; /* Build price table. */
}
/* Find the min */
int min = 2e9+1;
for(bases = LOWEST_BASE; bases <= HIGHEST_BASE; bases++)
if(price[bases] < min) min = price[bases];
/* Output */
for(bases = LOWEST_BASE; bases <= HIGHEST_BASE; bases++)
if(price[bases] == min)
printf(" %d", bases);
printf("\n"); /* Newline between numbers. */
}
----
package uva11005;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
/**
*
* @author awesq
*/
public class UVa11005 {
public static HashMap<Character, Integer> hm = new HashMap<>();
public static final int MAX_BASE = 36;
public static final String DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
try (Scanner sc = new Scanner(System.in)) {
int cases = sc.nextInt();
for (int index = 1; index <= cases; index++) {
hm.clear();
// There is no line feed before the first case.
if (index != 1) {
System.out.println("");
}
System.out.println("Case " + index + ":");
// Map every character to its value.
for (int i = 0; i < MAX_BASE; i++) {
hm.put(DIGITS.charAt(i), sc.nextInt());
}
// Processing numbers
int numbers = sc.nextInt();
while (numbers-- > 0) {
int printNum = sc.nextInt(), minInk = Integer.MAX_VALUE;
ArrayList<BaseInkPair> baseInkAl = new ArrayList<>();
for (int baseIndex = 2; baseIndex <= MAX_BASE; baseIndex++) { // From binary to base 36. Get ink cost for all bases.
int ink = getNumInkInBase(Integer.toString(printNum, baseIndex).toUpperCase());
if (ink < minInk) {
minInk = ink;
}
baseInkAl.add(new BaseInkPair(baseIndex, ink));
}
System.out.print("Cheapest base(s) for number " + printNum + ": ");
// Output the minimum bases.
boolean flag = false;
for (BaseInkPair bip : baseInkAl) {
if (bip.ink == minInk) {
if (flag == true) {
System.out.print(" ");
}
System.out.print(bip.base);
flag = true;
}
}
System.out.println("");
}
}
} catch (Exception e) {
}
}
public static int getNumInkInBase(String printNum) {
int inkSum = 0;
for (int i = 0; i < printNum.length(); i++) {
inkSum += hm.get(printNum.charAt(i));
}
return inkSum;
}
}
// The object of an inner class can't be used or created in an outer class's public static void main method.
class BaseInkPair {
public int base;
public int ink;
public BaseInkPair(int base, int ink) {
this.base = base;
this.ink = ink;
}
}
留言列表
