Skocz do zawartości

  • 👋 Witaj na MPCForum!

    Przeglądasz forum jako gość, co oznacza, że wiele świetnych funkcji jest jeszcze przed Tobą! 😎

    • ✅ Pełny dostęp do działów i ukrytych treści
    • ✅ Możliwość pisania i odpowiadania w tematach
    • ✅ System prywatnych wiadomości
    • ✅ Zbieranie reputacji i rozwijanie swojego profilu
    • ✅ Członkostwo w jednej z największych społeczności graczy

    👉 Dołączenie zajmie Ci mniej niż minutę – a zyskasz znacznie więcej!

    Zarejestruj się teraz

zagadka prezesa

encoreeFTW

Rekomendowane odpowiedzi

Sopelek997 Weteran

Sopelek997

Opublikowano
Weteran

Sopelek997

Opublikowano

na razie wykminiłem tylko, że suma tych 10 liczb podzielona przez 20 da ilosc diamentow w środkowym pudełku (ale nie wiem czy zawsze). Idę kminić dalej, jak coś znjadę to napisze

 

oczywiście można to robić brute force, ale wątpię, żeby o to docelowo chodziło

 

@edit. Poddaję się na razie, nie mam pojęcia. Siądę jeszcze później do tego.

981841412442977292370.png
Sopelek997 Weteran

Sopelek997

Opublikowano
Weteran

Sopelek997

Opublikowano

mamy zestaw dziesięciu sum par (y1...y10) i liczby w pudełkach (x1...x5) oba posortowane rosnąco

pewne jest to, że

y1 = x1+x2

y2 = x1+x3

 

y9 = x3+x5

y10 = x4+x5

reszta może zależeć od rozkładu liczb. Jednak wydaje mi się, że z tego już można ułożyć coś sensownego, ponieważ występują wszystkie xsy

 

idę myśleć dalej...

@edit #1

 

y2-y1 = x3-x2 //to dużo ułatwia

y10-y9 = x4-x3

czyli wydaje mi się, że najlepiej jak na razie byłoby brute force na x1, x2, x5 (x4 opcjonalnie zamiast x2 Najlepiej rozróżnic, gdzie jest mniejszy przedział, czy między x1,x2, czy miedzy x4,x5)

wiemy też, że

y1/2 < y2/2 < x3 < y9/2 < y10/2

981841412442977292370.png
metin1998 Uczeń

metin1998

Opublikowano
Uczeń

metin1998

Opublikowano

Moje rozwiązanie, zoptymalizowany brute force

 


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

bool contain(int* a, int  {
for (int i=0; i<10; i++)
    if(a[i] ==  return true;

return false;
}

int compare (const void * a, const void * 
{
  return ( *(int*)a - *(int*)b );
}

bool mymemcmp(int *a, int *b, int siz) {
for(int i=0; i < siz; i++)
if(a[i] != b[i]) return false;

    return true;
}

int main()
{
int bb=0;
int tab[10];
for(int i =0; i < 10; i++)
    cin >> tab[i];

qsort(tab,10,sizeof(int),compare);

for( int i0=2; i0 < 4999; i0++)
for( int i1=2; i1 < 4999; i1++)
{
if(contain(tab,i0+i1))
for( int i2=2; i2 < 4999; i2++)
{
if(contain(tab,i1+i2))
if(contain(tab,i0+i2))
for( int i3=2; i3 < 4999; i3++)
{
if(contain(tab,i1+i3))
if(contain(tab,i2+i3))
if(contain(tab,i0+i3))
for( int i4=2; i4 < 4999; i4++){
if(contain(tab, i0 + i4))
if(contain(tab, i1 + i4))
if(contain(tab, i2 + i4))
if(contain(tab, i3 + i4))
   {
       int* newtab = new int[10];
    newtab[0] = i0+i4;
    newtab[1] = i1+i4;
    newtab[2] = i2+i4;
    newtab[3] = i3+i4;
    newtab[4] = i2+i3;
    newtab[5] = i1+i3;
    newtab[6] = i0+i3;
    newtab[7] = i0+i2;
    newtab[8] = i1+i2;
    newtab[9] = i0+i1;
    qsort(newtab,10, sizeof(int), compare);
    if(mymemcmp(newtab,tab,10)) {
        cout << i0 << endl;
        cout << i1 << endl;
        cout << i2 << endl;
        cout << i3 << endl;
        cout << i4 << endl;
        goto out;
    }
    delete newtab;
   }

}
}
}
}
out:

return 0;
}

 

 

PROOF:

http://ideone.com/bJGPSe

Pisze boty do gier WWW na zlecenie.

Sopelek997 Weteran

Sopelek997

Opublikowano
Weteran

Sopelek997

Opublikowano

dla wejścia

9000
8000
6000
7000
8000
5000
10000
7000
6000
4000

nie daje wyniku. (Powinny wyjść liczby 200 razy większe niż w przykładzie nr 2)

w dodatku wykonuje się to prawie 3 sekundy.

Jak chcesz zostać przy takim brute force, to posortuj tą tablicę i użyj przeszukiwnia binarnego

981841412442977292370.png
encoreeFTW Budowniczy

encoreeFTW

Opublikowano
Budowniczy

encoreeFTW

  • Autor
Opublikowano

no wczytuje liczby, sortuje tablice, potem dziele sume tablicy na 20, i mam srodkowa, reszta to tak jak napisal sopelek, no i dziala po czesci xD

w tym na ideone dodalem sobie wypisywanie jeszcze tablicy, bo wydawalo mi sie przez moment ze cos zle jest w niej

mirraseq Specjalista

mirraseq

Opublikowano
Specjalista

mirraseq

Opublikowano

Posortuj sobie pary skrzynek, nazwijmy je od p1 do p10.
Zdaniem prawdziwym będzie wtedy:

 

p1 ≤ p2 ≤ p3 ≤ ... ≤ p10

 

Po ustawieniu w kolejności od najmniejszej do największej skrzynek, które nazwę a, b, c, d i e, zdaniem prawdziwym będzie:

 

a ≤ b ≤ c ≤ d ≤ e

 

p1 ma wartość najmniejszą zatem składa się ze skrzynek, w których jest najmniej diamentów. W tym przypadku w a i b.

p2 zatem musi być sumą skrzynek a i c, ponieważ jest to suma najmniejszej i większej lub równej wartości b.

p3 jest parą skrzynek b i c.

 

Znamy wartości dla trzech pierwszych, najmniejszych sum. Obliczając układ równań otrzymamy następujące równanie:

 

b = (p1 + p3 - p2)/2

 

wtedy

 

a = p1 - b

c = p3 - b

 

W ten sposób uzyskaliśmy trzy najmniejsze wartości jakie są w trzech skrzynkach.

 

Wartość p10 to suma diamentów w skrzynkach o największej wartości, czyli d i e.

p9 jest równa sumie diamentów ze skrzynek c i e.

Zatem można zapisać

 

c + e = p9

d + e = p10

 

Jako, że obliczyliśmy uprzednio wartość c, to reszta obliczeń pozostaje kwestią rozwiązania układu równań.

Przykład:


Pary skrzynek: 10, 12, 16, 10, 6, 12, 18, 8, 14, 14

 

6 ≤ 8 ≤ 10 ≤ 10 ≤ 12 ≤ 12 ≤ 14 ≤ 14 ≤ 16 ≤ 18

 

b = (6 + 10 - 8)/2

b = 8/2

b = 4

 

a = p1 - b

a = 6 - 4

a = 2

 

c = p3 - b

c = 10 - 4

c = 6

 

c + e = 16

e = 16 - c

e = 16 - 6

e = 10

 

d + e = 18

d = 18 - e

d = 8

 

Zatem:

a = 2

b = 4

c = 6

d = 8

e = 10

 

Przedstawiony sposób sprawdza się także przy ilościach diamentów powtarzających się. Ale po co ta reszta wartości? Można sprawdzić, czy podane pary skrzynek są prawidłowe poprzez sumowanie i dopasowanie.

 

PS. Nudziło mi się w robocie :E

YOU MUST DIE

- Ganon, Koridai

encoreeFTW Budowniczy

encoreeFTW

Opublikowano
Budowniczy

encoreeFTW

  • Autor
Opublikowano

 

 



#include <iostream>
#include <cstdlib>

using namespace std;

int compare (const void * a, const void * ;


int main()
{
ios_base::sync_with_stdio(0);

unsigned tablica[10], wyjscie[5] = {0, 0, 0, 0, 0}, suma = 0;

for(int i = 0; i<10; i++)
{
cin>>tablica[i];
suma+=tablica[i];
}

qsort(tablica,10,sizeof(int),compare);

wyjscie[1]=(tablica[0]+tablica[2]-tablica[1])/2;
wyjscie[0]=tablica[0]-wyjscie[1];
wyjscie[2]=tablica[2]-wyjscie[1];
wyjscie[3]=tablica[8]-wyjscie[2];
wyjscie[4]=tablica[9]-wyjscie[3];

qsort(wyjscie,5,sizeof(int),compare);

for(int wypisz = 0; wypisz<5; wypisz++)cout<<wyjscie[wypisz]<<"\n";


return 0;
}




int compare (const void * a, const void * 
{
return ( *(int*)a - *(int*)b );
}

 

 

 

jeden test wiecej passed, nie mam sily juz do tego ;f

nadal 2 dupa, pewnie jakis chamski przypadke w sprawdzaczce, za glupi na to jestem chyba xD

mirraseq Specjalista

mirraseq

Opublikowano
Specjalista

mirraseq

Opublikowano

No to kombinujemy dalej, znalazłem przypadek, kiedy nie sprawdza się mój sposób:

dla skrzynek: 1, 3, 3, 3, 5 będą następujące pary: 4, 4, 4, 6, 6, 6, 6, 8, 8, 8.

 

b = (p1 + p3 - p2)/2

b = (4 + 4 - 4)/2

b = 2 <- nieprawda!

 

Przypatrzmy się zatem pierwszej i ostatniej parze, których jesteśmy pewni.

 

a + b = p1

d + e = p10

 

Suma jakich dwóch liczb da nam 4?

1 + 3 = 4

2 + 2 = 4

 

A co w przypadku ostatniej pary?

1 + 7 = 8

2 + 6 = 8

3 + 5 = 8

4 + 4 = 8

 

Możemy zatem prześledzić możliwe przypadki składników dla wszystkich sum ale nie korzystając z brute force.

= - to będzie przykładowa część liczby jako 1 jednostka

? - niewiadoma część liczby

| - separator

 

[=|===] <- a = 1, b = 3

[===|?] <- b = 3, c = ?

[?|====] <- c = ?, d = 4

[====|====] d = 4, e = 4

 

Zadanie polegałoby na tym, by przemieszczać separatory dla a + b i d + e tak, aby odnaleźć taką liczbę c, dzięki której uda się odtworzyć pary skrzynek.

YOU MUST DIE

- Ganon, Koridai

Zarchiwizowany

Ten temat przebywa obecnie w archiwum. Dodawanie nowych odpowiedzi zostało zablokowane.

Tematy
×
×
  • Dodaj nową pozycję...