Common BoardThe product of natural numbers with a given condition in this problem will be maximal if and only if the middle arithmetic of these numbers is the most closely to the number e=2.71828... It's a mathematical sentence which are proved! P.S. Sorry for my bad English Why is that true? You can get AC without math :P Well, you only need to understand that optimal partition can't contain any x >= 4(as 2*(x-2) >= x in this case), it obviously can't contain ones, and it can't contain more than 2 copies of 2, as 2*2*2<3*3. Surpisingly, there is only one way to express any x >= 2 as sum of 3's and not more than two 2's. That's a very nice idea. Let me clarify it for those who had problems understanding bsu.mmf.team's English. First of all, 'middle arithmetic' is an arithmetic mean. The thing is, the product will be maximal if (a_1 + a_2 + ... + a_n) / n ≈ e. Well, it's not hard to figure out that the output of the program should be something like that: 3 * 3 * 3 * ... * ? used RMQ using segment tree to find lca in log(n) total time complexity O(n+q*(lgn)) = O(q*lgn) Almost the same numbers (0.268, 11500) for table for 2^i -th ancestor. Some graph problems having very low rating (caravans, Ivan's car) are quite hard to solve while some other problems (like Gear-wheels, Labyrinth) have rating two times higher and are incredibly easy. For each x (x=0,1,2,..,n-1) (x is horizontal axis) find y0=x*tg(a) and y1=(x+1)*tg(a), where tg(a) is (m-1)/(n-1). Add to answer floor (y1) - floor(y0) +1. If y1 is a whole number then subtract 1 from answer. program pr; Var n,k,i,s,q:integer; a:array[1..100000] of integer; b:array[1..100000] of integer; Begin q:=0; read(n,k); for i:=1 to n do readln(a[i]); for i:=1 to n do b[i]:=k-a[i]; for i:=1 to n do begin if b[i]<0 then s:=abs(b[i]); if b[i]>=0 then q:=q+b[i] ; end; write(s,' ',q) End. What is the WA#5?Какой WA#5? Можете объяснить, зачем даётся переменная m. Я успешно решил задачу без её использования: public static void Main() { var queryCount = int.Parse(Console.ReadLine().Split(' ')[0]); var queries = Enumerable .Range(0, queryCount) .Select(number => Console.ReadLine()) .ToArray(); foreach (var line in Solve(queries)) Console.WriteLine(line); } Не все люди решают задачи как Вы. Некоторым людям нужно количество запросов, чтобы, например, понять какого размера брать массив или тому подобное. Часто можно не учитывать какие то параметры, но это не значит, что они не нужны. Вот код... Я не понимаю как уменьшить расход памяти... но программа написана верно и работает... #include<iostream> using namespace std; int main(){ int n,i,j; float x; cin >> n; unsigned int a[250000]; for(i=1;i<=n;i++){ cin>>a[i]; } bool k=true; for (i=1;(i<n && k==true);i++){ k=false; for(j=1;j<=n-i;j++){ if (a[j]>a[j+1]) { swap(a[j],a[j+1]); k=true; } } } if (n%2==0){ cout << (a[n/2]+a[n/2+1])/2; } else {cout << a[n/2];} } Не храни 250 000 unsigned int 'ов. Храни, например, только половину -- 125 000. Тогда, очевидно, расход памяти сократится в два раза. Edited by author 12.06.2017 17:55 I solved this problem using a Binary indexed tree modification(read about Counter tree fenwick). It utilizes 2n memory and lets you find MAX of a subarray in logarithmic time. My solution: 0.062s, 812 kb, yet i haven't tried to do some optimization, I used std::vector which is slower than an array. Nevertheless, I'm pretty ok with such a result Could someone provide any hint? Edited by author 10.06.2017 23:14 Here's a brainless but simple way i did it. 0. Mini-optimization: remove all repeated numbers, leaving only unique ones, and reduce k respectively. Let A be the array with those unique numbers. 1. Make a list of indices that point to numbers which have 1st bit 1, 2nd bit 1, ..., 32nd bit 1. Like for example: L[1..32][0..nmax], L[5][0] — amount of numbers which have 1 on 5th bit, A[L[5][1]], A[L[5][2]], ... — those numbers. 2. Main algo. Make current_result = 0. Going from higher bit to lower (i = 1..32), if list is not empty (L[i][0] > 0) and ith bit is 0 in current_result, then choose random index j, and do current_result = current_result or L[i][j]. Increase i and repeat either till you reach the last bit or reach the limit of numbers to be deleted. Then update the best reached result. 3. Spam step 2 for a certain time. I initially decided to consume entire 2s, but apparently even 200ms is enough to ac. Clever way is DP, yeah, but requires thinking :) var a,b,c,d:integer; begin Read(a,b,c,d); While a<>c do begin a:=a+b; c:=c-d end; a:=c; WriteLn(a); end. Почемууу(( Why((( Карочь хрень полная Поможете?? Help me? Edited by author 25.03.2016 14:04 Have you tried to run your program on task sample locally, using debugger? Or at least print A and C values at the end of each cycle iteration? Why no? You should try. Edited by author 25.03.2016 15:29 Refer the example. I'm just a novice programmer. I try very hard. Help. I don't understand. ( YANDEX translator) "Refer the example" И чо? "Я отладила программу на примере, пытаюсь сдать acm, получаю WA. Почему?"? "При локальном запуске, на примере, получаю неправильный ответ/программа зависает. Почему?"? "Что такое debugger?"? В общем, телепаты в отпуске. P.S. Посмотрел попытки на acm.timus.ru. Все TLE 1. Патамушта цЫкл While a<>c do begin a:=a+b; c:=c-d end; бесконечный, как и ожидается. Edited by author 26.03.2016 03:04 Ну да :D Бывает. А ты на янде переводил? Особенно это выдал яндекс Патамушта цЫкл Они никогда не будут равны, если не состыкуются. Возьмем данные 150 50 1000 100 200(+50) 900 (-100) 250 800 300 700 350 600 400 500 450 400!!!! Edited by author 10.06.2017 17:58 Hi. My solution works on my computer but there is not. What's wrong with my code? #include <iostream> using namespace std; int main() { int n, c = 1; int pix[100][100]; for ( int i = 0; i < n; ++i ) { for ( int j = 0; j < n; ++j ) { pix[i][j] = 0; } } cin >> n; for ( int i = 0; i < n; ++i ) { for ( int j = (n - 1); j >= 0; --j ) { if ( pix[i][j] > 0 ) continue; int ii = i, jj = j; while ( ii < n && jj < n ) { pix[ii][jj] = c; ii++; jj++; c++; } } } for ( int i = 0; i < n; ++i ) { for ( int j = 0; j < n; ++j ) { cout << pix[i][j] << " "; } cout << endl; } return 0; } Edited by author 10.06.2017 15:16 Edited by author 10.06.2017 15:16 Edited by author 10.06.2017 15:17 import java.util.Scanner; public class _1206 { public static void main(String[] args) { Scanner s = new Scanner(System.in); int n = 36; long k = s.nextInt(); while (k > 1) { n *= 55; k--; } System.out.println(n); } } Edited by author 05.05.2014 17:02 var a:array [1..200000] of int64; n,i: integer; begin while not seekeof do begin inc(i); read(a[i]); end; for n:=i downto 1 do begin writeln(sqrt(a[n]):4:4); end; end. I copied the solution from the other guy p.s. Sorry man, i dont know your nickname Edited by author 09.06.2017 11:43 var i,j,n,n#,n2,a,m:integer; l:array[#..400#,#..2] of longint; begin read(n); for i:=# to n do read(l[i,#]); read(n1); for i:=# to n# do begin read(a); for j:=# to 400# do if l[j,#]=a then l[j,2]+=#; end; read(n2); for i:=# to n2 do begin read(a); for j:=# to 400# do if l[j,#]=a then l[j,2]+=#; end; for i:=# to 400# do if l[i,2]=2 then m:=m+#; writeln(m); end. Where is # change it with 1 using System; using System.Collections.Generic; using System.Linq; namespace ThreeprimeNumbers { public static class IntExtensions { public static bool IsPrime(this int number) { for (var divisor = 2; divisor < number; divisor++) if (number % divisor == 0) return false; return true; } } internal static class Solver { private static Func<IEnumerable<int>> ThreeDigitPrimeNumbers = () => Enumerable.Range(100, 900).Where(number => number.IsPrime()); private static Dictionary<int, IEnumerable<int>> PrefixCorrespondance(IEnumerable<int> primeNumbers) { return primeNumbers .GroupBy(number => number / 10) .ToDictionary(group => group.Key, group => group.Select(item => item)); } internal static long Solve(int digitCount) { var table = new long[digitCount - 2, 90]; var prefixes = PrefixCorrespondance(ThreeDigitPrimeNumbers()); for (var counter = 10; counter < 100; counter++) table[0, counter - 10] = (prefixes.TryGetValue(counter, out var collection)) ? collection.Count() : 0; for (var counter = 1; counter <= digitCount - 3; counter++) foreach (var pair in prefixes) foreach (var primeNumber in pair.Value) { var suffix = primeNumber % 100 - 10; table[counter, pair.Key - 10] += (suffix < 0) ? 0 : table[counter - 1, suffix]; table[counter, pair.Key - 10] %= 1000000009; } long sum = 0; for (var counter = 0; counter < 90; counter++) sum = (sum + table[digitCount - 3, counter]) % 1000000009; return sum; } public static void Main() { int.TryParse(Console.ReadLine(), out int digitCount); Console.Write(Solve(digitCount)); } } } I use ferrari method to find roots. Then i got next equation 1/((x-a)*(x-b)*(x-c)*(x-d)), where a,b,c,d -roots of equation. How to calculate such an integral??? If someone can answer here or kilik94@yandex.ru, i would be very grateful! i'm not exactly sure of the solution but i think you could use rezidue theorem and solve the complex integral What is the test data for Test#2? package main import ( "bufio" "os" "strconv" "fmt" "strings" ) func main() { reader := bufio.NewReader(os.Stdin) firstLine, _ := reader.ReadString('\n') count, _ := strconv.Atoi(strings.Trim(firstLine, "\n")) result := make([]int, count) for i := 0; i < count; i++ { position, _ := reader.ReadString('\n') result[i] = countFieldsUnderAttack(position) } for _, val := range result { fmt.Println(val) } } func countFieldsUnderAttack(position string) int { result := 0 var positionInts [2]int positionInts[0] = int(position[0]) - int('a') + 1 positionInts[1] = int(position[1]) - int('1') + 1 moves := [8][2]int{ {1, 2}, {2, 1}, {-1, -2}, {-2, -1}, {-1, 2}, {2, -1}, {1, -2}, {-2, 1}, } for _, move := range moves { if move[0] + positionInts[0] > 0 && move[0] + positionInts[0] <= 8 { if move[1] + positionInts[1] > 0 && move[1] + positionInts[1] <= 8 { result++ } } } return result } Edited by author 08.06.2017 23:12 Nevermind. Implemented reading input with bufio scanner and it worked. It seems that i dont understand go reader. |
|