> как
Мат.индукция
Прочитай CLRS, а затем дропни все эти олимпиады, все равно от них пользы никакой.
В ВУЗе надо учиться, дискретную математику и алгоритмы знать, а еще лучше опыт олимпиад начиная с 9 класса иметь.
Я эти олимпиады и дрочу, чтобы в ВУЗ поступить, если я возьму 1 место на области, мне 100 баллов по одному из ЦТшных предметов дадут, да и мне гораздо приятнее Писать код, чем делать физику.
>Прочитай CLRS
Спасибо за совет, часто вижу эту книгу, по ходу действительно годная.
>дропни все эти олимпиады
Читай выше.
То есть, мне для задачи выше нужно было знать мат инукцию?
Спасибо, интересная книга
Нахуя тебе это надо? Реальные проблемы на олимпиадную хуйню не разу не похожи. У реальных проблем нет красивого однозначного решения. В реальных проблемах у тебя всегда есть дохуя времени подумать, не надо задротить, ботать ебанутые алгоритмы наперед. Ты можешь несколько дней гуглить, изучать проблему, сравнивать реализации. Можешь написать куски тупо брутфорсом, не заебываясь, а потом переписать. Самое главное, что олимпиадные задачи тренируют тебя только в решении олимпиадных задач. Чтобы уметь писать компилятор, например, надо писать компиляторы по возрастающей сложности начиная с простых. Чтобы кодить графоний надо начинать с текстурированного кубика, и т.д. Ботая задачи ты развиваешь только нахуй ненужный ИРЛ скилл решения олимпиадных задач, и тем самым тратишь время впустую.
Я прекрасно понимаю все то, что ты написал, мне не раз повторяли, что при трудоустройстве всем будет похуй, где ты там что занял, но, как я писал выше, олимпиадное программирование даёт мне сто баллов по ЦТ по какому-то предмету, а это облегчает мое поступление в сотни раз(потому что не нужно будет сдавать физику). Естественно, после главной олимпиады я забью болт на эти задачи и буду заниматься действительно полезными вещами.
ЦТ - это в Беларуси?
А зачем тебе физика, или у вас не сдается информатика?
> ЦТ - это в Беларуси?
Да
> у вас не сдается информатика?
Да
Странно, в РФ уже несколько лет как вузы требуют информатику вместо физики на прогерские специальности.
.
Двачую этого инженера.
Что учат на информатике в вузах?
матан
Наверно, лучше всего спросить тут.
Доставьте задачи на быстрое преобразование Фурье, чтобы я мог их сдать и проверить свой быдлокод.
Доставьте задачи на быстрое преобразование Фурье, чтобы я мог их сдать и проверить свой быдлокод.
> если я возьму 1 место на области, мне 100 баллов по одному из ЦТшных предметов дадут
Давно такие правила? Это же тысячи ебаных стобальников.
Поступал в МГУ в 2008, был первым на области и призером зональной олимпиадки зона Сибирь, шутники, а не то что вы подумали, нихуя мне 100 не поставили.
Какие есть хорошие соревнования типа Google code jam, в которых стоит поучаствовать?
Не обязательно именно в таком олимпиадном формате.
Не обязательно именно в таком олимпиадном формате.
Чот мне думается, что проще будет выучить школьную физику.
Та же всего три раздела:
эм а равно эф
пэ вэ рано ню эр тэ
и равно у делить на эр
Если ты на способен осознать эту хрень, то и погромист из тебя выйдет так себе.
#include <math.h> / sin /
#include <stdlib.h> / abs /
#include <assert.h> / assert /
using namespace std
const int N=2^8;
const double omega=1;
const double pi=3.14
double x[N];
for (int i=0, i<N, i++){
y=sin(pi/(N+1)omega i);
};
double freq[N];
complex<double> spectr[N];
fft(&y,&freq,&spectr,N);
double It=0;
double Iw=0;
for (int i=0, i<N, i++){
assert( ( (freq==omega && abs(spectr)>0 ) || (abs(spectr==0) );
It+=y^2;
Iw+=(abs(spectr))^2;
};
assert(It-Iw==0);
Бля, макба съела звездочки, а я въебал сравнение даблов в сях, но общая идея, надеюсь, ясна: ты идешь на википедию, смотришь все свойства преобразования Фурьи и их и проверяешь.
Таки нет. Где как. И на факультетах в одном институте тоже различается.
Например, в МЭИ на прогерские специальности одного факультета берут только с физикой. А на прогерские специальности другого берут с информатикой. Причем названия у специальностей одинаковые, но там, кажется, учебная программа различается.
> Что учат на информатике в вузах?
> матан
Вот как раз-таки для ОПа нужно прояснить один очень-очень важный момент.
ОП, читай внимательно: в институте, ЛЮБОМ, даже западном, тебя не будут учить писать софт. Никогда. Там из тебя попытаются сделать специалиста-математика-невротъебаться-архитектора, который составляет алгоритмы там, блядь, рисует блок-схе-е-е-емы, блядь... То есть из тебя на вышке будут пытаться сделать специалиста высокого класса, который... ну... архитектор, да. Там будет очень много матана.
Я не учился по прогерской специальности. Но вот у меня сестра поступила в институт на факультет прикладной математики. Им дали задачи по программированию. Ну, я прошу учил, и подумал, что сейчас я там ей все сделаю. Да, блядь. Я охуел. Вот что-то типа твоих этих олимпиадных задач, только посложнее. Хотя мне даже разницу определить трудно.
И вот со всеми этими задачами программист на своей работе не сталкивается вообще. Так что у тебя два стула: идти на другой факультет(ибо ты отобъешь у себя желание прогать и развиваться вообще, у моего друга так же было, говорит, что институт отбил у него вообще все желание и он прогать нормально не может, но программистом работает) и учить прошу параллельно, а потом фрилансить/вкатываться на работку(в прогеры, наслышан, и без дипломов берут, только знания показать нужно), либо второй стул: сдать все это/задрочить физику поступить, в общем, на специальность прогера и мучиться с этим ебучим матаном. Станешь ты прогером или нет, как показывала практика на других, зависит только от тебя.
На ксис собрался штоли? Не иди, подумой.
реально хуйня полная, дрочат как не в себя, нихуя не дадут там, а времени на самообразование не будет
реально хуйня полная, дрочат как не в себя, нихуя не дадут там, а времени на самообразование не будет
лол на ксисе работаешь со второга курса, приходя в универ 5 раз в семестр сдать лабы, алллё.
Щас бы в МЭИ идти на прогера.
Кстати! Мальчик то няшный на ОП-пике.
> учить прошу параллельно, а потом фрилансить/вкатываться на работку
Зачем тогда на вышку поступать?
на военник копить
Щас бы выбирать, где на прогера учиться.
Ну, а что, думаешь, легко будет учить прошу, работая с 9 утра до 9 вечера в каком-нибудь маке? Лучше прикинься типа лингвистом хочешь стать, чтоб предки деньги давали.
По-другому только если ты в свои 18 уже можешь быть джуном или имеешь навыки, чтоб фрилансить.
Ох, жиза...
Чувак, знай, ты не один. У меня та же проблема. Я искренне желаю тебе удачи!
>И как я должен был САМ до этого дойти?
Не уверен, но мб опыт в математике?
не согласен. прелесть олимпиадных задач как раз в след. 2 пунктах (сугубо имхо, конечно):
1) научить анализировать задачу и последовательно идти к решению. легко решать простые алг. задачи, для которых нужно лишь применить существующий алг. гораздо сложнее проанализировать задачу, которая решается не совсем очевидным способом
2) привыкаешь работать под давлением, тк есть временные рамки
ТЫ ХУЙЕСОС ВОТ И ВСЕ
>2)
Хуяк хуяк и в продакшен лишь бы к дедлайну успеть? Прямой путь на галеру
причем тут море. я не говорю, что спортивное программирование единственный ценный опыт. я всего лишь утверждаю, что он помогает развивать вполе полезные скиллы.
Сука, полезные скилы блядь, мой одногруппник бывший, когда одимпиадки писал, вместо того, что бы сидеть и делать нормальный продуманный алгоритм хуярил чудовищные костыли и выигрывал их. В одной задаче было нужно было указать номер строки (причем смещения этой строки тоже считались) в которую входит заданная строка и он сделал свич/кейс на 40 позиций и руками записывал все варианты смещения строки, это был полный пиздец. Я к олимпиадкам после этого с крайним сомнением отношусь, потому что ты либо ты держишь алгоритм в памяти (хотя полезнее знать, в каких случаях его лучше, а там и нагуглить и встроить запросто) либо высираешь стены говнокода
строй свою выборку на одном примере, удачи, чо
Профиты где? Построение архитектуры? Нет времени. Выбор оптимального решения? Нет времени. Ты либо делаешь костыль "лишь бы работало" либо проигрываешь.
Тебе уже выше объяснили, что навыки олимпиадника пригодятся тебе только когда попросят сортировку пузырьком на листочке нарисовать
За примерами к яндексу и гугле сходи. Они олимпиандников любят.
>я хочу задротить и заниматься хуйней, тратить время впустую, чтобы пройти тест, который каждый раз становится все легче. А потом через 4 годика пойти работать на завод.
>Но даже мой организм отказывается от этого. Что мне делать?
Если нравится программировать, то занимайся именно этим а не хуетой, а если нет, то и дальше время впустую трать
вот тебе делать нечего
Двачую ОПа, некоторые задания мало того, что требует неочевидной или крайне изысканной реализации, такещё и имеют какое-то припёзднуто-ебанутное описание, которое умственный инвалид делал, лол
Конечно любят. Можно тешить их чсв работой в "крутой компании" и за счёт этого платить меньше.
Лол. Предоставь-ка, пожалуйста, пруфы того, что прогеры из гугла получают меньше, чем другие.
>С мая начал активно участвовать во всех раундах на Codeforces, в 90% случаев решаю одну задачу, дальше тупо ничего придумать не могу.
кекнул с тебя. Div1 бог итт
В Гугле, Фейсбуке и Амазоне топовые зарплаты. Больше платят только всякие илитные хедж фонды
А причем тут олемпиады по программированию? Тогда тебе надо к олемпиаде по физике готовиться, раз 100 балов по ней хочешь. А даж если не получиться то уже будет легче написать физику.
>И как я должен был САМ до этого дойти?
ты должен быть знать ответ.
>Но я не понимаю, как так можно сидеть и думать?
Иди зубри матешу, мыслитель.
Я часто даже ни одной не могу решить, хотя вкатываюсь в программирование с 2010 года.
>В Гугле, Фейсбуке и Амазоне топовые зарплаты
И чо? Можно макачить сайты на пеашпи и получать огромные для обычного мужика деньги
>Можно макачить сайты на пеашпи и получать огромные для обычного мужика деньги
Нет, нельзя.
Чо нельзя? За 30-40к можно пеашпи макакой пойти. Чем тебе не деньги? Мужики на заводах хуярят годами за 15к, а тут в два раза больше предлагают, а ему все мало.
>Я часто даже ни одной не могу решить, хотя вкатываюсь в программирование с 2010 года.
Ничего удивительно. А ты думал выучишь синтаксис С++ и станешь победителем всех олимпиад? Такое только в аниме бывает.
Вообще не ябу что это за олимпиады по "программированию", но судя по ОП-посту это просто определенные математические задачи, которые нужно уметь распознать. Не зная математику, ты не сможешь решить такую задачу.
>Не зная математику, ты не сможешь решить такую задачу
Там надо знать задротские алгоритмы и уметь их реализовывать. По этой хуйне даже книги пишут, там кормен или кнут.
А вообще только долбоебы и задроты изучают всю эту ебанину: какой нормальный человек будет дрочить все эти графы деревья сортировки? Один хуй, почти никому это еще не пригодилось
>И как я должен был САМ до этого дойти?
ну это обычное дело. дается задача, там хуева туча связей, графики и рисунки, нихуя не ясно, а решение основывается на том, что имеется теорема Сосницкого о произведении радиусов вписанных окружностей.
это обычная хуйня для олимпиадок, там нужна большая теор.подготовка, книжек надо больше читать. найти решение задачи в этой ситуации думанием - это все равно что сделать открытие в этой области за полчаса. просто нереально.
Это интересно и поэтому я изучаю это. Я долбаеб?
>Я долбаеб?
да
Прочти книгу грокаем алгоритмы и забудь об этой хуйне. Иначе скатишься к матанопитухам и те тебя выебут в сраку
>графы деревья сортировки
это не задротство, а обычный курс информатики
>надо знать задротские алгоритмы
для решения олимпиадных задач вполне хватит 2-3 книги, и базовых алгоритмов будет более чем достаточно. гораздо сложнее проанализировать задачу и понять, какие алгоритмы надо применять
>это не задротство, а обычный курс информатики
То-то я вижу, какие понятные книги написаны по алгоритмам, обычный курс информатики, похуй, что требуется знание математики за 3 курс.
>хватит 2-3 книги
Ну найди мне такие книги, чтобы я понял там хотя бы 60%, притом что я могу только в школьную математику
зачем тебе?
бери задачки средней сложности (например TopCoder div 1 250 - div 1 500) решай их, если не сможешь решить за день например, читай едиториал. Очень редко что там какой-то хитровыебнутый алгоритм. Самое сложное что мне попадалось это бипартит матчинг в див1 500, в основном как тебе выше написали - задачи на умение анализировать а не на знание алгоритмов
мимо желтый топкодер
>зачем тебе?
Чтобы не обсираться на собесах
>div 1
Лол, я на кф часто не могу решить почти ни одной задачи из div 2, а ты div 1 советуешь
Надо что-нибудь полегче?
>?
блядь, вопрос не нужен
>И как я должен был САМ до этого дойти?
Никак, надо просто было начать заниматься олимпиадами по математике и программированию с 5-6 класса. Сейчас уже поздно, забудь об олимпиадах
Насчет гугла не знаю, но в яндексе получают меньше, чем другие
ну тогда бери див2 250-500
главное чтобы тебе было СЛОЖНО, нет смысла решать тысячи простых задач.
берешь задачку - думаешь бля пиздец хуй решу, думаешь часа 3 например или день, потом открываешь эдиториал, становится все очевидно. Пишешь код (ОБЯЗАТЕЛЬНО) по эдиториалу. Если там какой-то новый для тебя алгоритм - ок идешь читаешь, разбираешься. Потом читаешь чужие решения (там могут быть крутые техники, полезно посмотреть).
а что сложного? обычное дп
Сука, мне даже самые простые задачи на codeforces даются очень тяжело, даже задачи уровня A почти не решаются.
И что такое эдиториал? Где он?
ну разбор задач типа, после раунда опубликовывают обычно. Если из архива решаешь там где то ссылка есть сбоку на разбор (на кодефорсес)
Ну я разборы читаю всегда, но очень часто совсем ничего не понимаю.
Вот именно они тяжело даются. Особенно задачи на динамику и жадные алгоритмы. Я пытался понять, что это, но везде натыкался на тонны математики и непонятные объяснения.
матиматика нинужна кокко-кококо!
Господа, а есть какой-то смысл решать задачки именно с кф или именно с топкодера? Я решаю на тимусе и вроде норм.
тимус переодически отваливается. буквально недавно он лежал около 2-3 недель
На кф есть разборы и там можно смотреть по тестам, где ты обосрался
в последнее время у меня не показывает тест кейс, из-за которого решение не прошло, если это дорешивание/архив задача
У меня кстати тоже, надеюсь скоро исправят
Ну вот я дошел до этой задачи.
http://codeforces.com/problemset/problem/158/B
Я так понял, ее надо решать перебором сочетаний, типо сочетать 3 и 1, 2 и 2, и.т.д, я пытался что-то написать, но ничего не вышло, я потерял суть решения и обосрался.
Решил посмотреть решения на третьем питоне и вот увидел такое:
count = input()
a,b,c,d = map(input().split().count,['1','2','3','4'])
print(c+d + (max(a-c,0) + b*2 + 3)//4 )
Если первые две строчки мне еще понятны, то вот что делается в третьей? Это какая-то формула или что? Может кто-нибудь объяснить?
Кстати соглашусь с ним
Олимпиадный код выглядит ужасающе, надо только посмотреть на такое решение:
/
ID: jbsu321
PROG: test
LANG: C++
/
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <string>
#include <sstream>
#include <list>
#include <bitset>
#include <ctime>
#define ms(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define CL(a) a.clear()
#define pi (2acos(0))
#define oo 1<<29
#define dd double
#define ll long long
#define ff float
#define MP make_pair
#define EPS 10E-10
#define fr first
#define sc second
#define MAXX 100
#define SZ(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define pall pair<ll,ll>
#define padd pair<dd,dd>
#define paii pair<int,int>
#define ull unsigned long long
#define csprint printf("Case %lld: ", C++)
#define bpc __builtin_popcount
#define REP(i,N) for(i=0;i<N;i++)
#define REV(i,N) for(i=N;i>=0;i--)
#define FOR(i,p,k) for (i=p; i<k;i++)
#define ISS istringstream
#define OSS ostringstream
#define VS vector<string>
#define vi vector<int>
#define vd vector<double>
#define vll vector<long long>
#define SII set<int>::iterator
#define SI set<int>
#define mem(a,b) memset(a,b,sizeof(a))
#define fs first
#define sc second
#define pii pair < int , int >
#define EQ(a,b) (fabs(a-b)<ERR)
#define FORE(i,a) for(typeof((a).begin())i=(a).begin();i!=(a).end();i++)
#define round(i,a) i = ( a < 0 ) ? a - 0.5 : a + 0.5;
#define makeint(n,s) istringstream(s)>>n
#define read() freopen("test.txt","r",stdin)
#define icin3(a,b,c) scanf("%lld%lld%lld", &a, &b, &c)
#define icin2(a,b) scanf("%lld%lld", &a, &b)
#define icin1(a) scanf("%lld", &a)
#define dcin3(a,b,c) scanf("%lf%lf%lf",&a,&b,&c)
#define dcin2(a,b) scanf("%lf%lf",&a,&b)
#define dcin1(a) scanf("%lf",&a)
using namespace std;
//ll Pow(ll B,ll P){ ll R=1; while(P>0) {if(P%2==1) R=(RB);P/=2;B=(BB);}return R;}
int BigMod(ll B,ll P,ll M){ ll R=1; while(P>0) {if(P%2==1){R=(RB)%M;}P/=2;B=(BB)%M;} return (int)R;} /// (B^P)%M
//ll Gcd(ll a,ll b){ if(b==0)return a; Gcd(b,a%b); return;}
///int rrr[]={1,0,-1,0};int ccc[]={0,1,0,-1}; //4 Direction
///int rrr[]={1,1,0,-1,-1,-1,0,1};int ccc[]={0,1,1,1,0,-1,-1,-1};//8 direction
///int rrr[]={2,1,-1,-2,-2,-1,1,2};int ccc[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
///int rrr[]={2,1,-1,-2,-1,1};int ccc[]={0,1,1,0,-1,-1}; //Hexagonal Direction
///int month[]={31,28,31,30,31,30,31,31,30,31,30,31}; //month
//ll fact[] = {1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000,20922789888000,355687428096000,6402373705728000,121645100408832000,2432902008176640000};
ll ncr(ll a, ll b)
{
ll res = 1;
b=max(b,a-b);
for(ll i=b+1 , j=1 ;i<=a ; i++,j++)
res=((resi)/j);
return res;
}
ll npr(ll a, ll b)
{
ll res = 1;
for(ll i=a-b+1; i<=a; i++)
res=i;
return res;
}
string decimal_to_binary(ll cur)
{
string v;
while(cur)
{
v.pb((cur%2)+'0');
cur/=2;
}
return v;
}
long long lcm(ll x, ll y)
{
ll r;
return ((r/x)y);
}
ll power(ll a, ll b)
{
ll ans = 1;
for(int i=0; i<b; i++)ans=a;
return ans;
}
//void factorial(ll mm){fact[0]=fact[1]=1;fact[2]=2;for(int i=3; i<1001; i++)fact=(ifact[i-1])%mm;}
ll vagerMod(ll a, ll b, ll mm){return ((a%mm)(BigMod(b,mm-2,mm)))%mm;}
//9,9+902,9+902+9003,9+902+9003+90004,9+902+9003+90004+900005,9+902+9003+90004+900005+9000006,9+902+9003+90004+900005+9000006+90000007,9+902+9003+90004+900005+9000006+90000007+900000008
ll arrToNumberOfDigits[]={9,9+902,9+902+9003,9+902+9003+90004,9+902+9003+90004+900005,9+902+9003+90004+900005+9000006,9+902+9003+90004+900005+9000006+90000007,9+902+9003+90004+900005+9000006+90000007+900000008};
//int loop1[]={1,1,1,0,0,-1,-1,-1};
//int loop2[]={-1,0,1,-1,1,1,0,-1};
//int color[1000000];
//int cpp[1000000];
pall MV(ll a, ll b, ll c, ll d){pall aa;aa.fr=c-a;aa.sc=d-b;return aa;}
ll CP(ll a, ll b, ll c, ll d){return (ad-b*c);}
//void kmp()
//{
// ll k;
// k=par[0]=0;
// for(ll i=1; i<SZ(str); i++)
// {
// while(k>0&&str[k]!=str)k=par[k-1];
// if(str==str[k])k++;
// par=k;
// }
//}
string cut_leading_zero(string a)
{
string s;
int i;
if(a[0]!='0') return a;
REP(i,SZ(a)-1) if(a!='0') break;
FOR(i,i,SZ(a)) s+=a;
return s;
}
ll T, C=1, N;
void process()
{
int n;vector<int>v;
int c1=0, c2=0, c3=0, ans=0;
cin>>n;
for(int i=0; i<n; i++)
{
int x;
cin>>x;
if(x==4)ans++;
else
{
if(x==1)c1++;
if(x==2)c2++;
if(x==3)c3++;
}
}
ans+=(c2/2);//cout<<ans<<endl;
if(c2%2==1)c2=1;else c2=0;
ans+=min(c1,c3);
int m = min(c1,c3);
c1-=m;
c3-=m;//cout<<"---> "<<ans<<" "<<c1<<" "<<c2<<" "<<c3<<endl;
int y=0;
if(c2==1)y=2;
int z = c1+y;
ans+=(z/4);
if(z%4!=0)
{
ans++;
}
ans+=c3;
cout<<ans<<endl;
sort(all(v));
return;
}
int main()
{
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
process();
return 0;
}
Олимпиадный код выглядит ужасающе, надо только посмотреть на такое решение:
/
ID: jbsu321
PROG: test
LANG: C++
/
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <string>
#include <sstream>
#include <list>
#include <bitset>
#include <ctime>
#define ms(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define CL(a) a.clear()
#define pi (2acos(0))
#define oo 1<<29
#define dd double
#define ll long long
#define ff float
#define MP make_pair
#define EPS 10E-10
#define fr first
#define sc second
#define MAXX 100
#define SZ(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define pall pair<ll,ll>
#define padd pair<dd,dd>
#define paii pair<int,int>
#define ull unsigned long long
#define csprint printf("Case %lld: ", C++)
#define bpc __builtin_popcount
#define REP(i,N) for(i=0;i<N;i++)
#define REV(i,N) for(i=N;i>=0;i--)
#define FOR(i,p,k) for (i=p; i<k;i++)
#define ISS istringstream
#define OSS ostringstream
#define VS vector<string>
#define vi vector<int>
#define vd vector<double>
#define vll vector<long long>
#define SII set<int>::iterator
#define SI set<int>
#define mem(a,b) memset(a,b,sizeof(a))
#define fs first
#define sc second
#define pii pair < int , int >
#define EQ(a,b) (fabs(a-b)<ERR)
#define FORE(i,a) for(typeof((a).begin())i=(a).begin();i!=(a).end();i++)
#define round(i,a) i = ( a < 0 ) ? a - 0.5 : a + 0.5;
#define makeint(n,s) istringstream(s)>>n
#define read() freopen("test.txt","r",stdin)
#define icin3(a,b,c) scanf("%lld%lld%lld", &a, &b, &c)
#define icin2(a,b) scanf("%lld%lld", &a, &b)
#define icin1(a) scanf("%lld", &a)
#define dcin3(a,b,c) scanf("%lf%lf%lf",&a,&b,&c)
#define dcin2(a,b) scanf("%lf%lf",&a,&b)
#define dcin1(a) scanf("%lf",&a)
using namespace std;
//ll Pow(ll B,ll P){ ll R=1; while(P>0) {if(P%2==1) R=(RB);P/=2;B=(BB);}return R;}
int BigMod(ll B,ll P,ll M){ ll R=1; while(P>0) {if(P%2==1){R=(RB)%M;}P/=2;B=(BB)%M;} return (int)R;} /// (B^P)%M
//ll Gcd(ll a,ll b){ if(b==0)return a; Gcd(b,a%b); return;}
///int rrr[]={1,0,-1,0};int ccc[]={0,1,0,-1}; //4 Direction
///int rrr[]={1,1,0,-1,-1,-1,0,1};int ccc[]={0,1,1,1,0,-1,-1,-1};//8 direction
///int rrr[]={2,1,-1,-2,-2,-1,1,2};int ccc[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
///int rrr[]={2,1,-1,-2,-1,1};int ccc[]={0,1,1,0,-1,-1}; //Hexagonal Direction
///int month[]={31,28,31,30,31,30,31,31,30,31,30,31}; //month
//ll fact[] = {1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000,20922789888000,355687428096000,6402373705728000,121645100408832000,2432902008176640000};
ll ncr(ll a, ll b)
{
ll res = 1;
b=max(b,a-b);
for(ll i=b+1 , j=1 ;i<=a ; i++,j++)
res=((resi)/j);
return res;
}
ll npr(ll a, ll b)
{
ll res = 1;
for(ll i=a-b+1; i<=a; i++)
res=i;
return res;
}
string decimal_to_binary(ll cur)
{
string v;
while(cur)
{
v.pb((cur%2)+'0');
cur/=2;
}
return v;
}
long long lcm(ll x, ll y)
{
ll r;
return ((r/x)y);
}
ll power(ll a, ll b)
{
ll ans = 1;
for(int i=0; i<b; i++)ans=a;
return ans;
}
//void factorial(ll mm){fact[0]=fact[1]=1;fact[2]=2;for(int i=3; i<1001; i++)fact=(ifact[i-1])%mm;}
ll vagerMod(ll a, ll b, ll mm){return ((a%mm)(BigMod(b,mm-2,mm)))%mm;}
//9,9+902,9+902+9003,9+902+9003+90004,9+902+9003+90004+900005,9+902+9003+90004+900005+9000006,9+902+9003+90004+900005+9000006+90000007,9+902+9003+90004+900005+9000006+90000007+900000008
ll arrToNumberOfDigits[]={9,9+902,9+902+9003,9+902+9003+90004,9+902+9003+90004+900005,9+902+9003+90004+900005+9000006,9+902+9003+90004+900005+9000006+90000007,9+902+9003+90004+900005+9000006+90000007+900000008};
//int loop1[]={1,1,1,0,0,-1,-1,-1};
//int loop2[]={-1,0,1,-1,1,1,0,-1};
//int color[1000000];
//int cpp[1000000];
pall MV(ll a, ll b, ll c, ll d){pall aa;aa.fr=c-a;aa.sc=d-b;return aa;}
ll CP(ll a, ll b, ll c, ll d){return (ad-b*c);}
//void kmp()
//{
// ll k;
// k=par[0]=0;
// for(ll i=1; i<SZ(str); i++)
// {
// while(k>0&&str[k]!=str)k=par[k-1];
// if(str==str[k])k++;
// par=k;
// }
//}
string cut_leading_zero(string a)
{
string s;
int i;
if(a[0]!='0') return a;
REP(i,SZ(a)-1) if(a!='0') break;
FOR(i,i,SZ(a)) s+=a;
return s;
}
ll T, C=1, N;
void process()
{
int n;vector<int>v;
int c1=0, c2=0, c3=0, ans=0;
cin>>n;
for(int i=0; i<n; i++)
{
int x;
cin>>x;
if(x==4)ans++;
else
{
if(x==1)c1++;
if(x==2)c2++;
if(x==3)c3++;
}
}
ans+=(c2/2);//cout<<ans<<endl;
if(c2%2==1)c2=1;else c2=0;
ans+=min(c1,c3);
int m = min(c1,c3);
c1-=m;
c3-=m;//cout<<"---> "<<ans<<" "<<c1<<" "<<c2<<" "<<c3<<endl;
int y=0;
if(c2==1)y=2;
int z = c1+y;
ans+=(z/4);
if(z%4!=0)
{
ans++;
}
ans+=c3;
cout<<ans<<endl;
sort(all(v));
return;
}
int main()
{
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
process();
return 0;
}
>#define dd double
>#define ll long long
>#define ff float
Там ограничения по символам что ли? Зачем это
Я спрашивал у друга, который пишет так же, говорит, что так быстрее пишется.
Ну а вообще похоже на какой-то пиздец, как до такого можно дойти?
Индукцию, естественно, нужно знать, это же азы. Я рекомендую тебе порешать https://projecteuler.net/ . Там начинается все с совсем простых задачек, тебе будет по силам, и сложность постепенно нарастает, достигая максимума примерно на 200-й задаче. Так ты постепенно натренируешься решать более сложные задачи. Тут опыт нужен, и терпение чтобы его набраться.
>так быстрее пишется
Они что, кодят и продумывают решение одновременно? Эти секунды полной записи что то решают?
Бамп вопросу
возле задачи есть подсказка - жадный алгоритм.
подсчитай кол-во групп в зависимости от кол-ва участников в ней. после этого наиболее жадным образом укомплектуй такси: сначала кол-во групп с 4 челами, потом с 3 и 1 - тк сумма 4, то поместятся в одно такси. потом укомплектую двочки и тд
важно не забывать про крание случаи - наприер, 4 4 3 2 2 2 1 1
такси:
(4) (4) (3 + 1) (2 + 2) (2 + 1 + 1)
да, решают
>(4) (4) (3 + 1) (2 + 2) (2 + 1)
быстрофикс
>после этого наиболее жадным образом укомплектуй такси: сначала кол-во групп с 4 челами, потом с 3 и 1 - тк сумма 4, то поместятся в одно такси. потом укомплектую двочки и тд
Мне вот это тяжело дается, я не могу осилить такой большой объем
Вот начал решать эту задачу:
http://codeforces.com/contest/849/problem/A
И ничего не могу придумать. Вот совсем. Казалось бы, наверное, легкая задача, а я читаю условие и чувствую себя конченным овощем, который ни на что не годен.
Как научиться решать такие задачи, даже самые легкие?
http://codeforces.com/contest/849/problem/A
И ничего не могу придумать. Вот совсем. Казалось бы, наверное, легкая задача, а я читаю условие и чувствую себя конченным овощем, который ни на что не годен.
Как научиться решать такие задачи, даже самые легкие?
Там указан тэг greedy. Значит нужно гуглить что такое жадные алгоритмы, читать задачи по этой теме, разборы. Потом возвращаться к этой задаче и, если она стала понятна, решать и чувствовать удовлетворение, либо же снова гуглить, читать разборы аналогичных задач до просветления.
Может я неправ, но обычно так поступаю.
на самом деле нужно только внимательно прочитать условие и вспомнить четность нечетность.
1) если нужно нечетное кол-во подотрезков с нечетное длинной, то изначальная пос-ть должна иметь нечетную длинну
2) если каждый подотрезок должен начинается и оканчивается с нечетного числа, то и изнач. пос-дь должна первым и посл. числм содержать нечетные числа
но если выполн. 1 и 2 - то сама изнач. пос-ть подходит под решение
собственно нужно проверить на четность длину, первый и последний элементы
В разборе понятнее написано, лучше бы просто ссылку http://codeforces.com/blog/entry/54233 дал.
да по факту тоже самое написано, только на инглише
"Профиты где? Построение архитектуры? Нет времени. Выбор оптимального решения? Нет времени."
Лол, что ты несешь ? Какое время, какая архитектура, какой выбор ? Чаще всего (а особенно у тормоза вроде тебя) будет ситуация, когда ты просто НЕ ЗНАЕШЬ решения, не знаешь, что надо писать и какой должен быть алгоритм. Хотя насчет применения на работе - тут ты близок к истине.
мимо олимпиадник
>Чаще всего (а особенно у тормоза вроде тебя) будет ситуация, когда ты просто НЕ ЗНАЕШЬ решения, не знаешь, что надо писать и какой должен быть алгоритм.
Ну конечно, я же не решаю манязадачи с ебанутыми решениями и велосипедным кодом с читаемостью из ранних нулевых
Читаемость у них адекватная и однозначная, если у тебя с этим проблемы - значит недостаточно умен.
А вообще, хуль ты приперся в олимпиадный тред? Иди решай свои серьезные рабочие проблемы. Тут нет понятия велосипедного кода, он должен лишь решать задачу, а не удовлетворять каким-то твоим требованиям. Переменные называют в одну букву просто для удобства (тк человек прекрасно понимает, какая что обозначает), для меня например при перекате в корпоративную разработку было шоком, что их называют СЛОВАМИ. (но вообще для читаемости это конечно правильно). Ты абсолютно не понимаешь, о чем идет речь. Выбор решения ? Выбор, прости, из чего? Если ты нашел хоть одно, это уже ОЧЕНЬ хорошо, и суть решения не может быть костылем, тк ограничения по памяти и по времени накладываются. Это учит думать своей головой, выдумывать что-то свое. Может помочь в будущем, на каком-нибудь серьезном проекте с хайлоадом.
>Это учит думать своей головой, выдумывать что-то свое
Дальше не читал. Непродуктивная деятельность ничему не учит, потому что ее опыт не может быть применен для решения каких-то продуктивных задач. То есть, грубо говоря, играя в свои олимпиадные игры ты не станешь опытным программистом, ты станешь всего лишь опытным решателем олимпиадных игр
Что такое в сущности олимпиадная задача - это просто паззл
С учетом того, что на собеседованиях во всякие гуглы нужно решать всякие задачки олимпиадного типа, участие в олимпиадах может принести много профита.
Что можно почитать про жадные алгоритмы и динамическое программирование?
>Читаемость адекватная
И часто ты в гуглы собеседуешься?
Бамп вопросу
Ты находишь первое папавшееся решение и уже считаешь его правильным? Ты не продумываешь другие варианты, ведь у тебя нет времени на них, это очень плохая практика
Ну и
>Нормальная читаемость
>Переменные в одну букву
В Гугл пока не собеседовался (хотя рекрутеры зазывают), но собеседовался в Майкрософт и Фейсбук
>собеседовался в Майкрософт и Фейсбук
И чо, тебя взяли или просто посмеялись над тобой?
В оба места взяли - в МС сейчас работаю, скоро перехожу в Фейсбук. В США, если что.
С учетом того, что такие компании делают рабочие визы, для российских разработчиков тема олимпиадного программирования особенно актуальна.
Ну тогда подскажи, что почитать по жадным алгоритмам и динамическому программированию?
Я не знаю, я сам на задачках с leetcode тренировался. Если не мог решить, разбирал чужое решение. Специально не изучал. В олимпиадах я тоже не участвовал, поэтому мне такие задачи даются тяжело, приходится много практиковаться.
После универа были некоторые проблемы со вкатыванием именно туда, куда я хотел. В итоге плюнул и пошел в веб. Взяли на работу почти сразу, язык на котором теперь пишу (сейчас уже главный на проекте, вся хуйня) я учил перед собеседованием часов 5-6 (с нуля). Олимпиадное прошлое помогло и на собеседовании, и при изучении языка. Угораю с историей вкатывальщиков в веб, которые там годами ищут работу и прилагают титанические усилия. С другой стороны, понимаю, что их природа не шибко одарила, поэтому угорать неправильно.
Это так, пример того, как мне помогли олимпиадки.
Зашел на литкод и понял, что со мной что-то не так: не смог осилить даже самую первую задачу Two Sum, пизда, что делать?
Кстати я читал разбор несколько раз, вроде бы понял, но все равно до конца не понимаю.
Я мимо интересующийся, а есть ли программирование без вот этого всего пространственного мышления, чтобы как задрот делать одно и тоже и получать бабосы?
>пространственного мышления
Что за пространственное мышление? Геометрия что-ли, или что?
Ну типа там задачи на переливание сосудов, в какой бочке яд и прочая шиза, чтобы не сталкиваться с этим говном и просто вставлять чужой код в консольку или по книжке делать похожее.
Front end developers use HTML, CSS, and JavaScript to code the website and web app designs created by web designers. The code they write runs inside the user’s browser (as opposed to a back end developer, whose code runs on the web server). Think of it a little like this: the back end developer is like the engineer who designs and creates the systems that make a city work (electricity, water and sewer, zoning, etc.), while the front end developer is the one who lays out the streets and makes sure everything is connected properly so people can live their lives (a simplified analogy, but you get the rough idea). They’re also in charge of making sure that there are no errors or bugs on the front end, as well as making sure that the design appears as it’s supposed to across various platforms and browsers.
О то что надо, даже гугл перевел while the front end developer is the one who lays out the streets как "В то время как разработчик интерфейса - это тот, кто лежит на улицах"
Конкретнее
Как это помогло при изучении языка и как это помогло на собесе, только если сказать "я олимпиадник" и решить задачу с яйцами и 100-этажным зданием
Я тоже работу сразу нашел, но никаких олимпиадок не было
кормен
>не может быть применен для решения каких-то продуктивных задач
ну да, ты не встречаешь таких задач, значит их нет. справедливо
дасгупта
На ввод подаётся натуральное число N(до 10 000) и далее не более N натуральных чисел(каждое число до 1е9). Нужно найти первое натуральное число, которое нельзя представить суммой этих чисел, причём каждое из данных чисел может входить только 1 раз в сумму.
Пример:
Ввод: 4 1 1 1 5; Вывод: 4:
Так вот, решение этой задачи основывается на том, что если у нас имеется некоторый набор чисел (A1, A2, ..., Ak), такие, что можно представить любое число от 1 до их суммы S суммой некоторых этих чисел, то если мы добавим любое число Ak+1 <= S, то предыдущее свойство сохранится, т.е. можно представить любое число от 1 до их суммы, только уже S + Ak+1, суммой некоторых этих чисел.
И как я должен был САМ до этого дойти? Как я должен был связать сумму набора чисел и то, что если добавить число <= этой суммы, то сохранится это свойство? Я просто не могу, у меня уже сил нету, я не помню, когда я решал реально сложную задачу САМ, у меня мотивация после такого тупо на ноль исходит. Вот я вижу, что некоторые пишут: "Я думал над задачей два дня и всё таки решил, ух, сложная задача". Но я не понимаю, как так можно сидеть и думать? Просто перебирать возможные пути решения? Ну, я перебирал. Первая мысль была просто рекурсию, зафигачить, но увидел, что ограничения не позволяют. Динамику тут тоже не впереть. Были ещё несколько бредовых идей, но они не прошли. И вот что мне делать, если все адекватные, на мой взгляд, варианты закончились? Тупо тыкать пальцем в небо и искать такие закономерности, которые даже после чтения разбора у меня в голове не могут уложиться? Может дело в питании, и мой мозг не получает витаминов, или то, что я каждый день 5+ часов ебусь с этими задачами? Сегодня вот проснулся, сел, прочитал эту задачу, ну а дальше вы знаете. И просто настолько апатичное настроение, весь день тупо проспал. И у меня уже появилось подсознательное отвращение к задачам, я боюсь их решать, потому что думаю, что опять нихера не решу, потрачу полтора часа пытаясь выдумать решение, которое не сработает, потом ещё полтора часа буду разбираться в разборе, а потом я уже как выжатый лимон. А мне ведь область брать надо. И вроде бы нет недостатка в практике, скорее даже переизбыток. С мая начал активно участвовать во всех раундах на Codeforces, в 90% случаев решаю одну задачу, дальше тупо ничего придумать не могу. После контеста, всегда с помощью разбора решаю вторую и третью задачу, причём стараюсь по максимуму разобраться, чтобы все моменты для меня были понятны. Анон, помоги советом или просто поддержи, мне будет очень приятно.