Hallo. I have already solved this problem, but I want try to do it on different languages. So I need help with VB.NET 2010. Explain me, please, how I should read the input data. \u002f\u002a public class Main {} \u002a\u002f \u0069\u006d\u0070\u006f\u0072\u0074\u0020\u006a\u0061\u0076\u0061\u002e\u0069\u006f\u002e\u002a\u003b\u000d\u000a\u0069\u006d\u0070\u006f\u0072\u0074\u0020\u006a\u0061\u0076\u0061\u002e\u0075\u0074\u0069\u006c\u002e\u002a\u003b\u000d\u000a\u000d\u000a\u0070\u0075\u0062\u006c\u0069\u0063\u0020\u0063\u006c\u0061\u0073\u0073\u0020\u004d\u0061\u0069\u006e\u0020\u007b\u000d\u000a\u000d\u000a\u0009\u0053\u0063\u0061\u006e\u006e\u0065\u0072\u0020\u0069\u006e\u003b\u000d\u000a\u0009\u0050\u0072\u0069\u006e\u0074\u0057\u0072\u0069\u0074\u0065\u0072\u0020\u006f\u0075\u0074\u003b\u000d\u000a\u0009\u000d\u000a\u0009\u0076\u006f\u0069\u0064\u0020\u0073\u006f\u006c\u0076\u0065\u0028\u0029\u0020\u007b\u000d\u000a\u0009\u0009\u0069\u006e\u0074\u0020\u0061\u0020\u003d\u0020\u0069\u006e\u002e\u006e\u0065\u0078\u0074\u0049\u006e\u0074\u0028\u0029\u003b\u000d\u000a\u0009\u0009\u0069\u006e\u0074\u0020\u0062\u0020\u003d\u0020\u0069\u006e\u002e\u006e\u0065\u0078\u0074\u0049\u006e\u0074\u0028\u0029\u003b\u000d\u000a\u0009\u0009\u006f\u0075\u0074\u002e\u0070\u0072\u0069\u006e\u0074\u006c\u006e\u0028\u0061\u0020\u002b\u0020\u0062\u0029\u003b\u000d\u000a\u0009\u007d\u000d\u000a\u0009\u000d\u000a\u0009\u0076\u006f\u0069\u0064\u0020\u0072\u0075\u006e\u0028\u0029\u0020\u007b\u000d\u000a\u0009\u0009\u0069\u006e\u0020\u003d\u0020\u006e\u0065\u0077\u0020\u0053\u0063\u0061\u006e\u006e\u0065\u0072\u0028\u0053\u0079\u0073\u0074\u0065\u006d\u002e\u0069\u006e\u0029\u003b\u000d\u000a\u0009\u0009\u006f\u0075\u0074\u0020\u003d\u0020\u006e\u0065\u0077\u0020\u0050\u0072\u0069\u006e\u0074\u0057\u0072\u0069\u0074\u0065\u0072\u0028\u0053\u0079\u0073\u0074\u0065\u006d\u002e\u006f\u0075\u0074\u0029\u003b\u000d\u000a\u0009\u0009\u0074\u0072\u0079\u0020\u007b\u000d\u000a\u0009\u0009\u0009\u0073\u006f\u006c\u0076\u0065\u0028\u0029\u003b\u000d\u000a\u0009\u0009\u007d\u0020\u0066\u0069\u006e\u0061\u006c\u006c\u0079\u0020\u007b\u000d\u000a\u0009\u0009\u0009\u006f\u0075\u0074\u002e\u0063\u006c\u006f\u0073\u0065\u0028\u0029\u003b\u000d\u000a\u0009\u0009\u007d\u000d\u000a\u0009\u007d\u000d\u000a\u000d\u000a\u0009\u0070\u0075\u0062\u006c\u0069\u0063\u0020\u0073\u0074\u0061\u0074\u0069\u0063\u0020\u0076\u006f\u0069\u0064\u0020\u006d\u0061\u0069\u006e\u0028\u0053\u0074\u0072\u0069\u006e\u0067\u0020\u0061\u0072\u0067\u0073\u005b\u005d\u0029\u0020\u007b\u000d\u000a\u0009\u0009\u006e\u0065\u0077\u0020\u004d\u0061\u0069\u006e\u0028\u0029\u002e\u0072\u0075\u006e\u0028\u0029\u003b\u000d\u000a\u0009\u007d\u000d\u000a\u007d #include<iostream> #include<string> using namespace std; int n,sum[999],l=0; char a[101],b[101]; int main(){ cin>>n; for(int i=0;i<n;i++) cin>>a[i]>>b[i]; for(int i=0;i<n;i++){ if(a[i]=='a') a[i]='1'; if(a[i]=='b') a[i]='2'; if(a[i]=='c') a[i]='3'; if(a[i]=='d') a[i]='4'; if(a[i]=='e') a[i]='5'; if(a[i]=='f') a[i]='6'; if(a[i]=='g') a[i]='7'; if(a[i]=='h') a[i]='8'; } for(int i=0;i<n;i++){ if(a[i]-48+2<=8&&a[i]-48+2>0&&b[i]-48+1<=8&&b[i]-48+1>0) sum[i]=sum[i]+1; if(a[i]-48+1<=8&&a[i]-48+1>0&&b[i]-48+2<=8&&b[i]-48+2>0) sum[i]=sum[i]+1; if(a[i]-48-1<=8&&a[i]-48-1>0&&b[i]-48+2<=8&&b[i]-48+2>0) sum[i]=sum[i]+1; if(a[i]-48-2<=8&&a[i]-48-2>0&&b[i]-48+1<=8&&b[i]-48+1>0) sum[i]=sum[i]+1; if(a[i]-48-2<=8&&a[i]-48-2>0&&b[i]-48-1<=8&&b[i]-48-1>0) sum[i]=sum[i]+1; if(a[i]-48-1<=8&&a[i]-48-1>0&&b[i]-48-2<=8&&b[i]-48-2>0) sum[i]=sum[i]+1; if(a[i]-48+1<=8&&a[i]-48+1>0&&b[i]-48-2<=8&&b[i]-48-2>0) sum[i]=sum[i]+1; if(a[i]-48+2<=8&&a[i]-48+2>0&&b[i]-48-1<=8&&b[i]-48-1>0) sum[i]=sum[i]+1; } for(int i=0;i<n;i++) cout<<sum[i]<<endl; } Подсказка Используйте + var n,i,j,k:integer;s:real;a:array[1..20,1..20] of real;zer:boolean; label 1; begin s:=1; readln(n); for i:=1 to n do for j:=1 to n do read(a[i,j]); for k:=1 to n-1 do if a[k,k]=0 then begin zer:=true;goto 1; end else for i:=k+1 to n do for j:=k+1 to n do a[i,j]:=a[i,j]-a[i,k]*a[k,j]/a[k,k]; for k:=1 to n do s:=s*a[k,k]; writeln(s:0:0); 1:if zer then writeln('0'); for i:=1 to n do begin for j:=1 to n do write(a[i,j],' '); writeln; end; end. var a:array[1..100,1..100] of integer;k,n,m,max,x,y,i,j:integer; begin readln(n,m); readln(x,y); for i:=1 to n do for j:=1 to n do a[i,j]:=abs(i-x)+abs(j-y); for k:=1 to m-1 do begin readln(x,y); for i:=1 to n do for j:=1 to n do if a[i,j]>abs(i-x)+abs(j-y) then a[i,j]:=abs(i-x)+abs(j-y); end; for i:=1 to n do for j:=1 to n do if a[i,j]>max then max:=a[i,j]; writeln(max); end. var ab,bc,ac,ad,bd,cd:real; a1,a2,a3,a4,b1,b2,b3,b4:real; s,s1,s2,s3:real; function stor(x,y,z,t:real):real; begin stor:=sqrt((sqr(x-y))+(sqr(z-t))); end; function square(n,k,v:real):real; var m:real; begin m:=(n+k+v)/2; square:=trunc(sqrt(m*(m-n)*(m-v)*(m-k))*10); end; begin {repeat} writeln ('Введите координату вершины A'); readln (a1,b1); writeln ('Введите координату вершины B'); readln (a2,b2); writeln ('Введите координату вершины C'); readln (a3,b3); writeln ('Введите координаты точки D'); readln(a4,b4); AB:=stor(a1,a2,b1,b2); BC:=stor(a2,a3,b2,b3); AC:=stor(a1,a3,b1,b3); ad:=stor(a1,a4,b1,b4); bd:=stor(a2,a4,b2,b4); cd:=stor(a3,a4,b3,b4); {if(AB>=BC+AC)or(AC>=AB+BC)or(BC>=AB+AC) then writeln('Это не треугольник, введите данные заново'); until (AB<BC+AC)and(AC<AB+BC)and(BC<AB+AC);} s:=square(ab,bc,ac); s1:=square(ab,bd,ad); s2:=square(bd,cd,bc); s3:=square(cd,ad,ac); {writeln(s,' ',s1,' ',s2,' ',s3);} if abs(s-s1-s2-s3)<5 then writeln ('точка D является внутренней точкой треугольника ABC') else writeln ('точка D не является внутренней точкой треугольника ABC'); {writeln(abs(s-s1-s2-s3));} end. what's wrong with this site?? it's about 36 hours that all problems have waiting status. Sorry, due to hardware problem we have to stop judging at least until tomorrow. You may continue to submit your solutions, they will be judged as soon as the problem is fixed. Looks like hardware problems are resolved now. Judgement system is working in its usual mode. Have fun! var a,b:integer; begin readln(a,b); writeln(a+b); end. probably you are wrong this is so hard problem :) !!! var a,b:longint; begin read(a,b); writeln(a+b); end. (Try this,not readln,but read) :) Edited by author 12.04.2010 16:14 I uploaded the following solution but it only says "crash": using System; namespace Week2 { class Program { static void Main(string[] args) { int a, b; a = int.Parse(Console.ReadLine()); b = int.Parse(Console.ReadLine()); Console.WriteLine(a + b); } } } It happens because of you use ReadLine. These digits are on the same line, so you should just split them by space. You can find an example there: http://acm.timus.ru/help.aspx?topic=csharp using System; public class Sum { private static void Main() { string[] tokens = Console.ReadLine().Split(' '); Console.WriteLine(int.Parse(tokens[0]) + int.Parse(tokens[1])); } } Edited by author 14.10.2012 01:59Pascal var a,b:real; begin readln(a); readln(b); writeln(a+b); end. Edited by author 10.10.2012 17:42 Edited by author 13.10.2012 20:39 I'm not a Pascal programmer... But... Maybe because these digits are on the same line and you should use "read" instead of "readln"...? Yes, read instead of readln, and also longint instead of real What is the problem??? #include<iostream> using namespace std; main() {int a; int b; cin>>a; cin>>b; cout<<a+b<<endl; } #include<iostream> using namespace std; void main() {int a; int b; cin>>a; cin>>b; cout<<a+b<<endl; } just for return type!Thanks. A good way to get a competitive edge is to write down a game plan for what you're going to do in a contest round. This will help you script out your actions, in terms of what to do both when things go right and when things go wrong. This way you can spend your thinking time in the round figuring out programming problems and not trying to figure out what the heck you should do next... it's sort of like precomputing your reactions to most situations. Mental preparation is also important. Game Plan For A Contest Round Read through ALL the problems FIRST; sketch notes with algorithm, complexity, the numbers, data structs, tricky details, ... * Brainstorm many possible algorithms - then pick the stupidest that works! * DO THE MATH! (space & time complexity, and plug in actual expected and worst case numbers) * Try to break the algorithm - use special (degenerate?) test cases * Order the problems: shortest job first, in terms of your effort (shortest to longest: done it before, easy, unfamiliar, hard) Coding a problem - For each, one at a time: * Finalize algorithm * Create test data for tricky cases * Write data structures * Code the input routine and test it (write extra output routines to show data?) * Code the output routine and test it * Stepwise refinement: write comments outlining the program logic * Fill in code and debug one section at a time * Get it working & verify correctness (use trivial test cases) * Try to break the code - use special cases for code correctness * Optimize progressively - only as much as needed, and keep all versions (use hard test cases to figure out actual runtime) Time management strategy and "damage control" scenarios Have a plan for what to do when various (foreseeable!) things go wrong; imagine problems you might have and figure out how you want to react. The central question is: "When do you spend more time debugging a program, and when do you cut your losses and move on?". Consider these issues: * How long have you spent debugging it already? * What type of bug do you seem to have? * Is your algorithm wrong? * Do you data structures need to be changed? * Do you have any clue about what's going wrong? * A short amount (20 mins) of debugging is better than switching to anything else; but you might be able to solve another from scratch in 45 mins. * When do you go back to a problem you've abandoned previously? * When do you spend more time optimizing a program, and when do you switch? * Consider from here out - forget prior effort, focus on the future: how can you get the most points in the next hour with what you have? Have a checklist to use before turning in your solutions: * Code freeze five minutes before end of contest? Turn asserts off. * Turn off debugging output. Tips & Tricks * Brute force it when you can * KISS: Simple is smart! * Hint: focus on limits (specified in problem statement) * Waste memory when it makes your life easier (if you can get away with it) * Don't delete your extra debugging output, comment it out * Optimize progressively, and only as much as needed * Keep all working versions! * Code to debug: o whitespace is good, o use meaningful variable names, o don't reuse variables, o stepwise refinement, o COMMENT BEFORE CODE. * Avoid pointers if you can * Avoid dynamic memory like the plague: statically allocate everything. * Try not to use floating point; if you have to, put tolerances in everywhere (never test equality) * Comments on comments: o Not long prose, just brief notes o Explain high-level functionality: ++i; /* increase the value of i by */ is worse than useless o Explain code trickery o Delimit & document functional sections o As if to someone intelligent who knows the problem, but not the code o Anything you had to think about o Anything you looked at even once saying, "now what does that do again?" o Always comment order of array indices * Keep a log of your performance in each contest: successes, mistakes, and what you could have done better; use this to rewrite and improve your game plan! Complexity Basics and order notation The fundamental basis of complexity analysis revolves around the notion of ``big oh'' notation, for instance: O(N). This means that the algorithm's execution speed or memory usage will double when the problem size doubles. An algorithm of O(N 2) will run about four times slower (or use 4x more space) when the problem size doubles. Constant-time or space algorithms are denoted O(1). This concept applies to time and space both; here we will concentrate discussion on time. One deduces the O() run time of a program by examining its loops. The most nested (and hence slowest) loop dominates the run time and is the only one mentioned when discussing O() notation. A program with a single loop and a nested loop (presumably loops that execute N times each) is O(N 2), even though there is also a O(N) loop present. Of course, recursion also counts as a loop and recursive programs can have orders like O(b N), O(N!), or even O(N N). Rules of thumb * When analyzing an algorithm to figure out how long it might run for a given dataset, the first rule of thumb is: modern (2004) computers can deal with 100M actions per second. In a five second time limit program, about 500M actions can be handled. Really well optimized programs might be able to double or even quadruple that number. Challenging algorithms might only be able to handle half that much. Current contests usually have a time limit of 1 second for large datasets. * 16MB maximum memory use * 210 ~approx~ 10 3 * If you have k nested loops running about N iterations each, the program has O(N k) complexity. * If your program is recursive with b recursive calls per level and has l levels, the program O(b l) complexity. * Bear in mind that there are N! permutations and 2 n subsets or combinations of N elements when dealing with those kinds of algorithms. * The best times for sorting N elements are O(N log N). * DO THE MATH! Plug in the numbers. Examples A single loop with N iterations is O(N): 1 sum = 0 2 for i = 1 to n 3 sum = sum + i A double nested loop is often O(N 2): # fill array a with N elements 1 for i = 1 to n-1 2 for j = i + 1 to n 3 if (a[i] > a[j]) swap (a[i], a[j]) Note that even though this loop executes N x (N+1) / 2 iterations of the if statement, it is O(N 2) since doubling N quadruples the execution times. Consider this well balanced binary tree with four levels: An algorithm that traverses a general binary tree will have complexity O(2 N). Solution Paradigms Generating vs. Filtering Programs that generate lots of possible answers and then choose the ones that are correct (imagine an 8-queen solver) are filters. Those that hone in exactly on the correct answer without any false starts are generators. Generally, filters are easier (faster) to code and run slower. Do the math to see if a filter is good enough or if you need to try and create a generator. Precomputation Sometimes it is helpful to generate tables or other data structures that enable the fastest possible lookup of a result. This is called precomputation (in which one trades space for time). One might either compile precomputed data into a program, calculate it when the program starts, or just remember results as you compute them. A program that must translate letters from upper to lower case when they are in upper case can do a very fast table lookup that requires no conditionals, for example. Contest problems often use prime numbers - many times it is practical to generate a long list of primes for use elsewhere in a program. Decomposition (The Hardest Thing At Programming Contests) While there are fewer than 20 basic algorithms used in contest problems, the challenge of combination problems that require a combination of two algorithms for solution is daunting. Try to separate the cues from different parts of the problem so that you can combine one algorithm with a loop or with another algorithm to solve different parts of the problem independently. Note that sometimes you can use the same algorithm twice on different (independent!) parts of your data to significantly improve your running time. Symmetries Many problems have symmetries (e.g., distance between a pair of points is often the same either way you traverse the points). Symmetries can be 2-way, 4-way, 8-way, and more. Try to exploit symmetries to reduce execution time. For instance, with 4-way symmetry, you solve only one fourth of the problem and then write down the four solutions that share symmetry with the single answer (look out for self-symmetric solutions which should only be output once or twice, of course). Forward vs. Backward Surprisingly, many contest problems work far better when solved backwards than when using a frontal attack. Be on the lookout for processing data in reverse order or building an attack that looks at the data in some order or fashion other than the obvious. Simplification Some problems can be rephrased into a somewhat different problem such that if you solve the new problem, you either already have or can easily find the solution to the original one; of course, you should solve the easier of the two only. Alternatively, like induction, for some problems one can make a small change to the solution of a slightly smaller problem to find the full answer. The Idea Solving a problem using complete search is based on the ``Keep It Simple, Stupid'' principle. The goal of solving contest problems is to write programs that work in the time allowed, whether or not there is a faster algorithm. Complete search exploits the brute force, straight-forward, try-them-all method of finding the answer. This method should almost always be the first algorithm/solution you consider. If this works within time and space constraints, then do it: it's easy to code and usually easy to debug. This means you'll have more time to work on all the hard problems, where brute force doesn't work quickly enough. In the case of a problem with only fewer than a couple million possibilities, iterate through each one of them, and see if the answer works. Careful, Careful Sometimes, it's not obvious that you use this methodology. Problem: Party Lamps [IOI 98] You are given N lamps and four switches. The first switch toggles all lamps, the second the even lamps, the third the odd lamps, and last switch toggles lamps 1, 4, 7, 10, ... . Given the number of lamps, N, the number of button presses made (up to 10,000), and the state of some of the lamps (e.g., lamp 7 is off), output all the possible states the lamps could be in. Naively, for each button press, you have to try 4 possibilities, for a total of 410000 (about 106020 ), which means there's no way you could do complete search (this particular algorithm would exploit recursion). Noticing that the order of the button presses does not matter gets this number down to about 100004 (about 1016 ), still too big to completely search (but certainly closer by a factor of over 106000 ). However, pressing a button twice is the same as pressing the button no times, so all you really have to check is pressing each button either 0 or 1 times. That's only 24 = 16 possibilities, surely a number of iterations solvable within the time limit. Problem 3: The Clocks [IOI 94] A group of nine clocks inhabits a 3 x 3 grid; each is set to 12:00, 3:00, 6:00, or 9:00. Your goal is to manipulate them all to read 12:00. Unfortunately, the only way you can manipulate the clocks is by one of nine different types of move, each one of which rotates a certain subset of the clocks 90 degrees clockwise. Find the shortest sequence of moves which returns all the clocks to 12:00. The ``obvious'' thing to do is a recursive solution, which checks to see if there is a solution of 1 move, 2 moves, etc. until it finds a solution. This would take 9k time, where k is the number of moves. Since k might be fairly large, this is not going to run with reasonable time constraints. Note that the order of the moves does not matter. This reduces the time down to k9 , which isn't enough of an improvement. However, since doing each move 4 times is the same as doing it no times, you know that no move will be done more than 3 times. Thus, there are only 49 possibilities, which is only 262,072, which, given the rule of thumb for run-time of more than 10,000,000 operations in a second, should work in time. The brute-force solution, given this insight, is perfectly adequate. Sample Problems Milking Cows [USACO 1996 Competition Round] Given a cow milking schedule (Farmer A milks from time 300 to time 1000, Farmer B from 700 to 1200, etc.), calculate * The longest time interval in which at least one cow was being milked * The longest time interval in which no cow is being milked Perfect Cows & Perfect Cow Cousins [USACO 1995 Final Round] A perfect number is one in which the sum of the proper divisors add up to the number. For example, 28 = 1 + 2 + 4 + 7 + 14. A perfect pair is a pair of numbers such that the sum of the proper divisor of each one adds up to the other. There are, of course, longer perfect sets, such that the sum of the divisors of the first add up to the second, the second's divisors to the third, etc., until the sum of the last's proper divisors add up to the first number. Each cow in Farmer John's ranch is assigned a serial number. from 1 to 32000. A perfect cow is one which has a perfect number as its serial. A group of cows is a set of perfect cow cousins if their serial numbers form a perfect set. Find all perfect cows and perfect cow cousins. Sample Problem: Barn Repair [1999 USACO Spring Open] There is a long list of stalls, some of which need to be covered with boards. You can use up to N (1 <= N <= 50) boards, each of which may cover any number of consecutive stalls. Cover all the necessary stalls, while covering as few total stalls as possible. The Idea The basic idea behind greedy algorithms is to build large solutions up from smaller ones. Unlike other approaches, however, greedy algorithms keep only the best solution they find as they go along. Thus, for the sample problem, to build the answer for N = 5, they find the best solution for N = 4, and then alter it to get a solution for N = 5. No other solution for N = 4 is ever considered. Greedy algorithms are fast, generally linear to quadratic and require little extra memory. Unfortunately, they usually aren't correct. But when they do work, they are often easy to implement and fast enough to execute. Problems There are two basic problems to greedy algorithms. How to Build How does one create larger solutions from smaller ones? In general, this is a function of the problem. For the sample problem, the most obvious way to go from four boards to five boards is to pick a board and remove a section, thus creating two boards from one. You should choose to remove the largest section from any board which covers only stalls which don't need covering (so as to minimize the total number of stalls covered). To remove a section of covered stalls, take the board which spans those stalls, and make into two boards: one of which covers the stalls before the section, one of which covers the stalls after the section. Does it work? The real challenge for the programmer lies in the fact that greedy solutions don't always work. Even if they seem to work for the sample input, random input, and all the cases you can think of, if there's a case where it won't work, at least one (if not more!) of the judges' test cases will be of that form. For the sample problem, to see that the greedy algorithm described above works, consider the following: Assume that the answer doesn't contain the large gap which the algorithm removed, but does contain a gap which is smaller. By combining the two boards at the end of the smaller gap and splitting the board across the larger gap, an answer is obtained which uses as many boards as the original solution but which covers fewer stalls. This new answer is better, so therefore the assumption is wrong and we should always choose to remove the largest gap. If the answer doesn't contain this particular gap but does contain another gap which is just as large, doing the same transformation yields an answer which uses as many boards and covers as many stalls as the other answer. This new answer is just as good as the original solution but no better, so we may choose either. Thus, there exists an optimal answer which contains the large gap, so at each step, there is always an optimal answer which is a superset of the current state. Thus, the final answer is optimal. Conclusions If a greedy solution exists, use it. They are easy to code, easy to debug, run quickly, and use little memory, basically defining a good algorithm in contest terms. The only missing element from that list is correctness. If the greedy algorithm finds the correct answer, go for it, but don't get suckered into thinking the greedy solution will work for all problems. Sample Problems Sorting a three-valued sequence [IOI 1996] You are given a three-valued (1, 2, or 3) sequence of length up to 1000. Find a minimum set of exchanges to put the sequence in sorted order. Algorithm The sequence has three parts: the part which will be 1 when in sorted order, 2 when in sorted order, and 3 when in sorted order. The greedy algorithm swaps as many as possible of the 1's in the 2 part with 2's in the 1 part, as many as possible 1's in the 3 part with 3's in the 1 part, and 2's in the 3 part with 3's in the 2 part. Once none of these types remains, the remaining elements out of place need to be rotated one way or the other in sets of 3. You can optimally sort these by swapping all the 1's into place and then all the 2's into place. Analysis: Obviously, a swap can put at most two elements in place, so all the swaps of the first type are optimal. Also, it is clear that they use different types of elements, so there is no ``interference'' between those types. This means the order does not matter. Once those swaps have been performed, the best you can do is two swaps for every three elements not in the correct location, which is what the second part will achieve (for example, all the 1's are put in place but no others; then all that remains are 2's in the 3's place and vice-versa, and which can be swapped). Friendly Coins - A Counterexample [abridged] Given the denominations of coins for a newly founded country, the Dairy Republic, and some monetary amount, find the smallest set of coins that sums to that amount. The Dairy Republic is guaranteed to have a 1 cent coin. Algorithm: Take the largest coin value that isn't more than the goal and iterate on the total minus this value. (Faulty) Analysis: Obviously, you'd never want to take a smaller coin value, as that would mean you'd have to take more coins to make up the difference, so this algorithm works. Maybe not: Okay, the algorithm usually works. In fact, for the U.S. coin system {1, 5, 10, 25}, it always yields the optimal set. However, for other sets, like {1, 5, 8, 10} and a goal of 13, this greedy algorithm would take one 10, and then three 1's, for a total of four coins, when the two coin solution {5, 8} also exists. Topological Sort Given a collection of objects, along with some ordering constraints, such as "A must be before B," find an order of the objects such that all the ordering constraints hold. Algorithm: Create a directed graph over the objects, where there is an arc from A to B if "A must be before B." Make a pass through the objects in arbitrary order. Each time you find an object with in-degree of 0, greedily place it on the end of the current ordering, delete all of its out-arcs, and recurse on its (former) children, performing the same check. If this algorithm gets through all the objects without putting every object in the ordering, there is no ordering which satisfies the constraints. # include <stdio.h> # include <conio.h> # include <math.h> # include <stdlib.h> # include <time.h> # include <limits.h> int count = 0; int A[100][100] , M , N , gidildi[100] = {0}; grafoku() { int i , j , k; scanf("%i %i",&N,&M); for( i = 0 ; i < N ; ++i ) for( k = 0 ; k < N ; ++k ) A[i][k] = 0;
for( k = 0 ; k < M ; ++k ){ scanf("%d %d",&i , &j); A[i - 1][j - 1] = 1; A[j - 1][i - 1] = 1; }
return 0; } DFS( unsigned int dugum ) { int gidildi[100] = {0}; unsigned i;
gidildi[dugum] = 1; for( i = 0 ; i < N ; ++i ) if( A[dugum][i] != 0 && gidildi[i] == 0 ) DFS(i); } int kontrol(int dugum , int i) { A[dugum][i] = 0; A[i][dugum] = 0; DFS(i); for( i = 0 ; i < N ; ++i ) gidildi[i] = 0; if( count == N ){ count = 0; return 1; } count = 0; return 0; } main() { int i , j = 1 , toplam = 0 , tek = 0 , euler_yolu[100] = {0} , dugum , sinir;
grafoku();
/*Euler yolu var mı?*/
for( i = 0 ; i < N ; ++i ){ for( j = 0 ; j < N ; ++j ) toplam += A[i][j]; if( toplam % 2 == 1 ) tek++; toplam = 0; }
if( !( tek == 2 || tek == 0 ) ) return;
/*Euler yolu var mı?(bitti)*/
dugum = 0; for( i = 0 ; i < N ; ++i ) if( A[dugum][i] == 1 ) if( kontrol(dugum , i) ){ euler_yolu[j] = i; dugum = i; j++; i = 0; } else{ A[dugum][i] = 1; A[i][dugum] = 1; } /*yazdırılıyor.*/
for( i = 0 ; i <= M ; ++i ) printf("%i ",euler_yolu[i]);
system("pause"); }
import java.io.*; public class D { public static void main (String args []) throws Exception { BufferedReader d = new BufferedReader(new InputStreamReader(System.in)); String v = d.readLine(); BufferedReader e = new BufferedReader(new InputStreamReader(System.in)); String c = e.readLine(); try { int a = Integer.parseInt(v); int b = Integer.parseInt(c); System.out.println(a+b); } catch(Exception e1) {System.out.println("Error translating text to int");} System.out.println(); } } Why Wrong answer?? That he WANT????? Read FAQ how to input numbers I wonder how to achieve 0.001 execution time? If someone point out general approches to optimize time complexities, it'll be better! Thank you in advance! Approve. I has never got the time less than 0.015 even on this stupid problem. Maybe, the point is in the language you use? I write in C, compile as C++ code. Maybe, if I wrote in Pascal, I would approach 0.001? I believe the runtime you get also depends on the traffic of judge so if you have sent your solution for 999 times and you've got 0.015 all the time, you may send it once more, for the 1000th time and get 0.001 :-D time 0.001 is impossible the minimal time on timus is 0.014 and you should sent the problem 100 times to achieve it. It's minimal time any compilator need to read and write an so on. Hi, you can check my result it's 0.001/ id: 55151 Edited by author 28.03.2012 12:34 Edited by author 19.07.2012 00:39 // Nvidia CUDA Driver API 4.1 //======================== #include <cuda.h> #include <stdio.h> #include <device_launch_parameters.h> #include <Windows.h> //======================== #pragma comment(lib,"cuda.lib") //======================== int wmain() { // CUdevice cuDev; CUcontext cuCtx; CUmodule cuModl; CUfunction cuFunc; // CUdeviceptr pDmem[3]; CUstream stream[4]; CUevent start; CUevent end; size_t paramsize; void* kernelparams[4]; float time; // cuInit(0); cuDeviceGet(&cuDev,0); cuCtxCreate(&cuCtx,CU_CTX_SCHED_AUTO,cuDev); // cuEventCreate(&start,0); cuEventCreate(&end,0); // for(int i=0; i<4; i++) { if(cuStreamCreate(&stream[i],0)) { return 0; } } // cuModuleLoad(&cuModl,"matrixtile.ptx"); cuModuleGetFunction(&cuFunc,cuModl,"add"); // for(int i=0; i<3; i++) { if(cuMemAlloc(&pDmem[i],sizeof(int))) { return 0; } }
int a = 1; int b = 8; int r; cuEventRecord(start,0); if(cuMemcpyHtoDAsync(pDmem[0],(void*)&a,sizeof(int),stream[0])) { return 0; } if(cuMemcpyHtoDAsync(pDmem[1],(void*)&b,sizeof(int),stream[1])) { return 0; } if(cuMemcpyHtoDAsync(pDmem[2],(void*)&r,sizeof(int),stream[2])) { return 0; } // paramsize = sizeof(pDmem); kernelparams[0] = &pDmem[0]; kernelparams[1] = &pDmem[1]; kernelparams[2] = &pDmem[2]; kernelparams[3] = ¶msize;
// cuLaunchKernel(cuFunc,1,1,1,1,1,1,0,stream[3],kernelparams,0); cuEventRecord(end,0); cuEventSynchronize(end); cuEventElapsedTime(&time,start,end); wprintf(L"Time = %.7f\n\n",time); // cuMemcpyDtoHAsync(&r,pDmem[2],sizeof(int),stream[3]); cuCtxSynchronize(); // cuModuleUnload(cuModl); cuCtxDestroy(cuCtx); wprintf(L"result = %d\n",r); // ReadFile(GetStdHandle(STD_INPUT_HANDLE),0,0,0,0); return 0; } Time = 0.0076 milliseconds Edited by author 25.03.2012 21:23 you're genius bro ;) :D nice solution :) #include <stdio.h> main(){ int a,b; freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); scanf("%d %d",&a, &b); printf("%d",a+b); } Why I had wrong answer? In Visual Studio working perfectly! Edited by author 17.03.2012 19:46 Edited by author 17.03.2012 19:46 #include <stdio.h> int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "rt", stdin); freopen("output.txt", "wt", stdout); #endif int a, b; scanf("%d%d", &a, &b); printf("%d\n", a + b); return 0; } Network Flow... program problem; var en,et,ec,eu,ep,ex:Array[0..250000] of longint; dis:array[0..1000] of longint; v:array[0..1000] of boolean; i,j,k,n,m,w,cost,l:longint; a,b,ans,left,right:longint; function min(a,b:longint):longint; begin if a<b then min:=a else min:=b end; procedure addedge(s,t,c,u,k:longint); begin inc(l); en[l]:=en[s]; en[s]:=l; et[l]:=t; ec[l]:=c; eu[l]:=u; ep[l]:=l+k; end; procedure build(s,t,u,c:longint); begin addedge(s,t,c,u,1); addedge(t,s,-c,0,-1); end; function aug(no,m:longint):longint; var i,d:longint; begin if no=n then begin inc(cost,m*dis[1]); exit; end; v[no]:=true; i:=ex[no]; while i<>0 do begin if (eu[i]>0)and not v[et[i]] and(dis[et[i]]+ec[i]=dis[no]) then begin d:=aug(et[i],min(m,eu[i])); if d>0 then begin dec(eu[i],d); inc(eu[ep[i]],d); ex[no]:=i; exit(d); end; end; i:=en[i]; end; ex[no]:=i; exit(0); end; function modlabel:boolean; var d,i,j:longint; begin d:=maxlongint; for i:=1 to n do if v[i] then begin j:=en[i]; while j<>0 do begin if (eu[j]>0)and not v[et[j]] and(ec[j]-dis[i]+dis[et[j]]<d) then d:=ec[j]-dis[i]+dis[et[j]]; j:=en[j] end; end; if d=maxlongint then exit(true); for i:=1 to n do if v[i] then begin v[i]:=false; inc(dis[i],d); end; exit(false); end; function work:longint; var i:longint; begin cost:=0; repeat for i:=1 to n do ex[i]:=en[i]; while aug(1,maxlongint)>0 do fillchar(v,sizeof(v),0); until modlabel; work:=cost; end; function solve(x,d:longint):longint; var i,k,t,p,last,cost,lk:longint; begin fillchar(en,sizeof(en),0); fillchar(dis,sizeof(dis),0); k:=0; n:=2; t:=x; p:=0; while x<>0 do begin k:=k+x mod 10; x:=x div 10; inc(p); end; n:=1; x:=t; l:=k+p+1; last:=1; cost:=1; lk:=0; while x<>0 do begin k:=x mod 10; for i:=1 to k do begin inc(n); build(last,n,1,-cost); build(n,last+k+1,1,0); end; cost:=cost*10; inc(n); if last<>1 then begin if lk<k then build(1,last,k-lk,0); if k<lk then build(last,n,lk-k,0); end; last:=n; x:=x div 10; if lk<k then lk:=k; end; build(1,n,1,d); solve:=-work; end; begin readln(a,b); left:=1; right:=1000000000; while right-left>15000 do begin ans:=(left+right)shr 1; if solve(ans,b)>a then right:=ans else left:=ans; end; for i:=left to right do if solve(i,b)=a then begin writeln(i); halt; end; end. funny... =) :D Accepted! It Works!!! Edited by author 24.09.2012 17:13 #include <cstdio> int main() { int a,b; scanf("%i %i",&a,&b); printf("%i",a+b); return 0; } Hi, i'm trying to solve the A+B problem, and it works on my computer. But the compiler of this site doesn't accept my solution. It says "Compilation error" : "11e2cd04-2636-421c-9639-3a45ac221379 11e2cd04-2636-421c-9639-3a45ac221379(4) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int" here is my program: #include <iostream> using namespace std; main () { long a,b; cin >> a; cin >> b; cout << a+b; }; Where did I do mistakes? Thank you for attention. try this: #include <iostream> using namespace std; int main () { long a,b; cin >> a; cin >> b; cout << a+b; } But, it's the same. (: I think the difference is in return type of main. Kindly correct if i am wrong. I think the difference is in return type of main. Kindly correct if i am wrong. Thank you so much! Finally it worked! #include<stdio.h> void main() { float a,b,s=0.0; scanf("%f%f",&a,&b); s=a+b; printf("sum=%f",s) ; } i don't know where is problem in this programme Edited by author 27.09.2011 20:50 use int, lol Edited by author 15.10.2011 15:51 This is an example problem. You should read an FAQ to get start. First of all you haven't shown the type of main function :) output must be as this : cout <<(a+b); or: cout <<'a+b'; sorry for my English) int sum(int a,int b) { if(a==0)return b; if(b==0)return a; return sum((a&b)<<1,a^b); } so,cool. help me ! my email:mronoal@163.com thanks! oooo it's very task. But does not work. Why? ------------------- #include<iostream> using namespace std; int main() { int a,b; cout<<"a=";cin>>a; cout<<"b=";cin>>b; cout<<a+b<<endl; system("pause"); } Why it's have a mistakes Because you were asked to output only the sum of A and B, and NOT "a=" and "b=". A good thing is to read FAQ before starting to solve problems. |
|