CodeChef is a non-commercial competitive programming community
Login
Username (New User? Signup) Password (Forgot Password?)
Signup
Login or
Signup with
Connect
Note
  • Publicize your achievements on your Facebook Wall.
  • Challenge your friends or ask them for help.

Site Navigation

  • PRACTICE
    • Easy
    • Medium
    • Hard
    • Challenge
    • Peer
  • COMPETE
    • February CookOff
    • February Long Contest
    • January CookOff
  • DISCUSS
    • Wiki
    • Forums
    • Blog
    • Twitter
  • COMMUNITY
    • CodeChef Meetups
    • Campus Chapters
    • Host your Contest
    • User Groups
    • CodeChef TechTalks
    • All Educational Initiatives
    • Event Calendar
  • HELP
    • Frequently Asked Questions
    • FAQ for problem setters
    • Problem Setting
    • Ranks
    • Tutorials
  • ABOUT
    • About CodeChef
    • Team CodeChef
    • Press Room
    • CodeChef Financials
    • CodeChef Sponsorships
    • CEO's Corner
    • Contact Us
    • About Directi
Home  » October 2009 (Contest IX) » Kayaks » All Submissions » liubiaoyong [107762]
0
Your rating: None
using System;
using System.Collections.Generic;

namespace CodeChef_200910_H2
{

///


/// split persons ; group by weight & strength
///

class PersonGroup : IComparable
{
public int weight;
public int strength;
public int person_num;
// when fill the min speed, some stength left.
public decimal left_strength;

public int CompareTo(PersonGroup other)
{
if (left_strength > other.left_strength) return 1;
if (left_strength < other.left_strength) return -1;
return 0;
}
}

class CaseItem
{
int caseIndex;
int person_number;
int total_weight = 0;
int total_strengh = 0;
decimal aver_speed = 0;

// for add person numbers quickly
PersonGroup[,] groupTable = new PersonGroup[51, 51];
// for sort by left_strength
List personList = new List(51*51);

private void buildIndex()
{
for (int weight = 0; weight <= 50; weight++)
{
for (int strength = 0; strength <= 50; strength++)
{
PersonGroup p = new PersonGroup();
groupTable[weight, strength] = p;
p.weight = weight + 60;
p.strength = strength + 50;
personList.Add(p);
}
}
}

public CaseItem(int index)
{
this.buildIndex();

caseIndex = index;
person_number = int.Parse(System.Console.ReadLine());

for (int i = 0; i < person_number; i++)
{
string s = Console.ReadLine();
string[] a = s.Split(' ');
int weight = int.Parse(a[0]) + 10;
int strength = int.Parse(a[1]);

groupTable[weight - 60, strength - 50].person_num++;

total_weight += weight;
total_strengh += strength;
}
aver_speed = decimal.Round((0.0M + total_strengh) / total_weight, 8);
}

private decimal test_min_speed(decimal v)
{
foreach (PersonGroup pg in personList)
{
pg.left_strength = pg.strength - v * pg.weight;
}

QuickSort(personList, 0, personList.Count - 1);

int start = 0;
int end = personList.Count - 1;
decimal min_v = int.MaxValue;

while (personList[start].person_num == 0) start++;
while (personList[end].person_num == 0) end--;

int min_start_index = start, min_end_index = end;

int start_left = personList[start].person_num;
int end_left = personList[end].person_num;
PersonGroup pstart = personList[start];
PersonGroup pend = personList[end];

while (start <= end)
{
if (pstart.left_strength + pend.left_strength < min_v)
{
min_v = pstart.left_strength + pend.left_strength;
min_start_index = start;
min_end_index = end;
}

if (start_left > end_left)
{
start_left -= end_left;
end--;
pend = personList[end];
end_left = pend.person_num;
}
else if (start_left == end_left)
{
start++;
end--;
pstart = personList[start];
pend = personList[end];
start_left = pstart.person_num;
end_left = pend.person_num;
}
else
{
end_left -= start_left;
start++;
pstart = personList[start];
start_left = pstart.person_num;
}
}

min_v = (0.0M + personList[min_start_index].strength + personList[min_end_index].strength) /
(personList[min_start_index].weight + personList[min_end_index].weight);

return decimal.Round(min_v, 8);
}

public void Execute()
{
decimal min_speed = aver_speed;
decimal test_speed;
do
{
test_speed = min_speed;
min_speed = test_min_speed(test_speed);

} while (min_speed != test_speed);

System.Console.WriteLine(decimal.Round(min_speed, 6).ToString());
}

public void QuickSort(List a, int low, int high)
where T : IComparable
{
if (high - low <= 0)
{
return;
}
else if (high - low == 1)
{
if (a[high].CompareTo(a[low]) < 0)
{
T t = a[high];
a[high] = a[low];
a[low] = t;
}
return;
}

int mid = (low + high) >> 1;
T pivot = a[mid];

T t2 = a[mid];
a[mid] = a[low];
a[low] = t2;

int up = low + 1;
int down = high;

do
{
while (up <= down && a[up].CompareTo(pivot) <= 0) up++;
while (up <= down && a[down].CompareTo(pivot) > 0) down--;
if (up < down)
{
T t = a[up];
a[up] = a[down];
a[down] = t;
}

} while (up < down);

a[low] = a[down];
a[down] = pivot;

if (low < down - 1)
{
QuickSort(a, low, down - 1);
}
if (down + 1 < high)
{
QuickSort(a, down + 1, high);
}
}
}

class Round
{
int case_num;
CaseItem[] items;
public Round()
{
case_num = 1;
items = new CaseItem[case_num];

for (int i = 0; i < case_num; i++)
{
items[i] = new CaseItem(i + 1);
}
}

public void Execute()
{
foreach (CaseItem item in items)
{
item.Execute();
}
}
}

class Program
{
static void Main(string[] args)
{
//BuildDebug();
(new Round()).Execute();
// Debug();
}

static void BuildDebug()
{
using (System.IO.StreamWriter writer = new System.IO.StreamWriter("a.in"))
{
int n = 100000;

Random r = new Random(1000000);
writer.WriteLine(n);
for (int i = 0; i < n; i++)
{
int w = r.Next(n) % 51 + 50;
int s = r.Next(n) % 51 + 50;
writer.WriteLine(w.ToString() + " " + s.ToString());
}
}
}

static void Debug()
{
System.IO.TextReader stdin = System.Console.In;
System.IO.TextWriter stdout = System.Console.Out;

try
{
using (System.IO.StreamReader reader = new System.IO.StreamReader("a.in"))
{
using (System.IO.StreamWriter writer = new System.IO.StreamWriter("out.txt"))
{

long datetime1 = DateTime.Now.Ticks;

System.Console.SetIn(reader);
System.Console.SetOut(writer);
(new Round()).Execute();

long datetime2 = DateTime.Now.Ticks;

DateTime datetime3 = DateTime.Now;

long seconds = (datetime2 - datetime1) / (datetime3.AddSeconds(1).Ticks - datetime3.Ticks);

System.Console.WriteLine(" second is : " + seconds.ToString());
System.Console.WriteLine(" ticks is : " + (datetime2 - datetime1).ToString());
System.Console.WriteLine(" ticks per seconds : " + (datetime3.AddSeconds(1).Ticks - datetime3.Ticks).ToString());
}
}
}
finally
{
System.Console.SetIn(stdin);
System.Console.SetOut(stdout);
}
}
}
}


Comments

  • Login or Register to post a comment.

CodeChef is a non-commercial competitive programming community
  • About CodeChef
  • About Directi
  • CEO's Corner
  • C-Programming
  • Programming Languages
  • Contact Us
© 2009 Directi Group. All Rights Reserved. CodeChef uses SPOJ © by Sphere Research Labs
In order to report copyright violations of any kind, send in an email to copyright@codechef.com
CodeChef a product of Directi
The time now is:
CodeChef - A Platform for Aspiring Programmers

CodeChef was created as a platform to help programmers make it big in the world of computer programming. At CodeChef we work hard to revive the geek in you by hosting programming contests on a monthly basis. We also aim to have training sessions and events related to online programming for programmers around the world. Apart from providing a platform for programming competitions, CodeChef also has various tutorials and forum discussions to help those who are new to the world of computer programming.

Practice Section - A Place to hone your 'Computer Programming Skills'

Try your hand at one of our many practice problems and submit your solution in a language of your choice. Our judge accepts solutions in over 35+ programming languages. Online programming was never this much fun! Receive points, and move up through the CodeChef ranks. Use our practice section to better prepare yourself for the multiple programming competitions that take place through-out the month on CodeChef.

Compete - Monthly Programming Contests and Cook-offs

Here is where you can show off your computer programming skills. Take part in our 10 day long monthly programming contests and the shorter format Cook-off programming contests. Put yourself up for recognition and win great prizes. Prizes worth up to Rs.20,000 and $700 are up for grabs every month along with lots more CodeChef goodies.

Discuss

Are you new to computer programming? Do you need help with algorithms? Then be part of CodeChefs Forums and interact with all our programmers love helping out other programmers and share their ideas.

CodeChef Community

As part of our Educational initiative, we give institutes the opportunity to associate with CodeChef in the form of Campus Chapters. Hosting online programming competitions is not the only feature on CodeChef. Be a part of the CodeChef community through CodeChef meetups and techtalks. You can also host a programming contest for your institute on CodeChef and be a guest author on our blog.

Domain Name Registration, Web hosting, and Website Design provided by BigRock.com