Wątek przeniesiony 2016-06-23 13:21 z C/C++ przez ŁF.

Pomoc w zadaniach na olimpiadę informatyczną.

0

Witam. Chciałbym wziąć udział w olimpiadzie informatycznej dla gimnazjalistów. Ma ktoś jakieś rady czy wskazówki? Zrobiłem 1 zadanie. Czy jest ono poprawnie wykonane? O co chodzi z tym "W testach wartych 60% punktów zachodzi dodatkowy warunek M <1000, a w podzbiorze tych testów wartym 40% punktów zachodzi również warunek N <1 000." ?

#include <iostream>

using namespace std;

int main()
{
    cout<<"ile razy zapytasz?: ";
    int razy;
    cin>>razy;

    cout<<"jaki rozmiar tali?: ";
    int talia;
    cin>>talia;

    for(int i=1; i<=razy; i++) // petle z pytaniami tymi samymi
    {
    cout<<endl<<"jaki numer karty?: ";
    int numer;
    cin>>numer;

    cout<<"ile razy tasowac?: ";
    int tasowanie;
    cin>> tasowanie;

    int polowa = talia/2;

    for(int i=1; i<=tasowanie; i++) // petla z kartami
    {
        if (numer<=polowa)
        {
            numer*=2;
        }
        else
        {
            numer-=polowa;
            numer*=2;
            numer-=1;
        }
    }
    cout<<numer<<endl;
    }

}
2

Klep zadania na SPOJU. Masz tam automatyczna sprawdzarkę która ci powie czy jest dobrze czy źle.

0

Będę robił ale teraz chce otrzymać odpowiedź na moje pytanie

0

Przed wysłaniem powywalaj cout-y pytające, zwykle sprawdza maszyna więc zostaną uznane za odpowiedzi, naturalnie błędne. Wyjście ma wyglądać dokładnie tak jak opisano w zdaniu, Co zaś się tyczy

"W testach wartych 60% punktów zachodzi dodatkowy warunek M <1000, a w podzbiorze tych testów wartym 40% punktów zachodzi również warunek N <1 000."
, To jest to dodatkowa informacja że w niektórych testach będzie dużo kart. Aczkolwiek wygląda na to że 40 % punktów wystarczy do "zaliczenia" zadania.

3

Te programy są pisane pod roboty sprawdzające, a twój probgram drukuje coś dla człowieka, czgo na pewno nie ma w specyfikcaji zadania.
Nie pisz wszystkiego w main. Dziel problem na mniesze fragmenty w postaci funckji.

0

ten filmik może rozwiać większość twoich wątpliwości

0

Spróbowałem rozwiązać kolejne zadanie:
Przyciski
Limit pamięci: 32 MB

Bajtek znalazł ciekawą zabawkę. Zabawka ta ma przycisków. Nad każdym z pierwszych przycisków znajduje się mały licznik, początkowo wskazujący zero. Naciśnięcie przycisku pod licznikiem zwiększa wskazywaną przezeń liczbę o .

Zabawka szybko by się Bajtkowi znudziła, gdyby nie kuriozalne działanie przycisku o numerze . Po jego użyciu wszystkie liczników zaczyna wskazywać największą z widocznych dotąd na zabawce wartości. Na przykład, jeżeli i kolejne liczniki wskazują liczby , to po naciśnięciu przycisku o numerze wszystkie liczniki będą wskazywać .

Wiedząc, które przyciski wybierał kolejno Bajtek, chcemy poznać wartości wszystkich liczników po zakończeniu zabawy.
Wejście

Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite , (), oznaczające kolejno liczbę liczników na zabawce i liczbę operacji wykonanych przez Bajtka. Drugi wiersz wejścia zawiera liczb całkowitych (), oznaczających numery kolejnych przycisków wciskanych przez Bajtka.

Możesz założyć, że w testach wartych co najmniej punktów zachodzą dodatkowo warunki .
Wyjście

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać liczb całkowitych, oddzielonych pojedynczymi odstępami, oznaczających wartości znajdujące się na kolejnych licznikach po zakończeniu zabawy.
Przykłady

Dla danych wejściowych:

5 7
3 4 4 6 1 4 4

poprawną odpowiedzią jest:

3 2 2 4 2

Dla danych wejściowych:

7 10
1 1 1 8 1 1 1 8 2 7

poprawną odpowiedzią jest:

6 7 6 6 6 6 7

Dla danych wejściowych:

8 10
1 9 2 9 3 9 4 9 5 9

poprawną odpowiedzią jest:

5 5 5 5 5 5 5 5

Oto moje rozwiązanie:

#include <iostream>

using namespace std;

void sortowanie(int tab[], int n)
{
    for(int i=0; i<n-1; i++)
        for(int j=0; j<n-1; j++)
        if(tab[j]>tab[j+1]) swap(tab[j], tab[j+1]);
}


int main()
{
    int ile_licznikow;
    int ile_operacji;

    int operacja[10000];
    int licznik[10000];

    cin>>ile_licznikow>>ile_operacji;

    for(int i=0; i<ile_operacji; i++) // petla wykonujaca operacje
    {
        int dod;
        cin>>operacja[i];
        dod=operacja[i];
        for(int j=0; j<ile_licznikow + 1; j++) // petla dodajaca na podstawie jednej operacji
        {
            if(dod-1==j) // normalne wcisniecie przyciska
                {
                    licznik[dod-1]+=1;

                }
            else if(dod-1==ile_licznikow)  // wcisniece specjalne - n+1
            {
                sortowanie(licznik, ile_licznikow);
                int x=licznik[ile_licznikow-1]; // najwiekszy licznik
                for(int y=0; y<ile_licznikow; y++) //
                    licznik[y]=x;
            }

        }

    }
    int z=0;
    do{
            cout<<licznik[z]<<" ";
            z++;
    }while(z<ile_licznikow);


}
 
0

Dostałęm 21/100 punktów w http://main2.edu.pl . Pisze że wykonywanie programu trwało za długo. Co muszę zrobić żeby zoptymalizować ten program?

0

Nieoptymalnie wyznaczasz maksymalną wartość w momencie naciśnięcia przycisku n+1. Sortujesz (dodatkowo bąbelkowo) tablicę w najgorszym przypadku 1e6 elementów. Nie musisz sortować. Rozmiary tablic operacja, licznik są za małe.

0

U mnie wygląda to tak

Zadanie 	Data zgłoszenia 	Status 	Wynik
Przyciski (prz) 	2016-06-30 01:19:27 	Wstępne sprawdzanie: OK 	1
Raport ostatecznego sprawdzania
	Test 	Wynik 	Czas 	Wynik
	1
	OK 	0.00s/5.00s 	7/7
	2
	OK 	0.00s/5.00s 	7/7
	3
	OK 	0.00s/5.00s 	7/7
	4
	OK 	0.00s/5.00s 	7/7
	5
	OK 	0.00s/5.00s 	7/7
	6
	OK 	0.00s/5.00s 	7/7
	7
	OK 	0.01s/5.00s 	7/7
	8
	OK 	0.12s/5.00s 	7/7
	9
	OK 	0.23s/5.00s 	7/7
	10
	OK 	0.37s/5.00s 	7/7
	11
	OK 	0.66s/5.00s 	7/7
	12
	OK 	1.56s/5.00s 	7/7
	13
	OK 	1.59s/5.00s 	8/8
	14
	OK 	1.62s/5.00s 	8/8
0

Takie szybkie uwagi:

  1. po co ci tablica operacji? Nie wystarczy 1 zmienna?
  2. to już zauważył ktoś wcześniej: zamiast sortować zrób sobie funkcję znajdująca największą wartość
  3. (to jest takie czepianie się troszkę) z tego co czytałem, to bez jakiejś większej konfiguracji strumieni printf() i scanf() działają szybciej od cout i cin.
  4. tablicę liczników mógłbyś alokować dynamicznie
0

Poprawiłem parę rzeczy. Zamiast sortowania bąbelkowego wprowadziłem funkcję sprawdzającą czy dany element tablicy /licznik\ jest wiekszy od wartości maksymalnej.
Teraz mam 35/100 a reszta - program wywłaszczony. Co mogę jeszcze poprawić?

#include <iostream>

using namespace std;
int najwiekszy;
int ile_licznikow;
int licznik[1000000];


int najwiekszy_funkcja(int tab[])
{
    int i=0;
    do{
                if(licznik[i]>najwiekszy)
                    najwiekszy=licznik[i];
                i++;
    }while(i<ile_licznikow);
    return najwiekszy;
}


int main()
{

    int ile_operacji;

    int operacja;


    cin>>ile_licznikow>>ile_operacji;

    for(int i=0; i<ile_operacji; i++) // petla wykonujaca operacje
    {
        int dod;
        cin>>operacja;
        dod=operacja;
        for(int j=0; j<ile_licznikow + 1; j++) // petla dodajaca na podstawie jednej operacji
        {
            if(dod-1==j) // normalne wcisniecie przyciska
                {
                    licznik[dod-1]+=1;

                }
            else if(dod-1==ile_licznikow)  // wcisniece specjalne - n+1
            {
                int m= (najwiekszy_funkcja(licznik));
                for(int y=0; y<ile_licznikow; y++) //
                    licznik[y]=m;
            }

        }

    }
    int z=0;
    do{
            cout<<licznik[z]<<" ";
            z++;
    }while(z<ile_licznikow);


}
 
0

Zrób dynamiczną alokację tablicy

#include <iostream>

using namespace std;
 
int main(){
    int n;
    int m;
    int offset = 0;
    int mm = 0;
    int button;
    
    int* buttons = new int[1000000];
    
    cin >> n >> m;
    
    for(int i = 0; i < m; ++i){
      cin >> button;
      if(button == n + 1){
        offset = mm;
      } else {
        if(buttons[button - 1] < offset)
          buttons[button - 1] = offset;
        buttons[button - 1]++;
        mm = max(mm, buttons[button - 1]);  
      }
    }
    
    for(int i = 0; i < n; ++i){
      cout << max(offset, buttons[i]) << " ";
    }
    
    delete[] buttons;
    
    return 0; 
}
0

Sorry że tak późno odpowiadam ale miałem problemy techniczne. Problem został rozwiązany. Wielkie dzięki reptile333 i gepir :)

0

Mam jeszcze problem z innym zadaniem:
Kupiec
Limit pamięci: 32 MB

Bajtazar jest wędrownym kupcem, który przemieszcza się pomiędzy miastami leżącymi wzdłuż linii kolejowej. Jego cel jest prosty: kupić tanio, sprzedać z zyskiem i nie wydać zbyt dużo na podróż.

Wspomniane miasta są ponumerowane od do zgodnie z kolejnością występowania wzdłuż torów. Bajtazar chciałby zarobić możliwie najwięcej na pewnym konkretnym towarze, którego cenę w każdym mieście zna. Ponadto wie, ile kosztuje przejazd między dowolną parą sąsiadujących miast (droga w okolicy jest tylko jedna, więc bezpośrednio można poruszać się jedynie pomiędzy miastami o numerach oraz ). Jego zysk to cena, po której sprzeda towar, pomniejszona o cenę zakupu i sumaryczny koszt przejazdu. Niestety Bajtazar nie jest zbyt dobry z ekonomii i potrzebuje Twojej pomocy. Napisz program, który obliczy maksymalny możliwy zysk w jednej takiej parze transakcji, zakładając, że Bajtazar może rozpocząć i zakończyć podróż w dowolnych miastach.
Wejście

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę miast. W drugim wierszu znajduje się liczb całkowitych () pooddzielanych pojedynczymi odstępami. Są to ceny towaru w kolejnych miastach. Trzeci wiersz zawiera liczb całkowitych ( dla ) pooddzielanych pojedynczymi odstępami, oznaczających ceny przejazdu odpowiednio między miastami o numerach oraz .
Wyjście

Twój program powinien wypisać na standardowe wyjście jedną liczbę całkowitą - maksymalny możliwy zysk Bajtazara. Zauważ, że w skrajnym przypadku Bajtazar może kupić i sprzedać towar w tym samym mieście.
Przykład

Dla danych wejściowych:

4
19 5 2 3
5 1 1

poprawną odpowiedzią jest:

11

Wyjaśnienie do przykładu: Bajtazar kupuje towar w mieście numer 3 (cena: 2), następnie przejeżdża do miasta numer 1 (koszt tego przejazdu to ), gdzie sprzedaje towar w cenie 19. Łączny zysk Bajtazara to: 11.

Moje rozwiązanie 40/100 :

 // ConsoleApplication2.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;


long miasta;
//long*ceny_towarow = new long[];
//long*ceny_przejazdu = new long[];
vector <long> ceny_towarow(1000000);
vector <long> ceny_przejazdu(1000000);

long najmniejsze = 1000000000;
long m;
long zysk_lokalny = 0;


void korzysc(vector <long> tab,vector <long> tab1)
{
	for (int i = 1; i <= miasta; i++)
	{
		if (tab[i] < najmniejsze)
		{
			najmniejsze = tab[i];
			m = i;
		}
	}


	long zysk = 0;
	long podroz = 0;
	for (int i = 1; i <= miasta; i++)
	{
		podroz = 0;
		if (i < m)
		{
			for (int j = i; j < m; j++)
				podroz += tab1[j];
		}
		else if (i > m)
		{
			for (int j = m; j < i; j++)
				podroz += tab1[j];
		}
		zysk_lokalny = tab[i] - (podroz + najmniejsze);
		if (zysk_lokalny > zysk)
			zysk = zysk_lokalny;
	}
	cout << zysk;
}

int main()
{
	
	cin >> miasta;

	for (int i = 1; i <= miasta; i++)
	{
		cin >> ceny_towarow[i];
	}
	for (int i = 1; i <= miasta - 1; i++)
	{
		cin >> ceny_przejazdu[i];
	}
	korzysc(ceny_towarow, ceny_przejazdu);
    return 0;
}

Co powinienem poprawić, bo nie za bardzo wiem?

0
  1. zacznij od tego, że lepiej jest wykorzystywać wszystkie elementy, czyli indeksowac od 0
  2. przekazujesz kopie wektorów jako argumenty
  3. uzywasz zmiennych globalnych - poza wyjątkami jest to niewskazane
0
kaczus napisał(a):
  1. zacznij od tego, że lepiej jest wykorzystywać wszystkie elementy, czyli indeksowac od 0
  2. przekazujesz kopie wektorów jako argumenty
  3. uzywasz zmiennych globalnych - poza wyjątkami jest to niewskazane

Ale to chyba nie zwiększy znacząco szybkości programu.

Jakieś jeszcze sugestie?

0

Zadanie można rozwiązać za pomocą combo "prefix sums" + "kadane's algorithm"
"prefix sums" pozwala na liczenie odległości między miastami w czasie stałym O(1)
"kadane's algorithm" pozwala w czasie O(n) wyznaczyć maksymalny zysk

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

int main(){
  
  ios_base::sync_with_stdio(false);
  
  int n;
  cin >> n;
  vector<int> c(n);
  
  for(int i = 0; i < n; ++i)
    cin >> c[i];
  vector<int> p;
  vector<int> ps;
  
  p.push_back(0);
  
  int s = 0;
  for(int i = 0; i < n - 1; ++i){
    cin >> s;
    p.push_back(s);
  }
  
  s = 0;
  for(int i = 0; i < n; ++i){
    s += p[i];
    ps.push_back(s);
  }
  
  int res = 0;
  int x1 = 0;
  for(int i = 0; i < n; ++i){
    s = c[x1] - c[i] - (ps[i] - ps[x1]);
    if(s < 0) x1 = i;
    res = max(res, s);
  }
  
  x1 = n - 1;
  for(int i = n - 1; i > -1; --i){
    s = c[x1] - c[i] - (ps[x1] - ps[i]);
    if(s < 0) x1 = i;
    res = max(res, s);
  }
  
  cout << res;
  
  return 0;
}

1 użytkowników online, w tym zalogowanych: 0, gości: 1