Messages posted by: MOI

BATIR wrote:Zdravo. Koga otprilika kje bidat objaveni datumite za natprevarite 2018?

Мислам дека веќе има некои информации, на пример види тука http://cs.org.mk/index.php/natprevari/srednoobrazovanie/regionalennatprevar
Пишува XXVI РЕГИОНАЛЕН НАТПРЕВАР 10.03.2018

Инаку, знам дека денес има состанок поврзан со натпреварите, така да (претпоставувам) ќе бидат објавени посериозни информации, повици до наставниците и слично во текот на следната недела.

Perez wrote:Идеја ? Вајда треба со graphs , или .. ? Поточно тешко ми е да го средам кога оној дел во задачата кога вели ...
„ Уште повеќе, не ни внимавала кој е од лево, а кој е од десно.“

Ако ја решаваш како граф, тоа лево-десно може да го средиш така што ќе го гледаш графот како да е ненасочен (неориентиран).
Нешто вака:

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int k;
vector<int> G[100001];

int vis[100001];
int conn[100001];

int bfs(int from, bool backwards)
{
	int last;
	queue<int> q;

vis[from] = 1;
	q.push(from);

while (!q.empty())
	{
		last = q.front();
		q.pop();

for (int o : G[last])
		{
			if (vis[o] == 0)
			{
				q.push(o);
				vis[o] = true;
				
				if (!backwards)
				{
					conn[last] = o;
				}
				else 
				{
					conn[o] = last;
				}
			}
		}
	}

return last;
}

int main()
{
	cin >> k;
	for (int i=0; i<k-1; i++)
	{
		int f, t;
		cin >> f >> t;
		G[f].push_back(t);
		G[t].push_back(f);
	}

memset(conn, -1, sizeof(conn));
	memset(vis, 0, sizeof(vis));

int last1 = bfs(0, false);
	int last2 = bfs(k, true);

if (conn[last1] == -1)
	{
		//potrebno e da gi povrzeme posledniot element viden koga trgnavme od 0
		//i posledniot element viden koga trgnavme od k
		conn[last1] = last2;
	}
	
	int pos = 0;
	while (pos != k)
	{
		cout << pos << " ";
		pos = conn[pos];			
	}

cout << pos << endl; //pos = k (posledniot element)
	return 0;
}

Јас би ја решавал од десно налево. Нешто вака.

#include <iostream>
#include <string>
using namespace std;

long long MOD = 1000000007;
long long power[1000001];

int main()
{
	int t;
	cin >> t;

while(t--)
	{
		int n, z, k;
		cin >> n >> z >> k;

string s;
		cin >> s;

power[0] = 1;
		for(int i=1; i<=z; i++)
		{
			power[i] = power[i-1] * k;
			power[i] %= MOD;
		}

long long best = 0;
		long long last = 0;

//presmetaj za posledniot substring (potoa kje se dvizhime od desno nalevo)
		for (int l=0; l<z; l++)
		{
			char ch = s[n - l - 1];
			long long deg = power[z - l - 1];

last += (ch * deg);
			last %= MOD;
		}

best = last;
		for (int from=n-z-1; from >= 0; from--)
		{			
			//tuka, razgleduvame substring koj shto e ist kako prethodniot
			//samo go brisheme posledniot znak (najdesniot), i dodavame eden nov (levo)
			long long current = last;

//izbrishi go najdesniot
			current -= ((s[from + z]) * power[z-1]) % MOD;
			current += MOD;
			current %= MOD;

//site ostanati pomnozhi gi so k (toj znak shto prethodno bil so stepen X e sega stepen X+1, itn)
			current *= k;
			current %= MOD;

//dodadi znak od levo
			current += s[from];
			current %= MOD;

last = current;
			best = max(best, current);
		}

cout << best << endl;		
	}

return 0;	
}

boolTrue wrote:Ако може некој hint или предлог за точен алгоритам?

Јас вака нешто би пишувал.

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

int solve(set<int> s, int l, int m) {
    int added = 0;

for (int i=1; i<=l; i++) {
            if (s.lower_bound(i - m) != s.end() && *s.lower_bound(i-m) <= i) {
                //blokirano od levo ako ima zgrada pomegju (i-m) i (i)
                continue;
            }

if (s.lower_bound(i) != s.end() && *s.lower_bound(i) <= i+m) {
                //blokirano od desno ako ima zgrada pomegju (i) i (i+m)
                continue;
            }

//inaku, mozhe da stavime zgrada tuka
            added++;
            s.insert(i);
    }

return added;
}

int main() {
    int n, m;
    cin >> n >> m;

int k;
    cin >> k;

set<int> left;
    set<int> right;

for (int i=0; i<k; i++) {
        int b;
        cin >> b;

if (b % 2 == 1) {
            //za da se broevi od 1 pa nagore
            left.insert((b + 1) / 2);
        } else {
            //za da se broevi od 1 pa nagore
            right.insert(b / 2);
        }
    }

int totalRight = n / 2;
    int totalLeft = n - (totalRight);

int result = solve(left, totalLeft, m) + solve(right, totalRight, m);
    cout << result << endl;
    return 0;
}

Од денес, можете да забележите дека МЕНДО користи сигурна комуникација (https) - пред се, од причина што поновите browser-и како Firefox, Chrome (и други) инсистираат на тоа.

Сепак, според Google Analytics, постојат и неколку (невидено) многу стари browser-и од кои се пристапува до МЕНДО (претпоставувам од училишта), па за нив ќе остане да важи стариот начин на комуникација (бидејќи не поддржуваат понови сертификати).
Оваа промена не треба да предизвика никакви потешкотии и не би требало да правите ништо поразлично од она што сте го правеле досега (освен што можеби ќе биде побарано да се најавите повторно на сајтот, бидејќи сега комуникацијата е различна).
Ако забележите некои проблеми со МЕНДО кои се предизвикани од оваа промена, ве молам споделете ја тука или по емаил.

Perez wrote:Точно е се да а некоја друга идеја за помало време извршување ?

Една идеја би била Counting Sort, наместо повикот што го имам до функциите за сортирање. Бидејќи броевите се до 10^5, па можеме да искористиме таков алгоритам со линеарна сложеност.
Ама нема потреба.

Само што го пробав моето решение тука https://practice.geeksforgeeks.org/problems/print-k-smallest-elements-in-their-original-order/0 и поминува. Ако зборуваме за истиот систем.

Perez wrote:Значи идеја прва што ми падна да направам копија од дадената низа ... да ја соритрам по растечки редослед и после да искористам binary search .. ама нешто не ми штима бидејќи ми се повторуваат исти елементи со исти индекс ... де ваша помош малце

Не сум сигурен дека ограничувањава ти се ископирани точно, и дали временскиот лимит дозволува сортирање, ама еве да ја продолжам твојава идеја. Можеби ако чуваш за секој елемент покрај неговата вредност и позицијата, можеш прво да ги подредиш по вредност (за да ги добиеш најмалите), а потоа тие (најмалите) да ги подредиш и по позиција (индекс).
Нешто вака (не тестирав, оти баш и немам време):

Perez wrote:Сугестија : Текстовите на задачите да се што пократки и појасни ( да го нема оној дел кај пример „Мендо и неговите мечињаа дрн дрн си играле со бројки“ ), многу пати со професорот кога решаваме задачи се откажуваме од вакви задачи кај што пола текст е само тоа , бараме кај што се кратки и јасни и прецизни барањата, бидејќи не знам за другите али за мене кажувам дека многу губам време додека ја разберам задачата.

Го разбираме барањево, но МЕНДО е делумно систем за учење а делумно систем за спроведување на натпревари. На меѓународни натпревари постојат и (многу) подолги задачи, така да всушност идејата е да има некаков баланс - и кратки задачи и малку посложени.
Инаку, како (поранешен) натпреварувач, се сложувам со тебе дека пократките задачи се поубави.

Nj1234 wrote:Primer: pisam kod,go ispracam dobivam rezultati od testiranjeto od 1 do 20 i sega mi kazvit pogresen rezultat na 3 mesta kako da vidam kaj se tie greski?

Во најдобар случај, зависно од резултатот кој што ќе го добиеш од системот ("Погрешен одговор", "Надминат временски лимит", итн), ќе успееш самиот да откриеш што е грешката - на пример, ако е надминат временски лимит, потребно е да се напише поефикасен алгоритам и слично. Вака е и на меѓународен натпревар, каде што зависно од добиениот резултат од системот, би знаел дали е задачата точно решена (па можеш да решаваш и други), или дали да продолжиш со подобрување на кодот.

На МЕНДО, имаш и други (неколку) опции (сепак, добро е прво да се обидеш сам да најдеш што грешиш). Прво, можеш во форумот или викито да побараш дали постои решение на задачата со копчето "Пребарај" (на пример). Кај задачите за учење на C++ или алгоритми, дадени се решенијата и директно во задачата, па можеш да ги отвориш со "Види решение". Трето, можеш и да го користиш копчето "Побарај тест случај" за да симнеш одреден тест случај и да го извршиш на твојот компјутер (за да видиш што дава твојата програма наспроти точната, да користиш debugger, и слично).

Perez wrote:Надоградба на компајлерот C++ ставете GNU GCC 7.2.0 има многу нови работи

Тоа најчесто го правиме пред почетокот на натпреварите (таму некаде во февруари), за да не ја менуваме верзијата секој месец.
Инаку да, добра идеја.

Операторот / врши делење со отфрлање на остатокот. Операторот % го враќа остатокот од делењето. Во овој пример, со (k/10) ја бришеме последната цифра од бројот - а потоа, кога веќе имаме број со две цифри, со (% 10) ја земаме последната цифра од тој преостанат број (што е всушност средната цифра од троцифрениот број).
Да видиме преку пример. Нека k = 567. Во овој случај, 567/10 = 56. Потоа, со 56%10 добиваме остаток 6, што е всушност средната цифра од бројот 567 (што се бара во задачата).

P.S. Незнам зошто, ама очигледно не ме послуша дека треба да решаваш, или барем да ги извршиш програмите на твојот компјутер за некои примери, да пробаш што прави еден оператор, што друг и слично. Најдобро ќе сфатиш што како функционира ако решаваш задачи сам (или, ако не можеш сам подолго време и по повеќе обиди, тогаш го отвориш решението и се обидеш да разбереш како функционира некоја програма преку извршуваше за некои пример вредности [567, 456, 123, итн]). Подобро е повеќе време да потрошиш, него само да одиш брзо низ предавањата и задачите само колку да ги завршиш.

Nj1234 wrote:kako da go postavam ogranicuvanjeto X da e pogolem od Y i da koristi broevi od 1 do 100?

Ќе претпоставам дека зборуваш за задачата "Математика" од тренинг делот на МЕНДО. Во тој случај, нема потреба да поставуваш ограничувања или незнам што - тие броеви (1 до 100) означуваат за какви вредности треба да работи твојата програма (на пример, дека X и Y не може да се нула, што означува дека никогаш нема да имаш проблеми со делењето).

Второ, не треба да печатиш пораки како "Vnesi go prviot broj:" итн, туку излезот треба да е еднаков како што е дадено во задачата - т.е. да ги испечатиш само збирот, разликата, множењето и делењето.

Kiko206 wrote:Ај ве молам за помош ми треба ова задача: 11.Да се состави програма во Паскал со која една матрица abc[10x10] ќе се пополни со a во главната дијагонала и под неа,а со y во другите места. Вака некако треба да изгледа https://imgur.com/a/GPy5r

Ова делува како некоја задача за домашно, така да во иднина гледај сам да решаваш.

Nj1234 wrote:Jas sum nov ovde na forumov i vo c++ isto taka gi citam predavanjava solidni se za pocetnici moze da se naucat dosta raboti.Stignav do prvite zadaci nesto uspevam da resam nesto ne,i zabelezav deka treba da cekam dva dena za da vidam resenie od zadacite pa da sogledam kaj gresam a to mi izgledat premnogu dolgo .Ima li nacanin nekako da dojdam do gotovite resenija so cel ne da prepisam tuku da mozam da napravam analiza i sporedba tamu kaj so mi e potrebna bez da cekam dosta dolgo vreme.

Здраво, па има некои ученици кои бараат решение од другар или помош на форумот, или па дури и имаат направено два корисника на мендо (со две различни емаил адреси), но јас искрено сум против тоа. Сепак, како сакаш.

Поентата на чекањето не е за да те кочи во учењето или дека системот не сака/може да го покаже решението, туку да се обидеш сам да ги решиш задачите. Така најдобро се напредува - има луѓе кои само теоретски учат на памет, што е катастрофално - особено во делот со програмирање. Ова не го измислувам сега, туку можеш да најдеш и мислења/искуство од други ученици (без разлика дали сакаш да бидеш натпреварувач или не). Дури, кога решаваш сам, истражуваш (и учиш) и други работи со пребарување на Google и слично.