Задача e-olimp.com №1667. Ссылка на засчитанное решение. Вам задан связный ориентированный граф с [latex]N[/latex] вершинами и [latex]M[/latex] ребрами [latex]\left(1\leq N\leq 20000, 1\leq M\leq 200000 \right)[/latex]. Найдите компоненты сильной связности заданного графа и топологически отсортируйте его конденсацию. Входные данные Граф задан во входном файле следующим образом: первая строка содержит числа [latex]N[/latex] и [latex]M[/latex]. Каждая из следующих [latex]M[/latex] строк содержит описание ребра … Continue reading
e-olimp: 694. Минимум в очереди
e-olimp: 694 — Минимум в очереди Постановка задачи На вход программы подается набор операций с очередью. Каждая операция состоит в добавлении или удаления элемента из очереди. После выполнения каждой операции найдите наименьшее число, которое находится в очереди. Сложите все полученные числа и получите ответ. Если после некоторой операции очередь оказалась пуста, то ничего не прибавляйте … Continue reading
e-olimp 6130. Дек неограниченного размера (как список деков)
Как пишет Википедия в статье Double-Ended Queue, есть три основных способа реализации двухсторонней очереди (она же — дек, дека и т.д.): — хранить дек в циклическом буфере и расширять при переполнении (при таком подходе реже нужны расширения); — хранить содержимое дека в массиве, начиная от его центра, и при переполнении расширять массив (например, создавать новый … Continue reading
AA27
Задача: В строке вставить после предпоследнего символа первый и второй символ строки. Если длина строки меньше четырех, то вывести, что это сделать невозможно. [latex]s1[/latex] [latex]s2[/latex] Комментарий qwerty qwertqwy Тест пройден _ qwert y _ qwert _ y Тест пройден qwe — Невозможно выполнить операцию. C++:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include <iostream> #include <string> using namespace std; int main() { string s1, s2; getline(cin, s1); if(s1.length()<4){ cout << "Невозможно выполнить операцию." << endl; } else { s2=s1.substr(0, s1.length()-1); s2+=s1[0]; s2+=s1[1]; s2+=s1[s1.length()-1]; } cout << s2 << endl; return 0; } |
Java:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
import java.util.*; import java.lang.*; import java.io.*; class Ideone { public static void main (String[] args) { Scanner in = new Scanner(System.in); String s1 = in.nextLine(); String s2 = new String(); if(s1.length()<4){ System.out.println("Невозможно выполнить операцию."); } else { s2=s1.substring(0, s1.length()-1); s2+=s1.charAt(0); s2+=s1.charAt(1); s2+=s1.charAt(s1.length()-1); } System.out.println(s2); } } |
Дана строка [latex]s1[/latex]. Переписываем из неё в строку … Continue reading
АА5
В заданной строке удалить все пробелы. Если пробелов не было, выдать сообщение об этом, иначе напечатать количество удаленных пробелов. Ввод Вывод Однажды во дворе стояла ясная погода. Однаждыводворестоялаяснаяпогода. 5 Единство предмета речи — это тема высказывания. Единствопредметаречи—этотемавысказывания. 6 Слово. Слово. Пробелов не было. Код программы:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <iostream> #include <string> using namespace std; int main() { int k=0; string s; getline(cin, s, '\n'); int i=0; for(i ; i<s.length(); i++){ if(s[i]==' ') { k++; s.erase(i, 1); i--; } } cout<<s; if(k==0){ cout<<endl<<"Пробелов не было."; } else{ cout<<endl<<k; } return 0; } |
Вводим строку из стандартного потока ввода. Используем getline. Вводим счетчик пробелов. … Continue reading
e-olimp 4004. Есть ли цикл?
Задача: Дан ориентированный граф. Требуется определить, есть ли в нём цикл. Технические условия: Входные данные: В первой строке вводится натуральное число [latex]N ( N \leq 50)[/latex] — количество вершин. Далее в [latex]N[/latex] строках следуют по [latex]N[/latex] чисел, каждое из которых — «0» или «1«. [latex]j [/latex] -е число в [latex]i[/latex] -й строке равно «1» тогда и только тогда, когда … Continue reading
АА20
Условие: В заданной строке удалить последнюю пару символов «:=», которая найдется в строке. Тесты: Ввод Вывод sdfsd fdg :=sdrgs := :+:=:= sdf FUHIUh := sdfdf sdfsd fdg :=sdrgs := :+:=:= sdf FUHIUh sdfdf фыпва :+вап:=аоап:=вр := в фыпва :+вап:=аоап:=вр в Код программы:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <iostream> #include <string> using namespace std; int main() { string text; // входная строка string subStr ( ":=" ); // искомая подстрока getline ( cin, text ); // считывание входной строки size_t pos = text.rfind( subStr ); // нахождение последней позиции искомой подстроки if ( pos != string::npos ) { text.replace ( pos, subStr.length(), "" ); // замена подстроки } cout << text << '\n'; // вывод результата return 0; } |
Код программы на Java:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
import java.util.*; import java.lang.*; import java.io.*; class SeqApp { public static void main( String[] args ) { String subStr = ":=" ; // искомая подстрока // считывание входной строки Scanner in = new Scanner(System.in); // входная строка String text = in.nextLine(); in.close(); int pos = text.lastIndexOf( subStr ); // нахождение последней позиции искомой подстроки if ( pos >= 0 ) // меняем текст только если нашли подстроку { String left = ""; if ( pos > 0 ) // выделяем левую чать до найденной подстроки, может быть пустой { left = text.substring( 0, pos ); } String right = text.substring( pos + subStr.length() ); // выделяемм правую чать после подстроки text = left + right; // результирующий текст } // вывод результата System.out.println( text ); } } |
Ссылка на ideone.com: https://ideone.com/Z94AwR План программы: … Continue reading
e-olimp 553. Рекурсия
Задача: Рекурсия Решение ссылка на ideone, засчитанное решение на e-olimp
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include<iostream> #include<vector> #include<set> #include<map> #include<string> using namespace std; map<string,set<string>> G; map<string,bool> used; map<string,bool> rec; vector<string> V; void dfs(string cur, string aim){ if(used[cur] || rec[aim]) return; used[cur] = 1; for(auto i = G[cur].begin(); i != G[cur].end(); i++){ if(*i != aim){ dfs(*i,aim); }else{ rec[aim] = 1; return; } } } int main(){ //input int n; cin >> n; for(int i = 0; i < n; i++){ string curVert; cin >> curVert; V.push_back(curVert); int m; cin >> m; while(m--){ string inp; cin >> inp; G[curVert].insert(inp); } if(i != n-1){ string stars; cin >> stars; } } //work for(auto i : V){ dfs(i, i); used.clear(); } for(auto i : V){ cout << i << (rec[i] ? ": YES" : ": NO") << endl; } return 0; } |
Идея решения Можно заметить, что каждая процедура — это вершина ориентированного графа. Чтобы узнать, является ли процедура потенциально рекурсивной, нужно было запустить из неё поиск в глубину и узнать, сможем ли мы прийти к ней вновь. Было решено использовать map<string,set<string>> как структуру для описания графа: … Continue reading
Стек, дек и очередь неограниченного размера
Задачи: Стек, Очередь и Дек Решение: Код для задачи на неограниченный стек:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#include <iostream> #include <string> using namespace std; struct Node{ Node * prev; int x; Node(){prev = nullptr; x = 0;} Node(Node * a, int b){prev = a; x = b;} }; struct stack{ private: Node * Head = nullptr; int Size = 0; public: int size(){ return Size; } void push(int p){ Node * NewHead = new Node(Head,p); Head = NewHead; Size++; } int back(){ if(Size){return Head->x;} else{return 0;} } int pop(){ if(Size){ int x = Head->x; Node * NewHead = Head->prev; delete Head; Head = NewHead; Size--; return x; }else{ return 0; } } void clear(){ while(Size > 0){ Node * NewHead = Head->prev; delete Head; Head = NewHead; Size--; } } }; int main() { stack myStack; while(true){ string s; cin >> s; if(s == "exit"){cout << "bye\n"; break;} else if(s == "push"){ int inp; cin >> inp; myStack.push(inp); cout << "ok\n"; }else if(s == "back"){ if(myStack.size()){ cout << myStack.back() << endl; }else{ cout << "error\n"; } }else if(s == "size"){ cout << myStack.size() << endl; }else if(s == "pop"){ if(myStack.size()){ cout << myStack.pop() << endl; }else{ cout << "error\n"; } }else if(s == "clear"){ cout << "ok\n"; myStack.clear(); } } return 0; } |
Код для задачи на неограниченную очередь:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
#include <iostream> #include <string> using namespace std; struct Node{ Node * prev; int x; Node(){prev = nullptr; x = 0;} Node(Node * a, int b){prev = a; x = b;} }; struct queue{ private: Node * Front = nullptr; Node * Back = nullptr; int Size = 0; public: int size(){ return Size; } void push(int p){ if(Size == 0){ Node * NewNode = new Node(Back,p); Front = NewNode; Back = NewNode; }else{ Node * NewNode = new Node(nullptr, p); Back->prev = NewNode; Back = NewNode; } Size++; } int front(){ if(Size){return Front->x;} else{return 0;} } int pop(){ if(Size){ int x = Front->x; Node * NewNode = Front->prev; delete Front; Front = NewNode; Size--; return x; }else{ return 0; } } void clear(){ while(Size > 0){ Node * NewNode = Front->prev; delete Front; Front = NewNode; Size--; } Front = nullptr; Back = nullptr; } }; int main() { queue Q; while(true){ string s; cin >> s; if(s == "exit"){cout << "bye\n"; break;} else if(s == "push"){ int inp; cin >> inp; Q.push(inp); cout << "ok\n"; }else if(s == "front"){ if(Q.size()){ cout << Q.front() << endl; }else{ cout << "error\n"; } }else if(s == "size"){ cout << Q.size() << endl; }else if(s == "pop"){ if(Q.size()){ cout << Q.pop() << endl; }else{ cout << "error\n"; } }else if(s == "clear"){ cout << "ok\n"; Q.clear(); } } return 0; } |
Код для задачи на неограниченный дек:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 |
#include <iostream> #include <string> using namespace std; struct Node{ Node * prev; Node * next; int x; Node(){prev = nullptr; next = nullptr; x = 0;} Node(Node * a, Node * b, int c){prev = a; next = b; x = c;} }; struct deque{ private: Node * Front = nullptr; Node * Back = nullptr; int Size = 0; public: int size(){ return Size; } void push_back(int p){ if(Size == 0){ Node * NewNode = new Node(Back,Front,p); Front = NewNode; Back = NewNode; }else{ Node * NewNode = new Node(nullptr, Back, p); Back->prev = NewNode; Back = NewNode; } Size++; } void push_front(int p){ if(Size == 0){ Node * NewNode = new Node(Back,Front,p); Front = NewNode; Back = NewNode; }else{ Node * NewNode = new Node(Front, nullptr, p); Front->next = NewNode; Front = NewNode; } Size++; } int back(){ if(Size){return Back->x;} else{return 0;} } int front(){ if(Size){return Front->x;} else{return 0;} } int pop_front(){ if(Size){ int x = Front->x; Node * NewNode = Front->prev; delete Front; Front = NewNode; Size--; return x; }else{ return 0; } } int pop_back(){ if(Size){ int x = Back->x; Node * NewNode = Back->next; delete Back; Back = NewNode; Size--; return x; }else{ return 0; } } void clear(){ while(Size > 0){ Node * NewNode = Front->prev; delete Front; Front = NewNode; Size--; } Front = nullptr; Back = nullptr; } }; int main() { deque D; while(true){ string s; cin >> s; if(s == "exit"){cout << "bye\n"; break;} else if(s == "push_back"){ int inp; cin >> inp; D.push_back(inp); cout << "ok\n"; }else if(s == "push_front"){ int inp; cin >> inp; D.push_front(inp); cout << "ok\n"; }else if(s == "front"){ if(D.size()){ cout << D.front() << endl; }else{ cout << "error\n"; } }else if(s == "back"){ if(D.size()){ cout << D.back() << endl; }else{ cout << "error\n"; } }else if(s == "size"){ cout << D.size() << endl; }else if(s == "pop_front"){ if(D.size()){ cout << D.pop_front() << endl; }else{ cout << "error\n"; } }else if(s == "pop_back"){ if(D.size()){ cout << D.pop_back() << endl; }else{ cout << "error\n"; } }else if(s == "clear"){ cout << "ok\n"; D.clear(); } } return 0; } |
Засчитанные решения на сайте e-olimp: Стек, Очередь и Дек. Идея решения: Каждый элемент в структуре должен хранить информацию о предыдущем и последующем. Для этого была организована структура Node. Для … Continue reading
e-olimp 693. Минимум в стеке
Задача e-olimp.com №693. На вход программы подается набор операций со стеком. Каждая операция состоит в добавлении или удалении элемента из стека. После выполнения каждой операции найдите наименьшее число, которое находится в стеке. Сложите все полученные числа и получите ответ. Если после некоторой операции стек оказался пуст, то ничего не прибавляйте к ответу. Если выполнить удаление … Continue reading
e-olimp 6124. Стек неограниченного размера
Стек неограниченного размера Реализуйте структуру данных «стек«. Напишите программу, содержащую описание стека и моделирующую работу стека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы: push n Добавить в стек число n (значение n задается после команды). … Continue reading
АА24
Задача Ввести строку S и целое положительное число N, а также символы C1 и С2. Заменить каждое вхождение символа C1 на N символов C2. Тесты Данная строка C1 C2 n Получаемая строка Комментарий a111a111 a = 3 ===111===111 пройден omnomnom n — 1 om-om-om пройден Nina N Z 1 Zina пройден Решение Мы идем по … Continue reading
AA1
Задача. В заданной строке заменить подряд идущие пробелы на один пробел. Тесты: Ввод Вывод Комментарий as fg t as fg t Пройден rty g uio rty g uio Пройден
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include <iostream> #include <string> using namespace std; int main() { string a; getline(cin,a); string b; b+=a[0]; for (int i=1; i<a.length(); i++) { if ((a[i]!=' ')|| ((a[i]==' ') and (a[i-1]!=' '))) b+=a[i]; } cout<<b; return 0; } |
Решение: Будем записывать подходящие элементы в новую строку. Сразу добавим первый символ, он нам подходит вне зависимости от того, пробел он, или нет. … Continue reading
AA21
Задача. В строке сосчитать количество всех открывающих (квадратных, круглых и фигурных) и закрывающих скобок. Если открывающих скобок на одну больше, добавить закрывающую круглую скобку в конец, а если открывающих скобок на одну меньше, то удалить последнюю закрывающую. Тесты: Ввод Результат Комментарий ./main «({){« «({){« Пройдено ./main «({}){« «({}){)» Пройдено ./main «)]}]([[« «)]}([[« Пройдено Код программы: … Continue reading
AA3
Задача В заданной строке заменить каждую цифру символом «*». Тест Ввод Вывод a;iejfhu789LKSKJD55ahg7 a;iejfhu***LKSKJD**ahg* 123456789 ********* Q1D2F3G4H5J6K7L8’\ Q*D*F*G*H*J*K*L*’\ Guten Abend!Ich heise Katja. Ich bin 18 Jahre alt Guten Abend!Ich heise Katja. Ich bin ** Jahre alt
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <iostream> #include <string> #include <cctype> using namespace std; int main() { string s, n; char ch; getline(cin, s); for(int i = 0; i < s.length(); i++) { if ( isdigit(s[i])) { n += "*"; } else { n += s[i]; } } cout << n << endl; return 0; } |
Cсылка на программу:http://ideone.com/CoqOFb Решение: Пробежимся по всей строке и проверим каждый символ. Если найдется цифра, то меняем ее … Continue reading
АА22
В строке убрать все запятые, пробелы и точки. Буквы нижнего регистра привести к верхнему. input output Описание ./Task22 «he,.llo,. wo.,.,.,.,r.l. d» HELLOWORLD На входе поступает один параметр в кавычках, вкотором есть пробел. Он убирается программой. ./Task22 2425s,Go.oD b24.ye 2425SGOODB24YE На входе поступает два параметра, пробел между параметрами убирается автоматически (пробел служил разделением между параметрами).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <iostream> #include <string.h> using namespace std; int main(int argc, char* argv[]) { string s=""; if(argc > 1){ for( int i = 1 ; i < argc; i++){ for( int j = 0; j < strlen(argv[i]); j++){ if(argv[i][j]==' '||argv[i][j]=='.'||argv[i][j]==','){ s+=""; }else{ s+=toupper(argv[i][j]); } } } }else{s="Sorry";} cout << s << endl; return 0; } |
АА13
Задача. В заданной строке поменять местами рядом стоящие символы между собой (1 и 2, 3 и 4 и т.д., для строки нечетной длины, последний символ не менять). Тесты. Ввод Вывод Комментарий 123456 214365 Пройден abcde badce Пройден Код.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <iostream> #include <string> using namespace std; int main() { string s; cin >> s; //ввод строки for (int i=1;i<s.length();i+=2) { swap(s[i-1],s[i]); //меняем местами соседние буквы } cout << s; return 0; } |
Используя цикл, проходим по каждому второму символу строки и меняем его с предыдущим. Данный код на … Continue reading
А409
Дана действительная квадратная матрица порядка 9. Вычислить сумму тех из её элементов, расположенных на главной диагонали и выше неё, которые превосходят по величине все элементы, расположенные ниже главной диагонали. Если на главной диагонали и выше неё нету элементов с указанным свойством, то ответом должно служить сообщение об этом. 1 3 1 1 1 1 1 … Continue reading
А810
Дано натуральное число [latex]n (n <= 1000)[/latex]. Записать это число русскими словами (семнадцать, двести пятьдесят три, тысяча и т. д. ). Ход решения очень простой, читаем наше [latex]n[/latex] в тиме [latex]integer[/latex] и проверяем, если оно равно [latex]1000[/latex], то выводим ответ «тысяча», иначе берем число по модулю [latex]100[/latex] и присваиваем(дописываем) строке [latex]s[/latex] значение уже заранее описанного … Continue reading
AA12
Задача. В заданной строке заменить каждую точку или точку с запятой тремя точками подряд. Ввод Вывод asgahra.agargarhah;rehaehraeh.arhreh agerge..sgsgg.g asgahra…agargarhah…rehaehraeh…arhreh agerge……sgsgg…g ;;.grg . . ; ; ………grg … … … … Код программы (C++):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include <iostream> #include <string> using namespace std; int main() { ios::sync_with_stdio(false); string s, t; getline(cin, s); for (int i=0; i<s.length(); i++) { if (s[i]=='.'||s[i]==';') { t+="..."; } else { t+=s[i]; } } cout << t << endl; return 0; } |
Java:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
import java.util.*; import java.lang.*; import java.io.*; class Ideone { public static void main (String[] args) { Scanner in = new Scanner (System.in); String s, t=""; s = in.nextLine(); for (int i=0; i<s.length(); i++) { if (s.charAt(i)=='.'||s.charAt(i)==';') { t+="..."; } else t+=s.charAt(i); } System.out.println(t); } } |
Алгоритм решения: пройдём по всем символам строки от её начала и … Continue reading
Для отправки комментария необходимо войти на сайт.