Dragos (APOCALYPTO)

Vezi solutiile trimise	Nume	Dragos
	Cont	APOCALYPTO
	Rating	490
	Statut	Utilizator normal
	Forum	trimite mesaj privat, vezi activitate

zmeu2

This is a classic dynamic programming problem and, like most DP problems, is simple if and only if you "get" the induction piece. Additionally, getting full points required figuring out (or knowing) a nice trick for when you need to calculate the sums of lots of different ranges.

Reading the problem, it seems to be very clearly a DP problem. In particular, the fact that the line of coins is always a continuous subrange of the original line is a big clue, and that we should compute Bessie's optimal strategy on the range [i, j] (inclusive on both sides) in terms of smaller ranges. Suppose that s(i, j) is the sum of c[i], c[i+1], ..., c[j]. Let b(i, j) be the most that Bessie can win if she plays first on the subrange [i, j]. Then we see that
b(i, j) = max(c[i] + s(i+1, j) - b(i+1, j), c[j] + s(i, j-1) - b(i, j-1))
since s(i, j) - b(i, j) is, by definition, the most Bonnie can win if Bonnie plays second on the interval [i, j]. Actually, this equation is equivalent to
b(i, j) = max(s(i, j) - b(i+1, j), s(i, j) - b(i, j-1))
= s(i, j) - min(b(i+1, j), b(i, j-1))
which makes sense, since this is equivalent to minimizing the maximum that Bonnie could win.

This gives us an O(n^{3) solution, if we compute s(i, j) out each time. In retrospect, if you computed all n}2 values of s(i, j) first, and then ran this DP solution, that would be O(n^2). That wasn't the solution I had in mind, though, and there's a trick to be learned here! The trick is that you compute partial sums: you define an array S[i] = c⁰ + c¹ + ... + c[i-1], with length n+1. Then c[i] + c[i+1] + ... + c[j-1] = S[j] - S[i], which takes constant time to compute. This is a cute trick that is extremely useful to remember.

h1 http://infoarena.ro/problema/ciclu
COBAI
NOV 09 - 80
NOV 10 - 82
NOV 11 - 84
NOV 12 - 85
NOV 15 - 86
DEC 05 - 89
DEC 06 - 90
DEC 09 - 92
DEC 10 - 93
DEC 11 - 94
DEC 12 - 98
DEC 13 -100
DEC 14 -101
DEC 15 -102
Task 200 probleme pana la 5 IAN
22 zile 100 probleme to go.
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4184
Retine smenul de la sir23
Ai grija la '\n' problema nc

greseli
difprim 100 mii in loc de 10 milioane
qtri depinde la float long long timp int
grarb afisare pe dos
palalila2 zig zag nu merge invers? oare?

De facut problemele Balaur, Anticip si Microvirus de pe campion.

si http://acm.timus.ru/problem.aspx?space=1&num=1081

.
.
.
Probleme cu deque:knumere
.
.
.
..

.
..

.
.
.
.
h1. Selectati destinatia.

Programare dinamica

• Probleme ad-hoc
• Problema rucsacului
  Knapsack cu vector fara matrice de aparitii
  for i = 1 la n
  for j = S la 0
   dp[j]=d[j-g[i]]+c[i]

• Dinamica pe stari exponentiale
• Dinamica pe arbore
• Memoizare
• Exponentiere rapida de matrice

Grafuri

• Parcurgere in latime BFS ^{[problema clasica]}
• Parcurgere in adancime DFS ^{[problema clasica]}
• Algoritmul lui Dijkstra ^{[problema clasica]}
• Algoritmul Bellman-Ford ^{[problema clasica]}
• Flux maxim ^{[problema clasica]}
• Flux maxim de cost minim ^{[problema clasica]}
• Lowest Common Ancestor ^{[problema clasica]}
• Lant hamiltonian
• Lant eulerian
• 2-SAT ^{[problema clasica]}
• Componente tare conexe ^{[problema clasica]}
• Componente biconexe

Structuri de date

• Hash
• Heapuri
• Arbori de intervale ^{[problema clasica]}
• Arbori indexati binar ^{[problema clasica]}
• Arbori indexati binar 2D
• Arbori echilibrati
• Trie ^{[problema clasica]}
• Deque ^{[problema clasica]}
• Multimi disjuncte/ disjoint datasets
• Range Minimum Query ^{[problema clasica]}
• Ortogonal Range Search

Cautare

• Cautare binara ^{[problema clasica]}

Sortare

• Sortare

Siruri de caractere

• Parsare
• KMP
• Suffix array/ siruri de sufixe

Backtracking

• Submultimi ^{[problema clasica]}

Greedy

• Ad-hoc

Divide et Impera

• Ad-hoc

Matematica

• Ciurul lui Eratostene ^{[problema clasica]}
• Algoritmul lui Euclid ^{[problema clasica]}
• Exponentiere rapida ^{[problema clasica]}
• Formula
• Combinatorica

Geometrie

• Ad-hoc
• Baleiere
• Aria unui poligon
• Intersectie de poligoane
• Teorema lui Pick
• Infasuratoare convexa ^{[problema clasica]}
• Rotating calipers
• No fit polygon

Teoria jocurilor

• Ad-hoc

Diverse

• Operatii pe biti
• Operatii pe numere mari
• Evaluare de expresii ^{[problema clasica]}
• Normalizare
  .
  .
  .
  .
  .

.
.
...
.
.
.
.
.
.
.

.
.

-afisati numarul total de inregistrari din tabela voturi!
Select count(judet), count(nr_voturi) from voturi

-determinati pentru cate judete avem rezultatele votarii folosind tabela voturi
-sa se determine cel mai mare numar de voturi exprimate pentru un candidat intr-un judet
-sa se determine numarul de voturi primite de catre un candidat raportat la numarul de alegatori
-cel mai mare numar de voturi obtinut de catre un candidat intr-un judet
-procentul obtinut de catre fiecare candidat in fiecare judet
-numarul total de voturi in judetul sibiu
-procentul mediu obtinut de un candidat in toate judetele(cod 12)

-calculati numarul total de vturi obtinut de fiecvare candidat in toate cele 3 judete

-select candidat,numar_votuir
-aflati procentul mediu obtinut de fiecare candidat in toate cele 3 judete
-afisati toti candidatii care au obtinut un procent in alegeri mai mare de 5% din numarul total de persoane cu drept de vot

-afisati angajatii care au salariul mai mare decat salariul lui Ionescu
-afisati toate persoanele care lucreaza la aceiasi firma la care lucreazxa si ionescu
-afisati toate persoanele care nu locuiesc in aceiasi localitate cu ionescu
-afisati toate persoanele care lucreaza in aceiasi localitate in care si locuiesc
'

set default toF:\12c
set default to F:\12c
set default to F:/12c
set default to F:\12c
OPEN DATABASE f:\12c\data1.dbc EXCLUSIVE
MODIFY DATABASE
select count(judet), count(numar_voturi) from voturi
select count(distinct judet) from voturi
select max(numar_voturi) from voturi
select max(100*numar_voturi/numar_alegatori) from voturi,judete where voturi.judet=judete.cod_judet
select 100*numar_voturi/numar_alegatori, judete.judet,candidat from voturi,judete where judet=judete.cod_judet
select sum(numar_voturi) from voturi where judet="sb"
select sum(numar_voturi) from voturi where judet="SB"
select avg(100*numar_voturi/numar_alegatori) from voturi,judete where (candidat=12 and voturi.judet=judete.cod_judet)
select candidat,sum(numar_voturi) as total_voturi from voturi group by candidat
select 100*numar_voturi/numar_alegatori, judete.judet,candidat from voturi,judete where judet=judete.cod_judet
select 100*numar_voturi/numar_alegatori, judete.judet,candidat from voturi,judete where voturi.judet=judete.cod_judet
select candidat,numar_voturi from voturi group by candidat,numar_voturi
select candidat,avg(100*numar_voturi/numar_alegatori) from voturi,judete where voturi.judet=judete.cod_judet group by candidat
select candidat,100*sum(numar_voturi)/sum(numar_alegatori) from voturi,judete where voturi.judet=judete.cod_judet group by candidat
select candidat,100*sum(numar_voturi)/sum(numar_alegatori) from voturi,judete where voturi.judet=judete.cod_judet group by candidat having 100 * sum(numar_voturi)/sum(numar_alegatori)>5

select nume from angajati where salariul > (select salariul from angajati where nume="IONESCU")
select a.nume from persoane a,persoane b where a.idfirma=b.idfirma and b.nume="IONESCU"
select nume from persoane where idfirma=(select idfirma from persoane where nume="IONESCU")
select nume from persoane where localitate<>(select localitate from persoane where nume="IONESCU")
select nume from persoane where localitate=(select localitate from firme where idfirma=id)