ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1048. Сверхдлинные суммы

Показать все сообщения Спрятать все сообщения

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Ural {
    public class Prob1048 {
        private List<int> nums = new List<int>();
        int c = 0, cur = 0;

        private void AddNum(int v) {
            if (cur >= c) {
                nums.Add(v);
                c++; cur++;
            } else {
                nums[cur] = v;
                cur++;
            }

            if (v > 9) {
                for (int i = cur - 1; i > 0; i--) {
                    nums[i - 1]++;
                    nums[i] -= 10;
                    if (nums[i - 1] < 10)
                        break;
                }
            }
        }

        public void Run() {
            int N = Int32.Parse(Console.ReadLine());

            string[] tokens = Console.ReadLine().Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
            int sum = Int32.Parse(tokens[0]) + Int32.Parse(tokens[1]);
            AddNum(sum);

            for (int i = 1; i < N; i++) {
                tokens = Console.ReadLine().Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
                sum=Int32.Parse(tokens[0]) + Int32.Parse(tokens[1]);
                if (sum < 9) {
                    for (int j = 0; j < cur; j++) {
                        Console.Write(nums[j]);
                    }
                    cur = 0;
                }
                AddNum(sum);
            }

            for (int i = 0; i < cur; i++) {
                Console.Write(nums[i]);
            }

        }

        static void Main(string[] args) {
            new Prob1048().Run();
        }
    }
}
This problem can be solved using only a few ints. Just think a bit at how the addition is made and how the numbers are given in the problem. Good luck!
Changed the algo, used linkedlist, memory consumption was much less, but got tle...
And I think in the worst case, when the data comes like this:
9 9 9 9 ... 9
0 0 0 0 ... 1

We still have to store all the numbers...
Well, this first should be less than 9...
8 9 9 9 ... 9
0 0 0 0 ... 1
Well, try thinking a bit on this case, when the carry propagates. You don't need to store the numbers ;)
e.neverme писал(a) 17 апреля 2009 08:31
And I think in the worst case, when the data comes like this:
9 9 9 9 ... 9
0 0 0 0 ... 1

We still have to store all the numbers...
OMG 2 years old post, but anyway... HOW DO WE KNOW WHEN CARRY PROPAGATES???!!! Do I need to write an Oracle program? (Oh, then I need to use Delphi :D) Before writing answer, we should write this part where is carry propagates but we can't know when it is going to appear! :C Tell me what are you doing to solve this program with such short amount of memory.
morbidel писал(a) 20 апреля 2009 05:46
Well, try thinking a bit on this case, when the carry propagates. You don't need to store the numbers ;)
e.neverme писал(a) 17 апреля 2009 08:31
And I think in the worst case, when the data comes like this:
9 9 9 9 ... 9
0 0 0 0 ... 1

We still have to store all the numbers...

Edited by author 17.01.2012 02:05
OMFG I got it xD. I would NOT get it without this forum. Oh my God, it have brilliant and simple solution :)