Ulanovka Code Challenge - Разбор задач

[0xDEADBEEF]

В этой теме разбор и обсуждение задач контеста. Здесь мы ответим на ваши вопросы.

Архив с тестами, чекерами, настройками сервера здесь

Задача A. Готовимся к празднику

На новогоднем утреннике дети играли в несложную игру. Несколько человек выстраиваются в ряд и держат в руках таблички. На обратной стороне каждой из них написана одна цифра, таким образом ряд школьников в совокупности образует некоторое число К, которое и должны отгадать зрители. Однако в процессе отгадывания числа появилось еще несколько участников, которые хотели бы побыть "ведущими" в этой игре, на что руководство елки дало свое согласие. Чтобы не начинать игру заново и не придумывать новое число, организаторы решили немного изменить правила и в качестве нового числа взять такое, которое было бы кратно первоначальному. При этом необходимо, чтобы таблички достались всем вновь прибывшим школьникам, стоящим в ряду, и чтобы не осталось лишних табличек.

На каждой из табличек можно стереть старую цифру и написать новую. Ваша задача - подобрать такое число Р для "второго" раунда игры.

Формат ввода

Во входном потоке через пробел будут указаны числа К и М – количество школьников в «новом» ряду. K<100000, M<20.

Формат вывода

В выходной поток нужно вывести М - значное натуральное число Р, кратное К. Лидирующие нули не допускаются!

Эта задача на внимательное чтение и сообразительность. В условии задачи явно не сказано, что требуется найти минимальное число, удовлетворяющее заданным требованиям.

Отсюда простое решение:

Если длина требуемого числа равна длине первоначального числа, то выводим это число К. В противном случае можно дописать недостающие нули в конец, полученное число будет заведомо являться кратным К.

#include

using namespace std;

int main(){
int num, r;
cin >>num>>r;

cout < while(num){
num/=10;
r--;
}

while(r--){
cout <<0;
}
}

Задача B. Снежные городки

Как то во время зимних каникул выдался аномально погожий денек. И Ваня с Машей решились выйти на улицу поиграть, позвав с собой соседа Митю. Игра заключалась в следующем: каждый из них собирался построить свой городок - государство на снегу. Ребята уже облюбовали места для постройки главных замков своих городов - зданий городской ратуши, но перед тем как начать постройку, решили очертить границы. Идеальный городок-государство имеет форму круга, причем главный замок должен находиться в самом центре этого круга. Помимо этого, ребята решили, что их города будут дружественными соседями, и решили построить границы, исходя из этого желания. Два городка-государства называются дружественными, если их границы касаются друг друга строго в одной точке(при этом один из них может находиться на территории другого). Также городок-государство не может быть слишком маленьким - радиус полученного круга не должен быть меньше 0,1 метра. Необходимо выяснить, можно ли провести границы с учетом всех этих условий.

Формат ввода

Во входном потоке даны три пары чисел: x1,y1,x2,y2,x3,y3 - координаты трех центров ,будущих главных замков. Все числа целые и по модулю не превышают 10000.

Формат вывода

Если границы с учетом всех вышеприведенных условий провести можно, то вывести радиусы полученных окружностей с точностью до 0,001 (в том же порядке, в котором заданы их центры), в противном случае - вывести три раза -1 через пробел.

В данной задаче необходимо построить три попарно касающиеся окружности с центрами в заданных точках, причем радиусы должны быть не меньше 0.1. Для этого достаточно рассмотреть лишь общий случай, как показано на рисунке.

Если существуют окружности с заданными условиями, то их можно провести таким образом.

Вычислим расстояния между точками:

R(A1,A2), R(A2,A3), R(A1,A3)

Обозначим соответственно искомые радиусы через r1, r2, r3

Тогда можно составить следующую систему уравнений:

r1+r2=R(A1,A2);

r3-r1=R(A1,A3);

r3-r2=R(A2,A3);

Здесь за r3 и А3 мы приняли соответственно радиус и центр большой окружности.

Однако в ходе решения задачи нам может попасться случай, когда не из каждой точки можно провести большую окружность так, чтобы выполнялось условие величины радиуса. В этом случае необходимо рассмотреть все возможные варианты, то есть перебрать все возможные перестановки этих трех точек (соответственно вычисляя при этом новые значения R(A1,A2), R(A2,A3), R(A1,A3) при перестановке). Если ни при каком варианте окружности с радиусами не меньше 0.1 провести нельзя (находим их, решая вышеприведенную систему), выводим -1 -1 -1.

Так же в условии задачи подчеркнуто, что радиусы необходимо выводить в том порядке, в котором даны их радиусы, т.е. в ходе перестановок точек необходимо запоминать состояние текущей конфигурации относительно исходной.

#include
#include
#include
#include
#include
#include
using namespace std;
vector > x,y;
long double r[3],R[3];
long double ro(int a,int {
return sqrt((x[a][0]-x[b][0])*(x[a][0]-x[b][0])+(x[a][1]-x[b][1])*(x[a][1]-x[b][1]));
}
void output(){
long double f[3];
for (int i=0;i<3;i++){
for (int j=0;j<3;j++){
if (y[i][0]==x[j][0]&& y[i][1]==x[j][1]){
f[i]=r[j];
break;
}
}
}
cout<}
int main(){
x.resize(3);
y.resize(3);
for (int i=0;i<3;i++){
x[i].resize(2);
y[i].resize(2);
}
cin>>x[0][0]>>x[0][1];
cin>>x[1][0]>>x[1][1];
cin>>x[2][0]>>x[2][1];
int cnt=0;
for (int i=0;i<3;i++){
y[i][0]=x[i][0];
y[i][1]=x[i][1];
}
for (int j=0;j<6;j++){
R[0]=ro(0,1);
R[1]=ro(0,2);
R[2]=ro(1,2);
r[2]=(R[0]+R[1]+R[2])/2;
r[0]=r[2]-R[1];
r[1]=R[0]-r[0];
cnt=0;
for (int i=0;i<3;i++){
if (r[i]>=0.1) cnt++;
}
if (cnt==3){
output();
break;
}

next_permutation(x.begin(),x.end());
}
cnt=0;
for (int i=0;i<3;i++){
if (r[i]>=0.1) cnt++;
}
if (cnt<3){
cout<<-1<<' '<<-1<<' '<<-1< }
return 0;
}

Задача C. Праздник Серебрянной Луны

В дни старинного эльфийского праздника Серебряной Луны, называемый также САГААЛИАН, все эльфы 80-го уровня ездят друг к другу в гости. Однако на этот праздник всегда выпадает много снега, и дороги между некоторыми деревнями оказались завалены непроходимыми сугробами.

Высший Совет кланов поручил молодому эльфу первого уровня Девелопиану определить, существуют ли пути между наиболее популярными для визитов парами деревень.

Формат ввода

В первой строке входного потока даны три числа: N (2 <= N <= 5000) - количество деревень, M (0 <= M <= 10000) - количество дорог, не заваленных снегом, К (1 <= K <= 100) - количество запросов (количество интересующих Совет пар деревень). В последующих M строках заданы числа Хi и Yi (1 <= Хi , Yi <= N) номера эльфийских деревень, соединенных i-той дорогой. Далее следуют К строк, в каждой из которых дано два числа - (1 <= Аi , Вi <= N) - номера деревень, для которых нужно определить, можно ли эльфам этих деревень беспрепятственно встретиться.

Формат вывода

В выходной поток необходимо вывести К строк, в каждой из которых должно находиться одно слово - "YES", если по заданным дорогам можно добраться из деревни в деревню , и "NO" - в противном случае.

Задан граф, необходимо проверить 2 вершины на связанность. Это можно сделать 3 различными способами:

1. Пустить поиск в глубину (DFS) из одной вершины. Если при обходе вторая вершина будет найдена, то YES, иначе NO.

(подробно http://ru.wikipedia.org/wiki/DFS)

2. Тоже самое, только обходить граф в ширину (BFS).

(подробно http://ru.wikipedia.org/wiki/Поиск_в_ширину)

3. Используя правило треугольника, выяснить связанна ли каждая пара вершин.

Из 2х вариантов предпочтительный первый, как самый быстрый и легкий в кодировании.

Существует также решение, использующее on-line построение дерева достижимости

либо систему непересикающихся множеств.

#include
#include
#include

using namespace std;

int n,m,k,a,b;
vector > graph;
vector mark;

void input(){
cin >> n >> m >> k;
--a;
--b;
graph.resize(n);
int u, v;
for(int i=0; i cin >> u >> v;
--u; --v;
graph[u].push_back(v);
graph[v].push_back(u);
}

}

bool dfs(int start, int target){
if(start == target)
return true;
if(mark[start])
return false;
mark[start]=true;
bool ans=false;
for(int i=0; i ans = ans || dfs(graph[start][i], target);
return ans;
}

int main(){
input();
mark.resize(n);
for(int i=0; i cin >> a >> b;
--a;
--b;
fill(mark.begin(), mark.end(), false);
cout << (dfs(a,?"YES":"NO") << endl;
}
}

#include
#include

using namespace std;

vector used;
int n,m,k;
vector > g;

void dfs(int v){
used[v]=true;
for (int j=0;j if (!used[g[v][j]]){
dfs(g[v][j]);
}
}

}

int main(){
cin>>n>>m>>k;
g.resize(n);
used.resize(n);
for (int i=0;i int a,b;
cin>>a>>b;
g[a-1].push_back(b-1);
g[b-1].push_back(a-1);
}
for (int t=0;t int a,b;
used.assign(n,false);
cin>>a>>b;
dfs(a-1);
if (used[b-1]){
cout<<"YES"< }
else{
cout<<"NO"< }
}
return 0;
}

Задача D. Ледяной шпиль

Стена ледяного городка состоит из столбиков различной высоты (высота каждого столбика измеряется целым числом), но с одинаковыми шириной и длиной, равными единице.

Ваня и Маша решили построить у себя во дворе ледяной шпиль, для этих целей они решили позаимствовать ледяные столбики из ледяного городка. Шпиль получается установкой столбиков друг на друга.

Сторож ледяного городка дядя Петя разрешил Ване и Маше забрать любое количество столбиков с одним условием: чтобы периметр профиля стены (см. рисунок - периметр обозначен жирной линией и равен 24) после изъятия столбиков Ваней и Машей составлял не менее половины от первоначального.

После того, как Ваня и Маша вытаскивают из стены все столбики, они сдвигают оставшиеся справа налево, не изменяя порядок их следования, так, чтобы в стене не оставалось пустот.

Помогите Ване и Маше выбрать такие столбики, чтобы у них получился шпиль максимальной высоты и, одновременно, было выполнено условие сторожа дяди Пети.

Формат ввода

В первой строке входного потока содержится целое число n одержится целое число n (1 <= n <= 50) - количество столбиков в стене ледяного городка.

Во второй строке содержится n целых чисел hi (1 <= hi <= 100) - высоты столбиков, столбики рассматриваются слева направо.

Формат вывода

В первой строке выходного потока необходимо вывести одно целое число S — общую высоту столбиков, из которых составлен шпиль.

Данная задача решается при помощи динамического программирования. Будем решать следующую задачу: выберем какие столбики нам оставить таким образом, чтобы периметр оставшейся стены был не меньше половины исходного периметра, и при этом суммарная высота столбиков была как можно меньше, чтобы нам можно было унести как можно больше.

Сперва необходимо подсчитать следующие вещи:

1.периметр всей стены.

2.В массиве total [t] запоминаем значения суммарной высоты столбиков, начиная от 1-го до t-го включительно.

3.Также для каждого «куска» забора считаем следующие величины: wh[t][j], wp[t][j]. Здесь t — номер начального столбика в «куске», j — номер последнего столбика в куске.

Далее следует непосредственно сама динамика: заведем массив p[j][k], где будем хранить максимальное значение из периметров всех возможных наборов кусков, для которых j — номер последнего столбика в последнем куске, а k — суммарный вес всего набора. При этом мы рассматриваем только такие наборы, в которых между кусками есть хотя бы один «просвет», в противном случае мы могли бы рассматривать один сплошной кусок вместо двух примыкающих друг к другу. Это делается для экономии времени.

for j:=1 to n do
for i:=1 to j do
for k:=wh[i][j] to total[j] do
for j1:=i-2 downto 1 do
if (p[j1][k-wh[i][j]]>0) and
(p[j][k]

p[j][k]:=p[j1][k-wh[i][j]]+wp[i][j]-2*min(h[i],h[j1]));

Здесь min(a, — функция, дающая минимум из двух чисел, ее будет полезно написать.

Далее мы действуем по следующему принципу: проверяем всю полученную таблицу p[j][k], для всех значений этой таблицы, которые больше либо равны половине исходного периметра, выбираем значение с наименьшим k (что и описывалось в самом начале разбора этой задачи).

Ответом данной задачи будет разность между суммарной высотой исходного забора и данным полученным минимальным значением k. число будет заведомо являться кратным К.

#include
#include
#include
#include
using namespace std;

typedef struct{
int kol,beg,end,d,p;
} slice;

int n,P=0,maxP,total[50];
vector h;
vector > work;
int f[50][5001],pr[50][5001],is[50][5001];

int Abs(int x){
if (x<0) return -x;
return x;
}

void make_slices(){
work.resize(n);
int h0=0;
for (int i=0;i P+=Abs(h[i]-h0)+2;
h0=h[i];
slice s;
s.beg=i;
s.end=i;
s.kol=1;
s.d=h[i];
s.p=2*h[i]+2;
work[i].push_back(s);
for (int j=i+1;j s.end=j;
s.kol+=1;
s.d+=h[j];
s.p=s.p-h[j-1]+Abs(h[j]-h[j-1])+2+h[j];
work[j].push_back(s);
}
}
P+=h[n-1];
total[0]=h[0];
for (int i=1;i total[i]=total[i-1]+h[i];
}
}

void solve(){
for (int j=0;j for (int i=0;i<=j;i++){
f[j][work[j][i].d]=work[j][i].p;
pr[j][work[j][i].d]=-1;
is[j][work[j][i].d]=i;
for (int k=work[j][i].d;k<=total[j];k++){
for (int jj=i-2;jj>=0;jj--){
if (f[jj][k-work[j][i].d]>0 && f[j][k] f[j][k]=f[jj][k-work[j][i].d]+work[j][i].p-2*min(h[i],h[jj]);
pr[j][k]=jj;
is[j][k]=i;
}
}
}
}
}
}
void input(){
cin>>n;
h.resize(n);
for (int i=0;i cin>>h[i];
}
for (int j=0;j for (int k=0;k<=total[j];k++){
pr[j][k]=-1;
}
}
}
int main(){
input();
make_slices();
maxP=P%2 ? P/2+1 : P/2;
solve();
int minj=0,mink=total[n-1]+1;
for (int j=0;j for (int k=1;k<=min(total[j],mink);k++){
if (f[j][k]>=maxP){
if (k mink=k;
minj=j;
}
}
}
}
cout<
return 0;
}

Задача E. Сладкое ассорти

В предновогодние дни фабрика сладостей "Морозко" решила сделать спец. предложение для покупателей - новогоднее ассорти из конфет "Шоколад под елкой". Однако среди сотрудников фабрики начались разногласия по поводу состава этого набора. У всех были разные предпочтения. Они сошлись во мнении, что в коробке должно быть К конфет, но какого именно сорта, они так и не решили. Тогда, так и не получив никакого совместного результата, сотрудники фабрики решили составить все возможные наборы и проголосовать. Однако число всех возможных наборов ассорти может оказаться слишком большим, и тогда покупатели уж точно не дождутся своих лакомств на прилавках до следующего Нового года. Ваша задача - определить число всех возможных наборов конфет. Известно, что в одном наборе не может присутствовать более одной конфеты одного сорта, и что всего фабрика производит N различных сортов конфет.

Формат ввода

Во входном потоке даны два числа: К и N. 1 <= K,N <= 100.

Формат вывода

В выходной поток нужно вывести одно число - количество всех возможных наборов ассорти "Шоколад под елкой" (число следует выводить без лидирующих нулей).

В задаче требуется посчитать количество всевозможных различных наборов, включающих себя k конфет имеющихся n сортов. Дополнительно сказано, что конфета одного типа не может входит в набор более одного раза; т.е. конфета конкретного сорта либо входит в набор, либо нет. Другими словами, требуется посчитать количество всевозможных различных наборов, включающих себя k из n имеющихся конфет, т.е. число сочетаний.

В комбинаторике сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми.

Число сочетаний из n по k равно биномиальному коэффициенту, и может быть посчитано по формуле:

C(n, k) = n!/(n-k)!k!

Этой формулой можно воспользоваться для подсчёта числа сочетаний при небольших значениях n и k. В случае, когда n и k достаточно велики, например до 100, как в условии задачи, для представления значения не хватит разрядности стандартных типов, таких языков программирования как Паскаль или Си. К примеру C(100,50)= 100891344545564193334812497256, что существенно больше максимального значения 32 или 64 битного беззнакового целого типа. Для представления больших чисел в программе нам придется написать свою, т.н. «длинную арифметику». Т.е. написать самим алгоритмы основных арифметических операций. Но в данном случае мы можем не реализовывать деление, вычитание и факториал, а воспользоваться другой – рекуррентной формулой (т.е. считающей значение функции от значения этой же функции, но с другими параметрами), где используется только сложение:

Это тождество позволяет расположить биномиальные коэффициенты для неотрицательных n, k в виде треугольника Паскаля, в котором каждое число равно сумме двух вышестоящих.

C(n, k) = C(n-1, k-1)+C(n-1, k)

Треугольная таблица, предложенная Паскалем в «Трактате об арифметическом треугольнике» (1654). Таблицы для изображения биномиальных коэффициентов были известны и ранее (Тарталье, О. Хайяму и др.).

Прямым, но не совсем подходящим нам в данном случае, отражением рекуррентных функций в языках программирования являются рекурсивные функции.

Мы можем определить её как

function Comb(n,k:integer):TNum;
begin
if (k=0) or (n=k) then
assign_one(Comb)
else
add( Comb(n-1,k-1), Comb(n-1,k), Comb);
end;

TNum – это определённый нами тип длинного числа.

assign_one – это реализованная нами функция присвоения единицы длинному числу, указанному в качестве параметра.

add – это реализованная нами функция сложения длинных чисел, где первые два параметра – слагаемые, а третий – возвращаемая сумма.

Если k=0 или n=k, то решение известно и равно 1.

Как уже говорилось, написание такой рекурсивной функции - не совсем правильный подход, т.к. такая функция будет в процессе работы множество раз вызываться с одни и теми же параметрами, заново считая то, что уже было посчитано. Число лишних вызовов достаточно велико, что хотя бы при k=10 и n=40 программа работает довольно долго и не укладывается в отведённый лимит в 4 секунды.

Решение этой проблемы в том, чтобы запоминать в программе посчитанный ранее результат. Такой подход называется динамическим программированием. Обычно при этом заводят матрицу, где на пересечении n-ой строки и k-го столбца стоит значение функции от n и k.

И инициализируют начальные значения, в «границах»: в программе мы заполним единицами строку матрицы при n=0 и диагональ (n=k).

В нашем случае матрица запомненных значений функции практически представляет собой треугольник Паскаля.

program combination;
const
max_num_pos = 63;
max_n = 100;
max_k = 100;
type
TNum = array[0..max_num_pos] of byte;

var
matr: array[0..max_n,0..max_k] of TNum;
n,k,i,j: integer;

procedure add (var a,b,res: TNum);
var
carry: byte;
i: integer;
begin
carry := 0;
for i:=0 to max_num_pos do
begin
res[i] := (a[i] + b[i] + carry) mod 10;
carry := (a[i] + b[i] + carry) div 10;
end;
end;

procedure assign_one(var a:TNum);
var
i: integer;
begin
a[0] := 1;
for i:=1 to max_num_pos do
a[i] := 0;
end;

procedure print_num(var a:TNum);
var
pos: integer;
begin
pos := max_num_pos;
while a[pos] = 0 do
pos:=pos-1;
while pos<>-1 do
begin
write(a[pos]);
pos:=pos-1;
end;
end;

begin
read(k,n);

for i:=0 to n do
assign_one(matr[i,0]);

for i:=0 to n do
assign_one(matr[i,i]);

for i:=2 to n do
for j:=1 to i-1 do
add(matr[i-1,j], matr[i-1,j-1], matr[i,j]);

print_num(matr[n,k]);
end.

def fact n
n <= 1 ? 1 : n * fact(n - 1)
end

a=gets.split(/\s+/)
k=a[0].to_i
n=a[1].to_i

puts fact(n)/(fact(k)*fact(n-k))

Задача F. Магическая бухгалтерия

Всякий колдун, маг и чародей имеет проблемы с заучиванием сложных заклинаний. И всякий колдун, маг и чародей знает, что сложность заклинания почти никак не коррелирует с его эффективностью. Это знает и начинающий чародей Фрай Бээс Де Ядро не желающий заучивать талмуды сложных магических текстов. По своим субъективным чародейским соображениям он оценивает сложность по принципу: квадрат количества всех слов в тексте заклинания минус сумма квадратов "частот" слов. Частотой слова называется количество его вхождений в текст, а словом одна латинская буква или последовательность латинских букв, символы отличные от латинских букв считаются разделителями. Магические слова не могут быть разделены ничем (даже переводом строки), иначе они утрачивают свою силу. Например, заклинание

wget -P ulanovka.ru --http-user=odmin --http-passwd=CjdcTvYtGfhjkm http://adminka.ulanovka.ru

тянет на 172 балла по шкале Фрая. В нём 14 слов, "http" встречается 3 раза, "ulanovka" и "ru" - 2 раза, и все остальные слова по одному разу:.

Формат ввода

На входном потоке содержится текст заклинания, состоящий из латинских букв, знаков припинания, чисел и других печатаемых символов. Объем текста заклинания не превышает 1,5 мегабайт.

Формат вывода

На выходной поток необходимо вывести одно число - сложность заклинания по шкале Фрая.

Техническая задача. Необходимо было выделить из текста слова - последовательность подряд идущих латинских букв, и построить частотный словарь. Частотный словарь - это пары (слово, количество вхождений в текст).

Один существенный нюанс здесь сотоял в том, что объем входных данных был очень большой и нужно было аккуратно вводить данные (в ччастности не использовать Scanner в Java)

Доступные способы создания частотных словарей:

1. Для тех языков, в которых есть структуры данных на основе сбалансированных бинарных деревьев (например std::map в C++ или TreeMap в Java), либо хэш-таблицы (например tr1::unordered_map в C++ или HashMap в Java) использовать их.

2. Для языков в которых нет таких структур - писать самостоятельно.

http://ru.wikipedia.org/wiki/Хеш-таблица

После постоения необходимо провести вычисления по заданной формуле.

#include
#include
#include

using namespace std;
using namespace tr1;

string get_word(){
char ch;
string str;

cin >>ch;
while(!isalpha(ch) && cin){
ch = cin.get();
}

if (!cin)
return "";

do{
str+=ch;
ch = cin.get();
}while(cin && isalpha(ch));

return str;
}

typedef unsigned long long num_t;
typedef unordered_map dict_t;
typedef dict_t::const_iterator dict_iterator_t;

dict_t dict;
num_t word_num;

int main(){
string word = get_word();
while(word != ""){
word_num++;
dict[word]++;
word=get_word();
}

num_t sum = 0;
for (dict_iterator_t i = dict.begin(); i != dict.end(); ++i){
sum += i->second * i->second;
}

cout <}

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Iterator;

public class F {
char[] data = new char[1<<21];
int len = 0;

void input() throws IOException {

InputStreamReader reader = new InputStreamReader(System.in);

len = reader.read(data);
}

int offs = 0;

boolean isAlpha(char ch){
return (ch>='A' && ch <='Z') || (ch>='a' && ch <='z');
}

String getWord(){
String ret = "";

while(offs < len && !isAlpha(data[offs]) ){
offs++;
}

while(offs < len && isAlpha(data[offs]) ){
ret += data[offs++];
}

return ret;
}

long solve() {
long ans = 0;

HashMap dict = new HashMap();

String word = getWord();
while(word != ""){
ans++;

Long oldVal = dict.get(word);

if(oldVal == null)
dict.put(word, new Long(1));
else
dict.put(word, oldVal+1);

word = getWord();
}

ans*=ans;

Iterator i = dict.values().iterator();
while(i.hasNext()){
long l = i.next();
ans-= l*l;
}

return ans;
}

public static void main(String[] args) throws IOException {
F f = new F();
f.input();
System.out.println(f.solve());
}

}

Задача G. Подарок Деда Мороза

Дед Мороз по долгу службы знает о том, насколько хорошо вел себя в уходящем году каждый ребёнок нашей страны, знает он и о том, кто участвовал в городских, республиканских, российских и международных олимпиадах по математики и программированию. На носу новый год и Дедушка Мороз захотел поощрить самых хороших молодых программистов огромным количеством конфет-ирисок фабрики "АМТА". Таких ребятишек набралось пятнадцать человек, и чтобы никого не обидеть всё количество конфет нужно поделить поровну на всех. Помогите Деду Морозу разделить ириски на всех ребят.

Формат ввода

На входном потоке в одной строке находится длинное натуральное число N (количество ирисок), в десятичной записи которого может присутствовать до 50000 знаков. Лидирующие нули отсутствуют. Требуется определить, делится ли данное число нацело на 15.

Формат вывода

На выходной поток необходимо вывести ответ: слово "YES", если число N делится нацело на 15, слово "NO" - в противном случае.

Дано длинное целое число, необходимо узнать делится ли оно на 15.

Делимость на 15 это одновременная делимость на 3 и на 5. Число делится на 3, если сумма его цифр делится на 3. Число делится на 5 если последняя цифра 0 или 5.

Особенность этой задачи в том, что данное число имеет порядка 50000 знаков, и не влезает не в один целочисленный тип. Поэтому считывать его нужно в массив и проверять по вышеизложенным критериям. Считывание его в LongInt и лобовая проверка на делимось на 15 не является корректной.

#include

using namespace std;

int main(){
char ch;
int sum = 0;
while(cin >>ch){
sum += ch-'0';
}

if ((ch == '0' || ch =='5') && (sum % 3 == 0)){
cout <<"YES"< } else {
cout <<"NO"< }
}

[X-tender]

Задача B:

при этом один из них может находиться на территории другого

В задаче четко написано 1 из них может находиться на территории другого, а не каждый.

Более того, в случае если точки находятся на одной прямой, то существует бесконечное кол-во решений.

Добавлено спустя 10 минут 4 секунды:

Альтернативное решение жюри

Хехъ, а где уравнивание языков? Как-то не совсем честно получается. Более того в моем решении даже меньше операций.

[0xDEADBEEF]

В задаче четко написано 1 из них может находиться на территории другого, а не каждый.

1 из них, так-же как и другой на территории третьего. Условие следует понимать буквально. В случае, если бы только одному - это было бы явно выделенно.

Хехъ, а где уравнивание языков? Как-то не совсем честно получается. Более того в моем решении даже меньше операций.

Давайте определимся: нам нужно решить поставленную задачу, а не написать решение на определенном языке. Язык - это всего лишь инструмент. Качество, размер и другие параметры кода не оцениваются. А решения жюри - это доказательство корректности задачи и возможности решения.

[X-tender]

0xDEADBEEF, да бог с ним. Хотя условие следует понимать БУКВАЛЬНО, а в условии буквально написано 1 из них может находиться на территории другого, а говорится про 3 круга. И самое главное:

Более того, в случае если точки находятся на одной прямой, то существует бесконечное кол-во решений.

Как насчет этого?

Добавлено спустя 1 минуту 40 секунд:

Кроме того, хотелось бы увидеть тесты.

нам нужно решить поставленную задачу

Нужно, но библиотеки нужной не было...

[0xDEADBEEF]

Более того, в случае если точки находятся на одной прямой, то существует бесконечное кол-во решений.

Действительно это так. При любом расположении точек радиусы можно расположить как указанно на рисунке, поэтому другие случаи можно не рассматривать. На эту задачу стоял специальный чекер, который проверял решения на соответствие заданным условиям.

Тесты, чекеры и настройки сервера будут, как только найду место куда их выложить)

Нужно, но библиотеки нужной не было...

Это опять же вопрос выбора инструмента.

[X-tender]

Рекуррентную формулу для числа перестановок, видимо, надо было гуглить...

[Andrej]

Рекуррентную формулу для числа перестановок, видимо, надо было гуглить...

Или вспомнить треугольник Паскаля из школы.

[X-tender]

Andrej, хехъ я универовскую формулу для числа перестановок то выводил сам, т.к. не помнил и не гуглил для чистоты рез-та, а тут школу вспомнить... (12лет прошло со школы то)

Кому интересно, скидываю свои решения на перле:

print length($k*(10**($m-length($k)))+$k)==$m?$k*(10**($m-length($k)))+$k:$k*(10**($m-length($k)))-$k;

($k,$m)=split/\s+/,<>;

($k,$n)=split/\s+/,<>;
if ($k>$n) {print 0;exit(0);}
$s=$d=1;
for($i=0;$i<$k;$i++)
{$s*=$n-$i if $n!=$i;$d*=$i+1;}
printf("%.0f", $s/$d);

while(/([a-zA-Z]+)/ig) {
$w{$1}++;
$c++;
}
}
for my $key ( keys %w ) {$s+=$w{$key}**2;}
print ($c**2-$s);

while($_=<>){

$_=<>;
for(/\d/g){
$b+=$a=$_;
}
print $b%3==0 && $a%5==0?"YES":"NO";

[Andrej]

Кому интересно, скидываю свои решения на перле:

Мне они определенно нравятся. Жаль, что на ACM никогда не было Perl.

[X-tender]

Andrej, ага, очень жаль... Сейчас вообще только с/с++/java... Хотя на http://acm.mipt.ru интересно сорвеноваться еще и между языками.(Мне интересно Perl vs Ruby)

[danger]

МММ, парни, сделайте еще раз контест, тока пораньше))) а то люди же на каникулы ездили, и не смогли принять участие) И задачи подберите другие) я же знаю, вы можете)))