UVa 11536 - Smallest Sub-Array

Accepted date: 2015-08-26
Ranking (as of 2015-08-26): 11 out of 503
Language: C++

/*
  UVa 11536 - Smallest Sub-Array

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_11536_Smallest_Sub_Array.cpp
*/

#include <algorithm>
#include <cstdio>
using namespace std;

const int N_max = 1000000, K_max = 100;
int seq[N_max + 1], freqs[K_max + 1]; // freqs[i] is the number of occurences of i

int main()
{
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    if (K < 4) {
      printf("Case %d: %d\n", t, K);
      continue;
    }
    for (int i = 1; i <= K; i++)
      freqs[i] = 0;
    seq[1] = 1, seq[2] = 2, seq[3] = 3;
    freqs[1] = freqs[2] = freqs[3] = 1;
    int k = 3, min_length = N + 1;
    for (int i = 4, pi = 1; i <= N; i++) {
      int s = (seq[i - 1] + seq[i - 2] + seq[i - 3]) % M + 1;
      seq[i] = s;
      if (s <= K) {
        if (!freqs[s]++) {
          if (++k == K)
            min_length = min(min_length, i - pi + 1);
        }
        else {
          for ( ; pi < i; pi++) {
            int p = seq[pi];
            if (p > K)
              continue;
            if (freqs[p] < 2)
              break;
            freqs[p]--;
          }
          if (k == K)
            min_length = min(min_length, i - pi + 1);
        }
      }
    }
    printf("Case %d: ", t);
    if (min_length > N)
      puts("sequence nai");
    else
      printf("%d\n", min_length);
  }
  return 0;
}

UVa 1121 - Subsequence

Accepted date: 2015-08-24
Ranking (as of 2015-08-24): 14 out of 658
Language: C++

/*
  UVa 1121 - Subsequence

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_1121_Subsequence.cpp
*/

#include <algorithm>
#include <cstdio>
using namespace std;

const int n_max = 100000;
int integers[n_max];

int main()
{
  int N, S;
  while (scanf("%d %d", &N, &S) != EOF) {
    int s = 0, min_length = N + 1;
    for (int i = 0, pi = 0; i < N; i++) {
      scanf("%d", &integers[i]);
      if ((s += integers[i]) >= S) {
        for ( ; pi < i; pi++) {
          if (s - integers[pi] < S)
            break;
          s -= integers[pi];
        }
        min_length = min(min_length, i - pi + 1);
      }
    }
    if (min_length > N)
      min_length = 0;
    printf("%d\n", min_length);
  }
  return 0;
}

UVa 1584 - Circular Sequence

Accepted date: 2015-08-19
Ranking (as of 2015-08-19): 71 out of 636
Language: C++

/*
  UVa 1584 - Circular Sequence

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_1584_Circular_Sequence.cpp
*/

#include <cstdio>
#include <cstring>

int compare_string(const char* s, int length, int i, int j)
{
  for (int k = length; k; k--, i = (i + 1) % length, j = (j + 1) % length) {
    if (s[i] > s[j])
      return 1;
    else if (s[i] < s[j])
      return -1;
  }
  return 0;
}

int main()
{
  int T;
  scanf("%d", &T);
  while (T--) {
    const int nr_chars_max = 100;
    char s[nr_chars_max + 1];
    scanf("%s", s);
    int min_i = 0, length = strlen(s);
    for (int i = 1; i < length; i++)
      if (compare_string(s, length, i, min_i) < 0)
        min_i = i;
    printf("%s", &s[min_i]);
    if (min_i) {
      s[min_i] = '\0';
      printf("%s", s);
    }
/*
    for (int k = length; k; k--, min_i = (min_i + 1) % length)
      putchar(s[min_i]);
*/
    putchar('\n');
  }
  return 0;
}

UVa 1339 - Ancient Cipher

Accepted date: 2015-08-18
Ranking (as of 2015-08-18): 68 out of 761
Language: C++

/*
  UVa 1339 - Ancient Cipher

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_1339_Ancient_Cipher.cpp
*/

#include <functional>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int nr_letters = 26, nr_chars_max = 100;

int main()
{
  char s[nr_chars_max + 1], t[nr_chars_max + 1];
  int sl[nr_letters], tl[nr_letters];
  while (scanf("%s", s) != EOF) {
    scanf("%s", t);
    memset(sl, 0, sizeof(sl));
    memset(tl, 0, sizeof(tl));
    for (const char* p = s; *p; p++)
      sl[*p - 'A']++;
    for (const char* p = t; *p; p++)
      tl[*p - 'A']++;
    sort(sl, sl + nr_letters, greater<int>());
    sort(tl, tl + nr_letters, greater<int>());
    bool yes = true;
    for (int i = 0; i < nr_letters && (sl[i] || tl[i]); i++)
      if (sl[i] != tl[i]) {
        yes = false;
        break;
      }
    puts((yes) ? "YES" : "NO");
  }
  return 0;
}

UVa 10898 - Combo Deal

Accepted date: 2015-08-13
Ranking (as of 2015-08-13): 24 out of 479
Language: C++

/*
  UVa 10898 - Combo Deal

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_10898_Combo_Deal.cpp
*/

#include <algorithm>
#include <cstdio>
using namespace std;

const int nr_items_max = 6, nr_combos_max = 8;

int nr_items, nr_combos, prices[nr_items_max], quantities[nr_items_max], min_payment;
struct combo {
  int quantities_[nr_items_max];
  int price_;
} combos[nr_combos_max];

void combo_deal(int ci, int payment)
{
  if (ci == nr_combos) {
    for (int i = 0; i < nr_items; i++)
      if (quantities[i])
        payment += prices[i] * quantities[i];
      min_payment = min(min_payment, payment);
  }
  else {
    combo& c = combos[ci];
    for (int i = 1; ; i++) {
      int j;
      for (j = 0; j < nr_items; j++)
      if (c.quantities_[j] * i > quantities[j])
        break;
      if (j < nr_items || payment + c.price_ * i >= min_payment)
        break;
      for (j = 0; j < nr_items; j++)
        quantities[j] -= c.quantities_[j] * i;
      combo_deal(ci + 1, payment + c.price_ * i);
      for (j = 0; j < nr_items; j++)
        quantities[j] += c.quantities_[j] * i;
    }
    if (payment < min_payment)
      combo_deal(ci + 1, payment);
  }
}

int main()
{
  while (scanf("%d", &nr_items) != EOF) {
    for (int i = 0; i < nr_items; i++)
      scanf("%d", &prices[i]);
    scanf("%d", &nr_combos);
    for (int i = 0; i < nr_combos; i++) {
      combo& c = combos[i];
      for (int j = 0; j < nr_items; j++)
        scanf("%d", &c.quantities_[j]);
      scanf("%d", &c.price_);
    }
    int nr_orders;
    scanf("%d", &nr_orders);
    while (nr_orders--) {
      min_payment = 0;
      for (int i = 0; i < nr_items; i++) {
        scanf("%d", &quantities[i]);
        min_payment += prices[i] * quantities[i];
      }
      int payment = 0;
      combo_deal(0, payment);
      printf("%d\n", min_payment);
    }
  }
  return 0;
}

UVa 10350 - Liftless EME

Accepted date: 2015-08-07
Ranking (as of 2015-08-07): 8 out of 483
Language: C++

/*
  UVa 10350 - Liftless EME

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_10350_Liftless_EME.cpp
*/

#include <algorithm>
#include <limits>
#include <cstdio>
using namespace std;

const int nr_chars_max = 12, n_max = 120, m_max = 15, ladder = 2;
int times[n_max][m_max][m_max];
  // times[i][j][k] is the time from the i-th floor's j-th hole 
  // to the (i + 1)-th floor's k-th hole
int min_times[n_max][m_max];
  // min_times[i][j] is the min. time needed to reach i-th floor's j-th hole

int main()
{
  char s[nr_chars_max + 1];
  while (scanf("%s", s) != EOF) {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n - 1; i++)
      for (int j = 0; j < m; j++)
        for (int k = 0; k < m; k++)
          scanf("%d", ×[i][j][k]);
    for (int j = 0; j < m; j++)
      min_times[0][j] = 0;
    for (int i = 1; i < n; i++)
      for (int j = 0; j < m; j++) {
        int min_t = numeric_limits<int>::max();
        for (int k = 0; k < m; k++)
          min_t = min(min_t, min_times[i - 1][k] + times[i - 1][k][j]);
        min_times[i][j] = min_t;
      }
    int min_t = numeric_limits<int>::max();
    for (int j = 0; j < m; j++)
      min_t = min(min_t, min_times[n - 1][j]);
    min_t += ladder * (n - 1);
    printf("%s\n%d\n", s, min_t);
  }
  return 0;
}

UVa 1388 - Graveyard

Accepted date: 2015-08-06
Ranking (as of 2015-08-06): 17 out of 489
Language: C++

/*
  UVa 1388 - Graveyard

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_1388_Graveyard.cpp
*/

#include <algorithm>
#include <cstdio>
using namespace std;

const double perimeter = 10000.0;
const int n_max = 1000, m_max = 1000;
double cds[n_max], nds[n_max + m_max]; // current / new distances

int main()
{
  int n, m;
  while (scanf("%d %d", &n, &m) != EOF) {
    m += n;
    for (int i = 0; i < n; i++)
      cds[i] = (perimeter * (i + 1)) / n;
    for (int i = 0; i < m; i++)
      nds[i] = (perimeter * (i + 1)) / m;
    double d = 0.0;
    for (int i = 0, j = 0; i < n - 1; ) {
      if (cds[i] < nds[j]) {
        d += min(cds[i] - nds[j - 1], nds[j] - cds[i]);
        i++;
      }
      else if (cds[i] > nds[j])
        j++;
      else {
        i++, j++;
      }
    }
    printf("%.4lf\n", d);
  }
  return 0;
}

UVa 11088 - End up with More Teams

Accepted date: 2015-08-05
Ranking (as of 2015-08-05): 14 out of 488
Language: C++

/*
  UVa 11088 - End up with More Teams

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_11088_End_up_with_More_Teams.cpp
*/

#include <algorithm>
#include <functional>
#include <cstdio>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif
using namespace std;

const int n_max = 15, members_max = 3, promising = 20;
int integers[n_max];
int sums[n_max]; // sums[i] is the sum between integers[i] and integers[n - 1]
int members[n_max / members_max]; // members[i] is the number of members of i-th team
int points[n_max / members_max]; // ability points of i-th team

bool more_teams(int n, int m, int ti, int nr_teams, int& max_nr_teams)
{
  if (ti == n) {
    max_nr_teams = max(max_nr_teams, nr_teams);
    return max_nr_teams == m;
  }
  else if (n - ti + nr_teams > max_nr_teams) {
    bool more = false;
    for (int i = 0; i < m; i++)
      if (members[i] < members_max && points[i] + sums[ti] >= promising) {
        more = true;
        members[i]++;
        int nr = nr_teams;
        points[i] += integers[ti];
        if (members[i] == members_max && points[i] >= promising)
          nr++;
        if (more_teams(n, m, ti + 1, nr, max_nr_teams))
          return true;
        members[i]--;
        points[i] -= integers[ti];
      }
    if (!more) {
      max_nr_teams = max(max_nr_teams, nr_teams);
      return max_nr_teams == m;
    }
  }
  return false;
}

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  for (int cn = 1; ; cn++) {
    int n;
    scanf("%d", &n);
    if (!n)
      break;
    int m = n / members_max; // number of teams
    for (int i = 0; i < n; i++)
      scanf("%d", &integers[i]);
    for (int i = 0; i < m; i++)
      members[i] = points[i] = 0;
    sort(integers, integers + n, greater<int>());
    for (int i = n - 1, s = 0; i >= 0; i--) {
      s += integers[i];
      sums[i] = s;
    }
    int max_nr_teams = 0;
    more_teams(n, m, 0, 0, max_nr_teams);
    printf("Case %d: %d\n", cn, max_nr_teams);
  }
#ifdef __ELAPSED_TIME__
  fprintf(stderr, "elapsed time = %lf sec.\n",
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC);
#endif
  return 0;
}

UVa 12896 - Mobile SMS

Accepted date: 2015-08-01
Ranking (as of 2015-08-01): 23 out of 499
Language: C++

/*
  UVa 12896 - Mobile SMS

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_12896_Mobile_SMS.cpp
*/

#include <cstdio>

const int L_max = 100, N_max = 9, P_max = 4;

const char keys[N_max + 1][P_max + 1] = {
  {'\0', ' '},
  {'\0', '.', ',', '?', '"'},
  {'\0', 'a', 'b', 'c'},
  {'\0', 'd', 'e', 'f'},
  {'\0', 'g', 'h', 'i'},
  {'\0', 'j', 'k', 'l'},
  {'\0', 'm', 'n', 'o'},
  {'\0', 'p', 'q', 'r', 's'},
  {'\0', 't', 'u', 'v'},
  {'\0', 'w', 'x', 'y', 'z'}
};

int main()
{
  int T;
  scanf("%d", &T);
  while (T--) {
    int L, Ns[L_max];
    scanf("%d", &L);
    for (int i = 0; i < L; i++)
      scanf("%d", &Ns[i]);
    char message[L_max + 1];
    for (int i = 0; i < L; i++) {
      int P;
      scanf("%d", &P);
      message[i] = keys[Ns[i]][P];
    }
    message[L] = '\0';
    puts(message);
  }
}