Республиканская олимпиада по информатике 2013–2014, Этап 2, Тур 2, 8-11 классы

Жеңіс Шоңбаев. Батыс Қазақстан облысы, Орал қаласы, Дарынды балаларға арналған мамандандырылған С. Сейфуллин атындағы №11 облыстық қазақ мектеп-интернат кешені.

Енгізу файлының аты / Имя входного файла: F.in
Шығару файлының аты / Имя выходного файла: F.out
Есептің жауабы файлының аты / Имя файла решения задачи: F.{c,cpp,pas}
Уақыт шектеу / Ограничение по времени: 2 секунд
Жадыға шектеу / Ограничение по памяти: 64 мегабайт

F есебі Төлем

Бүгін Али жергілікті дүкенде C теңгеге сауда жасады. Али ақшаны төлейін деп жатқан кезде сатушы оған “Өтінемін, қайтарымсыз төлеңізші” деді. Алиде құны a1, a2, …, aN теңге болатын N тиын бар. Сіздің тапсырмаңыз Алидің берілген соманы кайтарымсыз төлей алатын немесе алмайтындығын анықтау.

Мәліметтерді енгізу форматы

Енгізу файлының бірінші жолында екі бүтін сан C (1 ≤ C ≤ 1000) және N (1 ≤ N ≤ 15) берілген. Келесі жолда N бүтін сан a1, a2, …, aN (1 ≤ ai ≤ 1000) — Алидің тиындарының құндары берілген.

Мәліметтерді шығару форматы

Егер Али қайтарымсыз төлей алатын болса «YES» деп шығарыңыз. Төлей алмаса «NO» деп шығарыңыз.

Мысал / Пример

F.in F.out Комментарий
10 6
1 20 4 3 11 59 3
8 2 6
YES
NO
1+4+5=10

Задача F Оплата

Сегодня Али в местном магазине сделал покупку за C тенге. Он только хотел расплатится и услышал от продавца фразу “Без сдачи пожалуйста, молодой человек”. У него есть всего N монет достоинств a1, a2, …, aN тенге. Определите, сможет ли он расплатится без сдачи.

Формат входных данных
В первой строке входного файла записаны два целых числа C (1 ≤ C ≤ 1000) и N (1 ≤ N ≤ 15) — общая сумма покупки и количство монет у Али соответсвенно. Во второй строке записаны N целых чисел a1, a2, …, aN (1 ≤ ai ≤ 1000)— достоинства монет Али.

Формат выходных данных
В единственной строке выведите слово «YES», если Али сможет расплатится без сдачи. Иначе, выведите «NO»

var f:boolean;

n,i,sum:integer;
a:array[1..15] of integer;
procedure recurs(i:integer; sum:integer);
var j:integer;
begin
if sum=0 then f:=true
else begin
for j:=i to n do
begin
if sum>0 then recurs(j,sum-a[j]) else if sum<0 then break;
end;
end;
end;
begin
assign(input,’f.in’);
assign(output,’f.out’);
reset(input);
rewrite(output);
readln(sum,n);
for i:=1 to n do read(a[i]);
recurs(1,sum);
if f=false then writeln(‘NO’) else writeln(‘YES’);
end.

#include <fstream>
using namespace std;

bool f = false;
int n;
int arr[15];

void recurs(int i, int sum){
if (sum == 0) {
f = true;
}
else {
for (int j = i + 1; j < n; j++){
if (sum>0)
recurs(j, sum – arr[j]);
else
if (sum < 0) {
return;
}
}
}
}
int main(){
ifstream in(“F.in”);
ofstream out(“F.out”);
int sum;
in >> sum >> n;
for (int i = 0; i < n; i++)
in >> arr[i];

recurs(-1, sum);

if (f == false) out << “NO”; else out << “YES”;
return 0;
}

 

Енгізу файлының аты / Имя входного файла: D.in
Шығару файлының аты / Имя выходного файла: D.out
Есептің жауабы файлының аты / Имя файла решения задачи: D.{c,cpp,pas}
Уақыт шектеу / Ограничение по времени: 2 секунд
Жадыға шектеу / Ограничение по памяти: 64 мегабайт

D есебі Үш сан

N бүтін саннан тұратын а1, а2, …, an тізбегі берілген. Сізге осы тізбекте қосындысы нөлге тең болатын үш санның бар немесе жоқ екендігін тексеру керек.

Мәліметтерді енгізу форматы
Енгізу файлының бірінші жолында бір бүтін сан N (1 ≤ N ≤ 200) берілген. Келесі жолда
N бүтін сан a1, a2, …, aN ( - 1000 ≤ ai ≤ 1000) — тізбек элементтері берілген.
Мәліметтерді шығару форматы
Егер тізбекте қосындысы нөлге тең үш сан болса «YES» деп шығарыңыз. Егер болмаса «NO» деп шығарыңыз.

Мысал / Пример

D.in D.out Комментарий
64 14 -6 2 1 22
4
4 -9 2 -1
YES
NO
(4) + (-6) + (2) = 0

Задача D Три числа

Дан массив из N целых чисел а1, а2, …, an. Вам нужно проверить, есть ли в этом массиве три числа сумма которых равна нулю.

Формат входных данных
В первой строке входного файла содержится одно целое число N (1 ≤ N ≤ 200). Во второй строке находятся N целых чисел a1, a2, …, aN ( - 1000 ≤ ai ≤ 1000) — элементы массива.
Формат выходных данных
В единственной строке выходного файла выведите одно слово «YES», если в этом массиве есть три числа сумма которых равна нулю. Иначе, выведите «NO».

var i,j,l,n:integer;
a:array[1..200] of integer;
label 1;
begin
assign(input,’d.in’); reset(input);
assign(output, ‘d.out’); rewrite(output);
readln(n);
for i:=1 to n do read(a[i]);
for i:=1 to n-2 do
for j:=2 to n-1 do
for l:=3 to n do
if a[i]+a[j]+a[l]=0 then begin writeln(‘YES’); goto 1; end;
writeln(‘NO’);
1:end.

Енгізу файлының аты / Имя входного файла: E.in
Шығару файлының аты / Имя выходного файла: E.out
Есептің жауабы файлының аты / Имя файла решения задачи: E.{c,cpp,pas}
Уақыт шектеу / Ограничение по времени: 2 секунд
Жадыға шектеу / Ограничение по памяти: 64 мегабайт

E есебі Кері алмастыру

N саннан тұратын алмастыру дегеніміз 1-ден N-ге дейінгі әр сан бір рет кездесетін тізбек.  b1, b2, …, bN алмастыруы a1, a2, …, aN алмастыруына кері алмастыру болу үшін 1-ден N-ге дейінгі барлық i үшін b[ai] = i болу керек. Берілген екі алмастыру үшін екіншісінін біріншісіне кері алмастыру болатынын немесе болмайтынин анықтаңыз.

Мәліметтерді енгізу форматы
Енгізу файлының бірінші жолында бір бүтін сан N (1 ≤ N ≤ 1000) берілген. Екінші жолда
N бүтін сан a1, a2, …, aN (1 ≤ ai ≤ N)— бірінші алмастыру элементтері берілген. Үшінші жолда
N бүтін сан b1, b2, …, bN (1 ≤ bi ≤ N)— екінші алмастыру элементтері берілген.
Мәліметтерді шығару форматы
Егер екінші алмастыру бірінші алмастыруға кері алмастыру болса «YES» деп шығарыңыз. Егер болмаса «NO» деп шығарыңыз.

Мысал / Пример

E.in E.out Комментарий
54 3 1 5 23 5 2 1 44
1 4 3 2
2 1 4 3
YESNO b[a1] = b[4] = 1, b[a2] = b[3] = 2, b[a3] = b[1] = 3, b[a4] = b[5] = 4, b[a5] = b[2] = 5

Задача E Обратная перестановка

Перестановкой из N чисел называется — последовательность чисел, где каждое число от 1 до N встречается ровно один раз. Перестановка b1, b2, …, bN является обратной перестановкой перестановки a1, a2, …, aN , если b[ai] = i для каждого i от 1 до N. Для заданных двух перестановок определите является ли вторая перестановка обратной первой.

Формат входных данных
В первой строке входного файла записано одно целое число N (1 ≤ N ≤ 1000) — размер перестановок. Во второй записаны N целых чисел a1, a2, …, aN (1 ≤ ai ≤ N) — первая перестановка. В третьей строке записаны N целых чисел b1, b2, …, bN (1 ≤ bi ≤ N) — вторая перестановка.
Формат выходных данных
В единственной строке выходного файла выведите одно слово «YES», если вторая перестановка является обратной первой. Иначе выведите «NO».

var i,j,l,n:integer;
a,b:array[1..200] of integer;
label 1;
begin
assign(input,’e.in’); reset(input);
assign(output, ‘e.out’); rewrite(output);
readln(n);
for i:=1 to n do read(a[i]);
for i:=1 to n do read(b[i]);

for i:=1 to n do if b[a[i]]<>i then begin writeln(‘NO’); goto 1; end;
writeln(‘YES’);
1:end.

Check Also

Электрондық күнделікті пайдалану туралы

Электрондық күнделікті пайдалану туралы тамаша бейнесабақ.  Өскембаева Кенже ханымның тамаша бейнесабақтары.

4 комментария

  1. Махсет Ауданов

    F есебінде жауап барлық уақытта дұрыс шыға бермейді. Мысалы, sum=20 n=6 10, 11, 12, 13, 14, 15 сандарын енгізгенде “YES” жауабы шықты. Бұл жерде 20ға тең болатын қосынды жоқ. Алгоритмде қате бар.

  2. Махсет Ауданов

    F есебінде жауап барлық уақытта дұрыс шыға бермейді. Мысалы, sum=20 n=6 10, 11, 12, 13, 14, 15 сандарын енгізгенде “YES” жауабы шықты. Бұл жерде 20ға тең болатын қосынды жоқ. Алгоритмде қате бар.

  3. #include
    using namespace std;

    bool f = false;
    int n;
    int arr[15];

    void recurs(int i, int sum){
    if (sum == 0) {
    f = true;
    }
    else {
    for (int j = i + 1; j 0)
    recurs(j, sum – arr[j]);
    else
    if (sum > sum >> n;
    for (int i = 0; i > arr[i];

    recurs(-1, sum);

    if (f == false) out << "NO"; else out << "YES";
    return 0;
    }
    мына вариантын карап корши……

  4. #include
    using namespace std;

    bool f = false;
    int n;
    int arr[15];

    void recurs(int i, int sum){
    if (sum == 0) {
    f = true;
    }
    else {
    for (int j = i + 1; j 0)
    recurs(j, sum – arr[j]);
    else
    if (sum > sum >> n;
    for (int i = 0; i > arr[i];

    recurs(-1, sum);

    if (f == false) out << "NO"; else out << "YES";
    return 0;
    }
    мына вариантын карап корши……

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Лимит времени истёк. Пожалуйста, перезагрузите CAPTCHA.