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


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

Ви не зайшли.

#1 2020-11-08 11:54:06

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

Розв'язок задачі Pillars

Щоб не чекати пів-року можливості побачити правильні розв'язки задач, пропону.ю ділитись ними тут.

Алгоритм:
Проаналізували задачу, встановили залежність між кількістю "стовпів" і "пустот"
https://drive.google.com/file/d/1NvJmGW … sp=sharing

Код:

#include <iostream>
using namespace std;
int main()
{
    long long int N,M;
    cin >> N >> M;
cout << (M==1?N:(N-M+1)*((N-M)/(M-1)  +1)+(1-M)*(1+(N-M)/(M-1))*((N-M)/(M-1))/2); 
return 0;
}

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

Поза форумом

 

#2 2020-11-08 17:20:32

GeniusDP
Олімпієць
Зареєстрований: 2020-10-15
Повідомлень: 18

Re: Розв'язок задачі Pillars

Код:

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int64_t n, m;
    cin >> n >> m;
    if(m==1){
        cout << n;
    }
    else{
        int64_t d, dmax=(n-m)/(m-1), ans=0;
        for(d=0; d<=dmax; d++){
            int64_t len=m + d*(m-1);
            ans+=n-len+1;
        }
        cout << ans;
    }
    return 0;
}
/*
Идея такая: для каждого возможного расстояния между соседними столбиками найдём длину "шаблона". Например, если d=2, m=4 шаблон будет 1001001001 => len=10. А дальше просто сдвигаем его несколько раз вправо, пока не упремся в левый. Ну типа len=3, n=5 получим
[шаблон]00, 0[шаблон]0, 00[шаблон]. Сумма по всем возможным d и будет ответом. По-моему вполне просто.) Не судите строго. Будут вопросы - пишите сюда.

*/

Відредаговано GeniusDP (2020-11-08 17:33:10)

Поза форумом

 

#3 2020-11-08 23:24:57

FordPerfect
Новий користувач
Зареєстрований: 2014-11-15
Повідомлень: 30

Re: Розв'язок задачі Pillars

Код:

#include <cstdio>

using std::scanf;
using std::printf;

int main()
{
    long long M,N;
    scanf("%lld%lld",&N,&M);
    long long K=(M>1?(N-1)/(M-1):1);
    printf("%lld",K*(2*N-(K+1)*(M-1))/2);
    return 0;
}

Поза форумом

 

#4 2020-11-11 18:11:34

andervish
Новий користувач
Зареєстрований: 2011-01-16
Повідомлень: 25

Re: Розв'язок задачі Pillars

python 2.7

Код:

n, m = map(int, raw_input().split())
i = 1
if m != 1:
    i = (n-1)/(m-1)
print i*n-i*(i+1)*(m-1)/2

Кстати, случая m=1 в тестах нет, поэтому такой код тоже набирает максимум.

Код:

n, m = map(int, raw_input().split())
i = (n-1)/(m-1)
print i*n-i*(i+1)*(m-1)/2

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt