How one can mathematically prove that it is always optimal to send people in one direction with max number of seats? Why I don't get AC here is my code: var n,k,m,AC:integer; begin readln(n,k); m:=n div 2; if k=m then AC:=0; if k<m then AC:=m-k; if k>m then AC:=k-m-1; write(AC); end. #include<stdio.h> int n,k,answer; int main() { scanf("%d %d",&n,&k); int len = n/2; if(k==len) { printf("0"); return 0; } else if(k<len) { answer = len - k; } else { answer = k - len - 1; } printf("%d",answer); } I have the same problem: test no. 5, wrong answer. (Sorry, i don't know english well) Я запихнул свой алгоритм в циклы for, ввод всех возможных значений, вывод. Просмотрел всё вручную, нет ошибок! Carefully read the condition. Visitor chooses a side in such a way that the number of people over whose feet he will stumble will be minimal. It is not always the shortest path. Внимательнее читайте условие. Зритель выбирает сторону так, чтобы споткнуться о меньшее число людей. Это не всегда наикратчайший путь. Try test 50 50 answer 47 40-20 18 40 27 24 .... ???? PROFIT!!! Edited by author 08.06.2010 03:26 Edited by author 08.06.2010 03:27 k == n is the same situation as k == 1 Very easy:) *first if k>n/2 make it smaller n/2: k=n-k+1 *then the answer is (n-k-2)
(......[Vasya].......[n-1][n] if [n-1] and [n] sit,then all people between [Vasya] and [n-1] will stumble at Vasya. And this will be the maximal answer ) *special case: n=2 => answer is 0 i dnt understand ur soln. why it be so?? the prog sttmnt says visitor chooses left || right end based on minimal no. of people s/he need to stumble upon. so let be test: 10 3 ur soln gives: 5 let last 2 and 1st 2 beseated. now why rest people should choose left end. prog sttmnt says it shd be right end. because only 2 need to be stumbled upon if right else 3. bt ur soln gives ac. so i thnk the prog sttmnt is all wrong || i am weak in english || the author is!!! Edited by author 29.11.2009 17:00 Roland is right example: 6 (1 Man, 2 Man, 3 empty, 4 empty, 5 empty, 6 You); answer - 3 Can you explain how do you get answer 3 for test 6,1? My solution: Veeeee Veeee1 V2eee1 V2ee31 V24e31 V24531, Where V - Vasya, e - empty place, 1,2,3... - visitors. Numbers 2 and 4 will stumble Vasyas feet, so my answer is 2. Veeeee Veeee1 Veee21 Vee321 Ve4321 V54321 The worst case. Answer - 3. Why 3? i think it have to be 4. Like Veeee1 - 0, Veee21 - 1, Vee321 - 2, Ve4321 - 3, V54321 - 4. The first case has the same problem tho Nvm, i get it. (the last sentence in first paragraph) Edited by author 23.01.2020 16:05 I think is 2 (1 man, 2 man ,3 empty, 4 man,5 man, 6 you) ,the 3man may from left Edited by author 11.09.2016 19:43 Edited by author 11.09.2016 19:43 I don`t understand why it works. Example: 10 4 ###[Vasya]###### At worst viewers with the numbers 1, 2 will come first: [1][2]#[Vasya]###### and viewer 3 stumbles over Vasya`s feets. Next come viewers with the numbers 9 and 10: [1][2][3][Vasya]####[9][10] and viewers 5, 6, 7, 8 stumble over feets. So the answer is 5, but your program (AC program!) gives 4... Edited by author 08.12.2010 14:45 Next come viewers with the numbers 9 and 10: [1][2][3][Vasya]####[9][10] and viewers 5, 6, 7, 8 stumble over feets. You should consider only those viewers who stumble Vasya's feet. Write order for this test. ###[Vasya]###### ###[Vasya]#####[1] ###[Vasya]####[2][1] ###[Vasya]###[3!][2][1] ###[Vasya]##[4!][3!][2][1] ###[Vasya]#[5!][4!][3!][2][1] ###[Vasya][6!][5!][4!][3!][2][1] Edited by author 14.12.2010 09:37 Edited by author 30.08.2011 05:38 i had that problem and solved it. 2 nd test is n=2 and answer is 0; //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("avx") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds; using namespace std;
#define re return #define pb push_back #define eb emplace_back #define all(x) (x).begin(), (x).end() #define fi first #define se second #define sqrt(x) sqrt(abs(x)) #define mp make_pair #define pi (3.14159265358979323846264338327950288419716939937510) #define fo(i, n) for(int i = 0; i < n; ++i) #define ro(i, n) for(int i = n - 1; i >= 0; --i) #define unique(v) v.resize(unique(all(v)) - v.begin())
template <class T> T abs (T x) { re x > 0 ? x : -x; } template <class T> T sqr (T x) { re x * x; } template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; } template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }
typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<string> vs; typedef double D; typedef long double ld; typedef long long ll; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef unsigned long long ull; typedef tree <pair<int, char>, null_type, less<pair<int, char>>, rb_tree_tag, tree_order_statistics_node_update> _tree; int main() { int n, k; cin >> n >> k; cout << max(0, max(n - k - 2, k - 3)) << endl; } import java.util.Scanner; public class Sold_Out { public static void main(String[] args){ Scanner scan = new Scanner(System.in);
int n = scan.nextInt(); int k = scan.nextInt();
if(n<3){ System.out.println(0); return; }
System.out.println(Math.max(k - 1, n - k) - 2); } } your programm works only because of weak tests. for example: 3 1 your answer is 0, but the correct one is 1. 1 _ _ 1 _ 3 1 2 3 -> there is 1 person from both sides and the distance to number 2 is equal, so in the worst case the person will hit vasya. Edited by author 13.01.2016 01:14 Edited by author 13.01.2016 01:14 #include "stdio.h" int main() { int n,i; scanf("%d %d",&n,&i); if(n==2) {printf("0"); return 0; } if(i<=n/2) printf("%d",n-i-2); else printf("%d",i-1-2); } Please help me .this code failed at test case 5 #include <stdio.h> int main() { int n,k; scanf ("%d\n%d" ,&n,&k); int l, pos; l = n % 2 ;
if ( l != 0 || n < 1 || k < 1 || k > n || n > 50 ) { printf("invalid input"); } else { if (n != 2 ) { if ( k <= n/2 ) { pos = n/2 - k ; printf("%d", pos); } else { pos = k - ((n/2) + 1 ); printf("%d", pos); } } } if ( n == 2 ) { pos = 0; printf("%d", pos); } return 0; }
# include <iostream> using namespace std; int main () { int n,k,sol; cin>>n>>k; if(int(n/2) && 1<=k<=n<=50){ if(k<=n/2) sol=n-3; if(k>n/2) sol=k-3; if(n==2) sol=0; } cout<<sol<<endl; } Edited by author 26.06.2014 22:00 AC if(k<=n/2) sol=n-2-k; Edited by author 09.07.2014 22:52 var a,b,n,k:integer; begin readln(n,k); a:=n div 2; if k>a then b:=n-k else if (k=a) or (k=a+1) then b:=0 else b:=a-k; writeln(b) end. where is my mistake? falls on 5th var i,nr,n,k,c:integer; begin read(n,k); nr:=trunc(n/2); if (k>nr) then begin for i:=nr+1 to k-1 do inc(c); end; if (k<nr) then begin for i:=k+1 to nr do inc(c); end; write(c); end. Your code is very bad and solution is wrong too. At first nr:=trunc(n/2) n is even because of this you could write nr=n div 2; 2.for i:=nr+1 to k-1 do inc(c); -----> this is very bad code.If you want something like that you should write c:=k-1-(nr+1)+1; 3.end here should be if (k > nr) Writeln(k -3)
else WriteLn(n - k - 2); where is my mistake? falls on 5th var i,nr,n,k,c:integer; begin read(n,k); nr:=trunc(n/2); if (k>nr) then begin for i:=nr+1 to k-1 do inc(c); end; if (k<nr) then begin for i:=k+1 to nr do inc(c); end; write(c); end. your mistake in DNA!! A person with mistake in DNA solved more problems than you. really???!!! and how do you know it? how name type this problem, type, where you should create 1-2 formuli and choise minimal or maximal value in one of it? Suppose * n in uneven, * the first (n-1)/2 seats and the last (n-1)/2 seat has the same number of people already sitting and * the person sitting in seat (n+1)/2 arrives. The description does not say if he will choose left or right. I got AC by assuming he will not choose the same side as Vasya. 1 ≤ k ≤ n ≤ 50; n is even No subject Edited by author 18.07.2011 13:04 Edited by author 18.07.2011 13:04 I don't know where I made mistake,it falls on 5th example!!! # include <iostream> using namespace std; int n,k,m,sol; int main () { cin>>n>>k; m=n/2; if (k==m) sol=0; if (k<m) sol=m-k; if (k>m) sol=k-m-1; cout<<sol<<endl; system("pause"); } Mine too. where is my mistake? falls on 5th var i,nr,n,k,c:integer; begin read(n,k); nr:=trunc(n/2); if (k>nr) then begin for i:=nr+1 to k-1 do inc(c); end; if (k<nr) then begin for i:=k+1 to nr do inc(c); end; write(c); end. |
|