Форум Всеукраїнської інтернет-олімпіади NetOI


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#1 2011-12-28 18:06:11

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Розв’язки задач 2 туру

Почну нову тему, хоч il____ уже й почав викладати рішення в існуючих. По-моєму, зручніше буде, коли обговорення рішень проходить окремо від обговорення задач.


Викладаю код уже перевірених задач, поступово додаватиму коментарі.


SORTING

Загальна ідея:

назвемо "циклом" таку підмножину даної послідовності, що за будь-якої послідовності обмінів, кожен обмін двох елементів циклу ставитиме на "своє" місце не більше, ніж 1 число. Очевидно, що для сортування кожного циклу потрібно k-1 обмін, де k - кількість елементів циклу.
Якщо у нас m таких циклів, то відповіддю буде sum{i=1;m}(k_i-1)=sum{i=1;m}(k_i)-m;
Оскільки, sum{i=1;m}(k_i)=n, то відповіддь перетворюється на n-m. Де n - к-ть елементів у масиві, m - к-ть "циклів";

Код:

#include <vector>
#include <iostream>
using namespace std;

int main()
{
    int N,t,res;
    cin>>N;
    res=N;
    vector<int> a(N);
    for(int i=0;i<N;i++)cin>>a[i],a[i]--;
    for(int i=0;i<N;i++)
    {
        if(a[i]==-1)continue;
        t=i;
        do
        {
            int T=t;
            t=a[t];
            a[T]=-1;
        }while(t!=i&&t>=0);
        res--;
    }
    cout<<res<<endl;
}

SEQUENCE
Загальна ідея:
Позначимо за х шукане число. Тоді для пошуку ікса можна скласти квадратне рівняння. Після певної кількості перетворень сум отримаємо рівняння
x^2-2k^2 * x - k^2 * (2k+1).

Коренями цього рівняння будуть -k та k(2k+1)=k*n=n*(n-1)/2. Перший нам не підходить, а другий завжди задовольнятиме умові. Тобто відповіді "-1" бути не може.

Код:

#include <iostream>
using namespace std;

int main()
{
    int N;
    cin>>N;
    cout<<N*(N-1)/2<<endl;
}

PLUMS

Підійде будь-який алгоритм генерації магічних квадратів, описаний тут, оскільки у нашому квадраті умова про рівність сум має виконуватися тільки для рядків.

Код:

#include <vector>
#include <iostream>
using namespace std;

class almostMagic
{
    int N;
    vector<vector<int> > a;
public:
    void init()
    {
        int x=0,y=N/2,cnt=1;
        while(cnt<=N*N)
        {
            if(x<0){x=N-1;continue;}
            if(y<0){y=N-1;continue;}
            if(x>=N){x=0;continue;}
            if(y>=N){y=0;continue;}
            if(a[x][y]){x--;continue;}
            a[x][y]=cnt;
            cnt++;
            x--;y++;
        }
    }
    almostMagic(int n=0):N(n),a(n,vector<int>(n)){init();}
    friend istream& operator>>(istream &in,almostMagic& rhs)
    {
        in>>rhs.N;
        rhs.a.resize(rhs.N,vector<int>(rhs.N));
        rhs.init();
    }
    friend ostream& operator<<(ostream& out,almostMagic& rhs)
    {
        for(vector<vector<int> >::iterator i=rhs.a.begin();i!=rhs.a.end();++i)
        {
            for(vector<int>::iterator j=i->begin();j!=i->end();++j)
                out<<*j<<" ";
            out<<endl;
        }
    }
};

int main()
{
    almostMagic a;
    cin>>a;
    cout<<a;
}

SumOfPowers
Відправив на перевірку версію з використанням STL, яка при використанні оптимізації компілятора -О2 працює 200мс на найгіршому тесті, але без оптимізації, на жаль, майже 2 секунди. Оскільки тут, як я нещодавно дізнався, оптимізації вимкнені, то я отримав ТЛ-и на кількох тестах и отримав результат 33 бали(

Викладаю модифіковану, менш чуттєву до прапорів компіляції. Набирає 40 балів.

Загальна ідея:
Задачу можна звести до задачі про банкомат з нескінченною кількістю банкнот. "Номіналами" виступатимуть чила виду i^K. Така задача розв’язується за допомогою ДП з асимптотикою O(N*L), де N - максимальне вхідне число, L - кількість номіналів. Оскільки номіналів у нас N^(1/K), то маємо асимптотику O(N(1+1/K)).
І все було б добре, якби не квадрати. Для них асимтотика O(N^1.5) працює занадто довго.
Можна помітити, що будь-яке число можна розкласти на суму не більше, ніж 4 квадратів. По моєму, це навіть кимось доведено математично. Скористаємося цим фактом. Можна було б розкладати кожне число(перевірити, чи є число квадратом можна за О(1), розкласти на 2 квадрати - за O(sqrt(N), на 3 квадрати - за O(N). Якщо розкладання не знайдено, то відповідь - 4). Але в такому разі асимптотика була б O(M*N), що при даних обмеженнях може бути навіть гірше ніж початкове O(N^1.5). Тому не будемо повністю "викидати" динаміку, адже ми все-одно неодноразово вирішуємо однакові підзадачі, що перекриваються. Заповнимо наш "банкоматний" масив тілько одиницями(O(sqrt(N)) та двійками (O(N)). далі розглядаємо в циклі всі наші числа, і якщо це число ще не розкладене на 1 чи 2 квадрати - пробуємо відняти від нього всі i, такі що i^2<=N. І якщо на місці різниці стоїть двійка, то відповідь 3. Якщо жодного разу такої ситуації не виникло - відповідь 4.
Таким чином, для квадратів отримали асимптотику O(N+M*sqrt(N))


Ну і ще деякі незначні оптимізації та хаки для крайніх випадків(при К=1, очевидно, відповідь для будь-кого числа - 1. А при К>=20 при даних обмеженнях відповіддю для будь-якого числа буде саме це число, оскільки 2^20>987654).

Код:

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

typedef unsigned long long ull;

ull fast_pow(ull x,ull power)
{
    ull res=1;
    while(power)
    {
        if(power%2)res*=x;
        x*=x;
        power>>=1;
    }
    return res;
}

int main()
{
    int K,M,max=numeric_limits<int>::min();
    cin>>K>>M;
    static int a[9876];
    for(int i=0;i<M;i++)cin>>a[i],max=std::max(max,a[i]);
    if(K>=20)
    {
        for(int i=0;i<M;i++)cout<<a[i]<<" ";
        return 0;
    }
    if(K==1)
    {
        for(int i=0;i<M;i++)cout<<1<<" ";
        return 0;
    }
    static int powers[1000],result[987656];
    memset(result,0x7f,sizeof(result));
    result[0]=0;
    ull t;
    for(int i=1;;i++)
    {
        t=fast_pow(i,K);
        powers[i-1]=t;
        if(t>max)break;
        result[t]=1;
        result[t+1]=2;
    }
    if(K==2)
    {
        for(int k=0;powers[k]<=max;k++)
            for(int j=k;powers[j]+powers[k]<=max;j++)
                if(result[powers[j]+powers[k]]!=1)result[powers[j]+powers[k]]=2;
        for(int i=0;i<M;i++)
        {
            int res=result[a[i]]<=3?result[a[i]]:4;
            for(int k=0;powers[k]<=a[i]&&res==4;k++)
            {
                if(result[a[i]-powers[k]]==2)res=3;
            }
            result[a[i]]=res;
            cout<<res<<" ";
        }
    }
    else
    {
        for(int i=2;i<=max;i++)
        {
            for(int j=0;powers[j]<=i/2;j++)
            {
                if(result[i]<=2)break;
                if(result[i-powers[j]]+1<result[i])result[i]=result[i-powers[j]]+1;
            }
        }
        for(int i=0;i<M;i++)
            cout<<result[a[i]]<<" ";
    }
}

Platforms

Як і багато інших, я провтикав можливість стрибати назад і отримав 12 балів. Як і у багатьох інших, після додавання однієї умови задача пройшла на 40 балів.

Принцип роботи пояснювати, думаю, не має сенсу - банальна динаміка. Але якщо комусь потрібно все-таки описати алгоритм, то опишу)

Код:

#include <vector>
#include <iostream>
#include<algorithm>
using namespace std;

typedef long long ll;

int main()
{
    int N;
    cin>>N;
    vector<ll> a(N),b(N),c(N);
    for(int i=0;i<N;i++)cin>>a[i];
    b[0]=c[0]=0;
    b[1]=llabs(a[1]-a[0]);
    c[1]=(a[1]-a[0])*(a[1]-a[0]);
    for(int i=2;i<N;i++)
    {
        b[i]=min(b[i-1]+llabs(a[i]-a[i-1]),b[i-2]+3*llabs(a[i]-a[i-2]));
        c[i]=min(c[i-1]+(a[i-1]-a[i-2])*(a[i-1]-a[i-2])+3*(a[i]-a[i-2])*(a[i]-a[i-2]),min(c[i-1]+(a[i]-a[i-1])*(a[i]-a[i-1]),c[i-2]+3*(a[i]-a[i-2])*(a[i]-a[i-2])));
    }
    cout<<b.back()<<" "<<c.back()<<endl;
}

Відредаговано Dim_ov (2011-12-30 12:47:15)

Поза форумом

 

#2 2011-12-29 10:55:51

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Розв’язки задач 2 туру

(И.Н. Порублёв  А.Б. Ставровский Алгоритмы и программы решение олимпиадных задач)
вроде этот код посимпатичнее будет... smile

Код:

//Plums
#include <iostream>
using namespace std;
int main() {
    int N,NN;
    cin >> N;
    NN=N*N;
    for(int i=1,n; i<=N; i++)
    {
        n=i;
        cout << n;
            while(n<=NN)
            {
            if (n%N == 0) n++; else n=n+N+1;
                if (n<=NN) cout<<" "<<n;
            }
            cout << endl;
    }

        return 0;
 }

А задачу SumOfPowers на 40 баллов решило всего 10 человек!
Интересно, поделится кто-нибудь решением, или нет?

Відредаговано LVV (2011-12-30 10:47:01)


Вік живи - вік навчайся.

Поза форумом

 

#3 2011-12-29 13:30:55

Unknown
Новий користувач
Зареєстрований: 2011-10-28
Повідомлень: 31

Re: Розв’язки задач 2 туру

Platforms - 40 : (после того, как узнал про вариант прыжка назад, добавил 2 строчки и сдал sad )

Код:

#include <iostream>
using namespace std;

long long MINIMUM(long long a,long long b){
     if(a<b)return a;
     else return b;
     }   

long long A(long long z){
     return z>0 ? z : -z ;
     }     
      
main(){
       long long a[50001],b[50001],c[50001];
       int i,n;
       cin>>n;
       for(i=1;i<=n;i++)cin>>a[i];
       b[0]=0;
       b[1]=0;
       b[2]=A(a[2]-a[1]);
       c[0]=0;
       c[1]=0;
       c[2]=(a[2]-a[1])*(a[2]-a[1]);
       for(i=3;i<=n;i++){
                         long long b1,b2; //два варианта, чтоб не запутаться (1 задача)
                         long long c1,c2,c3; //три варианта, чтоб не запутаться (2 задача)
                         
                         b1=A( a[i]-a[i-1] )+b[i-1]; //вариант прыжка с соседней платформы

                         b2=A( 3*(a[i]-a[i-2]) )+b[i-2]; //вариант прыжка через платформу

                         b[i]=MINIMUM(b1,b2);
                         
                         c1=(a[i]-a[i-1])*(a[i]-a[i-1])+c[i-1]; //вариант прыжка с соседней платформы

                         c2=3*(a[i]-a[i-2])*(a[i]-a[i-2])+c[i-2]; //вариант прыжка через платформу

                         c3=( (a[i-1]-a[i-2])*(a[i-1]-a[i-2])+c[i-1] ) + 3*(a[i]-a[i-2])*(a[i]-a[i-2]); //вариант прыжка с соседней назад, и через платформу

                         c[i]=MINIMUM( MINIMUM(c1,c2),c3 ); 
                         
                         }
       cout<<b[n]<<" "<<c[n];
       }

Відредаговано Unknown (2011-12-29 13:37:32)

Поза форумом

 

#4 2011-12-29 18:53:28

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Розв’язки задач 2 туру

LVV написав:

А задачу SumOfPowers на 40 баллов решило всего 10 человек!
Интересно, поделится кто-нибудь решением, или нет?

Оновив шапку

Поза форумом

 

#5 2011-12-29 19:16:53

Ilya Porublyov
журі
Зареєстрований: 2005-10-27
Повідомлень: 130

Re: Розв’язки задач 2 туру

Щодо SumOfPowers

Основний алгоритм такий.
Заводимо одновимірний масив DP[] від 0 до maxN (максимального зі згаданих у вхідних даних Ni).
Ініціалізуємо його як DP[i]=i, тому що яким би не був показник K завжди можна набрати i як суму i штук 1^K. Далі перебираємо всі такі основи j, що j^K <= maxN, і для кожного з них дивимося, чи може використання такого степеню зменшити кількість доданків:
DP[i + j^K] = min(DP[i + j^K] ,  DP[i]+1), де i знов-таки перебираються всі можливі.
Після завершення цих (вкладених) циклів, просто виводимо для кожного вхідного Ni відповідний елемент DP[Ni].

АЛЕ!!! Хоча описаний алгоритм формально правильний для всіх можливих вхідних даних, фактично його доцільно використовувати виключно при 3<=K<=19.

При K>=20 відповідь для будь-якого Ni все одно гарантовано буде Ni, тому що навіть 2^K вже більше за Ni.

При K=1 цей алгоритм працюватиме дуже довго, вертаючи для будь-якого Ni гарантовану відповідь 1, бо будь-яке Ni можна подати у вигляді одного доданку Ni^1

Найменш очевидний момент -- при K=2 алгоритм теж працює занадто довго. Треба було знайти у літературі/Інтернеті/ще_де-небудь факт, що будь-яке натуральне число може бути подане у вигляді суми не більш як чотирьох квадратів натуральних чисел, а також ознаки, для яких саме чисел ця кількість буде 1, для яких 2, для яких 3 і для яких 4.

І для K=1 та K=2 доцільно НЕ заповнювати табличку DP, а просто розв"язувати окремо для кожного введеного Ni.


Можливо, в якійсь невеликій мірі все це (різні алгоритми при різних K) і брудний хак. Але, на моє тверде переконання, лише в зовсім невеликій. У значно меншій, ніж, наприклад, масив констант.

Поза форумом

 

#6 2011-12-29 19:40:24

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Розв’язки задач 2 туру

Ilya Porublyov написав:

Можливо, в якійсь невеликій мірі все це (різні алгоритми при різних K) і брудний хак. Але, на моє тверде переконання, лише в зовсім невеликій. У значно меншій, ніж, наприклад, масив констант.

До речі, журі не відстежували, скільки було спроб таки відправити мегабайти захардкоджених відповідей? smile

Поза форумом

 

#7 2011-12-29 20:11:24

Зевс
Новий користувач
Зареєстрований: 2009-11-03
Повідомлень: 62

Re: Розв’язки задач 2 туру

Dim_ov написав:

то маємо асимптотику O(N(1+1/K))

А если k=3? Ведь тогда асимптотика N*N^{1/3} = 10^6 * 10^2 = 10^8. Многовато, разве нет? Или уже решения, которые делают 10^8 операций, принимаются? (безусловно сейчас на неплохих компьютерах/серверах такие решения влазят в 1с, но...).
Лично у меня было написано такое же решение, которое было описано выше Ilya Porublyov, но я подумал, что отправив его, для небольших k в ТЛ оно не влезит.


Может кто-то подсказать, почему код:

#include <iostream>
using namespace std;

int main()
{
  int k, m, n;
  scanf("%d%d", &k, &m);
  for (int i=0; i<m; (i != (m-1)) ? printf(" ") : printf("\n"), ++i) {
    scanf("%d", &n);
    if (k >= 20) printf("%d", n); else
    if (k >= 13) printf("%d", (n/(1<<k)) + (n%(1<<k))); else
    if (k ==  1) printf("1"); else
    printf("0");
  }
}

на некоторых тестах работает больше секунды и получает ТЛ (на онлайн проверке)?

Відредаговано Зевс (2011-12-29 20:16:43)

Поза форумом

 

#8 2011-12-29 20:49:00

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Розв’язки задач 2 туру

Зевс написав:

А если k=3? Ведь тогда асимптотика N*N^{1/3} = 10^6 * 10^2 = 10^8. Многовато, разве нет? Или уже решения, которые делают 10^8 операций, принимаются? (безусловно сейчас на неплохих компьютерах/серверах такие решения влазят в 1с, но...).
Лично у меня было написано такое же решение, которое было описано выше Ilya Porublyov, но я подумал, что отправив его, для небольших k в ТЛ оно не влезит.

Ну, я вирішив не гадати, влізе чи не влізе, а просто спробувати smile І працює воно ~400ms без оптимізацій та ~200ms з -О2. ДП для квадратів працювало, якщо не помиляюся, близько 2-3 секунд, тобто удесятеро довше, ніж для кубів. Що, в принципі й логічно (10^9/10^8=10, зі збільшенням К час зменшується експоненціально). Ну і комп’ютер у мене не самий швидкий(2.33 ГГц). Так що в секунду влазить із запасом навіть на не найсучаснішому сервері.



Чому код отримує ТЛ-и навіть не уявляю smile

UPD: Схоже причина - перемішування введення та виведення. Якщо читати в масив, а потім опрацьовувати - то без ТЛ-ів. Мабуть різні тести по-різному вводяться перевіряючою системою в програму.

Відредаговано Dim_ov (2011-12-29 21:31:01)

Поза форумом

 

#9 2011-12-29 22:43:12

MItornaDOS
Новий користувач
Звідки: Вінницька область
Зареєстрований: 2007-11-08
Повідомлень: 74

Re: Розв’язки задач 2 туру

Хм... я чогось думав що scanf і printf не в iostream, а в stdio.h
у мене цей код навіть не компілиться... а север приймає... і перевіряє
Дивина...

Поза форумом

 

#10 2011-12-30 09:15:23

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Розв’язки задач 2 туру

Dim_ov написав:

Оновив шапку

В Visual Studio 2010 Ваш код SumOfPowers не компилируется. sad

в

Код:

ull fast_pow(ull x,ull power)

ull - не определён. sad

Відредаговано LVV (2011-12-30 11:09:39)


Вік живи - вік навчайся.

Поза форумом

 

#11 2011-12-30 10:34:09

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Розв’язки задач 2 туру

Ilya Porublyov написав:

Щодо SumOfPowers

Основний алгоритм такий...........

Ну, с алгоритмом более-менее понятно.
А нельзя ли увидеть код рабочей программы.
Просто я был уверен в правильности свого решения, но полный набор тестов оно не прошло. И не попричине тайм-лимита, а по причине неверных результатов.
Вот и хотелось бы сравнить и проверить кое-что.
Поскольку полные наборы тестов являются секретом до самого завершения олимпиады, то хотелось бы всё таки хоть один рабочий код полнобальной программы SumOfPowers увидеть, чтобы Новый год встретить спокойно smile

С наступающим! smile


Вік живи - вік навчайся.

Поза форумом

 

#12 2011-12-30 11:01:14

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Розв’язки задач 2 туру

Зевс написав:

Может кто-то подсказать, почему код:

#include <iostream>
using namespace std;

int main()
{
  int k, m, n;
  scanf("%d%d", &k, &m);
  for (int i=0; i<m; (i != (m-1)) ? printf(" ") : printf("\n"), ++i) {
    scanf("%d", &n);
    if (k >= 20) printf("%d", n); else
    if (k >= 13) printf("%d", (n/(1<<k)) + (n%(1<<k))); else
    if (k ==  1) printf("1"); else
    printf("0");
  }
}
на некоторых тестах работает больше секунды и получает ТЛ (на онлайн проверке)?

MItornaDOS написав:

Хм... я чогось думав що scanf і printf не в iostream, а в stdio.h
у мене цей код навіть не компілиться... а север приймає... і перевіряє
Дивина...

У Visual Studio компілює нормально...

Але результати видає абсурдні: навіть на стандпртний тест 2 3 9 17 6 видає три нулі.


Вік живи - вік навчайся.

Поза форумом

 

#13 2011-12-30 12:27:33

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Розв’язки задач 2 туру

LVV написав:

Але результати видає абсурдні: навіть на стандпртний тест 2 3 9 17 6 видає три нулі.

Якщо я все правильно зрозумів, результати і не претендують на правильність. Питання було у тому, чому цей код, який має працювати за О(М), видає ТЛ-и на онлайн-перевірці.

Поза форумом

 

#14 2011-12-30 12:39:50

Зевс
Новий користувач
Зареєстрований: 2009-11-03
Повідомлень: 62

Re: Розв’язки задач 2 туру

Конечно даже на стандартный тест этот код выдает нули, так как это не код рабочей программы smile. Мой код рабочей программы не проходит некоторые тесты по ТЛ, хотя все остальные отрабатывает правильно за 0,01с - 0,02с. И я не могу понять почему. Вот я его и упростил - конечно же теперь все тесты FAILED, только дело в том, что вот такой простой кусок кода на тех же самых тестах получает ТЛ. И не ясно, почему. Я тоже думал, что возможно дело в том, что идет поочередный ввод/вывод, но во-первых большинство-то тестов проходит. А во-вторых чем же это плохо, если программа выводит ответ сразу, а не сохраняет все ответы в массив и потом их выводит. Еще ни на одной олимпиаде, ни на одной проверяющей системе такой проблемы я не встречал. Хотя все-равно довольно странным остается то, что большинство тестов проходят.

Уважаемое Жюри, если проблема действительно в поочередном вводе/выводе, можете написать, пожалуйста, об этом. Мне хотелось бы разобраться с образовавшейся ситуации, чтобы в следующий раз не делать подобных ошибок. Заранее спасибо.

Поза форумом

 

#15 2011-12-30 12:49:09

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Розв’язки задач 2 туру

LVV написав:

Dim_ov написав:

Оновив шапку

В Visual Studio 2010 Ваш код SumOfPowers не компилируется. sad

ull - не определён. sad

випадково видалив трохи зайвого)) Вже має працювати.

Поза форумом

 

#16 2011-12-30 13:03:54

shadybaby
Новий користувач
Зареєстрований: 2011-11-22
Повідомлень: 3

Re: Розв’язки задач 2 туру

LVV
що до SumOfPowers..

введи 3 1 32

що виводить?

Поза форумом

 

#17 2011-12-30 15:45:17

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Розв’язки задач 2 туру

shadybaby написав:

LVV
що до SumOfPowers..

введи 3 1 32

що виводить?

Да Вы прямо мои мысли читаете. smile

Действительно:
32 = 2^3+2^3+2^3+2^3 (4 слагаемых)
А у меня не так.
Выходит, мой алгоритм никудышний, хоть и набрал 11 баллов...)
Спасибо за пример.
С Наступающим!

Відредаговано LVV (2011-12-31 06:51:58)


Вік живи - вік навчайся.

Поза форумом

 

#18 2011-12-31 13:19:11

iama
Новий користувач
Зареєстрований: 2011-12-26
Повідомлень: 3

Re: Розв’язки задач 2 туру

Мій SumOfPowers, надіслав не ту версію і втратив 3 бали sad

Код:

#include <iostream>
#include <set>
#include <cstdio>
#include <cstring>
#include <cmath>

#define MAX_N 1000001

using namespace std;

int mpow (long long a, long long n)
{
    long long  p = 1 % n;

    while (n)
    {
        if (n % 2)
            p = p * a;
        if (n /= 2)
            a = a * a;

        if (p > MAX_N)
            return MAX_N;
    }

    return p;
}

int d[MAX_N], dp[1001], sv[10000], n, m, k, qp, i, j;

int main()
{
    cin >> k >> n;

    for (i = 0; i < n; i++)
        cin >> sv[i];

    if (k == 1)
    {
        cout << '1';

        for (i = 1; i < n; i++)
            cout << " 1";

        cout << endl;

        // return 0; -3 бали тут :(
    }

    if (k == 2)
    {
        char s2[MAX_N] = {}, s3[MAX_N] = {};

        for (i = 1; i <= 1000; i++)
            dp[i] = i*i;

        for (i = 1; i <= 1000; i++)
            for (j = 1; dp[i] + dp[j] < MAX_N; j++)
                s2[dp[i] + dp[j]] = 1;

        for (i = 0; i < n; i++)
        {
            d[sv[i]] = 4;

            int sq = sqrt(double(sv[i]));

            if (sq * sq == sv[i])
            {
                d[sv[i]] = 1;
                continue;
            }

            if (s2[sv[i]])
            {
                d[sv[i]] = 2;
                continue;
            }

            d[sv[i]] = 4;

            for (j = 1; j*j <= sv[i]; j++)
                if (s2[sv[i] - j*j])
                {
                    d[sv[i]] = 3;
                    continue;
                }
        }

        cout << d[sv[0]];

        for (i = 1; i < n; i++)
            cout << ' ' << d[sv[i]];

        cout << endl;

        return 0;
    }

    m = 0;
    for (i = 1; dp[i-1] < MAX_N; i++)
        dp[i] = mpow(i, k), m++;

    d[0] = 0;

    for (i = 1; i < MAX_N; i++)
    {
        d[i] = i;

        for (j = 1; dp[j] <= i; j++)
        {
            qp = d[i - dp[j]] + 1;

            if (d[i] > qp)
                d[i] = qp;
        }
    }

    cout << d[sv[0]];

    for (i = 1; i < n; i++)
        cout << ' ' << d[sv[i]];

    cout << endl;

    return 0;
}

Поза форумом

 

#19 2011-12-31 18:35:04

Unknown
Новий користувач
Зареєстрований: 2011-10-28
Повідомлень: 31

Re: Розв’язки задач 2 туру

iama написав:

втратив 3 бали sad

Можете сказать на каких примерно тестах потеряли? Просто потерял примерно столько, сколько и вы

Поза форумом

 

#20 2011-12-31 18:52:20

iama
Новий користувач
Зареєстрований: 2011-12-26
Повідомлень: 3

Re: Розв’язки задач 2 туру

Unknown написав:

iama написав:

втратив 3 бали sad

Можете сказать на каких примерно тестах потеряли? Просто потерял примерно столько, сколько и вы

Тесты, в которых k = 1, получил RE из-за того, что забыл прерывать выполнение после вывода правильного ответа. Если раскомментировать return 0; - будет заходить в полный балл.

Відредаговано iama (2011-12-31 18:53:12)

Поза форумом

 

#21 2011-12-31 19:08:15

Unknown
Новий користувач
Зареєстрований: 2011-10-28
Повідомлень: 31

Re: Розв’язки задач 2 туру

iama написав:

Тесты, в которых k = 1, получил RE из-за того, что забыл прерывать выполнение после вывода правильного ответа. Если раскомментировать return 0; - будет заходить в полный балл.

Ясно, я не из-за этого точно smile

Поза форумом

 

#22 2012-01-01 12:51:55

valikluks95
Новий користувач
Звідки: Александрия
Зареєстрований: 2010-12-03
Повідомлень: 5

Re: Розв’язки задач 2 туру

Когда будет работать онлайн-проверка? Сейчас выдает "Произошла техническая ошибка"

Поза форумом

 

#23 2012-01-01 14:54:59

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Розв’язки задач 2 туру

valikluks95 написав:

Когда будет работать онлайн-проверка? Сейчас выдает "Произошла техническая ошибка"

Все працює. Перевірте уважно поле "код задачі" перед відправкою.

Поза форумом

 

#24 2012-01-01 15:16:34

valikluks95
Новий користувач
Звідки: Александрия
Зареєстрований: 2010-12-03
Повідомлень: 5

Re: Розв’язки задач 2 туру

Дякую, я був неуважний

Поза форумом

 

#25 2012-01-02 12:39:16

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Розв’язки задач 2 туру

Якщо в умові задачі Sorting "є певна надлишковість", то в умові Platforms є певна, на мою думку, недосказанність.
Вважаючи умову Platforms дуже вдалою, я все таки хотів би зауважити, що хоч стрибки назад і можна вважати вдалою родзинкою задачі, то це лише тому, що ніхто на форумі не поставив питання щодо можливості таких стрибків. А якби таке питання було, то автори (чи журі) були б зобов'язані дати на нього вичерпну відповідь. І тоді ця "таємниця" перестала би бути таємницею. А значить учасники що вже встигли відправити свої рішення опинились би в гірших умовах, ніж ті учасники, що ще не зробили цього (і сдідкують за форумом).
Доречі, учасники, що не встигли прочитати повідомлення "Мимопроходящего", теж опинились в гірших умовах.
Хотів би також відзначити дуже велику розбіжність у складності задач ІІ туру. Порівняти хоча б задачу Sequence з Platforms чи з SumOfPowers.

А взагалі, я хочу подякувати авторам, що умови задач перших двох турів були продуманими, вичерпними і чіткими. Завдяки цому на форумі майже не "ломали списів" стосовно умов завдань, чи результатів туру.
Усіх з Новим роком. smile

Відредаговано LVV (2012-01-02 12:42:00)


Вік живи - вік навчайся.

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt