Я решил задачу с помощью графа, где вершинки - состояния ёмкостей,и рассмотрел из очередного состояния все переходы, запоминая те состояния ,где уже был. Но я никак не могу оценить кол-во возможных состояний. Может кто-нибудь подскажет как оценить? Самая грубая оценка - у нас есть числа a,b,c>=0 и a+b+c=N(для случая,когда не подливаем и не выливаем-в этом случае сумма константа). Тогда количество таких чисел O(N^3),но это ужасная оценка. Согласен, было бы интересно узнать максимальное количество возможных состояний и при каких значениях a,b,c оно достигается Edited by author 16.11.2019 13:00 Можно оценивать так: пусть ёмкости не превосходят значения C. Рассмотрим возможные переходы между состояниями. 1) Когда подливаем из заправки в канистру. Тогда канистра, в которую подливаем, становится полной. 2) Когда переливаем между канистрами. Тогда либо канистра, в которую переливаем, становится полной, либо канистра, из которой переливаем, становится пустой (либо и то, и то). Получается, что в каждом состоянии хотя бы одна канистра либо пустая, либо полная. Тогда количество состояний можно оценить как 6*(С+1)^2, то бишь O(C^2). I was using QUEUE. It was Memory limit exceed #8 or something similar. Replaced queue by simple an static array of one million elements. I was using state struct. There are three members of unsigned char type. So, with C limitations, I got AC with 16 MB. Obviously USED array is MLE. Probably using unordered_set is OK. Are there better things than unordered_set? Maybe there are some mathematical properties?.. DFS, record the state, if come into a state appeared before , ignore it. DFS is very slow, can anybody give some hints to DP? Это и есть ДП. Ведь ты переходишь по сути в известные состояния(т.е.уже просмотренные) и новые,для которых рассматриваешь переходы.Просто у нас не совсем стандартные размерности "подзадачи". ДП-это не только реккурентные соотношения. who give AC, please, give me right answers for this tests : 1) 1 200 245 2) 0 13 131 3) 37 39 41 4) 29 41 97 5) 0 64 129 6) 81 27 243 7) 240 241 242 thanx Edited by author 14.08.2008 21:51 1)446 2)15 3)76 4)167 5)7 6)13 7)723 0 also answer??? Edited by author 25.02.2006 14:04 i think it isn't. If you ask about 0 litres - then NO. Otherwise you'll get 7 for sample input. I have WA6 Edited by author 18.09.2006 22:29 Edited by author 18.09.2006 22:29 For example: 1 100 255 result: 356 I have correct answer on this test, but WA#6( Please post tests or correct idea. My program always WA in Test#6. What is Test#6? program Problem; function min( x, y: integer ): integer; begin if x < y then result:=x else result:=y; end; function max(x, y: integer): integer; begin if x > y then result := x else result := y; end; type
TKan = array[0..2]of byte; var Ok: array[0..255, 0..255, 0..255 ] of Boolean; R: array[1..1000] of boolean; K, Y: TKan; Count: Integer; procedure Calc(X: TKan ); var d, i, j: byte; begin if not Ok[X[0], X[1], X[2]] then begin Ok[X[0], X[1], X[2]] := true; for i := 1 to 7 do R[X[0] * (i and 1) + X[1] * ((i shr 1) and 1) + X[2] * ( ( i shr 2 ) and 1)] := true; for i := 0 to 2 do if X[i] = 0 then begin X[i] := K[i]; Calc(X); X[i] := 0; end; for i := 0 to 2 do for j := 0 to 2 do if i <> j then begin d := min(K[i] - X[i], X[j]); if d = 0 then continue; inc(X[i], d); dec(X[j], d); Calc(X); dec(X[i], d); inc(X[j], d); end; end; end; var a: integer; begin
FillChar(R, Sizeof(R),0); FillChar(Ok, Sizeof(Ok),0); read(K[0], K[1], K[2]); Y[0] := 0; Y[1] := 0; Y[2] := 0; Calc(Y); Count := 0; for a := 1 to 1000 do if R[a] then begin // writeln(a); inc(count); end; writeln(count); end. problem#1437 WA #1 it's impossible; 2 cases: "crash(int div by zero)" or "output limit" but you server give WA WHY!? include <stdio.h> int main() { int N; scanf("%i",&N); int b; scanf("%i",&b); scanf("%i",&b); if (N==0) N=b/0; else while (true) printf("123442343234234343423243242344"); return 0; } Do you know what "Output Limit Exceeded" means? Think about it before being rude. while (true) printf("123123123123"); gets output limit I know why this program don't work. it's optimization, I must add in last line "printf("%i",N);" in VS 6.0 program gets crash anyway but I realy don't understand, why it gets WA#1 this program on test #1 (0 3 4) don't output anything Edited by author 30.08.2006 12:55 Sometimes 1/0 isn't crash :( I tried to find mistakes in one my program so, but didn't receive crash - as you. Compiler tries to optimize your code and do not run last command (N=b/0) because value of N is not used after this assignment. I think the answer: 0 1 3 4 6 7 1 2 3 4 6 7 1 2 3 4 6 7 How can you measure 1??? I think: 0 2 3 4 6 7 How can you measure 2??? When you fill the third can, and put 3 to the second one, then the second can has 3,and the third one has 1. It is simple. just fill the second, pour it in the third. Then fill the second again and pour 1 L to the third. Finally there are 2 L in the second. ok, you're right. so the answer is: 1 2 3 4 6 7 yes, but i still can't understand how to make it in C++. :((((( the solution is:1 2 3 4 6 7 why 5 isn't an answer? while the second has 2,pour it to the third,and fill the second again. While the second has 2, the third is already filled completely. So you can not pour second to the third... If i used readln(a); readln(b); readln(c); I got WA on test #12 if i used read(a); read(b); read(c); i pass that test What the? faint!! me too!! IMHO: readln() reads EOLN from input buffer (eq. 0x13 or 0x10) From problem: "Each of the three input lines contains an integer..." but third line of file may contain EOF (no EOLN) at end and this don't reads by readln(); may be there are mistake... But I use C++ and I also can have errors in Pascal... p.s. Sorry for my English. What is test 2? i get crash, are the values bigger than 255? What is case 2? The test #2 is quite correct. Look for a problem in your code... |
|