[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Задача од GeeksForGeeks  XML
Forum Index » Други задачи
Author Message
Perez



Joined: 18/10/2014 18:53:59
Messages: 93
Offline

https://practice.geeksforgeeks.org/problems/challenge-by-nikitasha/0
Пробав да ја решам иако знаев дека однапред со мојата имплементација дека ќе го надминува времето на изврушување па затоа барам помош
MOI



Joined: 07/07/2010 16:31:48
Messages: 446
Offline

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



Joined: 18/10/2014 18:53:59
Messages: 93
Offline

аааа одлична идеја , јас пак цело време кога ги помрднувам се отпочеток ги пресметувам а ова навистина прекрасна идеја со едно множење пута 10 бришење со бришење на крајниот елемент со додавање однапред мхмх вкусно Фала многу
Perez



Joined: 18/10/2014 18:53:59
Messages: 93
Offline

Да не правам нов пост , па тука ќе постирам бидејќи имам задача исто од GeeksForGeeks
https://practice.geeksforgeeks.org/problems/path-in-matrix/0
Еве ја задачата, сакам идеја (не код) , јас мислам да почнам од нулти ред сите елементи да ги поминам така што ќе проверувам надоле
max(dp[i+1][j-1],dp[i+1][j],dp[i+1][j+1])+blabla[i][j] , но се си мислам дека вака нема да даде точен резултат до крај. Па затоа треба да се почне можеби од прв ред па да проверуваме max(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]) ??? ваша идеја
MOI



Joined: 07/07/2010 16:31:48
Messages: 446
Offline

Perezmax(dp[i+1 wrote:[j-1],dp[i+1][j],dp[i+1][j+1])+blabla[i][j] , но се си мислам дека вака нема да даде точен резултат до крај. Па затоа треба да се почне можеби од прв ред па да проверуваме max(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]) ??? ваша идеја

Второто. Со тоа што ќе имаш плус вредноста на полето каде што си - значи најдобриот пат до некое од претходните 3 полиња (од каде што можеш да дојдеш до тековното) плус вредноста на тековното поле.
Еве и код (кога веќе го искуцав) ако треба помош. Ја намалив големината за да не го читаш ако несакаш Ако сакаш, само ископирај го во некој друг документ.

#include <iostream>
using namespace std;

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

while (T--)
{
int N;
cin >> N;

int M[N][N];
for (int r=0; r<N; r++)
for (int c=0; c<N; c++)
cin >> M[r][c];

int best = 0;
for (int r=1; r<N; r++)
for (int c=0; c<N; c++)
{
int value = M[r-1][c];
if (c > 0) value = max(value, M[r-1][c-1]);
if (c+1 < N) value = max(value, M[r-1][c+1]);

M[r][c] = value + M[r][c];

if (r == N-1)
{
best = max(best, M[r][c]);
}
}

cout << best << endl;
}

return 0;
}
Perez



Joined: 18/10/2014 18:53:59
Messages: 93
Offline

Одлично, одлично (благодарам многу за помошта)
https://practice.geeksforgeeks.org/problems/subset-sum-problem/0
Сега за оваа задача треба да се направи матрица сумата на сите елементи и колку елементи
значи sum +=arr[0]+arr[1]+..+arr[n];
и dp[n][sum] ? но дали кодот ќе биде брз ако sum = 100 000 и n=100 ?
Perez



Joined: 18/10/2014 18:53:59
Messages: 93
Offline

Perez wrote:Одлично, одлично (благодарам многу за помошта)
https://practice.geeksforgeeks.org/problems/subset-sum-problem/0
Сега за оваа задача треба да се направи матрица сумата на сите елементи и колку елементи
значи sum +=arr[0]+arr[1]+..+arr[n];
и dp[n][sum] ? но дали кодот ќе биде брз ако sum = 100 000 и n=100 ?

Настрана од ова ме интересира дали MOI учествува на натпреварот или е организатор / професор ?
MOI



Joined: 07/07/2010 16:31:48
Messages: 446
Offline

Perez wrote: дали кодот ќе биде брз ако sum = 100 000 и n=100 ?

Не е многу за компјутер
Како помош, прочитај нешто за knapsack (оваа задача е варијација), и еве мое решение ако заглавиш. Генерално, knapsack (проблем на ранец во литература на македонски) е многу познат проблем, и се среќава во разни задачи (и на натпревари!).
(Инаку, ќе почнам да ти ги бришам прашањава да не ти помагаат и други, оти мислам дека треба прво да ги помислиш задачите сам - така најдобро се учи и најдобро се сфаќа зошто некој алгоритам е корисен или не - ако прашуваш за неколку задачи во ист ден, значи не си потрошил доволно време самиот и ние само ти правиме контра услуга)

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

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

while(T--)
{
int N;
cin >> N;

int dp[100001];
memset(dp, 0, sizeof(dp));

dp[0] = 1;
int sum = 0;

for (int i=0; i<N; i++)
{
int value;
cin >> value;

for (int j=sum; j>=0; j--)
{
if(dp[j])
{
dp[j + value] = 1;
}
}

sum += value;
}

if (sum%2 == 0 && dp[sum/2] == 1)
{
cout << "YES" << endl;
} else
{
cout << "NO" << endl;
}
}

return 0;
}



Perez wrote:Настрана од ова ме интересира дали MOI учествува на натпреварот или е организатор / професор ?

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

This message was edited 1 time. Last update was at 13/02/2018 18:26:48

Perez



Joined: 18/10/2014 18:53:59
Messages: 93
Offline

Фала многу , вака значи, значи DP ми е тешко може да сфатам дел, мм да ,може да не прашам и да не ја решам задачата по 2-3 дена или цела недела да изгубам на една задача
затоа не само hardwork , туку треба нели и smartwork . За да не губам цела недела на една задача одлучив да прашам за неколку задачи како се решаваат, па јас ги разгледувам повеќе време зошто така се решава конкретно DP , а сега вака MOI бидејќи ми помогна многу јас контам веќе малку повеќе DP . Сега решавам истите задачи со мали модификации многу побрзо време бидејќи веќе имам сретнато таква задача. Иначе не ми е целта само copy paste
Perez



Joined: 18/10/2014 18:53:59
Messages: 93
Offline

https://practice.geeksforgeeks.org/problems/equilibrium-point/0
Кодот мој
https://pastebin.com/wPtsEkPz

Input:
42
4 42 27 16 28 3 4 5 9 3 31 5 5 29 10 18 35 35 33 19 41 23 8 32 9 5 8 18 35 13 6 7 6 10 11 13 37 2 25 7 28 43

Its Correct output is:
-1

And Your Code's Output is:
9

Едноставен и глуп алгоритам е што го напишав за секој број зима сума1 од лево и од сума2 од десно и ако бидат еднакви тогаш ...break и да се испечати ...
ThePopivanov



Joined: 24/09/2015 23:17:41
Messages: 16
Offline

И јас иам таков код пишано ама не дозволува врменскиот лимит. Мојот код би требало да работи незнам оти прави проблем.
Perez



Joined: 18/10/2014 18:53:59
Messages: 93
Offline

Де прати .. може во условите е ... while(k>=0 ...
ThePopivanov



Joined: 24/09/2015 23:17:41
Messages: 16
Offline

И твојата надминува временски лимит, ја средив со овој код работи без проблем имав проблем со иницијализацијата

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

main()
{
int N;
cin >> N;
int A[N], zbir = 0;
for(int i = 0; i < N; i++)
{
cin >> A[i];
zbir += A[i];
}
int lz = 0, dz = 0, tr = 0;
for(int i = 0; i < N; i++)
{
if(i-1 >= 0) lz += A[i-1];
dz = zbir - A[i] - lz;

if(dz == lz)
{
tr = i+1;
break;
}
}
if(tr == 0) tr = -1;
cout << tr;
return 0;
}
Perez



Joined: 18/10/2014 18:53:59
Messages: 93
Offline

А да не ми текна вака може да да супер фала
 
Forum Index » Други задачи
Go to:   
Powered by JForum 2.1.8 © JForum Team