Блог пользователя gnull

Вопрос по задаче С контеста Codeforces Beta Round #57 (Div. 2) .
Автор gnull, 13 лет назад, По-русски
Как перевести из арабских цифр в римские? Я смотрел чужие исходники и все такое, но не понял способ. Объясните пожалуйста.
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Очень просто. Просто храним в константном массиве одно либо два римских числа которые дают суммы 1*10^k, 4*10^k, 5*10^k, 9*10^k(их 13), идем в порядке убывания и пока число >= текущего числа в массиве дописываем эту строку. Мой код: http://pastebin.com/uCHYDpFr
→ Ответить
13 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
мой код (ну, он маленький, пожалуй не буду его выкладывать на сторонний ресурс):
string to_roman(int x)
{
string I[] = { "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" };
string X[] = { "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" };
string C[] = { "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" };
string M[] = { "", "M", "MM", "MMM" };
string re;
re = I[x%10] + re;
x/=10;
re = X[x%10] + re;
x/=10;
re = C[x%10] + re;
x/=10;
re = M[x%10] + re;
return re;
}
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Вот ещё вариант:

string toR( int n )
{
   string s = "";
   int q;
   char v[4][4][3] = {
      { "I", "V", "IX", "IV" },
      { "X", "L", "XC", "XL" },
      { "C", "D", "CM", "CD" },
      { "M", "", "", "" },
   };

   loop(t,0,4)
   {
      q = n % 10;
      n /= 10;
      if( q == 9 )
         s = v[t][2] + s;
      else if( q == 4 )
         s = v[t][3] + s;
      else
      {
         loop(i,0,q%5)
            s = v[t][0] + s;
         if( q >= 5 )
            s = v[t][1] + s;
      }
   }
   return s;
}
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Мой:

string toroman(int n) {
    map<int, string> d;
    d[1] = "I"; d[5] = "V"; d[10] = "X"; d[50] = "L"; d[100] = "C"; d[500] = "D"; d[1000] = "M"; d[4] = "IV"; d[9] = "IX"; d[40] = "XL"; d[90] = "XC"; d[400] = "CD"; d[900] = "CM";

    string r;
    while(n) {
        map<int, string>::iterator it = d.lower_bound(n);
        if(it->first > n) it--;
        r += it->second;
        n -= it->first;
    }
    return r;
}
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    вот простая реализация с вики.
    а вот то, что я писал на контесте. Основное отличие в том, что константы догенерируются по начальным.
    → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится


    Офтоп.

    Вот какие-то противоречивые чувства решение вызывает: с одной стороны симпатично, а с другой стороны тащить для  такой задачи в программу STL с реализацией красно-черных деревьев как-то странно.

    Это, наверное, с тех времен, когда на компьютере крутилась СВМ, под которой на одной виртуальной машине работала MVS, где считали зарплату и одовременно за терминалами в TSO работал десяток студентов, еще десяток работали в ПДО, еще на одной виртуальной машине крутилась МОС ЕС (это UNIX) со своим десятком пользователей.
    И все это на одной ЕС-1036 с 4М памяти, процесором в 1Мгц  и без особых тормозов =)
    Да, времена изменились...
     

    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Времена не изменились.

      В Воронеже на Всероссийской студенчесской олимпиаде человек так 20 писали на одной машине. Предложенная MS VS 2010 запускалась минут 10. Затем секунд за 20 запускался диспетчер задач, ещё секунд 20 тратилось на убийство 2010 студии.

      Запускаем 2008 студию - скорость увеличивается вдвое, но всё равно если набираешь строчку
      for(int i=a;i<b;++i)
      то появиться она может лишь секунд через 10 посе написания закрывающей скобки.

      В итоге я не выдержал и писал в Borland'е.)
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Угу, нынче спокойно разменивается память на время, а память и время на простоту и надежность...
      → Ответить