3. Programmieraufgaben

Programmieraufgaben

  • K

    http://icpc.baylor.edu/worldfinals/problems

    Kann man sich Loesungen anderer User bei http://www.spoj.com/problems/ anschauen?

    0
  • S

    Ich kann nicht widerstehen, volkards Aufgabe zu machen!

    a) Schreibe ein Programm, das das möglichst genau simuliert und dann ausgibt, welche Zellen offen sind.

    Also, der doofe Ansatz:

    #include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>

int main()
{
	unsigned n;
	std::cin >> n;

	std::vector<bool> prison(n);

        for( unsigned i = 0; i != n; ++i )
	{
		for( unsigned j = i; j < n; j += i + 1 )
			prison[j] = !prison[j];
		std::copy( std::begin(prison), std::end(prison), std::ostream_iterator<bool>{std::cout << '\n'} );
	}
}

    Und jetzt gab es eine böse Überraschung. Das Problem ist viel zu primitiv.

    #include <iostream>

int main()
{
	unsigned n;
	std::cin >> n;

	unsigned counter = 2;
	while( n-- )
	{
		std::cout.put('1');
		for( unsigned i = 0; i != counter ; ++i )
		{
			if( !n-- )
				return 0;

			std::cout.put('0');
		}

		counter += 2;
	}
}

    Und Sublineare Komplexität ist hier sowieso unmöglich.

    Komm schon, volkard, da geht noch was.

    0
  • V

    gelöscht

    0
  • V

    Bitte in diesem Thread nur weiter Aufgaben sammeln.
    Und über die Aufgaben selber reden.
    Lösungen bitte in neuen Threads, damit eventuelle Diskussionen über Läsungen nicht alles hier sprengen.

    0
  • S

    volkard schrieb:

    Sone schrieb:

    ...

    Du solltest nur anzeigen, welche Zellen offen sind. Nicht alle Zellen.

    Das macht es noch einfacher.

    Da das Problem also offensichtlich nicht interessant ist, verzichte ich mal auf einen neuen Thread.

    0
  • K

    Und Sublineare Komplexität ist hier sowieso unmöglich.

    Wenn man den Simulationsschritt weglaesst, dann ist das anzeigen der "geschlossenen" Zellen leicht berechenbar.

    Komm schon, volkard, da geht noch was.

    Du hast doch genug Aufgaben/Links praesentiert bekommen, also was willst du?

    0
  • S

    knivil schrieb:

    Und Sublineare Komplexität ist hier sowieso unmöglich.

    Wenn man den Simulationsschritt weglaesst, dann ist das anzeigen der "geschlossenen" Zellen leicht berechenbar.

    Ich dachte, man muss den Zustand am Ende komplett anzeigen.

    Mit der Abänderung hast du natürlich Recht, daher auch mein Kommentar.

    Komm schon, volkard, da geht noch was.

    Du hast doch genug Aufgaben/Links praesentiert bekommen, also was willst du?

    Keine Ahnung, ich will mich nicht durch so viele uninteressante Probleme quälen wenn volkard doch sicher die interessanten kennt.

    0
  • V

    Könnte bitte jemand die Sone-Diskussion löschen oder in einen neuen Thread verlegen?

    0
  • ?

    Sone Scheiße

    0
  • K

    @Sone: Dann nimm doch http://icpc.baylor.edu/download/worldfinals/problems/icpc2013.pdf da gibt es auch Testfaelle mitgeliefert. Ich selbst habe self-assembly gemacht. Aber es ist meist so, dass es trivial wird, wenn man die Loesung gefunden hat.

    0
  • S

    Aber es ist meist so, dass es trivial wird, wenn man die Loesung gefunden hat.

    Deswegen mag' ich ja Probleme, die
    1. Sehr einfach zu formulieren und verstehen sind. Also keine ellenlangen Dinger bei denen man nach zehn Saetzen tl;dr denkt.
    2. keine "beste oder eindeutige Loesung" haben. Also kein eindeutiges Muster haben, sondern bei denen man die Loesung einfach optimieren muss.

    Vorige Aufgabe ist zwar schoen kurz, hat aber diese eine eindeutige und schnell gefundene Loesung.

    Hier ist eines, was ich aus diesen Gruenden gut fand: http://en.wikipedia.org/wiki/Gauss_circle_problem
    Ich finde, es ist eine wirklich huebsche Aufgabe.

    Die Aufgabe ist: Man habe einen Kreis mit Radius R. Packt man diesen nun auf den Ursprung eines Koordinatensystems - wie viele ganzzahlige Koordinaten liegen es nun auf ihm?

    Edit: Danke, knivil, fuer deinen Link - http://icpc.baylor.edu/download/worldfinals/problems/icpc2013.pdf
    Problem J ist interessant! 🙂

    0
  • K

    Du must schauen, bei Problem J ist das Zeitlimit 1 Sekunde. Ich vermute die Loesung ist trivial umzusetzen. Die Schwierigkeit ist sie zu finden.

    0
  • ?

    knivil schrieb:

    Du must schauen, bei Problem J ist das Zeitlimit 1 Sekunde. Ich vermute die Loesung ist trivial umzusetzen. Die Schwierigkeit ist sie zu finden.

    Das denke ich nicht. Das Einfachste, was mir einfällt, ist ein Kreissweep. Der läuft zwar schnell, aber trotzdem muss man beim Implementieren auf einiges achten.

    0
Anmelden zum Antworten